tianrong1945的个人博客分享 http://blog.sciencenet.cn/u/tianrong1945

博文

麦穗问题和博士相亲 精选

已有 12987 次阅读 2017-10-13 07:06 |个人分类:系列科普|系统分类:科研笔记

《趣谈概率和统计》之9

苏格拉底和他的学生柏拉图都是古希腊著名的哲学家。一天,柏拉图问苏格拉底:什么是爱情?苏格拉底叫他到麦田走一趟,目标是要摘回一棵最大最好的麦穗,但只可以摘一次,并且不许回头,路径不能重复。柏拉图以为很容易,但最后却空手而归,原因是他在途中看到很不错的,却总希望后面有更好的,使得最终错失所有的良机。苏格拉底告诉他:这就是爱情!

之后又有一天,柏拉图问苏格拉底:什么是婚姻?苏格拉底叫他到树林走一次,争取带回一根最好的树材,照样只采一次不许回头。最后柏拉图拖了一棵中等材质的树枝回来,原因是因为他接受了上次的教训,走了半途之后看到“差不多”的树就做决定了!苏格拉底说:这就是婚姻。

两位哲学家用麦穗问题来形象地比喻爱情婚姻之不同:前者是错过了的美好,后者是人生旅途中权衡之后某个时候的决择。人文学者及公众都为这段颇富哲理的名人小故事津津乐道。数学家们却从完全不同的、概率及统计的角度来解读它。

麦穗问题虽然很通俗,但却与“随机过程”有关。每棵麦穗的大小都可以看作是随机的,因此,当柏拉图在麦田中走一圈时,碰到一个又一个排成序列的随机变量,这不就是一个随机过程吗?

加以数学抽象之后的麦穗问题,等效于概率及博弈论中著名的秘书问题1,它还有多种变换版本:未婚夫问题、止步策略、苏丹嫁妆问题等等。下面我们用“傻博士相亲”的故事来叙述它,并介绍如何将微积分的基本概念用于分析随机过程。

且说几年前留学人员中有一位外号“傻博士”的学人,精通数学,小有成就,唯有一老大难问题尚未解决:已经将近40岁还没有交上女朋友。于是,那年他奉母命回国相亲,据说半个月之内来了100名佳丽应召。后来,这位傻博士经过严格的数学论证,采用了一种他认为的“最佳策略”,终于百里挑一,赢得美人归,如今已是儿女一双,其乐融融,在硅谷传为佳话。

这里还需加上一段话,描述傻博士母亲设定的条件。人们常说,有其父必有其子。对傻博士之母则用得上“有其子必有其母”,母亲要求他在这15天之内,要对这100位佳丽一个一个地面试,每位佳丽只能见一次面,面试一个佳丽之后立即给出“不喜欢”或“喜欢”的答案。如果“不喜欢”,则以后再无机会面试该位女子,如果答案是“喜欢”,则意味着博士选中了这位女子,相亲过程便到此结束。

看到这儿,你也许已经能领会到这个“博士相亲”与“麦穗问题”本质上是一致的了。那么,对于母亲这种“见好就收,一锤定音”的要求,傻博士的“最佳策略”又是怎么样的呢?

既然是“最佳”,那应该用得上微积分中的最优化、求极值的技巧吧。果然是如此,我们首先看看,傻博士是如何建造这个问题的数学模型的。

这看起来是个概率的问题。假设,我们想象,按照傻博士对女孩的标准,将100个女孩作了一个排行榜,从1100编上号,“#1”是最好的,然后,“#2”、“#3”……。当然,傻博士并不知道当时每一次面试的女孩是#多少。这些号码随机地分布在傻博士安排的另一个面试序列(123、…rin)中,见图1。傻博士的目的就是要寻找一种策略,使得这“一锤定音”定在“#1”的几率最高。

设想一下,傻博士可以有好多种方法做这件事。比如说,他可以想得简单一点,预先随意认定一个数字r(比如将r固定为等于20),当他面试到第r个人的时候,就定下来算了。这时候,因为r100中挑出来的任意一个,所以,这个人是“#1”的几率应该是1/100。这种简单策略的几率很小,傻博士觉得太吃亏。比如说,当他面试到第20个人时,如果看到的是个丑八怪(或者疯女子)也就这么定下来吗?显然这不是一个好办法。那么,将上面的方法做点修正吧:仍然选择一个数字(比如r=20),但这次的策略是:他从第20个人开始认真考察,将后面的面试者与前面面试过的所有人加以比较,比如说,如果傻博士觉得这第20个面试者比前面19个人都好,那便可以“见好就收”,否则,他将继续面试第21个,将她与前面20人相比较;如果不如前面的,继续面试第22个,将她与前面21人相比较;……如此继续下去,直到面试到比前面的面试者都要更好的人为止。

1:傻博士相亲的最佳策略

