私がん2面ダイスで、各面が けある程度の可能性がある pけサイコロを振ったときに何が出るか。この情報を静的に（つまり、固定された確率のセットに対して）保存して、サイコロをランダムに振ることを効率的にシミュレートできるような、適切なデータ構造があるかどうか知りたいです。
現在、私はO(lg んこの問題の解決策は、最初の累積確率の表を保存することです。け 全員の味方 け次に、[0, 1) の範囲内でランダムな実数を生成し、テーブルに対してバイナリ検索を実行して、累積値が選択した値以下になる最大のインデックスを取得します。
私はこのソリューションをかなり気に入っていますが、ランタイムが確率を考慮していないのは奇妙に思えます。特に、常に片側が出てくる、または値が均一に分布しているという極端なケースでは、単純なアプローチを使用してロールの結果を O(1) で生成できますが、私のソリューションでは依然として対数的に多くのステップが必要になります。
実行時に何らかの形で「適応的」な方法でこの問題を解決する方法について、何か提案はありますか?
アップデート：この質問に対する回答に基づいて、私は次のように書きました。この問題に対する多くのアプローチを説明した記事、およびそれらの解析。Voseのalias法の実装ではΘ(ん) の前処理時間と、サイコロを振るたびに O(1) の時間で、これは本当に印象的です。これが回答に含まれる情報への有用な追加となることを願っています。
ベストアンサー1
あなたが探しているのはエイリアスメソッドこれはオー(1) method for generating a fixed discrete probability distribution (assuming you can access entries in an array of length n in constant time) with a one-time O(n) set-up. You can find it documented in chapter 3 (PDF) of "Non-Uniform Random Variate Generation" by Luc Devroye.
The idea is to take your array of probabilities pk and produce three new n-element arrays, qk, ak, and bk. Each qk is a probability between 0 and 1, and each ak and bk is an integer between 1 and n.
We generate random numbers between 1 and n by generating two random numbers, r and s, between 0 and 1. Let i = floor(r*N)+1. If qi < s then return ai else return bi. The work in the alias method is in figuring out how to produce qk, ak and bk.