c++ - どの確率関数を使用するか

Question

ベクター内の「e」edges_in_sorted_order から「n」個のエッジを確率的に選択したいと考えています。しかし、私は選択に確率を使いたいです。また、最初から大きなエッジを選択したくありません。

つまり、最初は小さなエッジに重みを付け、エッジを取得するにつれて、残りの大きなエッジにも重みを付けていきます。

n と e のどの確率関数を選択すればよいですか?

while( edgesTaken < n ) {
     for each edge i and edgesTaken < n
         probability = pdf( edgesTaken, i)
         if ( prob > THRESHOLD )
              take the edge
 }

Answer 1

最初のエッジが 1 である確率は、choose(n-1,e-1)/choose(n,e) です。

より一般的には、最初のエッジが k である確率は [choose(nk,e-1)/choose(n,e)] * 1/k

また、1-k にエッジが 1 つだけ存在する確率が必要な場合もあります: [choose(nk,e-1)/choose(n,e)]

ここから、あなたは物事をまとめることができると思います!

PS 説明すると、3 つの関数は、条件を満たすエッジを選択する方法の数の比率を、n から e エッジを選択する方法の数である choose(n,e) に与えます。