“波斯公主选驸马”问题的理论分析和数学推导

波斯公主选驸马

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

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

最佳选法是 pass 掉最开始的 100/e 名男子（e = 2.718… 是自然对数，即100/e 约等于 37）。但是记录下这37 名男子中最英俊者。之后鱼贯而来的男子中，出现的第一位英俊程度超越所有前 37人者，即为驸马。如果人都走光了，也没出现这么一位 Mr. Right，那么就只好选择第100位男子。

这个最佳选法，后面有很有意思的数学推导。

正解后面的思考方法

数学的推论且不论，这个答案背后是一个可为广泛应用的思考方法。公主选择的难处在于她不知道这百人的英俊程度是怎样分布的，是在怎样一个范围内。所以她最佳的策略是，pass 掉最初 37 位男子，但是把他们看成一个有代表性的sample，从而了解这百人相貌的大致分布。然后在这个认知的基础上进行选择。

真实的谈情说爱当然不是一个简单的选美。普通人也不能像波斯贵族那样要谁有谁。但是思维方法共通。假如你是一位女生，第一次恋爱的时候，也许你觉得男朋友不够细腻，不解风情。但你无法判断的是，是否天下男生大多如此，还是你特别倒霉碰到这样的极品。你唯有试过三个五个后，才能够对男性这个物种有个全局的判断。所以，当你和第一任男朋友分手后，大可不必悲天悯人，亦或对天下男人失望。正确的态度是：okay，我现在有一个data point, 现在我来找些更多的data points。

花多长时间学习？

找到多少 data points 才够呢？换句话说我们学习到什么时候才能够信任自己对世界的判断？以下这个小故事中，我们可以看出大自然是怎么解决这个问题的。

1944年冬天，二战进入尾声。德国人封锁了荷兰德占区的补给。1944-1945年的冬天，被称为”hunger winter”（饥饿的冬天）。有四百五十万荷兰人遭受饥饿，一万八千人饿死。1945年，德国战败，封锁也随之解除。

但这个饥饿冬天所带来的影响却一直留存到几十年后。那些封锁期间怀着孩子的妇女，她们肚子里发育中的胚胎，虽无知觉，也经历了这场灾难。几十年后，当这些孩子成为50岁的中年人，科学家们发现他们会比之前，或者之后出生的荷兰孩子都更肥胖，更容易有心血管疾病。

对此的一种解释是，还在妈妈肚子里的时候，我们的身体就在学习这是怎样一个世界：是个食物充足，衣食无忧的世界？还是一个有上顿没下顿的世界？这些荷兰饥荒那年出生的婴儿，他们的身体学习到：“这是一个食物匮乏的世界”。哪怕他们成年之后，荷兰已经是一个富余的发达国家，他们的身体还是不忘早年饥饿的经历，会尽力存储脂肪，准备着下一个饥饿冬天的到来。结果就是这个人群更容易肥胖，并且更容易患有与肥胖相关的心血管疾病。

有意思的是，对食物丰富与否的学习，在10月怀胎中完成，居然之后几十年也无法扭转。这个学习的窗口，是我们的身体，我们的基因所决定的。孩子学东西快，是因为他们的身体和大脑就是 specialized 学习机器。有研究说，人脑中负责抽象思维的前额叶在25岁才定型。换句话说，25岁以前，我们的思维，特别是那些高级的认知能力，还在不断变化着。而这其中很多的变化，就来自我们的环境。这种变化，就是我们在学习我们所在的，到底是怎样一个世界；怎样的思维和行为，是在这个世界上行得通的。

从人脑的发育看来，过了25岁，至少从生理上来说，这种学习就停止了。这个 deadline 取决于基因，而基因来源于千百万年的进化。千百万年中，人类的平均寿命是徘徊在20-30岁。这可能就是为什么我们的学习，从我们身体的设计上看来，是在25岁就截止了。

我们无法影响自己生理、身体上的学习，但是有些事情的学习，却是我们可以影响的，而且应该去影响的。选择怎样的工作？居住在哪个城市？找什么样的伴侣？这些似乎不是应该匆匆忙忙，赶着一个deadline （特别是25岁的deadline）去决定的事情。你会进行很多比较，才决定购买一辆汽车或者房子。而工作、伴侣，这些更重要的决定，你当然要更多比较比较，了解一下你是在怎样的一个世界里，才做决定。

也许你30岁了，没有婚配的对象，不喜欢正在做的工作，但有种种压力期待你“别折腾，安顿下来”。这压力可能来自于一个一直不给个人选择的社会传统，或者来自于一个预期寿命只有30岁的进化压力。但是这一切都变了：社会已经有越来越多的选择余地，我们也可以预料之中的活到80，90岁。

