カテゴリカルディストリビューションから交換せずにサンプリングすることで、特定のセットを選択する確率

Question

$ 1、\ dots、n $ のカテゴリカルディストリビューションがあるとします。 $ p_i $ < / span>項目 $ i $ 。 $ k $ の固有オブジェクトを取得するまで、この分布から繰り返しサンプルします。取得したオブジェクトのセットが正確に $ \ {1、\ dots、k \} $ の設定確率を計算したいです。

この確率を計算する効率的な方法は、 $ p_1、\ dots、p_n $ 、 $ 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 \}の$ $ のすべての順列を超えています $ \ sigma \ $ 。 （ここでは $ \ sigma $ $ 1、\ dots、k $ が選択されている順序を表します。 。）しかしながら、確率のこの式には、 $ k！$ という条件が含まれますので、このようにして確率を計算すると、 $ k $ 。それを計算するためのより効率的な方法はありますか？

もちろん、一般性を損なうことなく、 $ n= k + 1 $ を想定することができます。

Answer 1

各 $ \ sigma \ subeteq [k + 1] $ の場合、確率 $ q（\SIGMA）$ $ | \ sigma | $ 要素が表示されます $ \ sigma $ 次の再発を使用して： $ q（\ appentset）= 1 $ 、および $ \ sigma \ neq \ hemptyset $ $$ Q（\ SIGMA）=SUM _ {\ sigma \ in \ sigma} Q（\ Sigma- \ Sigma）\ frac {P_ \ Sigma} {p_ \ sigma + \ sum _ {\ tau \ notin \ sigma} p_ \ tau}。 $$ $ q（[k]）$ に興味があります。合計計算時間は、 $ O（k2 ^ k）$ x （算術演算を無視してください）、タンデンの合計を計算してください。おそらくこれは $ o（2 ^ k）$ に改善することができます。