Probabilidade de selecionar um determinado conjunto, por amostragem sem substituição de uma distribuição categórica

Question

Suponha que eu tenha uma distribuição categórica em itens $ 1, \ Dots, n $ , que atribui probabilidade $ p_i $ < / span> para item $ i $ . Eu agora rei repetidamente amostra dessa distribuição, até ter obtido $ k $ objetos exclusivos. Eu gostaria de calcular a probabilidade de que o conjunto de objetos obtidos seja exatamente $ \ {1, \ DOTS, K \} $ .

Existe uma maneira eficiente de calcular essa probabilidade, dada $ p_1, \ pontos, p_n $ e $ k $ ?

Eu posso ver que a probabilidade tem o formulário

$$ 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)})}, $$ Onde a soma é sobre todas as permutações $ \ sigma \ em s_k $ na $ \ {1, \ pontos, k \} $ . (Aqui $ \ sigma $ representa a ordem em que os itens $ 1, \ pontos, k $ são selecionados .) No entanto, esta fórmula para a probabilidade envolve $ k! $ termos, por isso, compensando a probabilidade dessa maneira levaria tempo exponencial no recipiente de matemática $ k $ . Existe uma maneira mais eficiente de computar?

Claro, sem perda de generalidade podemos assumir $ n= k + 1 $ .

Answer 1

Para cada $ \ sigma \ subseteq [k + 1] $ , você pode calcular a probabilidade $ Q (\Sigma) $ que a primeira $ | \ sigma | $ elementos para aparecer são $ \ sigma $ Usando a seguinte recorrência: $ Q (\ FORTSET)= 1 $ e quando $ \ sigma \ neq \ forkset $, $$ Q (\ sigma)=sum _ {\ sigma \ in \ sigma} q (\ sigma- \ sigma) \ frac {p_ \ sigma} {p_ \ sigma + \ sum _ {\ tau \ notin \ sigma} p_ tau}. $$ Você está interessado em $ Q ([K]) $ .O tempo total de computação é $ o (k2 ^ k) $ (ignorando aritmética), se você calcular a soma no denominador em conjunto.Talvez isso possa ser melhorado para $ o (2 ^ k) $ .