等確率ランダム関数の実現

タイトル:
ランダム関数rand()は、pの確率で0を生成し、1−pの確率で1を生成することが知られているが、現在、1/nの等確率で1~nの間の任意の数を生成させる新しいランダム関数newRand()の設計が求められている.
解析:既知のランダム関数rand()によって等確率で0と1の新しいランダム関数Rand()を生成し、k(kは整数nのバイナリ表現のビット数)次Rand()関数を呼び出し、kの長さの0と1のシーケンスを得ることができ、このシーケンスによって形成される整数は1-nの間の数字である.なお、生成シーケンスから得られる整数はnより大きい可能性があり、nより大きい場合、得られる整数がnより大きくないまで再生成される.
ステップ1:rand()関数からRand()関数を生成し,Rand()関数などの確率で0と1を生成する.

int Rand()  
{  
    int i1 = rand();  
    int i2 = rand();  
    if(i1==0 && i2==1)  
        return 1;  
    else if(i1==1 && i2==0)  
        return 0;  
    else  
        return Rand();  
    return -1;  
}  

ステップ2:整数nのバイナリ表現が持つビット数kを計算し、k=1+log 2 n(logは2をベースとするn)ステップ3:k回Rand()を呼び出して乱数を生成する.

int newRand()  
{  
    int result = 0;  
    for(int i = 0 ; i < k ; ++i)  
    {  
        if(Rand() == 1)  
            result |= (1<<i);  
    }  
    if(result > n)  
        return newRand();  
    return result;  
}  

タイトル:
関数rand 5()が与えられ、関数はランダムに1〜5の整数を生成することができ、生成確率は同じである.この関数を用いて関数rand 7()を構築し,関数rand 7()が1−7の整数をランダムに等確率で生成できるようにすることが要求される.分析:多くの人の第一反応はrand 5()+rand()%3を利用してrand 7()関数を実現することであり、この方法は確かに1-7間の乱数を生成することができるが、よく考えてみると数字生成の確率は等しくないことが分かった.rand()%3が0を生成する確率は1/5であり,1と2を生成する確率はいずれも2/5であるため,この方法は6と7を生成する確率が5を生成する確率より大きい.正しい方法はrand 5()関数を用いて1〜25の間の数値を生成し、そのうちの1〜21を1〜7にマッピングし、22〜25を破棄することである.例えば(1,1),(1,2),(1,3)を生成するとrand 7()のうちの1とみなされ,残りの4種類が出現すると廃棄されて再生成される.シンプルな実装:

int rand7()  
{  
    int x = 0;  
    do  
    {  
        x = 5 * (rand5() - 1) + rand5();  
    }while(x > 21);  
    return 1 + x%7;  
}  

私の注:この考え方は、rand()が[0,N-1]を生成し、rand()をN進の一桁発生器と見なすと、rand(*N+rand()を用いて2桁のN進数を生成することができ、このようにして、3桁、4桁、5桁を生成することができる...のN進数です.このようなN進数を構成するように生成される乱数は、必ずランダムを保証することができるが、逆にrand()を用いてランダム数(rand 5()+rand()%3)を生成することは、確率平均を保証することはできない.
この問題ではNは5であるためrand 5(*)*5+rand 5()を用いて2ビットの5進数を生成することができ,範囲は1〜25である.さらに22−25を除去し、残りは3を除去し、rand 7()の発生器とする.
タイトル:rand 7()の関数が既知で、1から7のランダム自然数を返し、このrand 7()を利用してrand 10()をランダムに1~10させる.分析:
rand 10()の整数1〜10の均一な分布を保証するには、1〜10*nの均一な分布のランダムな整数区間(nは任意の正の整数)を構築することができる.xがこの1−10*n区間のランダム整数であると仮定すると、x%10+1は1−10区間に均一に分布する整数である.(rand 7()−1)*7+rand 7()は、1−49に均一に分布する乱数を構築することができるため(理由は以下の説明を参照)、41〜49のような乱数を除去することができ、得られた数1−40は依然として1−40に均一に分布している.これは、各数が独立したイベントと見なすことができるからである.次に、なぜ(rand 7()−1)*7+rand 7()が1−49に均一に分布する乱数を構築できるのかを説明する.まず、rand 7()−1は、離散整数集合{0,1,2,3,4,5,6}を得、各整数の出現確率は1/7である.(rand 7()−1)*7は、離散整数集合A={0,7,14,21,28,35,42}を得、各整数の出現確率も1/7である.一方rand 7()で得られた集合B={1,2,3,4,5,6,7}の整数ごとに出現する確率も1/7である.明らかに、集合AとBの任意の2つの要素の組み合わせは、1〜49の間の1つの整数に1つずつ対応することができ、すなわち、1〜49の間の任意の数は、AとBの2つの要素の1つの組み合わせを一意に決定することができ、逆に成立することができる.AとBの要素は独立イベントと見なすことができるので,独立イベントの確率式P(AB)=P(A)P(B)に基づいて,各組合せの確率は1/7*1/7=1/49となる.従って(rand 7()−1)*7+rand 7()で生成された整数は1−49の間に均一に分布し,各数の確率は1/49であった.プログラム:

int rand_10()  
{  
    int x = 0;  
    do  
    {  
        x = 7 * (rand7() - 1) + rand7();  
    }while(x > 40);  
    return x % 10 + 1;  
}  

注:なぜwhile(x>40)でwhile(x>10)を使わないのか、友人から聞いた.なぜならwhile(x>10)を使うと40/49の確率でwhileを循環する必要があり、死循環する可能性が高いからです.
タイトル:random 3()という乱数発生器が[1,3]の範囲の乱数を生成することが知られています.random 3()でrandom 5()関数を構築し、[1,5]の乱数を生成してください.分析:[1-3]範囲の数からより広い範囲の数をどのように構築しますか?このより広い範囲を同時に満たす数の出現確率は同じであり,考えられる演算には加算と乗算の2つが含まれる.3*(random 3)–1)+random 3();上記式の範囲は[1,9]であり、数の出現確率は同じである1/9であると計算できる.次に,[1,9]の範囲の数から[1,5]の数をどのように生成するかを考える.考えられる方法はrejection sampling法であり,[1,9]の乱数を生成し,数の範囲が[1,5]内でなければ再サンプリングする.解決方法:

int random5()  
{  
    int val = 0;  
    do  
    {  
        val = 3 * (random3() - 1) + random3();  
    }while(val > 5);  
    return val;  
}

まとめ:この問題をさらに抽象化し、random_が知られている.m()乱数生成器の範囲は[1,m]random_を求めるn()は[1,n]範囲の関数を生成し,mint random_n() { int val = 0; int t; //t n ， t<m*m do { val = m * (random_m() - 1) + random_m(); }while(val > t); return val; }
1つの関数rand()を与えて0からn-1の間の等確率乱数を生成することができて、どのように0からm-1の間の等確率の乱数を生成しますか?

int random(int m , int n)  
{  
    int k = rand();  
    int max = n-1;  
    while(k < m)  
    {  
        k = k*n + rand();  
        max = max*n + n-1;  
    }  
    return k/(max/n);  
} 

次の確率の乱数をどのように生成しますか?0が1回、1が2回、2が3回、n-1がn回?

int random(int size)  
{  
    while(true)  
    {  
        int m = rand(size);  
        int n = rand(size);  
        if(m + n < size)  
            return m+n;  
    }  
}  

関連記事http://blog.csdn.net/wangran51/article/details/8981753