S2E10. “随机”不是“胡来”(2)-随机数的生成

大老李聊数学(全集)

你可能听说过计算机里的随机数生成算法叫“伪随机数生成算法”,又叫“决定式随机位生成器”(deterministic random bit generator (DRBG)),意思就是它能随机生成1个二级制位,0或者1,而且是50%概率。为什么这种算法都是二进位的生成器?因为平时我们使用均匀分布随机数的场合是最多的,有了均匀分布的随机数,转换成其他分布也是比较简单的。而计算机内部又都是二进位,我有了产生0和1的二进位生成器,如果一个计算机内部浮点数是小数点后有32位,那我就可以产生32位随机二进位,作为0之后的32位小数位,这样我可以产生0-1之间的均匀分布的浮点数,供用户使用。 那为什么又叫“伪随机数生成算法”?为什么加一个“伪”字?很自然就是因为它达不到上一期讲过的“真随机数“的要求,目前计算机架构下也永远不可能有”真“随机数生成算法。但好在实际运用中我们不需要那么高的要求,在实际使用中,我们只要保证根据相当长历史随机数,你无法用当代主流的计算能力,在相当长的时间内,对我之后随机数的猜测的成功或失败概率,与½之间,无法产生任何“显著”的区别,或者用一个术语,就是差别是“可忽略的”(neglectable),就是你猜我随机数的成功失败概率与瞎猜之间的区别是可忽略的,那我就是很放心的。 线性同余法Python代码片段(作者: John D. Cook): for _ in range(N): z = a*z % m # LCG bit_string += format(z, formatstr) 岩浆灯: 公众号订阅,微信搜索:dalaoli_shuxue

18分钟
45
7年前

S2E09. 随机”不是“胡来”-随机数的检验

大老李聊数学(全集)

如果我想让你生成一串0和1的数字序列,而且符合所谓0-1二项分布,0和1的概率各50%,你会怎么做?当然,这很简单,你可以拿一枚硬币不停的丢,看到正面写个0,背面写个1。当然,也会有想偷懒的朋友会说,我就直接瞎写就可以了,只要我0和1写的总数差不多就可以了。现在问题,如果我给你两个0-1的序列,其中一个是某人用丢硬币的方法产生的,另一个是某人“随便”手写产生的,请问你有办法鉴别出来这两个序列哪个是丢硬币产生的,哪个是“手写”产生的? 但数学里,特别是密码学里,还是给“真”随机数给出了一个定义,比如”真正”的符合1/2对1/2概率的0-1二项分布的随机变量定义就是这样:设想一个游戏,我是给出0-1分布随机数的,你是猜随机数的。我每次会产生一个0或1的随机数,你要去猜。你有几个便利条件,我允许你在猜之前向我要任意多的数量的随机数。也就是说,你可以研究过往随机数的历史,如果你认为这对下一次猜测有用的话。而且你想要多少我就给你多少,这是一个便利条件。另一个便利条件是你有一个无限计算能力的计算机,要多块就多块,也就是你可以尽情的在猜之前利用这台机器机去分析,甚至于我可以先产生一个新的随机数,但不给你去看,你还是尽可以去算。等你觉得算够的时候,你就可以猜0或是1。而所谓“真”随机数就是,这个游戏经过非常多次之后,你能猜对的概率仍然是½,那么我产生的随机数就是所谓“真”0-1二项均匀分布。 微信公众号订阅:搜索"dalaoli_shuxue"。

12分钟
46
7年前
EarsOnMe

加入我们的 Discord

与播客爱好者一起交流

立即加入

扫描微信二维码

添加微信好友,获取更多播客资讯

微信二维码

播放列表

自动播放下一个

播放列表还是空的

去找些喜欢的节目添加进来吧