概率学的创立：Chevalier de Méré问题

2008 年 1 月 9 日 / 16 条评论

在1717年，法国流行这样一个赌博游戏：连续抛掷一个骰子四次，赌是否会出现至少一个1点。经过试验，赌徒Chevalier de Méré发现至少出现一个1点比不出现的几率似乎要稍微大一些。他总是赌“会出现”，每次算下来他总是赢。在这个赌博游戏的一个“加强版”中，赌徒们需要猜测，连续抛掷两个骰子24次，是否会出现至少一对1点。Chevalier de Méré想，两个骰子同时掷出1点的几率显然是单个骰子掷出1点的几率的1/6，为了补偿几率的减小则必须要抛掷骰子24次。因此，两个赌博游戏换汤不换药，赌“出现”获胜的几率应该是一样的。但奇怪的是，他每次都赌会出现一对1点，结果几乎每次的最终结果都是输。他感到百思不得其解，于是向数学家Pascal寻求一个合理的解释。Pascal与大数学家Fermat用信件进行了交流，最终提出了概率问题的若干原理，创立了概率学。
我们可以简单算一下，虽然直观感觉两个问题的概率应该相等，但实际上前者发生的概率大于0.5，后者发生的概率小于0.5，虽然两者相差并不多。

问题1：连续抛掷一个骰子4次，至少出现一个1点的概率是多少？
解答：在所有6^4种可能的情况中，一个1点都没有的情况有5^4种，因此至少出现一个1点的概率是(6^4-5^4)/6^4≈0.5177

问题2：连续抛掷两个骰子24次，至少出现一对1点的概率是多少？
解答：在所有36^24种可能的情况中，一对1点都没有的情况有35^24种，因此至少出现一对1点的概率是(36^24-35^24)/36^24≈0.4914

谁能用一句话解释清楚，为什么赌徒Chevalier de Méré的直觉是错误的？不用Ctrl+A了，这次没有藏啥东西。

参考资料：http://www.cut-the-knot.org/Probability/ChevalierDeMere.shtml

KMP算法与一个经典概率问题

2007 年 11 月 28 日 / 22 条评论

考虑一个事件，它有两种概率均等的结果。比如掷硬币，出现正面和反面的机会是相等的。现在我们希望知道，如果我不断抛掷硬币，需要多长时间才能得到一个特定的序列。

序列一：反面、正面、反面
序列二：反面、正面、正面

首先，我反复抛掷硬币，直到最近的三次抛掷结果形成序列一，然后我记下这次我抛掷了多少次才得到了我要的序列。重复执行这个过程，我可以算出得到序列一平均需要的抛掷次数。同样地，反复抛掷硬币直到序列二产生，它所需要的次数也有一个平均值。你认为这两个平均值哪一个大哪一个小？换句话说，出现序列一平均所需的抛掷次数少还是出现序列二平均需要的次数少？

大多数人会认为，两个序列会以同样快的速度出现，因为在所有“正”和“反”的8种三元组合里，“反正反”和“反正正”各占1/8，其概率是均等的。而事实上，我们将会看到掷出序列二所需的次数更少一些。不妨考虑这样一个问题：在由“正”和“反”构成的n位01序列中，有多少个序列以序列一结尾但之前不曾出现过序列一？有多少个序列以序列二结尾但之前不曾出现过序列二？当n比较小时，两者答案是一样的（例如n=3时符合要求的情况都是唯一的），但到后来n越大时，两者的差距越明显：后者的个数总比前者的个数要多一些。不妨看一看n=6的情况。对于序列一，只有以下5个序列是符合要求的：

反反反反正反
反正正反正反
正正正反正反
正反反反正反
正正反反正反

但对于序列二来说，符合条件的序列就有7个：

反反反反正正
反正反反正正
反反正反正正
正反反反正正
正正反反正正
正正正反正正
正反正反正正

