加载中…
个人资料
xpord
xpord
  • 博客等级:
  • 博客积分:0
  • 博客访问:5,074
  • 关注人气:2
  • 获赠金笔:0支
  • 赠出金笔:0支
  • 荣誉徽章:
相关博文
推荐博文
谁看过这篇博文
加载中…
正文 字体大小:

关于按概率生成随机数的问题的算法

(2011-12-09 19:27:27)
标签:

随机数

概率分布

算法

效率

分类: 解密枭殇
CopyLeft

问题:
有一个数集,比如说{0, 1, 2,..., n-1},同时给定了一个概率分布表p[n],要随机生成其中的一个数,并且要使生成的数满足这个概率分布,求一个有效的算法。

注:我用的是Java语言,其他语言类似。
首先,随机生成一个0到n-1的整数可以这样做:
int a = int( n * Math.random());
但是概率不同就不能这样做了,曾经想过生成一堆区间,但最终由于性能问题而作罢。

当时我先想到了一本书上这样一个例子:
给定一串输入,它的前面是有效数据,后面都是NULL,有效数据的个数为一个很大的N(但你不知道N究竟有多大),要求生成等概率的1到N的数据,并在和数据长度相当的运行时间内给出答案,并且只遍历数据一次。
记得当时书上给出的算法大致是这样的:
int k = 0;
while(x[k] != null){
    if(random() < 1/(k+1)) output = x[k];
    k++;
}
//其中x[]为数据,output为输出结果,random()返回0到1之间的一个随机数

此方法表示在第k次时有1/(k+1)的几率覆盖掉原来的值(k=0时被置为初值x[0]),这样可以保证output的每个值出现的概率都是均等的。此结论可由归纳法证明如下:
对数组长度N进行归纳
当N=1,2时结论成立,每个x[i]的出现可能性为1/N;
假设N=k时结论成立,N=k+1时,x[k]的概率为1/(k+1),而x[i](0<=i<k)的概率为条件概率,
为(1/k)*(1-1/(k+1))=...=1/(k+1),即这一步操作之后仍然保证概率均等
由归纳法知,上述算法满足条件。

于是我从中得到启发,改变其中random()后面的值,不就会产生概率不等的数据了吗?这些值并不直接知道,但是可以计算。
设这些值为s[0],s[1],...,s[n-1],这些值和概率表p[]的关系可由以下公式给出:

关于按概率生成随机数的问题的算法


s[]的意义是覆盖的可能性,s[0]=1,而且上面n个方程之和是恒等于1的,而且很容易给出s[]的解
double[] s = new double[n];
for (int k = n - 1; k > 0; k--) {
    s[k] = 1;
    for (int m = k + 1; m < n; m++) {
        s[k] *= 1 - s[m];
    }
    s[k] = p[k] / s[k];
}

以下是生成随机数r的方法
int r = 0;
for (int i = 1; i < n; i++) {
    if (Math.random() < s[i])
   = i; // 用了替换的算法
}

综上可知,此算法的时间复杂度为O(n^2),而且这种方法不依赖与概率的具体分布,也不依赖于数据的连续性,并且把算法的较为繁重的地方转移到了人工的计算上,也在某种程度上增加了性能。

本人拙见,欢迎发表见解。

0

阅读 评论 收藏 转载 喜欢 打印举报/Report
  • 评论加载中,请稍候...
发评论

    发评论

    以上网友发言只代表其个人观点,不代表新浪网的观点或立场。

      

    新浪BLOG意见反馈留言板 电话:4000520066 提示音后按1键(按当地市话标准计费) 欢迎批评指正

    新浪简介 | About Sina | 广告服务 | 联系我们 | 招聘信息 | 网站律师 | SINA English | 会员注册 | 产品答疑

    新浪公司 版权所有