文章目录(Table of Contents)
简介
在生活中,我们经常面临需要在不完全信息下做出决策的情形。从挑选伴侣、购买房产到职业选择,如何在恰当的时刻做出最佳选择是一个普遍而复杂的问题。
本文将介绍数学中的「最优停止问题」,会描述这个问题,并探讨如何应用这一理论来优化决策过程,增加成功的概率。这个问题其实也就是:你将要穿过一片麦田,在不能回头的前提下,如何摘下一株最大的麦穗?下面是这个问题的结论:
对于这类最优停止问题,可以采取的措施为:先拒绝前面的一定比例的候选人(或是事),用来观察和建立一个「标准」,然后从剩下的中选择第一个比之前所有候选人都好的人。这里比例通常为 37%,也就是接近 1/3。
参考资料
- 死理性派恋爱法:拒绝掉前面37%的人;
- 如何选择心仪对象,非常有意思的博客;
- 男生追女生的数学模型,非常有意思的论文;
- 最优停止理论——如何适“可”而止,部分的推导是从这里借鉴的,进行了一些完善;
问题描述
最优停止问题介绍
最优停止问题是决策理论中的一个经典问题,它涉及在一系列选择中决定最佳停止点的问题。这类问题的特点是:选项是顺序出现的,一旦放弃了某个选项,就无法再回头选择。同时我们也不清楚未来会遇到什么样子的方案,即未来是不可知的。因此,决策者必须在没有完全信息的情况下,基于已有的观察来做出最佳选择。
最优停止问题例子
一个广为人知的最优停止问题是「秘书问题」,或是被称为「相亲问题」,「苏丹的嫁妆问题」。这个问题假设是:你需要聘请一名秘书,有多个候选人按随机顺序进行面试。你在每次面试后都必须决定是否聘用当前的候选人。如果拒绝了,就不能再回头选择他。问题的关键在于找到一种策略,使得选择最佳候选人的概率最大化。
面对这类问题,Merrill M. Flood 在1949年首次提出 37% 法则。他所采取的的策略为:
- 首先对前面一部分面试者,无论优秀与否都直接拒绝,只考察目标,收集数据,用于确定「最基本的满意标准」。
- 然后对剩下的人进行面试,如果遇到一位比之前面试的人都优秀的面试者,那么就立即出手,直接聘请这个人,否则就继续面试
通过计算,Flood发现 37% 是一个最优停止点,也就是说选择前37%的人直接拒绝时,得到最适合担任秘书的人的概率最大。下面我们分享一下 37% 是如何计算得到的。
数学描述
问题描述
假设有 n 那个候选人,他们的质量顺序是随机的。你需要在面试过程中决定是否雇佣当前的候选人。一旦你拒绝了一个候选人,就不能再回头选择他。问题是确定一个策略,使得选择最优候选人的概率最大化。
策略选择
最优策略是:先拒绝前面的一定比例的候选人,用来观察和建立一个「标准」,然后从剩下的候选人中选择第一个比之前所有候选人都好的人。问题的关键是确定应该拒绝前面多少个候选人。
确定最优拒绝比例
下面开始推导最优的拒绝比例。首先我们定义变量:
n
:候选人总数。r
:观察的候选人数,这些候选人只用于设定标准,不会被选择。k
:表示第 k 个人是最优的候选人。
现在我们假设有两个事件,事件 A_k
表示第 k
个人被选中,事件 B_k
表示第 k
个人是最优秀的。于是我们希望最大化 k
取不同数值时候,P(A_k, B_k)
的概率,也就是:
![最优停止与选择心仪对象](https://img.mathpretty.com/blog_article/2024/06/20240615_161538_47dx382.jpg)
对于 P(B_k)
,表示第 k
个人是最优秀的,概率是 1/n,这个会随机出现 n
个候选人中的一个。此时上面的式子可以化简为如下的式子,我们将求和拆开:
![最优停止与选择心仪对象](https://img.mathpretty.com/blog_article/2024/06/20240615_162430_noi6wth.jpg)
这里 P(A_k|B_k)
表示第 k
个人被选中的概率。由于我们的策略是:
- 当
k<=r
的时候,我们不会进行任何选择,因此此时P(A_k|B_k)=0
; - 对于
k>r
的时候,若选择第k
个人,则表示在r+1~k-1
里面,没有比k
更好的人。或者可以说0~k-1
之间的最大值,出现在0~r
之间,此时的概率为r/(k-1)
。
于是上面的式子可以进一步化简,变为:
![最优停止与选择心仪对象](https://img.mathpretty.com/blog_article/2024/06/20240615_163109_hd24o0x.jpg)
我们希望上面的概率最大,于是将其转换为积分的形式:
![最优停止与选择心仪对象](https://img.mathpretty.com/blog_article/2024/06/20240615_163727_dc6yrvt.jpg)
对于上面的积分运算,可以参考下面是式子:
![最优停止与选择心仪对象](https://img.mathpretty.com/blog_article/2024/06/20240615_163800_okkh59y.jpg)
为了求上面式子最大,我们对其进行求导,也就是
![最优停止与选择心仪对象](https://img.mathpretty.com/blog_article/2024/06/20240615_164323_tdtgdn9.jpg)
我们使得导数为 0,对上面式子求解,得到 r=(n-1)/e
,也就是差不多总人数 37%
左右。
仿真实验
接下来我们进行仿真实验。首先测试选择比例都接近 0.37 的时候,此时选择是最优的概率如下表所示。可以看到选中最优的概率是接近 0.37 的。
![最优停止与选择心仪对象](https://img.mathpretty.com/blog_article/2024/06/20240615_170052_cs82pk8.jpg)
接下来我们测试不同的拒绝比例(也就是不同的 r/n)对结果的影响。结果如下图所示,可以看到在接近 0.35-0.45 之间的时候,按策略可以选中最优的概率是最大的:
![最优停止与选择心仪对象](https://img.mathpretty.com/blog_article/2024/06/20240615_170259_427m0cw.jpg)
下面是对于的代码,大家可以尝试不同的参数来验证结果:
- import numpy as np
- def optimal_stopping_simulation(n=1000, r=0.37, trials=1000):
- matches = 0
- for _ in range(trials):
- candidates = np.random.permutation(n)
- observation_end = int(n * r)
- best_during_observation = max(candidates[:observation_end])
- chosen_index = None
- for i in range(observation_end, n):
- if candidates[i] > best_during_observation:
- chosen_index = i
- break
- if chosen_index is None:
- chosen_index = n - 1 # 如果没有找到更好的,选择最后一个
- if chosen_index == np.argmax(candidates):
- matches += 1
- return matches / trials
- # 运行仿真并打印结果
- for r in np.arange(0.1, 0.9, 0.05):
- match_rate = optimal_stopping_simulation(r=r)
- print(f"r/n={r:.2f}, Match rate: {match_rate:.2f}")
当然,上面讲了这么多,只是为了解决一个最优化的问题。很多时候,比如谈恋爱(可能我们是有先验条件的),那这个结论不再成立(所以,也不要对照着这个来谈恋爱),如果一开始就很合适,也是可以在一起的。
最后在生活中,我们需要灵活的应用37%法则,结合自己的经验,寻找到那个令人满意的「可」之所在。
- 微信公众号
- 关注微信公众号
-
- QQ群
- 我们的QQ群号
-
评论