In einer Variation des Problems des Gutscheinsammlers kennen Sie die Anzahl der Gutscheine nicht und müssen diese anhand von Daten ermitteln. Ich werde dies als das Fortune-Cookie-Problem bezeichnen:
Bei einer unbekannten Anzahl unterschiedlicher Glückskeksnachrichten schätzen Sie indem Sie die Cookies einzeln abtasten und zählen, wie oft jedes Glück erscheint. Bestimmen Sie auch die Anzahl der Proben, die erforderlich sind, um ein gewünschtes Konfidenzintervall für diese Schätzung zu erhalten.
Grundsätzlich benötige ich einen Algorithmus, der gerade genug Daten abtastet, um ein bestimmtes Konfidenzintervall zu erreichen, z. B. mit Konfidenz. Der Einfachheit halber können wir davon ausgehen, dass alle Schicksale mit der gleichen Wahrscheinlichkeit / Häufigkeit auftreten. Dies gilt jedoch nicht für ein allgemeineres Problem, und eine Lösung hierfür ist ebenfalls zu begrüßen.
Dies scheint dem deutschen Panzerproblem ähnlich zu sein , aber in diesem Fall werden Glückskekse nicht fortlaufend gekennzeichnet und haben daher keine Reihenfolge.
Antworten:
Für den Fall gleicher Wahrscheinlichkeit / Häufigkeit funktioniert dieser Ansatz möglicherweise für Sie.
Sei die Gesamtstichprobengröße, N die Anzahl der beobachteten Gegenstände, N 1 die Anzahl der genau einmal gesehenen Gegenstände, N 2 die Anzahl der genau zweimal gesehenen Gegenstände, A = N 1 ( 1 - N 1K N N1 N2 und Q =N1A=N1(1−N1K)+2N2, Q^=N1K.
Dann ist ein ungefähres 95% -Konfidenzintervall auf die Gesamtpopulationsgröße gegeben durchn
Bei der Implementierung müssen Sie diese möglicherweise in Abhängigkeit von Ihren Daten anpassen.
Die Methode beruht auf Good and Turing. Eine Referenz mit dem Konfidenzintervall ist Esty, Warren W. (1983), "Ein normales Grenzgesetz für einen nichtparametrischen Schätzer der Erfassung einer Zufallsstichprobe" , Ann. Statist. Band 11, Nummer 3, 905-912.
Für das allgemeinere Problem hat Bunge freie Software entwickelt, die mehrere Schätzungen erstellt. Suche mit seinem Namen und dem Wort CatchAll .
quelle
Ich weiß nicht, ob es helfen kann, aber es ist das Problem, verschiedene Bälle während n Versuchen in einer Urne mit m Bällen zu nehmen, die unterschiedlich mit Ersatz gekennzeichnet sind. Laut dieser Seite (in Französisch) ergibt sich für X n, wenn die Zufallsvariable die Anzahl der verschiedenen Bälle zählt, die Wahrscheinlichkeitsfunktion aus: P ( X n = k ) = ( mk n m Xn P(Xn=k)=(mk)∑ki=0(−1)k−i(ki)(im)n
Then you can use a maximum likelihood estimator.
Another formula with proof is given here to solve the occupancy problem.
quelle
Likelihood function and probability
In an answer to a question about the reverse birthday problem a solution for a likelihood function has been given by Cody Maughan.
The likelihood function for the number of fortune cooky typesm when we draw k different fortune cookies in n draws (where every fortune cookie type has equal probability of appearing in a draw) can be expressed as:
For a derivation of the probability on the right hand side see the the occupancy problem. This has been described before on this website by Ben. The expression is similar to the one in the answer by Sylvain.
Maximum likelihood estimate
We can compute first order and second order approximations of the maximum of the likelihood function at
Likelihood interval
(note, this is not the same as a confidence interval see: The basic logic of constructing a confidence interval)
This remains an open problem for me. I am not sure yet how to deal with the expressionm−nm!(m−k)! (of course one can compute all values and select the boundaries based on that, but it would be more nice to have some explicit exact formula or estimate). I can not seem to relate it to any other distribution which would greatly help to evaluate it. But I feel like a nice (simple) expression could be possible from this likelihood interval approach.
Confidence interval
For the confidence interval we can use a normal approximation. In Ben's answer the following mean and variance are given:
Say for a given samplen=200 and observed unique cookies k the 95% boundaries E[K]±1.96V[K]−−−−√ look like:
In the image above the curves for the interval have been drawn by expressing the lines as a function of the population sizem and sample size n (so the x-axis is the dependent variable in drawing these curves).
The difficulty is to inverse this and obtain the interval values for a given observed valuek . It can be done computationally, but possibly there might be some more direct function.
In the image I have also added Clopper Pearson confidence intervals based on a direct computation of the cumulative distribution based on all the probabilitiesP(k|m,n) (I did this in R where I needed to use the
Strlng2
function from the CryptRndTest package which is an asymptotic approximation of the logarithm of the Stirling number of the second kind). You can see that the boundaries coincide reasonably well, so the normal approximation is performing well in this case.quelle