[解決済み] 加重乱数

質問

重み付き乱数を実装しようとしています。現在、壁に頭を打ち付けているばかりで、これを理解することができません。

私のプロジェクト (ホールデムのハンドレンジ、主観的オールインエクイティ分析) では、Boost のランダム関数を使用しています。そこで、私が 1 から 3 の間の乱数 (つまり、1、2、3 のいずれか) を選びたいとします。Boostのメルセンヌ・ツイスター・ジェネレータは、この点では魅力的に働きます。しかし、例えば次のように重み付けをしたい。

1 (weight: 90)
2 (weight: 56)
3 (weight:  4)

Boostには、このための何らかの機能があるのでしょうか？

どのように解決するのですか？

項目が個々の重みを持っている場合、ランダムに項目を選択するための簡単なアルゴリズムがあります。

1) すべての重みの合計を計算する。

2) 0以上かつ重みの総和より小さい乱数を選ぶ

3) 乱数から重さを引いて、乱数がその項目の重さより小さい項目を得るまで、項目を一つずつ見ていきます。

これを説明する擬似コード

int sum_of_weight = 0;
for(int i=0; i<num_choices; i++) {
   sum_of_weight += choice_weight[i];
}
int rnd = random(sum_of_weight);
for(int i=0; i<num_choices; i++) {
  if(rnd < choice_weight[i])
    return i;
  rnd -= choice_weight[i];
}
assert(!"should never get here");

これは、あなたのboostコンテナなどに適応させるのに簡単なはずです。

ウェイトがほとんど変更されないが、ランダムに 1 つを選ぶことが多く、コンテナがオブジェクトへのポインタを保存しているか、数ダース以上のアイテムがある限り (基本的に、これが役に立つか妨げになるかどうかは、プロファイルしなければわかりません)、最適化が行われます。

各アイテムに累積重量の合計を格納することで バイナリ検索 を使って、ピックウェイトに対応する項目をピックすることができます。

リスト内のアイテムの数がわからない場合、次のようなとてもすてきなアルゴリズムがあります。 リザーバーサンプリング というアルゴリズムがあり、これを適応して重み付けをすることができます。