你可以通过计算机编程枚举，计算一下n为其它值的情况。计算结果和刚才也一样：在n位01序列中，以序列二结尾但之前不含序列二的情况不会少于以序列一结尾但之前不含序列一的情况。这说明，抛掷第n次硬币后恰好出现了序列二，其概率不会小于恰好出现序列一的概率。显然，当n渐渐增大时，这个概率应该呈下降趋势；同时，随着n的增长，两个序列各自出现的概率由相等开始慢慢拉开差距，第n次抛掷产生序列二的概率下降得要缓慢一些，或者说更多的情况集中发生在n更小的时候。因此总的来说，出现序列二所需要的抛掷硬币次数的期望值更小。
虽然我们通过一系列的观察验证了这个结论，并且我们也相信这个结论是正确的（虽然没有严格的证明），但我们仍然不是很接受这个结论。这种情况是有悖于我们的直觉的，它与我们的生活经验不相符合。此刻，我们迫切需要一个解释，来说明这种出人意料的反常现象产生的原因。

    如果不亲自做几次试验的话，你很难体会到这种微妙的差距。考虑整个游戏的实际过程，“反正正”序列显然会出现得更早一些。假如某一次我们得到了序列“反正”。如果我们需要的是“反正反”序列，那么下一次抛掷结果为反面将结束本轮的抛掷，而下一次是正面则前功尽弃，你必须再次从零开始。如果我们需要的是“反正正”序列，那么下一次抛掷结果为正面将结束本轮的抛掷，而下一次是反面的话我至少不会惨到一切归零，这相当于我已经有了一个反面作为新的开头，只需再来两个正面即可。这样看的话，提前掷出“反正正”的可能性更大一些。
    反复体会上面的想法，了解KMP算法的网友会恍然大悟：这就是KMP算法的基本思路！考虑这样一个问题：我们在当前字串中寻找子串“反正正”第一次出现的位置。假如当前已经能匹配模式串的前两个字“反正”，主串中的下一个字是“正”则匹配成功，主串的下一个字是“反”则将使模式串的当前匹配位置退到第一个字。考虑一个更复杂的例子：我们希望在主串中寻找子串abbaba，现在已经在主串中找到了abbab。如果主串下一个字符是a，则成功匹配；如果主串下一个字符是b，则模式串最多能匹配到的位置退到了第三个字符，我只需要从abb开始继续匹配，而不必一切从头再来。
    我们可以用KMP算法完美地解决上面的问题。首先预处理出一个数组c，c[i,0]表示模式串匹配到了第i个字符，主串下一个字符为0（反）时，模式串的匹配位置将退到哪里；同样地，c[i,1]表示模式串匹配到了第i个字符，主串下一个字符为1（正）时，新的模式串匹配位置在什么地方。设f[i,j]表示第i次抛掷硬币后恰好匹配到模式串第j位有多少种情况，则f[i,j]=Σf(i-1,k) + Σf(i-1,l)，其中k满足c[k,0]=j，l满足c[l,1]=j。将f[i,j]除以2的i次方，我们就得到了相应的概率值。或者更直接地，设P[i,j]表示第i次抛掷硬币后，最远能匹配到的模式串位置是第j位的概率，则P[i,j]=Σ( P(i-1,k)/2 ) + Σ( P(i-1,l)/2 )。注意，我们还应该添加一种特殊的概率值P[i,*]，它表示在主串第i个字符以前已经成功匹配过的概率，这样的话下表中每一列的和才能为1。

    来看一看程序的输出结果：
Pattern 1: s[]="aba"
主串位置       1        2       3       4       5       6       7       8       9      10
匹配到s[0]  0.5000  0.2500  0.2500  0.2500  0.2188  0.1875  0.1641  0.1445  0.1270  0.1113
匹配到s[1]  0.5000  0.5000  0.3750  0.3125  0.2813  0.2500  0.2188  0.1914  0.1680  0.1475
匹配到s[2]  0.0000  0.2500  0.2500  0.1875  0.1563  0.1406  0.1250  0.1094  0.0957  0.0840
匹配到s[3]  0.0000  0.0000  0.1250  0.1250  0.0938  0.0781  0.0703  0.0625  0.0547  0.0479
已找到匹配  0.0000  0.0000  0.0000  0.1250  0.2500  0.3438  0.4219  0.4922  0.5547  0.6094

Pattern 2: s[]="abb"
主串位置       1        2       3       4       5       6       7       8       9      10
匹配到s[0]  0.5000  0.2500  0.1250  0.0625  0.0313  0.0156  0.0078  0.
0039  0.0020  0.0010
匹配到s[1]  0.5000  0.5000  0.5000  0.4375  0.3750  0.3125  0.2578  0.2109  0.1719  0.1396
匹配到s[2]  0.0000  0.2500  0.2500  0.2500  0.2188  0.1875  0.1563  0.1289  0.1055  0.0859
匹配到s[3]  0.0000  0.0000  0.1250  0.1250  0.1250  0.1094  0.0938  0.0781  0.0645  0.0527
已找到匹配  0.0000  0.0000  0.0000  0.1250  0.2500  0.3750  0.4844  0.5781  0.6563  0.7207

