シンプレックスからの均一なサンプリング

Question

n乱数の配列を生成するアルゴリズムを探しています。これにより、n数の合計は1であり、すべての数値が0と1以内にあります。たとえば、n = 3、ランダムポイント（x、y、 z）三角形の中にある必要があります。

x + y + z = 1
0 < x < 1
0 < y < 1
0 < z < 1

理想的には、エリア内の各ポイントが等しい確率を持たせたいです。難しすぎる場合は、要件を削除できます。ありがとう。

Answer 1

最初にあなたが中にサンプリングしたいと仮定しましょう

x + y + z = 1
0 ≤ x ≤ 1
0 ≤ y ≤ 1
0 ≤ z ≤ 1

サンプルポイントはまだ高い確率で要求されたエリアにあるため、これは大きな違いをもたらしません。

今、あなたはからのポイントをサンプリングすることに残されています シンプレックス. 。 3Dの例では、3Dで実現された2Dシンプレックス（三角形）を取得します。

ランダムに均一にポイントを選ぶ方法は、これで議論されました ブログ投稿 （コメントを参照）。

あなたの問題のために、それはあなたが間隔$（0,1）$から$ n-1 $ランダム数を取ることを意味します、そして、あなたは$ 0 $と$ 1 $を追加して、$ n+1 $番号のリストを取得します。リストを並べ替えてから、2つの連続した要素の違いを記録します。これにより、最大$ 1 $の$ n $番号のリストが表示されます。さらに、このサンプリングは均一です。このアイデアはドナルドB.ルービンにあります、 ベイジアンブートストラップ アン。統計学者。 9、1981、130-134。

たとえば（$ n = 4 $）、3つの乱数があります 0.4 0.2 0.1 次に、ソートされたシーケンスを取得します 0 0.1 0.2 0.4 1 そして、これは違いを与えます 0.1 0.1 0.2 0.6, 、および構築により、これらの4つの数値は1まで合計されています。

別のアプローチは次のとおりです：Hypercubeの最初のサンプル（つまり、あなたは忘れています x+y+z=1）次に、サンプルポイントを正規化します。正規化は、$ d $ -HyperCubeから$ D-1 $ -SIMPLEXへの投影です。でポイントが 中心 シンプレックスの方は、 外側. 。したがって、ハイパーキューブから均一にサンプリングすると、シンプレックスで均一なサンプリングが得られません。ただし、適切な指数分布でハイパーキューブからサンプリングする場合、この効果がキャンセルされます。この図は、両方のメソッドがどのようにサンプリングされるかアイデアを提供します。ただし、単純なフォームのため、「ソート」方法を好みます。また、実装が簡単です。

Answer 2

これは、既存の回答に追加することです。

devroye この種の質問のための優れた参照です。第7章では、OPの後の均一な注文統計を生成するために必要なアルゴリズムを示しています。

均一な注文統計を生成するために、$ [0,1] $の$ n $サンプルを並べ替えます。このアプローチでは、$ o（n log n）$時間がかかります。より迅速な方法（本で利用可能）には、$ mathrm {exp}（1）$ pdfからの$ n $ norand数$ x_1、 ldots、x_n $をサンプリングすることが含まれます。 （これらはです 間隔 均一なPDFの）。次に、値を返します$$（y_i）_ {1 leq i leq n} = frac { sum limits_ {1 ldots i} x_j} { sum limits_ {1 ldots n} x_j} $ $ $ o（n）$ time全体で自動的にソートされます。 （ここではA.Schulzの答えと重複しています。計算をより明確にするだけです）。

同じアプローチを逆CDFサンプリングを介して、$ [0,1] $を超える不均一なPDFをサンプリングするために、適応できます。また、標準的なシンプレックス以外のシンプレックス上で均一にサンプリングできるトリックもあります（たとえば、$ 2x+3y+z = 5 $）。

Answer 3

X[0] = 0
for i = 1 to N-1
    X[i] = uniform(0,1)
X[n] = 1
sort X[0..N]
for i = 1 to N
    Z[i] = X[i] - X[i-1]
return Z[1..N]

ここ、 uniform(0,1) 実際の数を独立して0〜1の間に均一に分布します。

Answer 4

見る この紙: ：スミス、N。、トロンブル、R。 ユニットシンプレックスから均一にサンプリング.