云风的 BLOG: 不那么随机的随机数列

曾经看过这样一种赌徒的策略：假设在一场赌大小的赌博游戏中，赔率是 1:1 ，而庄家不会出千，开大和开小的概率均等（皆为 50%）。赌徒一开始压一块钱，如果他压错了，那么下一次就压两块，再错继续加倍。一旦压对，赌徒永远可以保证有一块钱的进帐。并且从 1 块钱重新开始。

看起来，这种策略能保证永远包赚不赔。但实际上为什么没有人用这个方案发财呢？

放到现实中，试图采用这个策略去赌博的人，几乎都会赔的倾家荡产（当然只要是赌博，差不多都是这个结局）。不要怪运气，不要怪庄家出千，因为这个策略从一开始就注定了失败。

让我们把赌博游戏换成等价的扔硬币实验。请问，连续掷出 7 次正面的概率有多少？

稍有概率常识的人都可以心算出答案：1/128 ，也就是略小于 1% 。比 D&D 跑团时投出 20 重击要难多了（拜一下骰子大神）。

那么，谁能凭直觉说出，掷 30 次硬币，至少出现一次“连续 7 次正面”的概率有多少？我写了个小程序计算了一下，答案远大于大多数人的直觉，居然达到了 18.3% 这么高。

好了，现在把掷出正面换成压对大小。也就是说，你参加 30 次赌局，出现连续 7 次压对，或连续 7 次压错的概率并不那么的小。而且这个概率还会随着赌局次数增加，逐渐趋近于 1 。

这意味着什么？

如果你只有 128 块的赌本，在 30 次赌局中，输光的可能性居然有 18.3% 这么高。诚然，你可以运气很好，在一开始赢到一些额外的资金。但促进最初的策略所需要的进一步资金是 256 块，在 30 次赌局中是绝对不可能办到的。

赌徒可以增加自己的赌本，让自己可以承受更多的连续失败。但赌本的增加将是指数级上升的，但对提高不至于输光的概率却很有限（线形增加）。只要他在赌场上玩上一通宵，多少钱都能输干净。

赌博最终就是看谁的本钱多，而不是谁的运气更好（骰子大神啊，请不要跟我绝交。谈谈数学而已，莫要当真）。如果你赌本比不过庄家，乘早收手吧。btw, 这话是写给众多转战 A 股的朋友们的。

我想任何一个具有理性思维的人都不会对赌博有太多兴趣。想必我的 blog 的读者中这样的人居多，其实我今天主要是想谈游戏的 :) 。

我们前段开始内测了一个卡牌游戏（注：需要内测帐号的朋友请自己去官方论坛申请，不要找我 :) ）

在测试时，同事在50 张的卡组里放了 25 张生物卡。并认为，在游戏中每次摸新的卡，是生物卡的概率是 50% 。可是在实际游戏中，几乎每局都会发生连续 5 次都摸不到生物卡的情况。

一开始，我们认为系统的伪随机函数生成的伪随机数列不够随机。后来换了一个随机数函数，情况并没有得到改善。

今天我计算了一下，如果是掷硬币实验，连续 21 次中，至少出现 5 次连续正面的概率居然达到了 49.9% 。当次数增加到 30 次后，概率有 71.4% 之高。而我们的卡牌游戏，几乎每局都会有 20 多次摸牌机会，出现连续 5 次摸不到生物卡的概率其实够大了。经常出现这种情况，还真是怪不了伪随机数列的生成算法，或是洗牌函数。

写到这里，还有人不信邪。我掏出了我的 20 面骰。在桌上做起实验。

我们规定，投出 1-10 算小，11-20 算大。一直投下去，直到出现 5 次连续的大、而后游戏结束。最后统计一共投了多少次。在没有进行游戏之前，有人估计可能每玩一局可能会投接近 100 次；可实际结果另他失望（更接近计算结果）。

我们一共做了三组实验，分别在 22 次，24 次，31 次结束了。

如果有朋友想试试，可以用硬币或麻将用的六面骰实验。

所以说，当你在打网络游戏时，如果某天发现某件装备的凋落率，或是合成率远低于官方公布的数字。请不要抱怨自己命不好，也不要怀疑系统作弊。若让程序员们产生一个特定分布的作弊随机数列，又不那么容易被人看出规律（不够随机）出来，难度和成本（CPU 成本）比采用系统的随机数发生器要大的多。比如使用 Niederreiter Sequence 。

