Oszacowanie nw problemie kolektora kuponów

14

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. $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.

estimation coupon-collector-problem

— goweon
źródło

1

Czy wiemy, że wiadomości są równie częste?

— Glen_b

pytanie zredagowane: Tak

— goweon

2

Czy możesz zapisać funkcję prawdopodobieństwa?

— Zen

2

Ludzie prowadzący badania nad dziką przyrodą chwytają, znakują i uwalniają zwierzęta. Później wywnioskowują wielkość populacji na podstawie częstotliwości, z jaką chwytają już oznakowane zwierzęta. Wygląda na to, że twój problem jest matematycznie ich.

— Emil Friedman

6

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, i $K$ $N$ $N_1$ $N_2$ $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}}_{L o w e r} = \frac{1}{1 - \hat{Q} + \frac{1.96 \sqrt{A}}{K}}

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

{\hat{n}}_{U p p e r} = \frac{1}{1 - \hat{Q} - \frac{1.96 \sqrt{A}}{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 .

— soakley
źródło

1

Pozwoliłem sobie dodać odniesienie do Esty. Proszę dokładnie sprawdzić, czy to miałeś na myśli

— Glen_b

Czy jest możliwe @ soakley, aby uzyskać granice (prawdopodobnie mniej precyzyjne granice), jeśli znasz tylko (wielkość próby) i (liczba unikalnych przedmiotów)? tzn. nie mamy informacji o i .

K

$K$

N

$N$

N_{1}

$N_1$

N_{2}

$N_2$

— Basj

Nie wiem, jak to zrobić tylko z i

K

$K$

N .

$N.$

— soakley,

2

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: $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 .

— sylvain
źródło

2

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{matrix} L (m | k, n) = m^{- n} \frac{m!}{(m - k)!} \propto P (k | m, n) & = & m^{- n} \frac{m!}{(m - k)!} \cdot \underset{\begin{array}{l} Stirling number \\ of the 2nd kind \end{array}}{\underset{⏟}{S (n, k)}} \\ = & m^{- n} \frac{m!}{(m - k)!} \cdot \frac{1}{k!} \sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) (k - i)^{n} \\ = & (\binom{m}{k}) \sum_{i = 0}^{k} (- 1)^{i} (\binom{k}{i}) {(\frac{k - i}{m})}^{n} \end{matrix}

$\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{(\binom{n}{2})}{n - k}

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

m_{2} \approx \frac{(\binom{n}{2}) + \sqrt{{(\binom{n}{2})}^{2} - 4 (n - k) (\binom{n}{3})}}{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ę:

E [K] = m (1 - {(1 - \frac{1}{m})}^{n})

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

V [K] = m ((m - 1) {(1 - \frac{2}{m})}^{n} + {(1 - \frac{1}{m})}^{n} - m {(1 - \frac{1}{m})}^{2 n})

$\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))

— Sextus Empiricus
źródło

W przypadku nierównych prawdopodobieństw. Możesz przybliżyć liczbę plików cookie określonego typu jako niezależne zmienne rozproszone dwumianowe / Poissona i opisać, czy są one wypełnione, czy nie, jako zmienne Bernouilli. Następnie zsumuj wariancję i średnie dla tych zmiennych. Myślę, że w ten sposób Ben również wyliczył / oszacował wartość oczekiwaną i wariancję. ----- Problem polega na tym, jak opisujesz te różne prawdopodobieństwa. Nie możesz tego zrobić wyraźnie, ponieważ nie znasz liczby plików cookie.

— Sextus Empiricus