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

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±595%

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.

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

Odpowiedzi:

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, iN N 1 N 2 A = N 1 ( 1 - N 1KNN1N2 Q =N1A=N1(1N1K)+2N2,Q^=N1K.

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

n^Lower=11Q^+1.96AK

n^Upper=11Q^1.96AK

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 . N N 1 N 2KNN1N2
Basj
Nie wiem, jak to zrobić tylko z iN .KN.
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: n m X n P ( X n = k ) = ( mknmXnP(Xn=k)=(mk)i=0k(1)ki(ki)(im)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:mkn

L(m|k,n)=mnm!(mk)!P(k|m,n)=mnm!(mk)!S(n,k)Stirling number of the 2nd kind=mnm!(mk)!1k!i=0k(1)i(ki)(ki)n=(mk)i=0k(1)i(ki)(kim)n

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

m1(n2)nk

m2(n2)+(n2)24(nk)(n3)2(nk)

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.mnm!(mk)!

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(11m)n)
V[K]=m((m1)(12m)n+(11m)nm(11m)2n)

Powiedz dla danej próbki i zaobserwowano unikalne pliki cookie 95% granic wygląda następująco:n=200kE[K]±1.96V[K]

granice przedziału ufności

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).mn

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