最后附一张图片，我随手用一个 C 程序生成的。程序在图片的下方：

#include <stdio.h>
#include <stdlib.h>

int
main()
{
    int i,j;
    int map[128][128];
    memset(map,0,sizeof(map));
    for (i=0;i<1000;i++) {
        map[rand()%128][rand()%128]=1;
    }

    printf("P1\n128 128\n");
    for (i=0;i<128;i++) {
        for (j=0;j<128;j++) {
            printf("%d ",map[i][j]);
        }
        printf("\n");
    }
    return 0;
}

用任何 C 编译器编译运行，再用管道输出到一个 .pbm 图片文件中即可。它生成了 2000 个伪随机数，并作为 1000 个点画在画布上。

我们可以发现，很多点都碰在了一起（一致随机分布往往呈现出的这种集束现象）。这并非随机数产生的不好，而是一种常态而已。

反过来，开发人员真的想讨好玩家，可以做一个更“均匀”的随机数列。让游戏中的各种概率发生更符合“大众的直觉”。那么，考虑使用准随机数列（quasi-random_sequences）。不过要注意，计算量会增加很多。而且这样的数列并不随机，只是讨好玩家而已，跟物理世界中的随机性相差甚远。

在《科学计算导论》的中译版中，把 quasi-random sequences 也翻译作拟随机数列。这里有一篇介绍性质的 paper 可以参考。

Comments

其实最基础的随机算法也为玩家所理解和接受的概率最好采用原始的随机数表好了，只需要定期更新这张随机数表应该对于玩法的表现来说更为稳定，当然这个带来的开销就是内存了。
独立的随机事件应该还是可以接受此方法的。不过需要用到随机数的地方很多，如果都采用一张表又带来了相关性的问题，会使得某些组合的随机事件变得更为奇怪。

Posted by: flyff | (32) May 5, 2008 09:29 AM

k次中连续出现m次正面

k>n*m，n=1，2，3
是否可考虑出现n次连续出现m次正面的情况

Posted by: cowind | (31) April 30, 2008 11:23 AM

您好, 想请教一下， k次连续抛硬币，至少出现m次连续正面的概率，是怎么计算的？想了很久没想出来呵呵。

Posted by: 袭 | (30) April 26, 2008 10:06 AM

每次到这里都能看到好多好东西.
云风的大脑不是一般的大脑呀.
离上次问问题大概有1年了.
我知道您喜欢玩游戏,能看看我的webgame:61.161.125.7/tc
user:333
pass:333
指教一下吗?

Posted by: ot512 | (29) April 25, 2008 09:00 PM

好的伪随机序列，可以在一些简单运算下保持还是较好的分布，取模一般是一种，可以写个程序测试下分布的。

转为浮点，除以RAND_MAX再乘上随机范围，再取整，开销还是加大了很多的。

不过减少连续随机，避免连续随机的干扰，还是应该尽可能做到。

Posted by: Spe | (28) April 24, 2008 02:20 PM

@boyi

读死书是不可以的 :)
我相信以写程序为生的人 90% 都看过 TAOCP, 包括我这个天天写程序的人。

比如这个程序，只取了 2000 个随机数，就是在可接受范围内的。

如果认为不随机（这个程序生成的图片因为这个导致错误的说明了问题），可以写个程序做一下检验。

实际工程应用中，取模比“除以RAND_MAX 然后乘以128”用的多的多。是不是错误的用法要看用在怎样的环境。

解决随机性的问题，往往也不是把取模换成一对乘除法，而是换一个更好的随机数函数。比如将 rand()%128 换成 random()%128 （其实这个问题前面 Felix Wong 已经指出而我也解释过了）

Posted by: Cloud | (27) April 24, 2008 12:11 PM

最后这个程序写得有问题，随机数不是这么用的。不能取模，得除以RAND_MAX 然后乘以128,因为模128实际上是取了低7位，而一个随机数低位是不那么随机的，可以参看TAOCP,Knuth说过这个问题。

Posted by: boyi | (26) April 24, 2008 11:33 AM

这个程序不是很严谨。