这下我们可以清楚地看到，序列二提前出现的概率要大得多。注意到，根据我们的概率定义，表格中每一列的数字之和都是1。同时，倒数第二行的数字之和（有无穷多项）也应该为1，因为最后一行的概率就是倒数第二行的概率值累加的结果，而根据最后一行概率的定义，主串无穷长时已找到匹配的概率应该为1。因此，我们也可以把倒数第二行看作是模式串在主串第i个位置首次匹配成功的概率。我们可以根据这一结果近似地计算出抛掷次数的期望值。

Matrix67原创
转贴请注明出处

趣题：丢失的机票一个有趣的概率问题

2007 年 11 月 27 日 / 17 条评论

一架客机上有100个座位，100个人排队依次登机。第一个乘客把机票搞丢了，但他仍被允许登机。由于他不知道他的座位在哪儿，他就随机选了一个座位坐下。以后每一个乘客登机时，如果他的座位是空着的，那么就在他的座位坐下；否则，他就随机选一个仍然空着的座位坐下。请问，最后一个人登机时发现唯一剩下的空位正好就是他的，其概率是多少？

当最后一个乘客登机时，最后一个空位要么就是他的，要么就是第一个乘客的。由于所有人选择座位时都是随机选择的，这两个位置的“地位”相等，它们所面对的“命运”是相同的，不存在哪个概率大哪个概率小的问题。因此，它们成为最后一个空位的概率是均等的。也就是说，最后一个人发现剩下的空位正好是他的，其概率为50%。

来源：cut-the-knot
不知不觉地，这已经是第400篇日志了

Google面试题中的两道趣题

2007 年 10 月 22 日 / 44 条评论

看看下面两道题，它的解答非常简单，即使没学过信息学的人也可以想到答案。你能在多短的时间内想出问题的算法来？一小时？一分钟？一秒钟？

1. 给你一个长度为N的链表。N很大，但你不知道N有多大。你的任务是从这N个元素中随机取出k个元素。你只能遍历这个链表一次。你的算法必须保证取出的元素恰好有k个，且它们是完全随机的（出现概率均等）。

2. 给你一个数组A[1..n]，请你在O(n)的时间里构造一个新的数组B[1..n]，使得B[i]=A[1]*A[2]*…*A[n]/A[i]。你不能使用除法运算。

Solution:
1. 遍历链表，给每个元素赋一个0到1之间的随机数作为权重（像Treap一样），最后取出权重最大的k个元素。你可以用一个堆来维护当前最大的k个数。
2. 从前往后扫一遍，然后从后往前再扫一遍。也就是说，线性时间构造两个新数组，P[i]=A[1]*A[2]*…*A[i]，Q[i]=A[n]*A[n-1]*…*A[i]。于是，B[i]=P[i-1]*Q[i+1]。

突然想到，给别人(MM?)介绍信息学时，用这两道题当例子挺合适的。

趣题：非常具有启发性的概率问题

2007 年 8 月 1 日 / 30 条评论

问题：桌子上有10件东西。你随机取走几件，请问你手上的物体个数是奇数的可能性大还是偶数的可能性大？所谓“随机取物”，是说每一个物体被取走的概率都是1/2。因此，你有可能取走所有的物体，也有可能一样都没拿。

继续看下去之前，请你先思考一下。

把桌子上的物品个数换成5个，你的答案又是多少？

继续看下去之前，请你先思考一下。

显然，当桌子上物品数为5时，取走物品的个数是奇是偶概率一样，因为取0件和取5件的概率是相同的，取1件和取4件的概率也是相同的，取2件和取3件的概率还是相同的，最终算下来取奇数件和取偶数件的概率相同。现在再回过头去想想物品数为10的情况，仍然坚持你原来的答案吗？或者有什么新的想法？

继续看下去之前，请你先思考一下。

当桌子上有10件物品时，取走物品的个数是奇是偶概率仍然一样。把这10件物品平分成两堆，左边5件，右边5件，那么你会发现：左边和右边所取物品的个数有四种概率相等的组合：奇偶、偶奇、奇奇、偶偶。前两种情况下总的数目是奇数，后两种情况下总的数目是偶数。奇数和偶数的概率仍然相同。