《概率论的趣用》由会员分享，可在线阅读，更多相关《概率论的趣用（8页珍藏版）》请在金锄头文库上搜索。
1、概率论的趣用班级：1033005 姓名：蒋灿 学号：1103300533摘要：概率论与数理统计起源于17世纪，其在自然科学，社会科学，工程技术，军事科学及工农业生产等诸多领域发挥的作用众所周知。本文将介绍概率论的一些不为人知的趣用，包括Google借用马尔科夫链开发的PageRank算法；利用彩票漏洞运用概率论知识进行致富的实例；和利用概率分布函数建立的用于择偶的“拒人问题”。关键词： PageRank算法 彩票漏洞 37% 法则一 Google 的PageRank算法在谷歌诞生之前那段时间，流行的网页排名算法都很类似，它们都使用了一个非常简单的思想：越是重要的网页，访问量就会越大。但是这种排
2、名算法有两个很显著的问题：一是因为只能够抽样统计，所以统计数据不一定准确，而且访问量的波动会比较大，想要得到准确的统计需要大量的时间和人力，还只能维持很短的有效时间；二是访问量并不一定能体现网页的“重要程度”。PageRank 的算法，这种算法的主要思想是：越“重要”的网页，页面上的链接质量也越高，同时越容易被其它“重要”的网页链接。PageRank 求解了这样一个问题：一个人在网络上浏览网页，每看过一个网页之后就会随机点击网页上的链接访问新的网页。如果当前这个人浏览的网页 x 已经确定，那么网页 x 上每个链接被点击的概率也是确定的，可以用向量 Nx 表示。在这种条件下，这个人点击了无限多次
3、链接后，恰好停留在每个网页上的概率分别是多少？在这个模型中，我们用向量 Ri 来表示点击了 i 次链接之后可能停留在每个网页上的概率（ R 0 则为一开始就打开了每个网页的概率，后面我们将证明 R 0 的取值对最终结果没有影响）。我们假设只有3个网站的情况，初始时，点击每个网页概率相同。其中， A 表示每一次点击链接概率的矩阵。 A 的第 i 列第 j 行 A i, j 的含义是，如果当前访问的网页是网页i，那么下一次点击链接跳转到网页 j 的概率为 A i, j 。这样设计矩阵 A 的好处是，通过矩阵 A 和向量 R n-1 相乘，即可得出点击一次链接后每个网页可能的停留概率向量 R n 。
4、例如，令 R 1 = A R 0 ，可以得到点击一次链接后停留在每个网页的概率：之后一直迭代下去，有：对于上面的例子，迭代结果如下图：可以看到，每个网页停留的概率在振荡之后趋于稳定。在这种稳定状态下，我们可以知道，无论如何迭代，都有 R n = R n-1 。这样我们就获得了一个方程：而整个迭代的过程，就是在寻求方程 R = AR 的解。而无论 R 0 是多少，迭代无限多次之后，一定会取得令 R = AR 成立的 R 值。该模型有一个显著的特点，那就是每一次迭代的结果只与前一次有关，与更早的结果完全无关。这种过程又被称为马尔可夫过程或马尔可夫链。马尔可夫过程的数学定义是：如果对于一个随机变量序
5、列 X 0 、 X 1 、 X 2 、， 其中 X n 表示时间 n 的状态及转移概率P，有：即 X n 只受 X n-1 的影响，则此过程成为马尔可夫过程。其中 P( X n+1 | X n ) 称作“一步转移概率”，而两步、三步转移概率则可以通过一步转移概率的积分求得。当状态空间有限时，转移概率可以用用一个矩阵 A 来表示，称作转移矩阵。此时转移概率的积分即为矩阵的幂，k步转移概率可以用 A k 表示，这也是随机行走模型中的情况。而对于一个正的（每个元素都为正的）转移矩阵 A ，可以证明一定有：这就完整解释了为什么 R 0 的取值对最终结果没有影响。二 利用彩票漏洞致富前些天，美国波士顿地
6、区的一种彩票 “Cash WinFal”爆出了一个存在已久的漏洞。让人惊奇的是，一对 73 岁的夫妇已经利用这个漏洞赚了超过600万美元。这个叫做“Cash WinFal”的彩票游戏的基本规则很简单：每注彩票的价格为 2 美元，包含 1 46 中 6 个不重复的正整数。在普通的开奖周期（通常为一个星期）中，中奖情况为：选择 2 个和开奖号码相同的数字，赢 2 美元。选择 3 个和开奖号码相同的数字，赢 5 美元。选择 4 个和开奖号码相同的数字，赢 150 美元。选择 5 个和开奖号码相同的数字，赢 4,000 美元。当选择的 6 个数字和开奖号码完全相同时，则获得头奖（JACKPOT）。头奖
7、是一个滚动的奖池，也就是说，头奖的金额是不固定的，初始金额为 50 万美元。如果某一期没有人中头奖，那么奖金将在下一次开奖时增加，增加的数量和销售额有关，大约是这期销售额的 60%。如果连续数期都没有人能中头奖，经过这几期的积累，头奖（JACKPOT）金额会到达一个很庞大的数字，通常超过 200 万美元。这时候彩票的销售商就会启动一个特殊的开奖周期，这个周期被称作“ROLLDOWN”。ROLLDOWN周期结束后，不管有没有人赢得头奖，头奖的奖金都会重新变为 50 万美元。这个周期有另一个重大的变化，那就是小奖的奖金会相应地变高：选择 2 个和开奖号码相同的数字，奖金仍然是 2 美元。选择 3
8、个和开奖号码相同的数字，赢 50美元。选择 4 个和开奖号码相同的数字，赢 1,500 美元。选择 5 个和开奖号码相同的数字，赢 40,000 美元。当 6 个数字和开奖号码完全相同时，就能获得至少 200 万美元的超级大奖。表面上看，这个规则非常合理和人性化，但就是这样的一个规则，存在一个天大的漏洞，恰巧被那对夫妇发现，从而发了大财。这个漏洞到底在哪里呢？如果除去 ROLLDOWN，这个彩票和我们平时看到的彩票没有任何区别。所以，问题一定出在ROLLDOWN上。ROLLDOWN的特点是：最小的奖金和最大的奖金依然按照普通规则没有变化，但是另外三个奖级的奖金和之前相比翻了 10 倍。我们不妨
9、分别算一下在普通规则和ROLLDOWN规则中中奖金额的期望。对于最小的奖来说，要求奖券上的数字恰好有两个号码和开奖号码相同。如果中了这个奖，说明奖券上有两个号码是 6 个开奖号码之一，且有四个号码是剩余 40 个没有开出的号码之一。此时中奖的概率为：以此类推，我们还可以算出中其它几个等级奖金的概率：而除去这些中奖的情况，不中奖的概率为：设某个普通的开奖周期中JACKPOT的奖金为 100 万美元，此时每张彩票获得奖金的期望为：也就是说，彩票销售商平均每张彩票可以赚到 1.20美元 。但是对于 ROLLDOWN 周期，按头奖为 200 万美元计，每张彩票的奖金期望就是：此时购买彩票的人每张彩票平
10、均可以赚得 2.46 美元！对于每次只买一张或少数几张彩票的彩民，这样的改变其实没有什么影响：购买一张彩票命中 3 个号码或以上的概率实在太低，即使期望上升了，大部分此类彩民依然赢不到奖金。但是对于那些留意到这个规律的“有心人”来说，事情就变得不一样了。他们的做法是，在每个 ROLLDOWN 的周期，一口气购买 10 万美元以上的彩票。这样的购买行为就具有了统计学意义此时可以用每张彩票的期望乘以彩票的数量来近似地表示他们获得的利益： 以 10 万美元计，每个 ROLLDOWN 周期他们平均能够获得 12.3 万美元的奖金。不过要说的是，彩票是一个非常依赖运气的游戏。即使找到了漏洞，这也不是一个
11、稳赚不赔的交易只要不能几乎把所有可能的号码都买光，就依然有赔钱的风险。问题是这个风险有多大呢？我们可以把这对夫妇在每次 ROLLDOWN 周期买的每一张彩票的净利益作为一个随机变量，这样假设他们每次随机地购买 10 万美元的彩票（即 5 万张），就可以获得一系列随机变量 X1、 X2、 、 X50000，它们相互独立且服从同一分布。根据中心极限定理，我们可以知道，它们相加所得的随机变量服从如下的正态分布：经计算可知：这样，我们就能算出赔钱的概率为：所以即使利用了这个漏洞，每次投入10 万美元，仍然有 21.1% 的可能会赔钱。不过一次性购买更多的彩票可以减少赔钱的可能性如果一次购买 100 万
12、张彩票，赔钱的概率就仅剩 0.02%！但是这需要许多的初始资金，而且如此大规模的动作也很容易就被发现，因此这对夫妇选择的 10 万美元应该是比较适当的购买额了，由此推断，他们一定研究了很久，非常仔细地考虑了每个细节。三 “拒人问题”假设根据过去的经验，女生可以确定出今后将会遇到的男生个数，比如说 15 个、30 个或者 50 个。不妨把男生的总人数设为 n。这 n 个男生将会以一个随机的顺序排着队依次前来表白。每次被表白后，女生都只有两种选择：接受这个男生，结束这场“征婚游戏”，和他永远幸福地生活在一起；或者拒绝这个男生，继续考虑下一个表白者。我们不考虑女生脚踏两只船的情况，也不考虑和被拒男生
13、破镜重圆的可能。最后，男人有好有坏，我们不妨假设女生心里会给男生们的优劣排出个名次来。聪明的女生会想到一个好办法：先和前面几个男生玩玩，试试水深；大致摸清了男生们的底细后，再开始认真考虑，和第一个比之前所有人都要好的男生发展关系。从数学模型上说，就是先拒掉前面 k 个人，不管这些人有多好；然后从第 k+1 个人开始，一旦看到比之前所有人都要好的人，就毫不犹豫地选择他。不难看出，k 的取值很讲究，太小了达不到试的效果，太大了又会导致真正可选的余地不多了。这就变成了一个纯数学问题：在男生总数 n 已知的情况下，当 k 等于何值时，按上述策略选中最佳男生的概率最大？对于某个固定的 k，如果最适合的人
14、出现在了第 i 个位置（k i n），要想让他有幸正好被女生选中，就必须得满足前 i-1 个人中的最好的人在前 k 个人里，这有 k/(i-1) 的可能。考虑所有可能的 i，我们便得到了试探前 k 个男生之后能选中最佳男生的总概率 P(k)：用 x 来表示 k/n 的值，并且假设 n 充分大，则上述公式可以写成：对 -x ln x 求导，并令这个导数为 0，可以解出 x 的最优值，它就是欧拉研究的神秘常数的倒数 1/e ！也就是说，如果你预计求爱者有 n 个人，你应该先拒绝掉前 n/e 个人，静候下一个比这些人都好的人。假设你一共会遇到大概 30 个求爱者，就应该拒绝掉前 30/e 30/2.
15、718 11 个求爱者，然后从第 12 个求爱者开始，一旦发现比前面 11 个求爱者都好的人，就果断接受他。由于 1/e 大约等于 37%，因此这条爱情大法也叫做 37% 法则。不过，37% 法则有一个小问题：如果最佳人选本来就在这 37% 的人里面，错过这 37% 的人之后，她就再也碰不上更好的了。但在游戏过程中，她并不知道最佳人选已经被拒，因此她会一直痴痴地等待。也就是说，女生将会有 37% 的概率“失败退场”，或者以被迫选择最后一名求爱者的结局而告终。这个问题由数学家 Merrill M. Flood 在 1949 首次提出，这个问题被他取名为“未婚妻问题”。这个问题的精妙之处在于，在微积分界叱咤风云的自然底数 e，竟也出人意料地出现在了这个看似与它毫不相关的问题中。参考文献：1 谷歌怎么给搜索结果排序 . 果壳网2 彩票漏洞让你快速致富 . 果壳网3 死理性派恋爱法：拒绝掉前面37%的人 . 果壳网
