[解決済み] ロードされたサイコロをシミュレートするための効率的なデータ構造とアルゴリズムとは？

質問

もし、私が n -のサイコロがあり、それぞれの面が  k はある確率で  p _k をロールアップしたときに出てくる。この情報を静的に (つまり、固定された確率のセットに対して) 格納し、サイコロのランダムな出目を効率的にシミュレートするための良いデータ構造があるかどうか知りたいのです。

現在、私はO(lg)  n ) の解決策を持っています。の累積確率の表を保存しておくというものです。 k  の辺の累積確率の表を保存することです。  k の範囲内で無作為に実数を生成し、その累積値が選択された値より大きくない最大のインデックスを得るためにテーブル上で二項探索を実行します。

私はこの解決策が好きですが、ランタイムが確率を考慮に入れないのは奇妙に思えます。特に、片側が常に出てくるか、値が一様に分布しているという極端なケースでは、私のソリューションがまだ対数的に多くのステップを要するのに対し、素朴なアプローチを使用して O(1) でロールの結果を生成することが可能です。

誰か、実行時間に何らかの形で「適応的」な方法でこの問題を解決する方法について提案を持っていますか？

更新しました。 この質問に対する回答に基づいて、私は次のように書きました。 この問題に対する多くのアプローチについて説明した記事 という記事で、その解析結果とともに紹介されています。Voseのエイリアス法の実装では、Θ( n ) の前処理時間とダイス1個あたりのO(1)時間を与えるようです。これは実に印象的です。 これが回答に含まれる情報への有用な追加であることを望みます!

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

あなたが探しているのは のエイリアスメソッド を提供する O(1) を提供するもので、一回の O(n) セットアップで一定の離散確率分布 (長さ n の配列のエントリに一定時間でアクセスできると仮定) を生成する方法です。この方法は 第3章 (PDF) の "非一様乱数生成".Non-Uniform Random Variate Generation。 をLuc Devroyeが執筆しました。

このアイデアは、確率の配列p _k の3つの新しいn要素配列、q _k , a _k およびb _k . 各q _k は 0 から 1 の間の確率であり，各 a _k とb _k は1以上n以下の整数である。

0から1までの2つの乱数rとsを生成して1からnまでの乱数を生成し、i = floor(r*N)+1 とする。もしqが _i < s ならば a を返す。 _i else return b <サブ i . aliasメソッドでの作業は、qをどのように生成するかを考えることです。 _k , a _k およびb _k .