특정 세트를 선택할 확률, 범주 분포에서 교체없이 샘플링함으로써

Question

$ 1, \ dots, n $ 항목에 대해 범주화 된 배포가 있다고 가정 해보십시오 $ p_i $ < / span> 항목 $ i $ . 이제 $ k $ 고유 한 개체를 획득 할 때 까지이 배포에서 반복적으로 샘플을 샘플링합니다. 얻은 객체 세트가 정확히 $ \ {1, \ dots, k \} $ 인 확률을 계산하고 있습니다.

및 $ k $ ?

확률이 형식이 있음을 알 수 있습니다.

$$ 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)})}, $$ 합계가 $ \ {1, \ dots, k \}에서 s_k $ \ sigma>의 모든 순열 $ \ sigma \ $ . (여기서 $ \ sigma $ 은 $ 1, \ dots, k $ 을 선택한 순서를 나타냅니다. ) 그러나 확률에 대한이 공식은 $ k! $ 용어를 포함 하므로이 방법으로 확률을 계산하면 $ k $ . 그것을 계산하는 것이 더 효율적인 방법이 있습니까?

물론 일반성 손실없이 $ n= k + 1 $ 을 가정 할 수 있습니다.

Answer 1

각 $ \ sigma \ subetetq [k + 1] $ 의 확률 $ q (\Sigma) $ $ | \ sigma> 나타나는 $ \ sigma $ 다음 재발을 사용하여 $ q (\ equipyset)= 1 $ 및 $ \ sigma \ neq \ equipyset $, $$ q (\ sigma)=sum _ {\ sigma \ in \ sigma} \ frac {p_ \ sigma} {p_ \ sigma + \ sum _ {\ tau \ notin \ sigma} p_ \ tau}...에 $$ $ q ([k]) $ 에 관심이 있습니다.총 계산 시간은 탠덤의 분모에있는 합계를 계산하는 경우 $ o (K2 ^ K) $ (산술 무시)입니다.아마도 이것은 $ o (2 ^ K) $ 을 향상시킬 수 있습니다.