18

昨日、私はこのインタビューの質問をしましたが、完全には答えることができませんでした：

f() = 0 or 1完全な1：1分布の関数が与えられた場合、f(n) = 0, 1, 2, ..., n-1それぞれ確率1/nの関数を作成します

f()nが2の自然な累乗である場合、つまり2進数のビットを生成するために使用する場合の解決策を考え出すことができますk=ln_2 n。しかし、これは明らかに、たとえばn = 5の場合f(5) = 5,6,7は機能しません。これは、不要なものを生成するためです。

誰かが解決策を知っていますか？

4

4 に答える 4

24

説明したよりも2の最小の累乗の乱数を作成できnます。次に、このアルゴリズムがより大きい数を生成するときはいつでもn-1、その数を捨てて再試行してください。これは、拒否の方法と呼ばれます。

添加

アルゴリズムは

Let m = 2^k >= n where k is is as small as possible.
do
   Let r = random number in 0 .. m-1 generated by k coin flips
while r >= n
return r

このループが最大でのi反復で停止する確率は、によって制限され1 - (1/2)^iます。これは非常に急速に1になります。ループは30回の反復後も実行されており、確率は10億分の1未満です。

わずかに変更されたアルゴリズムを使用して、予想される反復回数を減らすことができます。 

Choose p >= 1
Let m = 2^k >= p n where k is is as small as possible.
do
   Let r = random number in 0 .. m-1 generated by k coin flips
while r >= p n
return floor(r / p)

たとえば、より単純なアルゴリズムで0 .. 4（n = 5）を生成しようとしている場合、結果の3/8である5、6、および7を拒否します。（p = 3たとえば）の場合pn = 15、m = 16になり、結果の15、つまり1/16のみが拒否されます。価格は、3回ではなく4回のコイントスと除算が必要です。コイントスを増やしpたり追加したりして、希望する限り拒否を減らすことができます。

于 2012-11-03T12:30:13.660 に答える
2

もう1つの興味深い解決策は、マルコフ連鎖モンテカルロ法であるメトロポリス-ヘイスティングスアルゴリズムによって導き出すことができます。これは、多数のサンプルが必要な場合に大幅に効率的になりますが、限界内の一様分布に近づくだけです。

 initialize: x[0] arbitrarily    
 for i=1,2,...,N
  if (f() == 1) x[i] = (x[i-1]++) % n
  else x[i] = (x[i-1]-- + n) % n

Nが大きい場合、ベクトルxには0からnまでの一様分布の数値が含まれます。さらに、受け入れ/拒否ステップを追加することで、任意の分布からシミュレートできますが、サブプロシージャとして[0,1]の均一な乱数をシミュレートする必要があります。

于 2013-05-30T00:34:29.890 に答える
0 
def gen(a, b):
  min_possible = a
  max_possible = b

  while True:
    floor_min_possible = floor(min_possible)
    floor_max_possible = floor(max_possible)
    if max_possible.is_integer():
      floor_max_possible -= 1

    if floor_max_possible == floor_min_possible:
      return floor_max_possible

    mid = (min_possible + max_possible)/2
    if coin_flip():
      min_possible = mid
    else:
      max_possible = mid
于 2016-12-10T04:44:40.753 に答える
-3 
My #RandomNumberGenerator #RNG

/w any f(x) that gives rand ints from 1 to x,  we can get rand ints from 1 to k, for any k:

get ints p & q, so p^q is smallest possible, while p is a factor of x, & p^q >= k;

Lbl A
i=0 & s=1; while i < q {
s+= ((f(x) mod p) - 1) * p^i;
i++;
}
if s > k,  goto A, else return s


//** about notation/terms:
rand = random
int = integer
mod is (from) modulo arithmetic 
Lbl is a “Label”, from the Basic language, & serves as a coordinates for executing code.  After the while loop, if s > k, then “goto A” means return to the point of code where it says “Lbl A”, & resume.  If you return to Lbl A & process the code again, it resets the values of i to 0 & s to 1.  
i is an iterator for powers of p, & s is a sum.  
"s+= foo" means "let s now equal what it used to be + foo".
"i++" means "let i now equal what it used to be + 1".
f(x) returns random integers from 1 to x. **//


I figured out/invented/solved it on my own, around 2008.  The method is discussed as common knowledge here.  Does anyone know since when the random number generator rejection method has been common knowledge?  RSVP.
于 2018-06-30T04:57:04.157 に答える