博士

やあ、ロボ子。今日は偏ったサイコロのシミュレーションについて話すのじゃ。

ロボ子

博士、こんにちは。偏ったサイコロですか？なんだか面白そうですね。

博士

そうじゃろ？例えば、Voseのエイリアスメソッドは、初期化にΘ(n)かかるけど、生成はΘ(1)で済む、最も効率的なアルゴリズムの一つらしいぞ。

ロボ子

Θ(n)とΘ(1)ですか。初期化に時間がかかっても、生成が速い方が嬉しい場面は多そうですね。

博士

まさにそう！記事によると、他にも色々手法があるみたいじゃ。例えば、確率の最小公倍数を使う方法もあるらしい。

ロボ子

最小公倍数ですか？それはどのように使うんですか？

博士

確率の分母の最小公倍数を計算して、そのサイズの配列を作るんじゃ。公平なサイコロの結果を、その配列を使って偏ったサイコロの結果にマッピングするらしいぞ。生成はO(1)だけど、初期化が最悪の場合O(∏di)になる可能性があるみたいじゃ。

ロボ子

なるほど。初期化が大変な場合もあるんですね。他に簡単な方法はありますか？

博士

偏ったコインを使う方法もあるぞ。各面を選択するかどうかを、偏ったコインをフリップして決めるんじゃ。これは最悪の場合O(n)かかるみたいじゃな。

ロボ子

それなら実装も簡単そうですね。用途によって使い分けるのが良さそうですね。

博士

そうじゃな。あと、ルーレットホイール選択ってのもあるぞ。累積確率の配列を作って、二分探索で乱数がどの範囲に落ちるか決めるんじゃ。初期化にΘ(n)、生成にΘ(log n)かかるらしい。

ロボ子

二分探索を使うんですね。それなら効率も良さそうです。

博士

さらに、最適ルーレットホイール選択ってのもあって、これは初期化にO(n^2)かかるけど、期待されるルックアップ時間を最小化できるらしいぞ。

ロボ子

O(n^2)ですか！初期化コストが高いですね。でも、それに見合うだけの価値がある場面もあるんでしょうね。

博士

ダーツ投げって方法もあるぞ。確率を長方形の面積として視覚化して、長方形にダーツを投げて結果を決めるんじゃ。

ロボ子

なんだかアナログな方法ですね。でも、直感的で分かりやすいです。

博士

エイリアスメソッドってのもあって、長方形を再配置して、各列に最大2つの異なる確率が含まれるようにするんじゃ。公平なサイコロと偏ったコインを使って結果を生成するらしい。

ロボ子

色々な方法があるんですね。偏ったサイコロ一つとっても、奥が深いですね。

博士

そうじゃろ？Voseのエイリアスメソッドは特にエレガントらしいぞ。初期化にちょっと手間はかかるけどな。

ロボ子

博士、今日は色々なことを教えていただきありがとうございました。私もVoseのエイリアスメソッド、勉強してみます。

博士

よし、ロボ子。じゃあ、次はもっと難しいテーマに挑戦するぞ！…って、あれ？私のサイコロ、どこに置いたかのじゃ？

ロボ子

博士、サイコロはさっきダーツ投げで使ってましたよ。的の真ん中に刺さってます。