博客
关于我
强烈建议你试试无所不能的chatGPT,快点击我
ZT等概率随机函数问题
阅读量:5880 次
发布时间:2019-06-19

本文共 4068 字,大约阅读时间需要 13 分钟。

1. 基础问题 和 解决办法。

已知: 有一个随机函数 rand_0_and_1_with_p(), 这个随机数生成器,它能够以概率 p 产生0,以概率 (1 - p) 产生1。

要求:使用这个随机函数,设计一个新的随机函数要求以等概率生成0和1。

 

解决办法:组合问题类型:可以两次调用 该 随机函数。 运行函数 rand_0_and_1_with_p() 一次,可以得到 P(0) = p, P(1) = 1 - p。那么运行该函数两次,会生成两个数字,P (0 and 1) = p(1 - p),P(1 and 0) = (1 - p)p。这样就出现了等概率。所以实现如下:

 

1 int rand_0_and_1_with_equal_prob() { 2 int tmp1 = rand_0_and_1_with_p(); 3 int tmp2 = rand_0_and_1_with_p(); 4 if (tmp1 == 0 && tmp2 == 1) { 5 return 0; 6 } else if (tmp1 == 1 && tmp2 == 0) { 7 return 1; 8 } else { 9 return rand_0_and_1_with_equal_prob();10 }11 12 }

 

 

2. 问题 升级版!

