Probabilità di selezionare un determinato set, campionando senza sostituzione da una distribuzione categoriale

Question

Supponiamo di avere una distribuzione categorica sugli articoli $ 1, \ punti, n $ , che assegna probabilità $ P_i $ < / span> per articolo $ i $ . Ora mi sento ripetutamente da questa distribuzione, finché non ho ottenuto $ K $ oggetti unici. Mi piacerebbe calcolare la probabilità che il set di oggetti ottenuti sia esattamente $ \ {1, \ dots, k \} $ .

C'è un modo efficiente per calcolare questa probabilità, data $ p_1, \ punti, p_n $ e $ k $ ?

Posso vedere che la probabilità ha il modulo

$$ p=sum_ \ sigma \ PROD_ {I= 1} ^ K {P _ {\ SIGMA (I)}} Over (1-P _ {\ Sigma (1 )}) \ cdots (1-p _ {\ sigma (1)} - \ dots-p _ {\ sigma (I-1)})}, $$ dove la somma è su tutte le permutazioni $ \ sigma \ in s_k $ su $ \ {1, \ Dots, K \} $ . (Qui $ \ sigma $ rappresenta l'ordine in cui gli elementi $ 1, \ punti, k $ sono selezionati .) Tuttavia, questa formula per la probabilità implica $ k! $ termini, quindi calcolo della probabilità in questo modo richiederebbe tempo esponenziale in $ k $ . C'è un modo più efficiente per calcolarlo?

Naturalmente, senza perdita di generalità possiamo assumere $ n= k + 1 $ .

Answer 1

Per ogni $ \ Sigma \ SOTETETQ [K + 1] $ , è possibile calcolare la probabilità $ Q (\Sigma) $ che la prima $ | \ sigma | $ elementi per apparire sono $ \ Sigma $ Utilizzo della successiva ricorrenza: $ Q (\ Dollset)= 1 $ e quando $ \ sigma \ neq \ vuoto $, $$ q (\ sigma)=sum _ {\ sigma \ in \ sigma} q (\ sigma- \ sigma) \ frac {p_ \ sigma} {p_ \ sigma + \ sum _ {\ tau \ notin \ sigma} p_ \ taau}. $$ Sei interessato a $ Q ([K]) $ .Il tempo totale di calcolo è $ o (k2 ^ k) $ (ignorando l'aritmetico), se calcoli la somma nel denominatore in tandem.Forse questo potrebbe essere migliorato a $ o (2 ^ k) $ .