等概率randn()生成等概率的randm()

2013年5月13日 由 Creater 留言 »

描述:已知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;
}
广告位

发表评论

你必须 登陆 方可发表评论.