1

私は基本的な個別の数学/確率の質問に出くわしました、そして私は私の解決策を改善するためのいくつかのアイデアを得たいと思いました。

コレクション（アルファベット、自然数など）が与えられていると仮定します。Xこのコレクションから特定の確率で特定の値を確実に引き出すにはどうすればよいですPか？

私のナイーブな解決策を例を挙げて説明します。

Collection = {A, B}
X = A, P = 1/4

配列を作成しv = [A, B, B, B]、関数を使用しrandて配列のインデックスを均一にサンプリングします。{0, 1, 2, 3}

このアプローチは機能しますが、効率的ではありません。が小さいほどP、のメモリストレージは大きくなりますv。したがって、stackoverflowコミュニティがこれを改善するためにどのようなアイデアを持っているのか疑問に思いました。

ありがとう！

4

2 に答える 2

5

区間 [0,1] を和集合が [0,1] である互いに素な区間に分割します。各イベントを選択する確率に対応する各パーティションのサイズを作成します。次に、[0,1] からランダムにサンプリングし、結果がどのパーティションにあるかを評価し、その間隔に対応する選択を検索します。あなたの例では、これは次の 2 つの間隔 [0,1/4) と [1/4,1] になります - [0,1] からランダムな一様値を生成します。サンプルが最初の間隔にあるX = A場合は選択し、他の間隔にある場合はX = B.

于 2012-10-13T10:55:29.563 に答える
1

あなたが提案した解決策は確かに素晴らしいものではありません。それを解決する最も一般的で効率的な方法は、mathematician1975 が述べているとおりです (これは逆 CDF 法として知られています)。多項サンプリングである特定の問題については、二項分布からの一連の描画を使用して、コレクションからサンプリングすることもできます。サンプリング方法に慣れていない場合、これは多くの場合、より直感的です。

コレクションの最初のアイテムの確率が p_1 の場合、間隔 [0-1] で均一にサンプリングします。サンプルが p_1 未満の場合は、項目 1 を返します。そうでない場合は、残りの結果を 1-p_1 で再正規化し、次の可能な結果でプロセスを繰り返します。サンプリングが失敗するたびに、残りの結果を拒否された結果の合計確率で再正規化し、残りの結果の合計が 1 になるようにします。最後の結果に到達した場合は、確率 1 でそれを返します。プロセスの結果は、ランダムなサンプルが分散されます。元のベクトルに従って。

この方法は、多項式の個々のコンポーネントが二項分布しているという事実を使用しており、多項式の任意のサブベクトルも、上で説明した再正規化によって与えられたパラメーターを持つ多項式です。

于 2012-10-16T10:30:57.953 に答える