以下是恋爱问题:
总共要和n个人恋爱。每次恋爱中都要决定是否和恋爱对象结婚,如果直到分手都没有结婚,同他(她)便不会再有第二次机会。恋爱中总能清楚了解同对方的合适程度,并能和之前的每一个对象做比较。
问什么样的策略,才能同最合适人选走进婚姻的概率最大?
这属于最佳停止问题。我们采取这样的策略:前r个恋爱对象都不结婚,然后从第r+1个开始,只要遇到一个比前r个对象都好的恋爱对象就结婚,现在的问题变为求最佳r值。
若按照我们之前选定的策略,能选中最合适对象(假设其为第i号对象)结婚许满足的条件:
i > r i>r i>r(否则会直接错过最合适对象)第1号到 i − 1 i-1 i−1号对象中,最合适的人位于1号到 r r r号中。(否则会在未遇到最合适对象之前结婚)
我们首先假设恋爱对象的合适程度是完全随机分布的。
以下列出i为各种值情况下,与最合适对象结婚的概率p:
i = 1 , p 1 = 0 i=1,p_1=0 i=1,p1=0
i = 2 , p 2 = 0 i=2,p_2=0 i=2,p2=0
. . . ... ...
i = r , p r = 0 i=r,p_r=0 i=r,pr=0
i = r + 1 , p r + 1 = r / r = 1 i=r+1,p_{r+1}=r/r=1 i=r+1,pr+1=r/r=1
i = r + 2 , p r + 2 = r / ( r + 1 ) i=r+2,p_{r+2}=r/(r+1) i=r+2,pr+2=r/(r+1)
i = r + 3 , p r + 3 = r / ( r + 2 ) i=r+3,p_{r+3}=r/(r+2) i=r+3,pr+3=r/(r+2)
. . . ... ...
i = n , p n = r / ( n − 1 ) i=n,p_n=r/(n-1) i=n,pn=r/(n−1)
因为恋爱对象的合适程度是完全随机分布,所以 n n n个对象中,最合适人选位于任意i号位置的概率均为 1 / n 1/n 1/n;
根据以上条件,即放弃前r个,从第r+1个开始,若遇到比前面都合适的对象则结婚,则选中对象为全部对象中最合适的概率为:
P r = 1 n ∑ i = 1 n p i = 1 n ∑ i = r + 1 n r i − 1 (1) P_r = \dfrac 1n\sum_{i=1}^np_i=\dfrac 1n\sum_{i=r+1}^n\dfrac r{i-1} \tag1 Pr=n1i=1∑npi=n1i=r+1∑ni−1r(1)
容易看出 P r P_r Pr是关于 n n n的函数。于是对于具体的 n n n值,我们可以计算出所有的 P r P_r Pr ,其中 r ∈ ( 0 , n ) r\in (0,n) r∈(0,n),同时容易知道 P 0 = 1 n P_0= \frac 1n P0=n1, P n = 0 P_n=0 Pn=0。
所以,对于每一个n,能选中最合适恋爱对象结婚的最大概率为:
max ( { P r , r ∈ [ 0 , n ] } ) \max({\{Pr,r\in[0,n]\}}) max({Pr,r∈[0,n]})
其中,取的最大概率值的r就是我们想要的恋爱问题的解。
理论已经说完了,接下来是对实际情况的求解。
若n比较小,可以通过动态规划方法求解。
若n趋近无穷大时,就变成了无穷序列的求和问题,上一篇文章中已经介绍了方法,这里写出推导:
P r = lim n → ∞ 1 n ∑ i = r + 1 n r i − 1 P_r=\lim\limits_{n \to \infty} \dfrac 1n\sum_{i=r+1}^n\dfrac r{i-1} Pr=n→∞limn1i=r+1∑ni−1r
= lim n → ∞ ( r n ∗ 1 n ∗ ∑ i = r + 1 n 1 i n − 1 n ) =\lim\limits_{n \to \infty} \bigg(\dfrac rn*\dfrac 1n*\sum_{i=r+1}^n\dfrac 1{\frac in- \frac 1n} \bigg) =n→∞lim(nr∗n1∗i=r+1∑nni−n11)
= lim n → ∞ ( r n ) ∗ ∫ lim n → ∞ ( r + 1 n ) 1 1 x d x =\lim\limits_{n \to \infty}\bigg(\dfrac rn\bigg)*\int_{\lim\limits_{n \to \infty} (\frac {r+1}n)}^1 \frac 1xdx =n→∞lim(nr)∗∫n→∞lim(nr+1)1x1dx
另 lim n → ∞ r n = a \lim\limits_{n \to \infty}\dfrac rn=a n→∞limnr=a,则上式:
= a ∫ a 1 1 x d x =a\int_a^1 \frac 1x dx =a∫a1x1dx
= a ln x ∣ a 1 =a \ln x \bigg|_a^1 =alnx∣∣∣∣a1
= − a ln ( a ) =- a \ln (a) =−aln(a)
这里画出 − a ln ( a ) - a \ln (a) −aln(a)关于 a a a的图像:
要求其最大值,只需求出导数为0的a值:
( − a ln ( a ) ) ′ = − ln ( a ) − 1 = 0 (- a \ln (a))^{'} = -\ln(a)-1=0 (−aln(a))′=−ln(a)−1=0
解得: a = 1 e a=\dfrac 1e a=e1,也就是 lim n → ∞ r n = 1 e \lim\limits_{n \to \infty}\dfrac rn=\dfrac 1e n→∞limnr=e1,即
r = n e r=\dfrac ne r=en
此时,得到的概率值最大为
P r = 1 e ≈ 36.8 % P_r=\dfrac 1e\approx36.8\% Pr=e1≈36.8%
远比直觉高。
但是在实际恋爱过程中,恋爱对象的适合程度可能不完全符合随机分布。如有经验之后可能比没经验前有更高概率和更加适合的对象谈恋爱,这时就不能再按最适合对象出现在每一个位置都是等概率的情况计算了。但是按照本文介绍的思路和原理,若确定了最适合对象分布位置的概率函数,依然可以求得最佳结婚策略,这里就不再啰唆了。
最后,祝愿每个人都能找到自己最适合的另一半。