重み付きランダム選択の仕組み

重み付けされたランダム選択は、オプションの確率が等しくない場合に使用します。重みは、各オプションが平均してどのくらいの頻度で勝つかを示します。

重要なポイント

確率 = 重量を総重量で割ったもの。
累積重みは、オプションを 0 から 1 までの間隔のセグメントに変換します。
安全なランダム値がポイントを選択します。一致するセグメントが優先されます。
置換なしで重み付けすると、勝者が削除され、残りの重みが再正規化されます。
多数の描画にわたって観察された頻度と予想される頻度を比較することによって公平性をテストします。

等しいランダム性と重み付けされたランダム性

通常のランダムピッカーは、すべてのオプションを同等に扱います。これは、各生徒に同じチャンスが与えられるべき教室の抽選では正しいことです。しかし、実際の決定の多くは意図的に不平等です。

ゲームでは、一般的な戦利品が頻繁に表示され、珍しい戦利品がめったに表示されないようにします。
抽選により、一部の参加者には他の参加者よりも多くのチケットが与えられます。
A/B テストでは、ユーザーの 80% が対照バリアントに送信され、20% が新しいバリアントに送信されます。
教師は、簡単な質問よりも難しい質問が頻繁に出てくることを望んでいます。

重み付けされたランダム性は依然としてランダム性です。違いは、確率分布が意図的に行われているということです。

重みはカウントではなく確率です

オプションの重み自体は確率ではありません。相対的な数値です。確率を取得するには、重みをすべての重みの合計で割ります。

オプションが次のとおりであるとします。

-A、重さ1。

B、重量 2。
C、ウェイト 7。

合計の重みは 10 なので、確率は 10%、20%、70% になります。 100回引くと70回くらいCが勝つはずです。 10 回しか引き分けなかった場合、C は 4、6、あるいは 0 回勝つ可能性があります。サンプルが小さいとノイズが多くなります。重みは長期的な期待を表します。

累積分布

累積分布は、これらの重みを 0 から 1 までの区間のセグメントに変換します。同じ例では、次のようになります。

A は 0.00 ～ 0.10 をカバーします。

・Bは0.10～0.30をカバーします。

C は 0.30 ～ 1.00 をカバーします。

各セグメントの幅はオプションの確率です。セグメントは重なり合わず、一緒に間隔全体をカバーします。

これが、重み付け選択でオプションごとに個別の確率を必要としない理由です。必要なのは重量とその合計だけです。

逆変換サンプリング

逆変換サンプリングは、その分布から選択する標準的な方法です。

総重量を計算します。
0 から合計までのランダムな値を選択します。
オプションを順に実行し、各重みを現在の合計に追加します。
累積重みがランダム値以上である最初のオプションで停止します。

選択したオプションが勝者となります。ランダムな値が A のセグメントに到達すると、A が勝ちます。 C のセグメントに着地すると、C が勝ちます。

このアルゴリズムでは、描画ごとに O(n) 時間がかかります。ここで、n はオプションの数です。これはシンプルで正確で、数十のオプションがあるページとしては十分な速度です。

交換ありと交換なし

置換の場合、各ドローは独立しています。同じオプションが複数回勝つ可能性があります。これは、すべての描画で元の確率を使用する必要がある場合に適切なモデルです。

置換しない場合、選択したオプションはプールから削除されます。残りの重みは、次の描画の前に再正規化されます。 A が削除されると、残りの合計が少なくなるため、B と C が次の抽選でより大きなシェアを獲得します。

置き換えがなければシャッフルではありません。すべての順列が同じ確率で生成されるわけではありません。重み付けされた順序が生成されます。重み付けが大きいオプションが先に表示される傾向があります。

大量のピックのためのエイリアス方式

膨大な数の描画または非常に大規模なオプションセットの場合は、エイリアスメソッドと呼ばれるより高速な代替手段があります。ルックアップテーブルを一度作成し、一定時間で各描画に応答します。

エイリアスメソッドは、何百万もの選択が必要なゲームやシミュレーションで役立ちます。リストが小さいブラウザツールの場合は、累積逆変換サンプリングの方が簡単で、完全に適切です。

よくある間違い

重みは間違いやすいです。次の間違いに注意してください。

他の重みがゼロでない場合、70 の重みを 70% として扱います。他の重みの合計が 30 以下の場合は、わずか 70% になります。
ゼロまたは負の重みを許可します。ゼロウェイトオプションでは決して勝つことはできません。負の重みを指定すると、分布が無意味になります。
予測不可能である必要がある引き分けに Math.random() を使用する。
バイアスされたマッピングを使用して、ランダムな値をセグメントに変換します。
10 回または 20 回の引き分けから公平性を判断します。サンプルが小さい場合、予想される分布とは大きく異なる可能性があります。

もう 1 つのよくある間違いは、重み付けとシャッフルを混同することです。すべての順列を同じ確率で必要とする場合は、リストをシャッフルします。加重された最初のピックが必要な場合は、加重されたドローを使用してください。

加重描画を検証する方法

予想される周波数と観測された周波数を比較します。重み 1、2、および 7 では、期待される確率は 10%、20%、および 70% になります。何千回もの描画を繰り返すと、観察される割合はその数値に近づくはずです。

小さなサンプルを拡大解釈しないでください。かなりの重みを持ったドローは、驚くべきストリークを生み出す可能性があります。重要なのは、サンプルが増加するにつれて観察された周波数が収束するかどうか、そしてその実装が文書化されているかどうかです。

公開ウェイトドローの場合は、オプション、ウェイト、結果を記録します。これにより、コードを公開しなくても描画を監査できるようになります。

このサイトが重み付きランダムを実装する方法

このサイトの重み付きピッカーは、累積的な重みと暗号的に安全なランダム値を使用します。確率プレビューには、描画する前に正規化された分布が表示されます。オプションは逆変換サンプリングで選択され、非置換描画では選択されたオプションが削除され、残りの重みが再正規化されます。

すべてがブラウザ内でローカルに実行されます。オプション、重み、結果はアップロードされません。

結論

重み付けされたランダム性は確率を変えるものであり、ランダム性の原因ではありません。重みを正規化し、安全なランダム値を使用して、一致する累積セグメントを選択します。これにより、戦利品テーブル、抽選会、A/B テスト、および教室での活動について、公平で不平等な確率が得られます。