根据图1,总结一下傻博士策略的基本思想:对开始的(r-1)个面试者,答复都是“不喜欢”,等于是“忽略”掉这些佳丽,只是和她们谈谈玩玩观察了解一下而已,直到第r个人开始,才认真考虑和比较,如果从r开始面试到第i个人的时候,觉得这是一个比前面的人都要更中意的人,便决定说“喜欢”,从而停止这场游戏。图1中还标出了一个“临时最佳者”,这和实际上隐藏着的排行榜中的“#1”是不同的。“临时最佳者”指的是傻博士一个一个面试之后到达某个时刻所看到的最好的佳丽,是随着傻博士已经面试过的人数的增加而变化的。

这儿便有了一个问题:对100个人而言,到底前面应该“忽略”掉多少个人,才是最佳的呢?也就是说,对n个面试者,r应该等于多大,才能使得最终被选定的那个面试者,是“#1”的几率最大?r太小了当然不好,比如说,如果令r=2,那就是说,只忽略第一个,如果第二个比第一个好的话,就定下了第二个,当然也可能继续下去,但很有可能使你的决定下得太快了,似乎还没有真正开始面试,过程就结束了!r太大显然也不行,比如说,令r=99,那就是说,从第99个人才开始比较。如此办法,因为忽略的人数太多,当然,“#1被忽略掉的可能性也非常大,面试了这么多的人,将傻博士累得半死,却不得好报,选出#1的几率只是大约为2/100而已。

也许,应该忽略掉一半,从中点开始考察?也许,这个数k符合黄金分割原则:0.618?也许与另外某个有名的数学常数p e有关?然而,这都是一些缺乏论据的主观猜测,傻博士是科学家,还是让数学来说话吧。

我们首先粗糙地考察一下,如果使用这种方法的话,对某个给定的r,应该如何估算最后选中#1的几率P(r)。对于给定的r,忽略了前面的r-1个佳丽之后,从第r个到第n个佳丽都有被选中的可能性。因此,在图1下方的公式中,这个总概率P(r)被表示成所有的P(i)之和。这儿的irn逐一变化,而P(i)则是选中第i个佳丽的可能性(概率)乘以这个佳丽是#1的可能性。

选中第i个佳丽的可能性是多少?取决于第i个佳丽被选中的条件,那应该是当且仅当第i个佳丽比前面i-1个都要更好,而且前面的人尚未被选中的情形下才会发生。也可以说,第i个佳丽被选中,当且仅当第i个佳丽比之前的“临时最佳者”更好,并且这个临时最佳者是在最开始被忽略的r-1个佳丽之中。因为如果这个临时最佳者是在从ri之间的话,她面试后就应该被选中了,然后就停止了“相亲过程”,第i个佳丽不会被面试。

此外,这第i个佳丽是#1的可能性是多少呢?实际上,按照等概率原理,每个佳丽是#1的可能性是一样的,都是1/n。因此根据上面的分析,我们便得到了图1所示的选中#1的概率公式。

从公式可知,选中#1的概率是傻博士策略中开始认真考虑的那个点r的函数。读者不妨试试在公式中代入不同的n及不同r的数值,可以得到相应情况下的Pn(r)。比如说,我们前面所举的当n=100时候的两种情形:P100(2)大约等于6/100P100(99)大约等于2/100

下面问题就是要解决:r取什么数值,才能使得Pn (r)最大?如果我们按照图1的公式计算出当n=100时,不同r所对应的概率数值,比如令r分别为281222……等等,将计算结果画在Pn (r)图上,如图2a所示。我们可以将这些离散点连接起来成为一条连续曲线,然后估计出最大值出现在哪一个点r。这是求得P(r)最大值的一种实验方法。

2:相亲问题中n=100时的概率曲线

然而,我们更感兴趣从理论上分析更为一般的问题。那就要用到微积分了。如果能给随机变量建立一套类似于普通微积分的理论,让我们能够像对普通的变量做微积分那样对随机变量做微积分。

在普通微积分里面,最基本的理论基础是“收敛”和“极限”的概念,所有其他的概念都是基于这两个基本概念的。对于随机过程的微积分,在数学家们建立了基于实分析和测度论的概率论体系之后,就可以像当初发展普通微积分那样先建立“收敛”和“极限”这两个概念。与普通数学分析不同的是,现在我们打交道的是随机变量,比以前的普通的变量要复杂得多,相应建立起来的“收敛”和“极限”的概念也要复杂得多。

在随机微积分中的积分变量是随机过程(比如说无规行走)。无规行走是时间的一个函数,但是却有一个特殊的性质:处处连续但是处处不可导。正是这个特殊的性质使得随机微积分与普通微积分大不相同。

