最优停止与选择心仪对象

王 茂南 2024年3月15日07:03:35
评论
3 2727字阅读9分5秒
摘要最优停止问题出发,介绍了麦穗问题和经典的秘书问题以及面对此类问题采取的策略。本文还根据该策略推导并验证了37%法则的正确性,并且简单分析了该法则的适用性。

简介

在生活中,我们经常面临需要在不完全信息下做出决策的情形。从挑选伴侣、购买房产到职业选择,如何在恰当的时刻做出最佳选择是一个普遍而复杂的问题

本文将介绍数学中的「最优停止问题」,会描述这个问题,并探讨如何应用这一理论来优化决策过程,增加成功的概率。这个问题其实也就是:你将要穿过一片麦田,在不能回头的前提下,如何摘下一株最大的麦穗?下面是这个问题的结论:

对于这类最优停止问题,可以采取的措施为:先拒绝前面的一定比例的候选人(或是事),用来观察和建立一个「标准」,然后从剩下的中选择第一个比之前所有候选人都好的人。这里比例通常为 37%,也就是接近 1/3

参考资料

 

问题描述

最优停止问题介绍

最优停止问题是决策理论中的一个经典问题,它涉及在一系列选择中决定最佳停止点的问题。这类问题的特点是:选项是顺序出现的,一旦放弃了某个选项,就无法再回头选择。同时我们也不清楚未来会遇到什么样子的方案,即未来是不可知的。因此,决策者必须在没有完全信息的情况下,基于已有的观察来做出最佳选择。

 

最优停止问题例子

一个广为人知的最优停止问题是「秘书问题」,或是被称为「相亲问题」,「苏丹的嫁妆问题」。这个问题假设是:你需要聘请一名秘书,有多个候选人按随机顺序进行面试。你在每次面试后都必须决定是否聘用当前的候选人。如果拒绝了,就不能再回头选择他。问题的关键在于找到一种策略,使得选择最佳候选人的概率最大化。

面对这类问题,Merrill M. Flood 在1949年首次提出 37% 法则。他所采取的的策略为:

  1. 首先对前面一部分面试者,无论优秀与否都直接拒绝,只考察目标,收集数据,用于确定「最基本的满意标准」。
  2. 然后对剩下的人进行面试,如果遇到一位比之前面试的人都优秀的面试者,那么就立即出手,直接聘请这个人,否则就继续面试

通过计算,Flood发现 37% 是一个最优停止点,也就是说选择前37%的人直接拒绝时,得到最适合担任秘书的人的概率最大。下面我们分享一下 37% 是如何计算得到的。

 

数学描述

问题描述

假设有 n 那个候选人,他们的质量顺序是随机的。你需要在面试过程中决定是否雇佣当前的候选人。一旦你拒绝了一个候选人,就不能再回头选择他。问题是确定一个策略,使得选择最优候选人的概率最大化。

 

策略选择

最优策略是:先拒绝前面的一定比例的候选人,用来观察和建立一个「标准」,然后从剩下的候选人中选择第一个比之前所有候选人都好的人。问题的关键是确定应该拒绝前面多少个候选人。

 

确定最优拒绝比例

下面开始推导最优的拒绝比例。首先我们定义变量:

  • n:候选人总数。
  • r:观察的候选人数,这些候选人只用于设定标准,不会被选择。
  • k:表示第 k 个人是最优的候选人。

现在我们假设有两个事件,事件 A_k 表示第 k 个人被选中,事件 B_k 表示第 k 个人是最优秀的。于是我们希望最大化 k 取不同数值时候,P(A_k, B_k) 的概率,也就是:

最优停止与选择心仪对象

对于 P(B_k),表示第 k 个人是最优秀的,概率是 1/n,这个会随机出现 n 个候选人中的一个。此时上面的式子可以化简为如下的式子,我们将求和拆开:

最优停止与选择心仪对象

这里 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)

于是上面的式子可以进一步化简,变为:

最优停止与选择心仪对象

我们希望上面的概率最大,于是将其转换为积分的形式:

最优停止与选择心仪对象

对于上面的积分运算,可以参考下面是式子:

最优停止与选择心仪对象

为了求上面式子最大,我们对其进行求导,也就是

最优停止与选择心仪对象

我们使得导数为 0,对上面式子求解,得到 r=(n-1)/e,也就是差不多总人数 37% 左右。

 

仿真实验

接下来我们进行仿真实验。首先测试选择比例都接近 0.37 的时候,此时选择是最优的概率如下表所示。可以看到选中最优的概率是接近 0.37 的。

最优停止与选择心仪对象

接下来我们测试不同的拒绝比例(也就是不同的 r/n)对结果的影响。结果如下图所示,可以看到在接近 0.35-0.45 之间的时候,按策略可以选中最优的概率是最大的:

最优停止与选择心仪对象

下面是对于的代码,大家可以尝试不同的参数来验证结果:

  1. import numpy as np
  2. def optimal_stopping_simulation(n=1000, r=0.37, trials=1000):
  3.     matches = 0
  4.     for _ in range(trials):
  5.         candidates = np.random.permutation(n)
  6.         observation_end = int(n * r)
  7.         best_during_observation = max(candidates[:observation_end])
  8.         chosen_index = None
  9.         for i in range(observation_end, n):
  10.             if candidates[i] > best_during_observation:
  11.                 chosen_index = i
  12.                 break
  13.         if chosen_index is None:
  14.             chosen_index = n - 1  # 如果没有找到更好的,选择最后一个
  15.         if chosen_index == np.argmax(candidates):
  16.             matches += 1
  17.     return matches / trials
  18. # 运行仿真并打印结果
  19. for r in np.arange(0.1, 0.9, 0.05):
  20.     match_rate = optimal_stopping_simulation(r=r)
  21.     print(f"r/n={r:.2f}, Match rate: {match_rate:.2f}")

当然,上面讲了这么多,只是为了解决一个最优化的问题。很多时候,比如谈恋爱(可能我们是有先验条件的),那这个结论不再成立(所以,也不要对照着这个来谈恋爱),如果一开始就很合适,也是可以在一起的。

最后在生活中,我们需要灵活的应用37%法则,结合自己的经验,寻找到那个令人满意的「可」之所在。

  • 微信公众号
  • 关注微信公众号
  • weinxin
  • QQ群
  • 我们的QQ群号
  • weinxin
王 茂南
  • 本文由 发表于 2024年3月15日07:03:35
  • 转载请务必保留本文链接:https://mathpretty.com/17200.html
匿名

发表评论

匿名网友 填写信息

:?: :razz: :sad: :evil: :!: :smile: :oops: :grin: :eek: :shock: :???: :cool: :lol: :mad: :twisted: :roll: :wink: :idea: :arrow: :neutral: :cry: :mrgreen: