码农要术：概率起源故事
May 11, 2020
注：本文关于概率的起源和历史，参考了《Games, Gods and Gambling》这本书，很有意思，建议大家都看看。
概率论起源于赌博。
概率雏形
1470年，也就是唐伯虎出生的那一年，有一本拉丁文的诗书《De Vetula》出版。上面有首诗记录了3个骰子和的排列组合结果。
左图为原始印刷，数字的写法和我们现在有些不同。右边可以看出，6种组合情况可以得到10和11，但是排列情况有27种。
140年后，也就是1610年，伽利略发现了木星的卫星。差不多在这个时候，资助伽利略的Tuscany大公请教了伽利略3个骰子和的问题。Tuscany大公是个赌徒，他在赌博时，发现三个骰子点数和为10比点数和为9出现的更频繁一些。他想不明白，按他的思路，有6种方式得到10，分别为631,622,541,532,442,433；同样有6种方式得到9,分别是621,531,522,441,432,333。他觉得这9和10出现的频率不应该有差异。
伽利略指出了大公的错误，三个骰子是不同的，631和613是不同的两种情况。可惜伽利略那个时候只考虑了频次，还没有形成概率的思想。
概率的思想是什么时候形成的呢？大概是1564年左右，这个时候伽利略刚出生。意大利博学家Cardano写了本书《Liber de Ludo Aleae (“Book on Games of Chance”)》，但是这本书直到大概一个世纪后的1663年才出版。伽利略1642年去世，所以也没有机会看到。Cardano据说是达芬奇一个律师朋友的私生子。他是第一个系统的推算概率的人，可以说是创派始祖。
三个骰子和的问题Cardano在《Liber de Ludo Aleae 》的第13章有提到并且解决。
从时间上来看，《De Vetula》其实已经给出了三个骰子和的答案，70年后Cardano也给出了答案，但是140年后的Tuscany公爵还是得请教伽利略，可见古代知识的流通极为困难。
Cardano在《Liber de Ludo Aleae 》第十四章中明确定义了“比例”，如果赌局中有利的所有可能的数目为A，不利情况的数目B，则应该根据A/B的结果来下注。
概率论的诞生
Cardano虽说是概率的创派始祖，但是真正变成概率论这样一门学科的标志性事件是1654年Pascal和Fermat的通信。这一年康熙出生，同年出生的还有一个数学家伯努利，在不久的将来也为概率的发展做出了极大的贡献。
故事的起源是另一个著名的赌徒Antoine Gombaud，但是他更让人熟知的名字是Chevalier de Méré（来自梅尔的骑士），国内大多翻译成德梅尔。德梅尔被一个赌徒分金的问题困扰。赌徒分金问题描述如下：
两个赌徒A和B水平相当，胜率各自50%，约定先赢s局的拿走所有赌注。当A赢了a局，B赢了b局的时候，比赛由于某些原因中断，问这时候符合分配奖金是公平合理的？
假设s=6,a=5,b=3。
这个问题最早是由意大利数学家Paccioli在1494年提出，当时Paccioli给出的答案是a:b这么分，也就是5:3。后续也有很多数学家思考过这个问题，但是按照已发生的事件进行推断。
1537年，Cardano也曾经思考过这个问题，他给出了一个公式。A还剩s-a局就可以获胜，B还剩s-b局可以获胜，两者的分金比率应该为f(s-b):f(s-a)=(s-b)(s-b+1):(s-a)(s-a+1)，也就是6:1。虽然答案错误，而且没搞清楚Cardano是怎么思考的，但是Cardano已经开始考虑用未来剩余的赌局来决策，而不是局限于已发生的事件。
直到1654年德梅尔向Pascal请教，Pascal和Fermat进行书信交流，并且用不同的解法给出了这个问题的正确答案。
Fermat给出了最朴素易懂的解法：如果比赛不终止，那么最多还需要比赛3场就可以分出胜负。可能的结果分别为{AAA,AAB,ABA,ABB, BAA,BAB, BBA, BBB}，所有的结果中，B只有一个结果获胜，也就是连胜三局。所以分金比例应该为7:1。
Pascal用了两种更难的解法，一种是Pascal三角形(杨辉三角)，一种是递推。
Pascal根据该Pascal三角形的性质：第n行第k个数字，等于从n-1件物品中一次取出k件的组合数。认为A在余下3场赢1场的组合数为，赢2场的组合数为，赢1场的组合数为，全输的组合数为，故应按照7:1来分。可以认为是Fermat解法的升级版本，给出了所有组合情况。
递推的解法也非常精彩。Pascal分析了这个问题的一个简化版本，就是s=3，a=2，b=1的情况。假设A和B的赌注一共为64个金币，当2:1比分的情况下，如果第三局A胜利了，那么会得到全部64枚金币，如果A输了，则比分变成2:2，这时候是平局，AB平分奖金。A可以说，不管哪一种情况，我至少会拿32个金币，至于剩余的32个金币，可能归我也可能归你，平分。这样A应该拿32+(64-32)/2=48个金币，B则拿16个金币。
用该思想来考虑s=6,a=5,b=4的情况。和s=3,a=2,b=1的情况类似，A应该拿32+(64-32)/2=48个金币。再考虑s=6,a=5,b=3的情况，如果下一局A胜利，则拿到所有奖金，如果A落败，则问题转化为s=6,a=5,b=4的情况。所以此时A可以说，我至少拿48个硬币，剩余金币平分，则A最终可以拿48+(64-48)/2=56个金币，B只能拿8个金币。和Fermat的7:1结果相同。
在递推解法里，Pascal可能无意之间使用到了期望，尤其是48+(64-48)/2这个式子。换一种说法，假设A赢了后得到x=64金币，输了后得y=48金币，则A应该分到多少金币？按Pascal的式子，应为y+(x-y)/2=(x+y)/2=x*0.5+y*0.5，这其实就是期望。
后来，荷兰数学家Huygens也参与了Pascal和Fermat的讨论，并且在1657年出版了一本书，名字叫《De ratiociniis in ludo aleae (“On Reasoning in Games of Chance”）》，标志着现代概率论的诞生。
这本书是如此的重要，准备单独写一篇来讲一下书中的内容。
Pascal和Fermat通信故事的结局
两位大牛的通信某种意义上也算是一种专利比赛和智力竞赛。信件中双方会强调自己对于新解法的发明权，同时双方也暗自较量，Fermat就问过Pascal关于数论的一些问题，比如为素数。每个比4倍数大1的素数（如5,13,17,29,37…）都是两个平方数之和，等等一系列问题。但是Pascal好像对数论没什么兴趣，再加上体弱多病，和Fermat通信后没多久，就宣布余生皈依上帝。