实际上的随机微积分一般都既牵涉到普通变量时间t,又牵涉到随机变量W(t)。所以,进行随机微积分时,如果碰到跟t有关的部分就用普通微积分的法则,而碰到跟W(t)有关的部分时就使用随机微积分的法则。

首先,我们想一个办法将Pn(r)变成r的连续函数,因为只有对连续函数,才能应用微积分。为了达到这个目的,我们分别用连续变量x=r/nt=i/n来替代原来公式中的离散变量ri。此外,最好使得研究的问题与n无关。因此,我们考虑n比较大的情形。n趋近于无穷大时,1/n是无穷小量,可用微分量dt表示,而公式中的求和则用积分代替。如此一来,图1P(r)的表达式对应于连续函数P(x)

                                                                               1

2b画的是连续函数P(x)=- x ln x)的曲线。这儿的logln都是表示自然对数,即以欧拉常数e为基底的对数函数。图中可见,函数在位于x等于0.4左右的地方,有一个极大值。

从微积分学的角度看,极大值所在的点,是函数的导数为零的点,函数在这个点具有水平的切线。但是导数为零,不一定对应的都是函数值为极大,而是有三种不同的情况:极大、极小、驻点。用该点二阶导数的符号,可以区别这三种情形,见图3

3:函数的极值处导数为零

所以,令公式(1)对x的导数为零,便能得到函数的极值点:x=1/e = 0.36。这个点概率函数P(x)的值也等于1/e,大约为0.36

将上面的数值用于傻博士的相亲问题。当n=100的时候,得到r=36。也就是说,在傻博士的面试过程中,他首先应该忽略前面的35位佳丽。然后,从第36位面试者开始,便要开始认真比较啦,只要看见第一个优于前面所有人的面试者,便选定她!利用这样的策略,傻博士选到#1的可能性是百分之三十六,大于三分之一。这个几率比起前面所举的几种情况的概率:1/1006/100,等等,要大多了。

相亲问题的策略还可以因不同情况有不同的修改。比如说,也许傻博士会换另一种思路考虑这个问题。他想,为什么一定只考虑#1的概率呢?实际上,#2也不一定比#1差多少啊。于是,他便将他原来的方法进行了一点点修改。

他一开始的策略和原来一样,首先忽略掉r-1个应试者。然后从第r个应试者开始考察、比较、挑选,等候出现比之前应试者都好的临时第一名。不过,在第r个人之后,如果这个临时第一名久久不露面的话,傻博士便设置了另外一个数字s,从第s个应试者开始,既考虑#1,也考虑#2

我们仍然可以使用与选择第一佳丽的策略时所用的类似的分析方法,首先推导出用此策略选出#1#2的离散形式的概率P(r,s)2。这时候的概率是两个变量rs的函数。然后,也利用之前的方法,将这个概率函数写成一个两个变量的连续函数。为此,我们假设从离散变量rs到连续变量xy的变换公式为:

                                                                                  2


然后,考虑n趋近于无穷大的情形,可以得到相应的连续概率函数为:

公式(3)是一个两个变量的函数,其函数随xy的变化可用一个3维空间中的2维曲面表示,如图4所示。这个函数的极值可以令P(x,y)xy的偏导数为0,见公式(4)。解出上面的方程便能得到这种新策略下相亲问题的解:当x= 0.347y= 0.667时,概率函数P(x,y)有极大值,等于0.574

42维概率分布函数

将上面的数值应用到傻博士相亲的具体情况,即n=100时,可以得到r=35s=67。以上的rs是四舍五入的结果,因为它们必须是整数。因此,傻博士如果采取这种“选择#1#2”的策略的话,他成功的几率大约是百分之五十七,比“选择#1”的成功的几率(36/100)又高出了许多。这个结果充分体现了数学的威力。

参考文献:

1Freeman,P.R. (1983). "The secretary problem and its extensions: Areview".[J],  InternationalStatistical Review / Revue Internationale de Statistique. 51 (2): 189206.

2S. M.Gusein-Zade, The problem of choice and the optimal stopping rule for asequence of random trials,  [J],   Teor. Veroyatnost. i Primenen., 11:3 (1966),534537

本文同步发表在“知识分子”上:《趣谈概率和统计》之9。




http://blog.sciencenet.cn/blog-677221-1080559.html

上一篇:量子迷雾:都是波函数惹的祸!
收藏 分享 举报

19 鲍海飞 王文磊 史晓雷 郭红建 侯勤福 文克玲 邵明飞 杨涛只 武夷山 王振鹏 张江敏 张海权 刘全慧 吴炬 杨波 郭景涛 吕洪波 袁贤讯 emberash

该博文允许注册用户评论 请点击登录 评论 (7 个评论)

数据加载中...

Archiver|手机版|科学网 ( 京ICP备14006957 )

GMT+8, 2017-12-12 03:22

Powered by ScienceNet.cn

Copyright © 2007-2017 中国科学报社

返回顶部