也许你要认真考虑一下波斯公主的问题：我是否应该继续收集data points？还是已经到了要做终生决定的时候？

回到波斯公主的题目

波斯公主的题目至少还教了我们另一点，就是哪怕你的方法是最优，你也永远不可能是每次都得到最英俊的驸马。在最优化的选择方法下，公主也只有 40% 左右的可能性选择到最帅的男人。就是说，如果这样选择十次，每次这百名男子以随机顺序出现，其中有6次，公主都会选到不是最帅的驸马。

生活就是有风险的，不可测的。这似乎是个打击，但也是一种释怀。尽人事，安天命。如果你按照一个正确的方法去做了，哪怕结果差强人意，这也并不是你的错。

我学会的另一点是，如果我是作为被选的一方（就像那100名男子），timing 是至关重要的。以下是一个简单的多的题目：

如果你是这百名男子中的一名，并且你能够决定自己出场的名次，你会选择在什么时候出场，以最大提高自己被选的概率？

答案是第38名。你不会选择在38名之前，因为你被选的概率是零（假设我们的公主学过高等数学，知道最佳选法）。你也不会选择后于38，因为你前面每多一个人，就意味着多了一分公主选上他的机会。

如果你有一位意中人，你当然要努力去追求幸福，但你可能也要想一下，这是否是最好的timing？

针对上述案例的数学模型分析

炮灰模型----对女生选择追求者的数学模型的建立

引言：上周我的一个朋友第N 次向女生表白遭到拒绝，作为好朋友的我除了同情之外觉得应该做点什么。之前一次聊天受到启发，加上出于对数学的兴趣，我对女生“选择与拒绝”的策略试着做了一个简单的建模，并得出比较有意义的结论。

摘要：每一个女生都渴望找到自己心中的白马王子，找到自己一生的幸福。但是面对追求者们，女生应该是选择还是拒绝，怎样才能以最大的可能找到自己的Mr. Right 呢？在这篇文章中我们运用数学中概率论的知识对女生选择追求者的这一过程进行数学建模，得到女生的选择的最优策略，最后对结果进行简单的讨论。

关键词：炮灰模型 排列 选择

模型假设：众所周知生活中涉及到感情的事情是很复杂的，把所有可能影响的因素都考虑到几乎是不可能的。为此我们先对现实进行简化，并做出一些合理的假设，考虑比较简单的一种情况。

    假设一个女生愿意在一段时间中和一位男生开始一段感情，并且在这段时间中有N 个男生追求这位女生。说明：这里的N 不是事先确定的，每个女生根据自身条件，并结合以往的经历和经验，猜测确定这个数字N 。比如其它各方面都相同的两个女生，一般来说，PP 的女生就要比不PP 的女生N 值相对要大一些。在适合这个女生的意义上，假设追求者中任何两个男生都是可以比较的，而且没有相等的情况。这样我们对这N 个男生从1 到N 进行编号，其中数字越大表示越适合这个女生。这样在这段时间中，女生的Mr. Right 就是男生N 了。现在问题变成面对这N 个追求者应该以怎样的策略才能使得在第一次选择接受的男生就是N 的可能性最大，注意到这N 个男生是以不同的先后顺序来追求这位女生的。
    为了将实际复杂的问题进行简化，我们做出下面几条合理的假设：
1、 N 个男生以不同的先后顺序向女生表白，即在任一时刻不存在两个或两个以上的男生向这位女生表白的情况的发生，而且任何一种顺序都是完全等概率的。
2、面对表白后的男生，女生只能做出接受和拒绝两种选择，不存在暧昧或者其它选择。
3、任一时刻，女生最多只能和一位男生谈恋爱，不存在脚踏多船的情况。
4、已经被拒绝的男生不会再次追求这位女生。
    基于上述假设，我们想要找到这样一种策略，使得女生以最大的概率在第一次选择接受的那个男生就是N ，i.e. Mr.Right 。
