数据, 术→技巧

选择的艺术:用数学获取最优选择

钱魏Way · · 69 次浏览

生活是所有选择的总和

大到一个国家如何选择合适的领导人和国家战略、一家企业如何选择自己的经营策略和项目方案,小到我们每个人每天选择吃什么、穿什么、用什么,可以说,一切组织和个人的荣耀与衰落,都源自选择与决策的能力,即决策力。人生充满风险、不确定性和偶尔欺诈,导致选择和决策的失败的原因,多半可能是依赖过去的成功经验,忽视重要的信息,进行表面的分析,屈从于外部压力,过于相信运气,或者误释重要数据,等等。

苏格拉底与麦穗问题

在古希腊,有这样一位哲学家,有一天,他带领着一群学生来带了一片麦地。他说到:你们沿着这条道挑选一颗最大的麦穗,但是只许进不许退。这位哲学家就是苏格拉底,而故事的结尾就是他的学生都空手而归。究其原因,每个人都不知道前方的麦穗是否还有更大的,因而就放弃了之前的麦穗,等走到尾时,就只能空手而归。

  • 第一个弟子没走多远,就看到一颗大麦穗,如获至宝地摘下。可是,越往前走,他越发现前面的麦穗远比手中的饱满。他懊恼而归。
  • 第二个弟子吸取前者的教训,每看到一个大麦穗时,他总是收回了自己伸出去的手:更大的麦穗一定在前头。麦田快走完时,两手空空的弟子情知不妙,想采一颗,却又觉得最饱满的已经错过。他失望而归。
  • 第三个弟子很聪明。他用前三分之一的路程去识别怎样的麦穗才是饱满的麦穗,第二个三分之一的路程去比较判断,在最后的三分之一的路程里他采摘了一颗最饱满的麦穗。他自然满意而归。

如果把苏格拉底的三个弟子归类,那么显然第一个是属于“先做了再说”之列。“先做了再说”,省略了思考过程,必然会导致行为的盲目性与无序性,其结果当然“懊恼而归”。第二个当属于“等等再说”之列。“等等再说”,总是在思索、观望这个台阶上停滞不前,“只想未做”必定两手空空,“失望而归”。第三个弟子则是“先想后做”。对事物有了充分的认识以及足够的判断之后,才不慌不忙地出手,他当然能够“满意而归”。

决策就是一次科学的赌博

1949 年,一位名为梅里尔·M. 弗勒德(Merrill M.Flood)的数学家首次提出了在学界赫赫有名的“未婚妻问题”。经过无数次的探讨、推导及演绎后,该问题广为流传的版本,便是著名的“波斯公主选驸马”难题。

波斯公主到了适婚年龄,要选驸马。候选男子 100 名,都是公主没有见过的。100 名候选人以随机顺序,从公主面前逐一经过。每当一名男子从公主面前走过时,公主要么选他为驸马,要么不选。如果选他,其余那些还没有登场的男子就都被遣散回家,选驸马的活动也就此结束。如果不选,当下这名男子离开,也就是淘汰掉此人,下一人登场,公主不可以反悔再重选。规则是,公主必须在这 100 人中选出 1 人做驸马,也就是说,如果前 99 人公主都看不中的话,她必须选择第 100 名男子为驸马,不管他有多么丑陋。

任务是,给公主设计选择方法,让她有最高概率选到百人中最英俊的男子为驸马。

从数学角度,“未婚妻问题”可以用这样的方式解决:首先你应该选择前s位男子组成一个样本空间s,样本空间s里的男子全部无条件放弃,但之后遇到的每一位男子都必须和样本空间里的男子进行比较,只要该男生比样本空间里所有男生都优秀,就选他。

依照这种策略,不管将来遇到多少个男子,你都能以某一较大的固定概率选中白马王子。至于概率具体是多少以及样本空间s应该选多大,需要做个简单的分析:

你选中最优男的概率可以分解为当前男子恰为最优男且同时被你选中的概率,即:

$$P(选中最优男)=P(当前男子为最优男) * P(被你选中|当前男生为最优男)$$

当前男生恰为最优男的概率比较简单,n中选1,就是$\frac{1}{n}$,即$P(当前男生为最优男)=\frac{1}{n}$。

而P(被你选中|当前男生为最优男)就比较复杂,需要分开讨论:

  • 最优男刚好位于样本空间s里,因为样本空间里的男生你已经全部无条件放弃了,所以这种情况你选中最优男的概率为0。
  • 最优男刚好位于样本空间s的下一位,即位于s+1处。这时你100%能选中他,因为我们的策略就是只要遇见优于样本空间s里的人就做出选择。
  • 最优男刚好位于样本空间s的下下一位,即位于s+2处。这时若要100%选中最优男,次优男必须位于样本空间s内(好于次优男的才是最优男)。而此时,次优男恰好位于样本空间是的概率为$\frac{s}{s+1}$(因为最优男在s+2处,所以次优男的位置只能是前面s+1的某处,所以位于样本空间s的概率就是$\frac{s}{s+1}$)。
  • 最优男刚好位于样本空间s的下下下一位,即位于s+3处。这时若要100%选中最优男,次优男必须位于样本空间s内。而此时,次优男恰好位于样本空间是的概率为$\frac{s}{s+2}$(因为最优男在s+3处,所以次优男的位置只能是前面s+2的某处,所以位于样本空间s的概率就是$\frac{s}{s+2}$)。
  • 最优男刚好位于样本空间s的下k位,即位于s+k处。这时若要100%选中最优男,次优男必须位于样本空间s内。而此时,次优男恰好位于样本空间是的概率为$\frac{s}{s+k-1}$
  • 最优男处于最后一位,即末尾的n处。这时若要100%选中最优男,次优男必须位于样本空间s内。而此时,次优男恰好位于样本空间是的概率为$\frac{s}{n-1}$

这样,以上各概率的和即为:

$$P(被你选中|当前男生为最优男)=1+ \frac{s}{s+1} + \frac{s}{s+2} + \frac{s}{s+3} +… + \frac{s}{s+k-1}+ … +\frac{s}{n-1}$$

所以:

$$P(选中最优男)=P(当前男生为最优男) * P(被你选中|当前男生为最优男)  \\ = \frac{1}{n} (1+ \frac{s}{s+1} + \frac{s}{s+2} + \frac{s}{s+3} +… + \frac{s}{s+k-1}+ … +\frac{s}{n-1}) \\ =\frac{s}{n}(1+ \frac{1}{s+1} + \frac{1}{s+2} + \frac{1}{s+3} +… + \frac{1}{s+k-1}+ … +\frac{s}{n-1}) \\= \frac{s}{n}\sum_{r=s}^{n-1}\frac{1}{r} \\= \frac{s}{n}\sum_{r=s}^{n-1}(\frac{n}{r} \cdot \frac{1}{n})$$

设$x=\frac{s}{n}$

则:

$$\frac{s}{n}\sum_{r=s}^{n-1}(\frac{n}{r} \cdot \frac{1}{n})\approx x\int_{x}^{1}\frac{1}{t} \mathrm{d}t=-x\ln x$$

要使 P(选中最优男) 取得最大值,当且仅当在其函数的导数为零处取得。$-x\ln x$求导,并令这个导数为 0,可以解出 x 的最优值为$\frac{1}{e}$。因为$x=\frac{s}{n}$,则$s=nx=\frac{n}{e}$。

将$ =\frac{1}{e}$代入得$P(选中最优男)=-\frac{1}{e}\ ln\frac{1}{e}=\frac{1}{e}$,其中e≈2.71828,所以选中最优男的概率恒为1/e≈37%。

参考链接:

发表评论

您的电子邮箱地址不会被公开。 必填项已用*标注