Oszacowanie nw problemie kolektora kuponów

W odmianie problemu z kolektorem kuponów nie znasz liczby kuponów i musisz to ustalić na podstawie danych. Będę nazywać to problemem związanym z ciasteczkami fortuny:

Biorąc pod uwagę nieznaną liczbę odrębnych wiadomości cookie fortuny , oszacuj , próbkując pliki cookie pojedynczo i licząc, ile razy pojawia się każda fortuna. Określ także liczbę próbek niezbędnych do uzyskania pożądanego przedziału ufności dla tego oszacowania.$n$$n$

Zasadniczo potrzebuję algorytmu, który pobiera próbki wystarczającej ilości danych, aby osiągnąć dany przedział ufności, powiedzmy z pewnością. Dla uproszczenia możemy założyć, że wszystkie fortuny pojawiają się z jednakowym prawdopodobieństwem / częstotliwością, ale nie dotyczy to bardziej ogólnego problemu, a rozwiązanie tego problemu jest również mile widziane.95 $n \pm 5$$95\%$

Wydaje się to podobne do problemu niemieckiego czołgu , ale w tym przypadku ciasteczka z wróżbą nie są kolejno oznaczane, a zatem nie mają kolejności.

W przypadku równego prawdopodobieństwa / częstotliwości to podejście może Ci pomóc.