正确的做法是为x和y使用不同的random seed，才会“更”随机。

Posted by: Felix Wong
--------------------
人家随手写的,你找到破绽也别说出来,还想破了人家的牛B不成?

Posted by: buffer | (25) April 24, 2008 09:30 AM

@yafare

对，是量子效应。不过具体我也不懂。物理系的人做的。

Posted by: Felix Wong | (24) April 24, 2008 01:12 AM

费了我好大的劲，总算算出来了。

你给出的数字都是正确的。

Posted by: ablmf | (23) April 23, 2008 10:15 PM

真随机数生成？说说看啥原理呢？

用到量子力学了么？

Posted by: yafare | (22) April 23, 2008 10:13 PM

云风的说法是对的。在分母小的情况下，统计结果不会有任何问题。

我是最近在做大量数值的模拟，对这个比较敏感。我最近做的研究涉及至少千万量级的数据，伪随机函数模拟的结果大概有5%的误差。后来结果在实验室找了个真随机数生成设备解决问题。呵呵。

btw，那个好笑的错误我小时候也犯过…大概是初一刚会用c的时候吧。hoho

Posted by: Felix Wong | (21) April 23, 2008 02:00 PM

呵呵，这种事我小时候也干过。

Posted by: dayn9 | (20) April 23, 2008 01:08 PM

楼下的似乎夸大了伪随机数列相继值之间的独立性问题。

用两个相继值取平面点的 x,y 最显著可见的问题是，对所需的随机数精度提高了一倍。在同一随机数产生器下，周期减少了一半。

正如前面我的回复中所提，1000 这个数量级下，影响是微乎其微的。

如正文中程序所呈现的，在 [0,128),[0,128) 平面上一致随机的取一点，等价于在 [0,128*128) 的一维空间上一致随机的取点。程序只是用了多一倍的比特数去取罢了。

既然提到 knuth ，自然应该读过 knuth 的书（btw, 按 knuth 自己的说法 linear congruential算法不是他首创的，他只是在他的书中总结）.

在 knuth 卷2 中，提到的统计校验方法里，谱检验就是一个重要方法。对于 2 维这个很低的维度上，我们应该信任系统提供的随机数做的足够好，足以通过 2 维的谱检验。

真要严格证明好坏的话，可以再写程序检验对比一下。

另外，random 固然可以得到更好的伪随机数列，但并非所有的 C 编译器默认带的标准库中都提供。例如 vc ;) 虽然我的工作都用 gcc 完成，但相信这里的读者中，vc 的用户占了更大的比例。

写到最后，突然想起几个月前公司内部一次 code review 中看到的一段让人哭笑不得的代码。

程序员被人抱怨说他的程序中生成的随机数不够随机。他想到程序库中生成的数列都是用个简单的公式递推的，这样前后邻接的数值岂不是都是相关的。

结果他对随机函数做了改进，每次调用随机数函数时都重新初始化随机种子，只使用数列的第一项。

Posted by: Cloud | (19) April 23, 2008 11:33 AM

哈哈哈，老家有个中学一群数学老师就是用这种策略集体买彩票的

============================

还真是搞笑呢....

Posted by: rotApple | (18) April 23, 2008 11:17 AM

为什么我说不能用同一个伪随机数生成x、y坐标呢？

一般来说，libc库的随机函数生成伪随机数的方法都是根据knuth的linear congruential算法。这个算法是通过一个周期很大的数列取得伪随机数。在同一个周期内，这个数列的数是不重复的。我们遇到重复的随机数，是因为在求随机数的时候有取值范围，所以在运算的时候通过求这个大数除以随机数的最大值的余数获得随机数。

假定这个伪随机数列 {a} 生成 uniformly distributed radom的整数。那么当取的数量 n->inf 的时候，取出的所有伪随机数的集合是整数集。如果这个伪随机数数列 {a} 按n, n+1分到两个数列上，很显然，不能保证这两个数列的数是uniformly random的。也不能保证xy平面上，获得的点是uniformly random的。因此，在严格的场合，这种做法是有问题的。严格的场合中，两个不同的随机函数生成的数列会比较好。

当然，一般的应用用标准库提供的随机数已经不错了。

另外要提出的一点是，随机数一般不推荐用rand。用random会较好。

