Dans une variante du problème du collecteur de coupons , vous ne connaissez pas le nombre de coupons et devez le déterminer en fonction des données. J'appellerai cela le problème du cookie de fortune:
Étant donné un nombre inconnu de messages distincts sur les cookies de fortune , estimez en échantillonnant les cookies un par un et en comptant le nombre d'apparitions de chaque fortune. Déterminez également le nombre d'échantillons nécessaires pour obtenir un intervalle de confiance souhaité sur cette estimation.
Fondamentalement, j'ai besoin d'un algorithme qui échantillonne juste assez de données pour atteindre un intervalle de confiance donné, disons avec une confiance de . Pour simplifier, nous pouvons supposer que toutes les fortunes apparaissent avec une probabilité / fréquence égale, mais ce n'est pas vrai pour un problème plus général, et une solution à cela est également la bienvenue.
Cela semble similaire au problème des chars allemands , mais dans ce cas, les cookies de fortune ne sont pas étiquetés séquentiellement et n'ont donc pas de commande.
Réponses:
Dans le cas d'une probabilité / fréquence égale, cette approche peut vous convenir.
Soit la taille totale de l'échantillon, N le nombre d'éléments différents observés, N 1 le nombre d'éléments vus exactement une fois, N 2 le nombre d'éléments vus exactement deux fois, A = N 1 ( 1 - N 1K N N1 N2 et Q =N1A = N1( 1 - N1K) + 2 N2, Q^= N1K.
Ensuite, un intervalle de confiance d'environ 95% sur la taille totale de la population est donné parn
Lors de la mise en œuvre, vous devrez peut-être les ajuster en fonction de vos données.
La méthode est due à Good et Turing. Une référence avec l'intervalle de confiance est Esty, Warren W. (1983), "Une loi limite normale pour un estimateur non paramétrique de la couverture d'un échantillon aléatoire" , Ann. Statist. , Volume 11, numéro 3, 905-912.
Pour le problème plus général, Bunge a produit un logiciel libre qui produit plusieurs estimations. Cherchez avec son nom et le mot CatchAll .
la source
Je ne sais pas si cela peut aider mais c'est le problème de prendre balles différentes lors de n essais dans une urne avec m balles étiquetées différemment avec remplacement. D'après cette page si X n si la variable aléatoire comptant le nombre de boules différentes la fonction de probabilité est donnée par: P ( X n = k ) = ( mk n m Xn P(Xn=k)=(mk)∑ki=0(−1)k−i(ki)(im)n
Ensuite, vous pouvez utiliser un estimateur du maximum de vraisemblance.
Une autre formule avec preuve est donnée ici pour résoudre le problème d'occupation .
la source
Fonction de vraisemblance et probabilité
En réponse à une question sur le problème d'anniversaire inversé, une solution pour une fonction de vraisemblance a été donnée par Cody Maughan.
La fonction de vraisemblance pour le nombre de types de cookies de fortunem lorsque nous tirons k différents cookies de fortune dans n tirages (où chaque type de cookie de fortune a une probabilité égale d'apparaître dans un tirage) peut être exprimée comme suit:
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.la source