可否在有限步骤内通过函数rand5()得到rand7()?

2013-12-06 22:48:21 +08:00
 suriv520
通过rand5()实现rand7()是一个挺有名的概率学面试题。是这样的:

函数rand5()可以随机产生概率均等的1-5这5个自然数。
要求通过rand5(),实现rand7(),即产生随机分布在1-7区间内的自然数。

大多数解法就是一个思路:把rand5()范围扩大然后映射到1-7这个区间内:
http://www.cnblogs.com/dwdxdy/archive/2012/07/28/2613135.html

但事实上,这些算法在极端情况下,会出现无限循环而得不到结果。

求(证):
有没有一种解法,能在有限的步骤内实现上述要求?
3684 次点击
所在节点    问与答
11 条回复
Mutoo
2013-12-06 23:33:58 +08:00
理论上是收敛的,不会无限循环。可以构造更大的组合使收敛速度加快。也就是用空间换时间。
sNullp
2013-12-07 00:06:28 +08:00
因为只用 1/5 通过加或者乘都无法得出 1/7 ,所以理论上永远存在无限循环。
SoloCompany
2013-12-07 00:27:00 +08:00
连续调用 7 次 rand5() 求和然后除以 5 取整不行么?
9hills
2013-12-07 00:34:31 +08:00
@SoloCompany 取下整就不是随机了,各点不是等概率的
9hills
2013-12-07 00:36:37 +08:00
@SoloCompany 这样最后应该是一个正态分布的概率图
SoloCompany
2013-12-07 00:40:00 +08:00
@9hills 我错了,简单验算一下,实验 n 次的结果数是 5 ^ n 不可能整除 7,可以推断是无法得到真随机的 rnd7(),但非常逼近还是可以的
9hills
2013-12-07 00:41:39 +08:00
@SoloCompany 不考虑取整。。你这个实际概率分布是正态分布啊<_<
SoloCompany
2013-12-07 00:48:20 +08:00
@9hills 我的意思已经不是相加了,是n阶矩阵,然后对结果数分类,由于不能整除7,算法总是会有一个余数存在,不能完全实现 rnd7()
以n=4为例,5^4=625 = 7*89 + 2
可以把625个结果按89个结果分类,落在这些结果中就取对应的值。但剩下2的区间就无法覆盖,就是说有 2/625 的偏差
SoloCompany
2013-12-07 00:56:17 +08:00
基于这个思路可以完善那个递归算法,先根据区间划分,然后进行实验
每次递归如果得到的4个rand5()结果落在 623 个结果内,就可以直接返回结果
如果不幸落在那 2 个结果里面,需要重复实验(也就是递归调用)
可以限制一下递归次数(比如10),如果10次随机数返回都落在那个2里面(这个几率很低了),就直接返回0
suriv520
2013-12-07 21:48:16 +08:00
@SoloCompany 摔!为毛v2ex没有回复提醒……

是的。我凭感觉也认为没有能在确定步骤内的得到结果的算法。或者说,理论上通过一元运算或二元运算,也无法将概率区间一一映射。

但貌似没办法给出严格意义上的证明……
regmach
2013-12-08 04:59:19 +08:00
插一个问题,怎么得到rand3() ?`

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/92136

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX