Wahrscheinlichkeit, ein bestimmtes Gerät auszuwählen, durch Abtastung ohne Ersatz von einer kategorialen Verteilung

Question

Angenommen, ich habe eine kategoriale Verteilung auf Elemente $ 1, \ DOTS, N $ , das Wahrscheinlichkeit $ p_i $ < / span> zu item $ i $ . Ich probe wiederholt von dieser Verteilung, bis ich $ K $ einzigartige Objekte erhalten habe. Ich möchte die Wahrscheinlichkeit berechnen, dass der Satz von erhaltenen Objekten genau ist $ \ {1, \ dots, k \} $ .

Gibt es einen effizienten Weg, um diese Wahrscheinlichkeit zu berechnen, gegeben $ p_1, \ dots, p_n $ und $ K $

Ich kann sehen, dass die Wahrscheinlichkeit das Formular hat

$$ p=sum_ \ sigma \ prod_ {i= 1} ^ k {p _ {\ sigma (i)} \ {\ Sigma (i)} \ over (1-p _ {\ Sigma (1 )}) \ CDOTs (1-P _ {\ Sigma (1)} - \ dots-p _ {\ Sigma (I-1)})}, $$ Wenn die Summe über alle Permutationen ist $ \ Sigma \ in S_K $ auf $ \ {1, \ dots, k \} $ . (Hier $ \ Sigma $ stellt die Reihenfolge dar, in der die Elemente $ 1, \ dots, k $ ausgewählt sind .) Diese Formel für die Wahrscheinlichkeit beinhaltet jedoch $ K! $ Begriffe, sodass die Wahrscheinlichkeit auf diese Weise Daten berechnen würde, würde in $ K $ . Gibt es einen effizienteren Weg, um es zu berechnen?

Natürlich können wir ohne Verlust der Allgemeinheit $ n= k + 1 $ annehmen.

Answer 1

für jeden $ \ Sigma \ Subseteq [k + 1] $ , können Sie die Wahrscheinlichkeitswahrscheinlichkeitsgängerklasse="Math-Container"> $ Q (\SIGMA) $ Dass der erste $ | \ Sigma | $ Elemente zu erscheinen, sind $ \ Sigma $ Verwenden Sie das folgende Wiederholung: $ q (\ emesyset)= 1 $ und wenn $ \ Sigma \ neq \ emesyet $, $$ q (\ SIGMA)=Sum _ {\ Sigma \ in \ Sigma} q (\ Sigma- \ Sigma) \ frac {p_ \ sigma} {p_ \ sigma + \ sum _ {\ tau \ notin \ sigma} p_ \ tau}. $$ Sie interessieren sich für $ q ([k]) $ .Die Gesamtberechnungszeit ist $ O (K2 ^ K) $ (ignorierende Arithmetik), wenn Sie die Summe in dem Nenner in Tandem berechnen.Vielleicht könnte dies für $ O (2 ^ k) $ verbessert werden.