• 欢迎浏览“String me = Creater\忠实的资深Linux玩家;”,请文明浏览,理性发言,有侵犯你的权益请邮件我(creater@vip.qq.com).
  • 把任何的失败都当作一次尝试,不要自卑;把所有的成功都想成是一种幸运,不要自傲。
  •    5年前 (2013-05-13)  杂七杂八 |   4 条评论  29 
    文章评分 0 次,平均分 0.0

    描述:已知randn可以等概率的产生[0,n)范围内的数。那么如何利用randn来等概率产生[0,m)内的数呢,根据m,n的大小分两种情况:

    第一种,即是n > m。
    比如rand5产生等概率函数rand3,rand7产生等概率的rand5等。

    这种算比较简单的了,randn说明[0,n)之间的数都是等概率产生,概率为
    $$\begin{array}{rcl}p = \frac{1}{n}\end{array}$$
    由于n > m,那么由randn产生[0,m)之间任意数的概率都是相等的
    $$\begin{array}{rcl}p1 =\frac{1}{n}\end{array}$$
    由randn产生[m,n)之间任意数的概率也是p1,但是落在[m,n)里的概率则为
    $$\begin{array}{rcl}p2 =\frac{n-m}{n}\end{array}$$
    现在需要设计randm(),使得值落在[0,m)之间每个数的概率为
    $$\begin{array}{rcl}p3 =\frac{1}{m}\end{array}$$
    由p1,p2得到取得0的概率为:第一次就取得0,那么概率为1/n,第二次才取得0(第一次取的非[0,m)内的数),那么概率为(n-m)/n * 1/n,一直继续下去。
    $$\begin{array}{rcl}p(0) =\frac{1}{n} + {\frac{n-m}{n} * \frac{1}{n}}+{\frac{n-m}{n}*\frac{n-m}{n}*\frac{1}{n}}+ \cdots\end{array}$$
    $$\begin{array}{rcl}p(0) =\frac{1}{n}*\sum_{i=0}^\infty \left(\frac{n-m}{n}\right)^i ={\frac{1}{n}}*{\frac{1}{1-\frac{n-m}{n}}} = \frac{1}{m}\end{array}$$
    取得其他数的概率也是类似!

    代码也很简单,如下所示

    int randm(int  m)
    {
    	int ret = m;
    	while(ret > m)
    		ret = randn();
    	return ret;
    }

    由rand5生成 rand3

    int Rand3()
    {
        int x;
        do
        {
            x = Rand5();
        } while (x >= 3);
        return x;
    }

    另外一种,那就是n<m。
    比如rand5产生等概率函数rand7.

    这种较为复杂了。我来分析分析。 有了n>m的经验,很自然就想到利用上面的简单方法。所以需要对randn进行扩增,使得扩展后的区间大于m.如何扩增呢?
    扩展1:比如randn()*k,扩展后可能的取值为0,k,2*k,3*k......这样就出现问题了,[1,k),[k+1,2k)之间的数产生的概率为0,不可取。所以需要再加上randn()
    扩展2:在扩展1的基础上,randn()*k + randn(),这种是可行的,加号前边是以倍数增加,加号后面则是领头,一般取k的值为n, 当然可以取其他值,下面我就以randn()*n + randn()来计算。

    randn()*n + randn()会产生的数为[0*n+0, (n-1)*n+(n-1)),即为$$\begin{array}{rcl}\left[0,n^2\right)\end{array}$$
    现在问题就转移到上边那种情况,但是还是有一点不同的是,如果仅仅在上边的区间$$\begin{array}{rcl}\left[0,n^2\right)\end{array}$$内取[0,m) ,这样达不到等概率且需要等于$$\begin{array}{rcl}\frac{1}{m}\end{array}$$
    在这里就需要用到取模,将多个长度为m的区间内的值,映射到[0,m),一个数映射到[0,m)的办法是对m取模。
    设在$$\begin{array}{rcl}\frac{1}{m}\end{array}$$这个区间内值x,大于x的丢弃,小于x的则映射到[0,m).那么,在[0,x)区间内对于[0,m)内的每个值最后都可以取x/m次(也就是包含了多少个长度为m的区间)可以得到取0的概率为
    $$\begin{array}{rcl}p(0) =\frac{\frac{x}{m} }{n^2} +\left(\frac{n^2-x}{n^2}\right)*\frac{\frac{x}{m} }{n^2} +\left(\frac{n^2-x}{n^2}\right)*\left(\frac{n^2-x}{n^2}\right)*\frac{\frac{x}{m} }{n^2} + \cdots\end{array}$$
    $$\begin{array}{rcl}p(0) =\frac{\frac{x}{m}}{n^2}*\sum_{i=0}^\infty \left(\frac{n^2-x}{n^2}\right)^i \end{array}$$
    $$\begin{array}{rcl}p(0) =\frac{x}{n^2*m}*{\frac{1}{1-\frac{n^2-x}{n^2}}}\end{array}$$
    $$\begin{array}{rcl}p(0) =\frac{1}{m}\end{array}$$
    另外由上边第一个式子,可以看出$$\begin{array}{rcl}x\%m==0\end{array}$$
    至此,得到了这种方式取得的概率是正确的。

    using namespace std;
    int randm(int  n, int m, int x)
    {
    	int ret = 0;
    	while(ret > x)
    		ret = randn() * n + randn();
    	return ret % m;
    }

    由rand5生成rand7

    int Rand7()
    {
        int x;
        do
        {
            x = Rand5() * 5 + Rand5();
        } while (x >= 21);
        return x % 7;
    }
     

    除特别注明外,本站所有文章均为String me = "Creater\忠实的资深Linux玩家";原创,转载请注明出处来自http://unix8.net/home.php/1134.html

    关于

    发表评论

    暂无评论

    切换注册

    登录

    忘记密码 ?

    切换登录

    注册

    扫一扫二维码分享