私はシミュレーションシステムに取り組んでいます。すぐに、いくつかのシミュレーション入力に対する実際の値の分布に関する実験データ (ヒストグラム) が得られます。
シミュレーションの実行時に、測定された分布に一致するランダムな値を生成できるようにしたいと考えています。元のヒストグラムを保存せずにこれを行うことをお勧めします。いくつかの良い方法は何ですか
編集: 入力データは、いくつかの異なる種類のイベントのイベント期間です。種類が異なれば分散機能も異なると思います。
少なくとも 2 つのオプション:
ウィリアム R. ギブスによる現代物理学の計算から:
[関数] を数値的に積分し、[ cdf ] を逆算することはいつでもできますが、特にpdfが急速に変化している場合、これはあまり満足のいくものではありません。
文字通り、範囲[0-1)をターゲット ディストリビューションの適切な範囲に変換するテーブルを作成します。次に、通常の (高品質の) PRNG を投げて、テーブルで翻訳します。面倒ですが、明確で実行可能で、完全に一般的です。
ターゲット ヒストグラムを正規化し、次に
x範囲内の位置 ( ) をランダムに選びます。繰り返しますが、単純ですが、明確で機能しています。非常に低い確率 (長い尾を持つピーク) が多いため、分布が遅くなる可能性があります。
これらの方法の両方を使用すると、区分的多項式近似またはスプラインでデータを近似して、ステップ関数ヒストグラムが必要ない場合に滑らかな曲線を生成できますが、時期尚早の最適化になる可能性があるため、後でそれを残します。
特別な場合には、より良い方法が存在する場合があります。
これはすべて非常に標準的なものであり、さらに詳細が必要な場合は、数値解析の教科書に記載されているはずです。
問題に関する詳細情報が役立ちます。たとえば、ヒストグラムはどのような値ですか? それらはカテゴリー的 (例: 色、文字) または連続的 (例: 高さ、時間) ですか?
ヒストグラムがカテゴリデータを超えている場合、カテゴリ間に多くの相関関係がない限り、分布をパラメータ化するのは難しいと思います.
ヒストグラムが連続データ上にある場合は、ガウス分布の混合を使用して分布を適合させようとすることがあります。つまり、$\sum_{i=1}^n w_i N(m_i,v_i)$ を使用してヒストグラムを当てはめてみます。ここで、m_i と v_i は平均と分散です。次に、データを生成する場合は、最初に重み w_i に比例する確率で 1..n から i をサンプリングし、ガウス分布から行うように x ~ n(m_i,v_i) をサンプリングします。
いずれにせよ、混合モデルについてもっと読みたいと思うかもしれません。
@dmckeeが言うように、特定の確率分布を生成するために必要なのは、累積分布関数の逆である 分位関数であるようです。
問題は次のようになります: 与えられた連続ヒストグラムを表す分位点関数を生成して保存する最良の方法は何ですか? 答えは入力の形状に大きく依存すると感じています-それが何らかのパターンに従う場合、最も一般的なケースよりも単純化する必要があります。行ったらここで更新します。
編集：
今週、この問題を思い出させる会話をしました。ヒストグラムを方程式として記述するのをやめて、テーブルだけを保存すると、O(1) 時間で選択を行うことができますか? O(N lgN) の構築時間を犠牲にして、精度を損なうことなくできることがわかりました。
N 項目の配列を作成します。配列への一様ランダム選択は、確率 1/N のアイテムを見つけます。アイテムごとに、このアイテムが実際に選択されるべきヒットの割合と、このアイテムが選択されていない場合に選択される別のアイテムのインデックスを格納します。
加重ランダム サンプリング、C 実装:
//data structure
typedef struct wrs_data {
double share;
int pair;
int idx;
} wrs_t;
//sort helper
int wrs_sharecmp(const void* a, const void* b) {
double delta = ((wrs_t*)a)->share - ((wrs_t*)b)->share;
return (delta<0) ? -1 : (delta>0);
}
//Initialize the data structure
wrs_t* wrs_create(int* weights, size_t N) {
wrs_t* data = malloc(sizeof(wrs_t));
double sum = 0;
int i;
for (i=0;i<N;i++) { sum+=weights[i]; }
for (i=0;i<N;i++) {
//what percent of the ideal distribution is in this bucket?
data[i].share = weights[i]/(sum/N);
data[i].pair = N;
data[i].idx = i;
}
//sort ascending by size
qsort(data,N, sizeof(wrs_t),wrs_sharecmp);
int j=N-1; //the biggest bucket
for (i=0;i<j;i++) {
int check = i;
double excess = 1.0 - data[check].share;
while (excess>0 && i<j) {
//If this bucket has less samples than a flat distribution,
//it will be hit more frequently than it should be.
//So send excess hits to a bucket which has too many samples.
data[check].pair=j;
// Account for the fact that the paired bucket will be hit more often,
data[j].share -= excess;
excess = 1.0 - data[j].share;
// If paired bucket now has excess hits, send to new largest bucket at j-1
if (excess >= 0) { check=j--;}
}
}
return data;
}
int wrs_pick(wrs_t* collection, size_t N)
//O(1) weighted random sampling (after preparing the collection).
//Randomly select a bucket, and a percentage.
//If the percentage is greater than that bucket's share of hits,
// use it's paired bucket.
{
int idx = rand_in_range(0,N);
double pct = rand_percent();
if (pct > collection[idx].share) { idx = collection[idx].pair; }
return collection[idx].idx;
}
編集 2: 少し調べたところ、O(N) 時間で構築を行うことさえ可能であることがわかりました。注意深く追跡すれば、大小のビンを見つけるために配列をソートする必要はありません。 更新された実装はこちら
離散点の加重分布を使用して多数のサンプルを抽出する必要がある場合は、同様の質問への回答を参照してください。
ただし、ヒストグラムを使用して連続ランダム関数を概算する必要がある場合、最善の策はおそらく dmckee の数値積分の答えです。または、エイリアシングを使用してポイントを左に保存し、2 つのポイントの間で均一な数を選択することもできます。
ヒストグラム (オリジナルまたは縮小) から選択するには、 Walker のエイリアス法 が迅速かつ簡単です。
正規分布の場合、以下が役立つ場合があります。
http://en.wikipedia.org/wiki/Normal_distribution#Generating_values_for_normal_random_variables