先考虑最简单的一种策略，如果一旦有男生向女生表白，女生就选择接受。这种策略下显然女生以1/N 的概率找到自己的Mr.Right 。当N 比较大的时候，这个概率就很小了，显然这种策略不是最优的。
    基于上面这些假设和模型，我们提出这样一种策略：对于最先表白的M 个人，无论女生感觉如何都选择拒绝；以后遇到男生向女生表白的情况，只要这个男生的编号比前面M 个男生的编号都大，即这个男生比前面M 个男生更适合女生，那么女生选择接受，否则选择拒绝。
    下面以N=3 为例说明：
    三个男生追求女生，共有六种排列方式：
     1 2 3；1 3 2；2 1 3；2 3 1；3 1 2；3 2 1
    如果女生采用上述最简单的策略，那么只有最后两种排列方式选择到Mr. Right ，概率为2/3!=1/3 。
    如果女生采用上面我们提出的策略，这里我们取M=1，即无论第一个人是否优秀，女生都选择拒绝。然后对于之后的追求者，只要他比第一个男生更适合女生就选择接受，否则拒绝。基于这种策略，“1 3 2 ”、“2 1 3 ”、“ 2 3 1 ”这三种排列顺序下女生都会在第一次做出接受的选择时遇到“3 ”，这样我们就把这种概率增大到3/3!=1/2。
    现在我们的问题就归结为，对于一般的N ，什么样的M 才会使这种概率达到最大值呢？（在这种模型中，前面M 个男生就被称为“炮灰”，无论他们有多么优秀都要被拒绝）

模型建立：在这一部分中，根据上面的模型假设，我们先找到对于给定的M 和N(1<M<N)，女生选择到Mr.Right 的概率的表达式。1 到N 个数字进行排列共有N! 种可能。当数字N 出现在第P 位置（M<P<=N），如果使上述策略在第一次选择接受时遇到的是N ，排列需要满足下面两个条件：
    1、N 在第P 位置
    2、从M+1 到P-1 位置的数字要比前M 位置的最大数字要小

 

 
    若记[x] 为不大于x 的最大整数，由以上推导我们可猜测当M 取[N/e] 或[N/e]+1 时，该表达式取得最大值。   用MATLAB 仿真，上述结论正确。

结果分析：
    由上述分析可以得到如下结论：为了使一个女生以最大的概率在第一次选择接受男生时遇到的正是Mr. Right ，女生应该采用以下的策略：
    拒绝前M=[N/e] 或者[N/e]+1 个追求者，当其后的追求者比前M 个追求者更适合则接受，否则拒绝。 
     “打战的时候，很多士兵身先士卒，跑到前线勇往直前。通常来说，走在最前面的，都会给大炮打中（古代的大炮像象个球一样滚过来的）成为灰烬。而后来的士兵，就踏着炮灰走到胜利，所以成为别人利益的牺牲品的人就叫炮灰。”--------百度上关于炮灰的解释
    在本篇文章中介绍的“炮灰模型”中，前M个男生就成了炮灰的角色，无论其有多么优秀，都会被拒绝。
    朋友，如果你追求一个女生而遭到拒绝，看完这篇文章后你会突然发现，也许这不是你的的错，也许你真的很优秀，只是很不幸，你成了“炮灰”。
    这几天在校内上看到很多朋友都因为拒绝或失恋而苦恼。希望上面这些看似复杂的推导和模型对你能有所启发。不要因为一次的拒绝而伤心、失落，振作起来，    你的Miss Right is waiting for you somewhere!

谨以此篇文章献给所有为爱而战的猛士们！ 

附： 
    将这个策略的最优性简证如下（限于篇幅，不借助复杂的数学公式了）：
     1.作为“策略”，可以认为应该类似于算法，对于确定的输入有确定的输出。因此对第M号追求者是否同意仅取决于之前M-1个人与该人的状况比较，以及M的大小；进一步地，显然与前M-1个人的好坏顺序无关（因为前M-1个人的顺序与第M个人及以后无关）。
    2.如果仅考虑选中N号，那么答应某个人的必要条件是此人比之前的都好（否则一定不是No.N） 
    3.综1、2，所有可能的策略都有相同形式：对于第K1,K2,...,Kt号人，如果比以前的都好，OK；如果不符合条件，“还是做朋友吧” 
    4.进一步，如果Km +1<K(m+1),将Km替换为Km + 1。简单计算可以发现（其实是我不想写了）在这一步答应且选对的概率不变（始终是1/n*前面没有答应的概率），但这一步答应的概率减小，后面答应且选对的概率相应增大（如果替换的是Kt，概率不变，但可以接着换K(t-1)使概率增大）。由此可以得出K1到Kt应该是连续整数且Kt=n 
    5.（继续） 再由作者的理论小推论一下：设女性最为灿烂的青春为18-28岁，在这段时间中将会遇到一生中几乎全部的追求者（之前之后的忽略不计），且追求者均匀分布，则女性从18+10/e=21.7即22岁左右开始接受追求……这告诉我们，想谈恋爱找大三大四的……