Probabilité de sélectionner un ensemble particulier, par échantillonnage sans remplacement d'une distribution catégorique

Question

Supposons que j'ai une distribution catégorique sur les éléments 1 $, \ points, n $ , qui attribue une probabilité $ p_i $ < / SPAN> ARTICLE $ I $ . J'échantillons maintenant à plusieurs reprises de cette distribution, jusqu'à ce que j'ai obtenu $ k $ objets uniques. J'aimerais calculer la probabilité que l'ensemble d'objets obtenus soit exactement $ \ {1, \ dots, k \} $ .

.

Y a-t-il un moyen efficace de calculer cette probabilité, étant donné $ p_1, \ dots, p_n $ et $ k $ ?

Je peux voir que la probabilité a la forme

$$ p=sum_ \ sigma \ prod_ {i= 1} ^ k {p _ {\ sigma (i)} \ over (1-p _ \ \ sigma (1 )}) \ CDOT (1-p _ {\ sigma (1)} - \ dots-p _ {\ sigma (I-1)})}, $$ où la somme est sur toutes les permutations $ \ sigma \ in s_k $ sur $ \ {1, \ dots, k \} $ . (Ici $ \ sigma $ représente la commande dans laquelle les éléments 1 $, \ points, k $ sont sélectionnés .) Toutefois, cette formule pour la probabilité implique k! $ termes, donc calculer la probabilité de cette manière prendrait du temps exponentiel dans $ K $ . Y a-t-il un moyen plus efficace de le calculer?

Bien sûr, sans perte de généralité, nous pouvons assumer $ n= k + 1 $ .

.

Answer 1

pour chaque $ \ sigma \ sous -éréeq [k + 1] $ , vous pouvez calculer la probabilité q (\Sigma) $ que le premier $ | \ sigma | $ éléments à apparaître sont $ \ sigma $ Utilisation de la récurrence suivante: $ Q (\ ELTYSET)= 1 $ et quand $ \ SIGMA \ NEQ \ NEKTYSET $, $$ q (\ sigma)=somme _ {\ sigma \ in \ sigma} Q (\ sigma- \ sigma) \ frac {p_ \ sigma} {p_ \ sigma + \ somme _ {\ tau \ notin \ sigma} p_ \ tau}. $$ Vous êtes intéressé par $ q ([k]) $ .Le temps de calcul total est $ o (k2 ^ k) $ (ignorant l'arithmétique), si vous calculez la somme dans le dénominateur en tandem.Peut-être que cela pourrait être amélioré pour $ o (2 ^ k) $ .