Niech będzie całkowitą wielkością próbki, będzie liczbą zaobserwowanych różnych elementów, będzie liczbą elementów widocznych dokładnie jeden raz, będzie liczbą elementów widocznych dokładnie dwa razy, iN N 1 N 2 A = N 1 ( 1 - N $K$$N$$N_1$$N_2$ Q =N$A=N_1(1− {N_1 \over K} )+2N_2,$$\hat Q = {N_1 \over K}.$

Następnie w przybliżeniu 95% przedział ufności od całkowitej wielkości populacji jest przez$n$

$$\hat n_{Lower}={1 \over {1-\hat Q+{1.96 \sqrt{A} \over K} }}$$

$$\hat n_{Upper}={1 \over {1-\hat Q-{1.96 \sqrt{A} \over K} }}$$

Podczas wdrażania może być konieczne dostosowanie ich w zależności od danych.

Metoda wynika z dobrych i Turinga. Odniesieniem do przedziału ufności jest Esty, Warren W. (1983), „Normalne prawo graniczne dla nieparametrycznego estymatora pokrycia przypadkowej próbki” , Ann. Statystyk. , Tom 11, numer 3, 905–912.

W przypadku bardziej ogólnego problemu firma Bunge stworzyła bezpłatne oprogramowanie, które generuje kilka szacunków. Szukaj według jego imienia i słowa CatchAll .

Nie wiem, czy to może pomóc, ale jest to problem z przyjmowaniem różnych piłek podczas prób w urnie z piłkami oznaczonymi inaczej z wymianą. Według tej strony (po francusku) jeśli jeśli zmienna losowa zliczająca liczbę różnych kulek, funkcja prawdopodobieństwa jest dana przez: n m X n P ( X n = k ) = ($k$$n$$m$$X_n$$P(X_n = k) = {m \choose k} \sum_{i=0}^k {(-1)^{k-i}{k \choose i}}{(\frac{i}{m})^n}$

Następnie możesz użyć estymatora maksymalnego prawdopodobieństwa.

Podano inną formułę z dowodem rozwiązania problemu obłożenia .

Funkcja prawdopodobieństwa i prawdopodobieństwo

W odpowiedzi na pytanie o problem z urodzinami wstecznymi Cody Maughan podał rozwiązanie funkcji wiarygodności.

Funkcja prawdopodobieństwa liczby typów gotowania fortuny gdy narysujemy różnych ciasteczek fortuny w losowaniach (gdzie każdy typ ciasteczka fortuny ma równe prawdopodobieństwo pojawienia się w losowaniu) może być wyrażony jako:$m$$k$$n$

$$\begin{array}{} \mathcal{L}(m \, \vert \, k,n ) = m^{-n} \frac{m!}{(m-k)!} \propto P(k \, \vert \, m,n) &=& m^{-n}\frac{m!}{(m-k)!} \cdot \underbrace{S(n,k)}_{\begin{subarray}{l}\text{Stirling number }\\ \text{of the 2nd kind}\end{subarray}}\\ &=& m^{-n}\frac{m!}{(m-k)!} \cdot \frac{1}{k!} \sum_{i=0}^k {(-1)^{i}{k \choose i}}{(k-i)^n} \\ &=& {{m}\choose{k}} \sum_{i=0}^k {(-1)^{i}{k \choose i}}{\left(\frac{k-i}{m}\right)^n} \end{array}$$

W celu ustalenia prawdopodobieństwa po prawej stronie zobacz problem z zajętością. Zostało to wcześniej opisane na tej stronie przez Bena. Wyrażenie jest podobne do tego w odpowiedzi Sylvaina.

Oszacowanie maksymalnego prawdopodobieństwa

Możemy obliczyć przybliżenia pierwszego i drugiego rzędu maksimum funkcji wiarygodności przy

$$m_1 \approx \frac{ {{n}\choose{2}}}{n-k}$$

$$m_2 \approx \frac{ {{n}\choose{2}} + \sqrt{{{n}\choose{2}}^2 - 4(n-k) {{n}\choose{3}}}}{2(n-k)}$$

Przedział prawdopodobieństwa

(Uwaga, to nie jest to samo co przedział ufności patrz: Podstawowa logika konstruowania przedziału ufności )

To pozostaje dla mnie otwarty problem. Nie jestem jeszcze pewien, jak poradzić sobie z wyrażeniem (Oczywiście można obliczyć wszystkie wartości i na tej podstawie wybrać granice, ale byłoby więcej miło mieć jakąś konkretną dokładną formułę lub oszacowanie). Nie mogę się odnieść do żadnej innej dystrybucji, która bardzo pomogłaby w jego ocenie. Ale wydaje mi się, że z tego podejścia opartego na przedziałach prawdopodobieństwa możliwe byłoby miłe (proste) wyrażenie.$m^{-n} \frac{m!}{(m-k)!}$

Przedział ufności

Dla przedziału ufności możemy użyć normalnego przybliżenia. W odpowiedzi Bena podano następującą średnią i wariancję:

$$\mathbb{E}[K] = m \left(1-\left(1 - \frac{1}{m}\right)^n\right)$$ $$\mathbb{V}[K] = m \left(\left(m-1\right)\left(1-\frac{2}{m}\right)^n + \left(1 - \frac{1}{m}\right)^n - m \left(1 - \frac{1}{m}\right)^{2n} \right)$$

Powiedz dla danej próbki i zaobserwowano unikalne pliki cookie 95% granic wygląda następująco:$n=200$$k$$\mathbb{E}[K] \pm 1.96 \sqrt{\mathbb{V}[K]}$

Na powyższym obrazku narysowano krzywe dla interwału, wyrażając linie jako funkcję wielkości populacji i wielkości próbki (więc oś x jest zmienną zależną podczas rysowania tych krzywych).$m$$n$

Trudność polega na odwróceniu tego i uzyskaniu wartości przedziału dla danej obserwowanej wartości . Można to zrobić obliczeniowo, ale być może istnieje bardziej bezpośrednia funkcja.$k$

Na obrazku dodałem również przedziały ufności Cloppera Pearsona w oparciu o bezpośrednie obliczenie skumulowanego rozkładu na podstawie wszystkich prawdopodobieństw (Zrobiłem to w R, gdzie musiałem użyć funkcja z pakietu CryptRndTest , która jest asymptotycznym przybliżeniem logarytmu liczby Stirlinga drugiego rodzaju). Widać, że granice pokrywają się dość dobrze, więc normalne przybliżenie działa w tym przypadku dobrze.$P(k \, \vert \, m,n)$Strlng2

# function to compute Probability
library("CryptRndTest")
P5 <- function(m,n,k) {
  exp(-n*log(m)+lfactorial(m)-lfactorial(m-k)+Strlng2(n,k))
}
P5 <- Vectorize(P5)

# function for expected value 
m4 <- function(m,n) {
  m*(1-(1-1/m)^n)
}

# function for variance
v4 <- function(m,n) {
  m*((m-1)*(1-2/m)^n+(1-1/m)^n-m*(1-1/m)^(2*n))
}


# compute 95% boundaries based on Pearson Clopper intervals
# first a distribution is computed
# then the 2.5% and 97.5% boundaries of the cumulative values are located
simDist <- function(m,n,p=0.05) {
  k <- 1:min(n,m)
  dist <- P5(m,n,k)
  dist[is.na(dist)] <- 0
  dist[dist == Inf] <- 0
  c(max(which(cumsum(dist)<p/2))+1,
       min(which(cumsum(dist)>1-p/2))-1)
}


# some values for the example
n <- 200
m <- 1:5000
k <- 1:n

# compute the Pearon Clopper intervals
res <- sapply(m, FUN = function(x) {simDist(x,n)})


# plot the maximum likelihood estimate
plot(m4(m,n),m,
     log="", ylab="estimated population size m", xlab = "observed uniques k",
     xlim =c(1,200),ylim =c(1,5000),
     pch=21,col=1,bg=1,cex=0.7, type = "l", yaxt = "n")
axis(2, at = c(0,2500,5000))

# add lines for confidence intervals based on normal approximation
lines(m4(m,n)+1.96*sqrt(v4(m,n)),m, lty=2)
lines(m4(m,n)-1.96*sqrt(v4(m,n)),m, lty=2)
# add lines for conficence intervals based on Clopper Pearson
lines(res[1,],m,col=3,lty=2)
lines(res[2,],m,col=3,lty=2)

# add legend
legend(0,5100,
       c("MLE","95% interval\n(Normal Approximation)\n","95% interval\n(Clopper-Pearson)\n")
       , lty=c(1,2,2), col=c(1,1,3),cex=0.7,
       box.col = rgb(0,0,0,0))