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

博文

麦穗问题和博士相亲 精选

已有 20896 次阅读 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

上一篇:量子迷雾:都是波函数惹的祸!
下一篇:德国坦克问题-再谈贝叶斯

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

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

数据加载中...

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

GMT+8, 2018-9-19 22:43

Powered by ScienceNet.cn

Copyright © 2007- 中国科学报社

返回顶部