已知: 有一个随机函数 rand_0_and_1_with_p(), 这个随机数生成器,它能够以概率 p 产生0,以概率 (1

求解: 使用这个随机函数 rand_0_and_1_with_p(),设计一个新的随机函数,要求以等概率产生 1 到 n 之间的随机数。

分析: 我们现在已经有了 (0, 1)的等概率随机数生成器。给定一个n,我们不妨将 (0, 1)等概率随机数生成器生成的0, 1 看作是二进制。 那么我们多云行几次,就可以生成一个二进制数字,如果这个二进制数字有 Log2(n) 个比特位。就可以了。

代码如下:

 

int rand_0_to_n_minus_1_with_equal_prob(int n) {int k = 0;while(n) {k++;n = n >> 1;}do {int res = 0;for(int i = 0; i < k; i++){res |= rand_0_and_1_with_equal_prob() << i;}} while(res >= n)return res;}

 

 

这里要注意,可能生成的数字会超过n,此时这里要舍弃这次随机数生成,重新再来一次。

3. 问题升级版 2!
问题: 给定函数 rand5() ,它能生成 1~5 之间的随机数字。
求解: 要求据此实现 rand7(),能产生1~7 之间的随机数字。
分析:
解法1:我们可以参照问题2解法,首先由 rand5() 生成 (0,1)等概率随机数生成器。然后由这个 (0, 1)等概率生成器生成 1~7 之间的等概率生成器。也就是 rand5()。

解法2:这个题目个人感觉非常棒,可以从题2中获得一定的灵感,题2中是将n表示成2进制,那是因为已知的随机函数是产生0和1的,对于该题,一直的随机函数是随机产生1~5的,我们可以很容易的将该函数转化成随机产生0~4,然后再将7表示成5进制的数,则1=015, 2=025, 3=035, 4=045, 5=105, 6=115, 7=125。不过这里我们同样是生成所有两位的五进制数,那么最高是445,即24,然后去掉21,22,23,24剩下的21个数0~20模7正好可以等概率生成0~6,然后加1即可。代码如下:

代码如下:

 

1 int rand7() {2 do {    3 int x = rand5() - 1;4 int y = rand5() - 1;5 int res = x * 5 + y;6 } while(res > 20)7 return (res % 7 ) + 18 }

 

 

4. 问题升级版 v3!

已知: rand_n() 可以产生 0 ~ n-1 之间的随机数

求解: 实现 rand_m() 产生 0~m-1 之间的随机数。

 

实现:如果 m <= n,那么直接生成即可。 如果m > n,将m用 <n进制> 数字表示,然后进行求解。

(起始就是问题3的思路扩展)

代码如下:

 

int rand_m() {int res = 0;if(m <= n) {do {res = rand_n();} while(res >= m)return res;}int count = 1;int tmp = n - 1;while(tmp < m) {tmp = tmp * n + n - 1;count ++;}int times = (tmp / m) * m;do {res = rand_n();for(int i = 0; i < count ;i++)res = res * n + rand_n();} while(res >= times)return res % m;}

 

 

5. 问题升级版 V4!

问题: 如何得到可以产生如下概率的随机数? 0出现1次,1出现2次,2出现3次,n-1出现n次。

分析: 我们注意到有如下规律:n - 1 = (n - 1) + 0 = (n - 2) + 1 = (n - 3) + 2 = ... = 2 + (n - 3) = 1 + (n - 2) = 0 + (n - 1)

可以发现,满足a + b = n - i的(a, b)数对的个数为n - i + 1个。所以我们得到如下代码:

 

int Rand(int n) {while(1) {int tmp1 = rand() % n;int tmp2 = rand() % n;if(tmp1 + tmp2 < n) {return tmp1 + tmp2;}}}

 

 

二. 随机数 范围扩展。

已知有个rand7()的函数,返回1到7随机自然数,让利用这个rand7()构造rand10() 随机1~10。

分析:要保证rand10()在整数1-10的均匀分布,可以构造一个1-10*n的均匀分布的随机整数区间(n为任何正整数)。假设x是这个1-10*n区间上的一个随机整数,那么x%10+1就是均匀分布在1-10区间上的整数。由于(rand7()-1)*7+rand7()可以构造出均匀分布在1-49的随机数(原因见下面的说明),可以将41~49这样的随机数剔除掉,得到的数1-40仍然是均匀分布在1-40的,这是因为每个数都可以看成一个独立事件。
下面说明为什么(rand7()-1)*7+rand7()可以构造出均匀分布在1-49的随机数:
首先rand7()-1得到一个离散整数集合{0,1,2,3,4,5,6},其中每个整数的出现概率都是1/7。那么(rand7()-1)*7得到一个离散整数集合A={0,7,14,21,28,35,42},其中每个整数的出现概率也都是1/7。而rand7()得到的集合B={1,2,3,4,5,6,7}中每个整数出现的概率也是1/7。显然集合A和B中任何两个元素组合可以与1-49之间的一个整数一一对应,也就是说1-49之间的任何一个数,可以唯一确定A和B中两个元素的一种组合方式,反过来也成立。由于A和B中元素可以看成是独立事件,根据独立事件的概率公式P(AB)=P(A)P(B),得到每个组合的概率是1/7*1/7=1/49。因此(rand7()-1)*7+rand7()生成的整数均匀分布在1-49之间,每个数的概率都是1/49。
程序:

 

1 int rand_10() 2 { 3 int x = 0; 4 do 5 { 6 x = 7 * (rand7() - 1) + rand7(); 7 }while(x > 40); 8 return x % 10 + 1; 9 }

 

 

注:由朋友问为什么用while(x>40)而不用while(x>10)呢?原因是如果用while(x>10)则有40/49的概率需要循环while,很有可能死循环了。

问题描述
已知random3()这个随机数产生器生成[1, 3]范围的随机数,请用random3()构造random5()函数,生成[1, 5]的随机数?
问题分析
如何从[1-3]范围的数构造更大范围的数呢?同时满足这个更大范围的数出现概率是相同的,可以想到的运算包括两种:加法和乘法
考虑下面的表达式:
3 * (random3() – 1) + random3();
可以计算得到上述表达式的范围是[1, 9] 而且数的出现概率是相同的,即1/9
下面考虑如何从[1, 9]范围的数生成[1, 5]的数呢?
可以想到的方法就是 rejection sampling 方法,即生成[1, 9]的随机数,如果数的范围不在[1, 5]内,则重新取样
解决方法

 

1 int random5() 2 { 3 int val = 0; 4 do 5 { 6 val = 3 * (random3() - 1) + random3(); 7 }while(val > 5); 8 return val; 9 }

 

归纳总结
将这个问题进一步抽象,已知random_m()随机数生成器的范围是[1, m] 求random_n()生成[1, n]范围的函数,m < n && n <= m *m
一般解法:

 

int random_n() { int val = 0; int t; //t为n的最大倍数,且满足t
t); return val; }

 

转载于:https://www.cnblogs.com/bloomingFlower/p/9563455.html

你可能感兴趣的文章
eclipse编辑器生命周期事件监听
查看>>
Python WOL/WakeOnLan/网络唤醒数据包发送工具
查看>>
sizeof(long)
查看>>
pxe网络启动和GHOST网克
查看>>
2.5-saltstack配置apache
查看>>
django数据库中的时间格式与页面渲染出来的时间格式不一致的处理
查看>>
Python学习笔记
查看>>
java String
查看>>
renhook的使用
查看>>
DOCKER windows 7 详细安装教程
查看>>
养眼美女绿色壁纸
查看>>
U盘启动盘制作工具箱 v1.0
查看>>
增强myEclipse的提示功能
查看>>
Zabbix汉化方法
查看>>
Java I/O系统基础知识
查看>>
Java多线程设计模式(2)生产者与消费者模式
查看>>
对象并不一定都是在堆上分配内存的
查看>>
刘宇凡:罗永浩的锤子情怀只能拿去喂狗
查看>>
php晚了8小时 PHP5中的时间相差8小时的解决办法
查看>>
JS(JavaScript)的初了解7(更新中···)
查看>>