乱数生成（a、b）ランダム（0,1）を呼び出す

Question

Random(0,1)関数が知られています。これは、均一なランダム関数です。つまり、50％確率で0または1を返します。 Random(a, b)を実装しているのはRandom(0,1)

です。これまでのところ、0から始まる範囲に範囲a-bを入れてから、インデックス0,1,2 ... b-aがあります。

次に、RANDOM(0,1)をb-a回呼び出すと、生成されたidxとして結果が合計されます。要素を返します。

しかし、この本には答えがないので、この方法が正しいかどうかはわかりません。各要素を返す確率が全く同じであり、1/(b-a+1)であることを証明するにはどうすればよいですか？

これを行うには適切な方法はありますか？

Answer 1

RANDOM（0、1）が確率0.5の0または1を返す場合、バイナリで番号（b-a + 1）を表すのに十分な値が得られるまでビットを生成できます。これにより、ランダムな数値が少し大きすぎる範囲になります。失敗した場合は、テストして繰り返すことができます。このようなもの（Pythonで）。

def rand_pow2(bit_count): 
    """Return a random number with the given number of bits.""" 
    result = 0 
    for i in xrange(bit_count): 
     result = 2 * result + RANDOM(0, 1) 
    return result 

def random_range(a, b): 
    """Return a random integer in the closed interval [a, b].""" 
    bit_count = math.ceil(math.log2(b - a + 1)) 
    while True: 
     r = rand_pow2(bit_count) 
     if a + r <= b: 
      return a + r 

Answer 2

乱数を合計すると、結果は均等に分布しません。ガウス関数のように見えます。 「多数の法則」を探したり、確率のある本/記事を読んでください。コインを100回裏返すのと同じように、100頭を与える確率は非常に低いです。 50頭近くのテールと50頭のテールに近い可能性があります。

Answer 3

0からa-bの範囲を置くあなたの傾きが最初に正しいです。しかし、あなたが言ったようにそれをすることはできません。 This questionはそれを正確に行う方法を尋ねており、the answerは一意の分解を利用しています。 eのような最大の必要な指数を記録して、2にm=a-bを書きます。次に、mの最大倍数が2^eより小さい場合は、kとします。最後に、の番号をRANDOM(0,1)と生成し、2の番号xの拡張子にしてください。x < k*mの場合は、xに戻り、そうでない場合はもう一度やり直してください。

int RANDOM(0,m) { 

    // find largest power of n needed to write m in base 2 
    int e=0; 
    while (m > 2^e) { 
     ++e; 
    } 

    // find largest multiple of m less than 2^e 
    int k=1; 
    while (k*m < 2^2) { 
     ++k 
    } 
    --k; // we went one too far 

    while (1) { 
     // generate a random number in base 2 
     int x = 0; 
     for (int i=0; i<e; ++i) { 
      x = x*2 + RANDOM(0,1); 
     } 
     // if x isn't too large, return it x modulo m 
     if (x < m*k) 
      return (x % m); 
    } 
} 

今、あなたは、単にaとbの間で一様に分布番号を取得するために、結果にaを追加することができます。プログラムは、このような何か（簡単なケースメートル< 2^2）を探します。

Answer 4

分割と征服は、ランダム（0,1）を使用して範囲[a、b]の乱数を生成するのに役立ちます。アイデアは、aがbと等しい場合、乱数は

は、ランダム生成[B、]の範囲の中間を探す（0,1）

上記の場合である

1. あります0は、他の再帰
2. を使用して範囲内の乱数[中間]を返し、次のように働いて「C」コードである再帰

を用いて、[B、中間+ 1]の範囲内の乱数を返します。

int random(int a, int b) 
{ 
    if(a == b) 
     return a; 

    int c = RANDOM(0,1); // Returns 0 or 1 with probability 0.5 
    int mid = a + (b-a)/2; 

    if(c == 0) 
     return random(a, mid); 
    else 
     return random(mid + 1, b); 
} 

Answer 5

あなたが同じ確率で{0, 1}を返しRNGを持っている場合は、あなたが簡単に等しい確率で数字に{0, 2^n}を返すRNGを作成することができます。

これを行うには、元のRNG n回を使用し、0010110111のような2進数を取得するだけです。それぞれの数は（0から2^nまで）同じである可能性が高い。

aからbにRNGを簡単に取得できます。b - a = 2^nです。以前のRNGを作成してaを追加するだけです。

b-aが2^nではない場合、最後に質問してください。

---

あなたはほとんど何もしなくてもいいことです。 rejection sampling技術に依存しています。大きなセットがあり、そのセットにRNGがあり、このセットのサブセットから要素を選択する必要がある場合は、大きなセットから要素を選択したまま、サブセット内に存在するまで破棄することができます。

だからあなたはすべてb-aを見つけて、b-a <= 2^nのような最初のnを見つけます。次に、より小さい要素を選択するまで拒否サンプリングを使用します。b-a単にaを追加するよりも。