重み付き乱数を生成する方法: 拒否サンプリングと反復重み加算?

重み付き乱数を生成する

はじめに

さまざまなアプリケーションでは、多くの場合、一連のオプションから乱数を選択します。各オプションには、選択される特定の確率が割り当てられます。この概念は、重み付き乱数の生成として知られています。

拒否サンプリング手法

重み付き乱数を生成する 1 つの方法は、拒否サンプリングによるものです。このアプローチには、各オプションが割り当てられた重みと同じ回数表示されるルックアップ テーブルの作成が含まれます。たとえば、オプション A の確率が 80% の場合、それはルックアップ テーブルに 80 回表示されます。乱数を生成するには、テーブル内のランダムな位置が選択され、対応するオプションが返されます。

拒否サンプリングの長所と短所

拒否サンプリングは定数を提供します-ルックアップ テーブルの構築後に乱数を選択する時間のパフォーマンス。ただし、テーブルを構築するには線形アルゴリズムのパフォーマンスが必要であり、大規模なオプションのセットや非常に正確な重みを持つオプションのセットでは問題が発生する可能性があります。

反復重み加算アプローチ

別のアプローチは、反復的な重み合計です。ここでは、[0,1) の範囲で乱数が生成され、重みの累積和と比較されます。乱数を超える重みに関連付けられたオプションが重み付き乱数として選択されます。

反復重み加算の利点と欠点

棄却サンプリングと比較して、反復重み加算は重み付け合計には前払いコストがありませんが、セット内のオプションの数に関連して線形平均アルゴリズム パフォーマンスが得られます。また、重みの合計が 1 になることも前提としています。

実装に関する考慮事項

これらのアプローチを実装するときは、重みの仕様を取る高階関数を作成することをお勧めします。重み付けされた乱数を生成する関数を返します。これにより、再利用が可能になり、ルックアップ テーブルを構築したり、重みを複数回累積したりするオーバーヘッドが回避されます。

以上が重み付き乱数を生成する方法: 拒否サンプリングと反復重み加算?の詳細内容です。詳細については、PHP 中国語 Web サイトの他の関連記事を参照してください。