Posted by: Felix Wong | (17) April 23, 2008 08:59 AM

有趣，头一次知道pbm这种东西

Posted by: nothanks | (16) April 22, 2008 10:25 PM

把上面程序编译，比如生成 a.exe

然后在控制台上输入 a.exe > r.pbm 就可以生成一个 r.pbm 文件了。

很多软件支持 pbm 格式的图片。例如 irfan view

Posted by: Cloud | (15) April 22, 2008 10:20 PM

文中"再用管道输出到一个 .pbm 图片文件中即可"我在网上百度，google了好久也没得出个所以然来，Cloud能不能具体说下怎么做的？

Posted by: adon | (14) April 22, 2008 09:33 PM

事件是互相独立的，在自然随机的情况下，输赢永远是个一半。但问题是现实中的赌场毕竟不是公益事业，搞了几十年，没陪没赚，就落了个验证自然随机的结果^_^
征途有个功勋精彩，有兴趣研究随机事件没钱的可以去哪里转转。。。
说起这个网易最近是不是策划走光了什么东西都在更征途学。。。就说最近的天降祝福活动貌似跟征途前些时间开的福临门没什么区别。而且最近听说经常搞些恶心的事，缺少大企业的大气，给我的直觉就是丁磊也是个土鳖级的“企业家”。。。失望哦

Posted by: liuworld | (13) April 22, 2008 05:41 PM

其实策划希望玩家在一定随机尝试次数后就肯定能获得需要的东西，也无可厚非。

搞个最多多少次可以100%获得，然后整体的概率的数学期望又可以是策划要求的数值的函数也满有意思的，不知道有没有人研究。

Posted by: Spe | (12) April 22, 2008 03:26 PM

“所以说，当你在打网络游戏时，如果某天发现某件装备的凋落率，或是合成率远低于官方公布的数字。请不要抱怨自己命不好，也不要怀疑系统作弊。”

这段太经典了，可策划们不这么认为，还非要程序员改“BUG”，要改成“绝对随机”的生成算法，我们有程序甚至真的用保存以往随机概率的方式生成下一步的概率，结果一塌糊涂

Posted by: Jean | (11) April 22, 2008 11:49 AM

掷 30 次硬币，至少出现一次“连续 7 次正面”的概率有多少

这个命题和

掷 30 次硬币，前7次都是正面概率有多少

是否等价？赌博应该用的是后者吧？

Posted by: nothanks | (10) April 22, 2008 10:43 AM

骰子大神啊，请不要跟我绝交。谈谈数学而已，莫要当真

......不坚定的科学主义者

Posted by: nothanks | (9) April 22, 2008 10:40 AM

所有的赌博中，只有21点才有可能打败庄家，因为其他的游戏每次都是独立事件。

Posted by: 不空 | (8) April 22, 2008 12:49 AM

关于赌博中的数学问题，强烈推荐一本书《数学乐旅》(http://www.bullog.cn/blogs/laoyao/archives/20610.aspx)

Posted by: 不空 | (7) April 22, 2008 12:46 AM

某天发现某件装备的凋落率，或是合成率远低于官方公布的数字。这确实是命不好啊

Posted by: Anonymous | (6) April 21, 2008 11:33 PM

从 0 循环到 2^30 ，统计中间每个数值的2进制形式中有连续 0 的个数大于等于 5 的数字个数。

Posted by: Cloud | (5) April 21, 2008 11:21 PM

”如果是掷硬币实验，连续 21 次中，至少出现 5 次连续正面的概率居然达到了 49.9% 。当次数增加到 30 次后，概率有 71.4% 之高。“

怎么算出来的？我怎么计算的30次只有30%

Posted by: justseesee | (4) April 21, 2008 11:00 PM

Posted by: rainfiel | (3) April 21, 2008 10:46 PM

无所谓的，没什么所谓更随机的。

真要分析的话，系统自带的随机函数的周期性是远大于 2000 的。

换用独立的随机数列的话，结果不会有太多变化。

Posted by: Cloud | (2) April 21, 2008 10:01 PM

Posted by: Felix Wong | (1) April 21, 2008 09:41 PM

云风的 BLOG

思绪来的快去的也快，偶尔会在这里停留

不那么随机的随机数列

TrackBack

Comments

Post a comment