趣味题——寻找最优者

寻找最优者：不可逆的做出选择，如何使得选到最优者的概率最大

---

题目描述

• 由于无人知道缘分何时到来,假设人的一生会遇到100个异性,这100个人参差不齐,其中有个人是最好的,100人随机的排着队出现,而我们对每个人必须决定是否接受,而且一旦决定后不能修改,那么用什么策略选择更有机会选到最好的那一个呢?

---

解决方案

策略设想

• 拒绝前k个人,然后从第k+1个开始,只要优于前面的所有人,则接受
• k值的设定比较难,太小了容易找到不好的,太多了容易错过最好的

证明

• 假设最优者出现在第$i(k< i \leq n)$个(事件A),那么最优者被选中(事件B)的概率为前i-1个中的最优者在前k个人中的概率
  $$P(B|A) = \frac{k}{i-1}$$

  • $P(B|A) = P(最优者被选中|第i个为最优者)$

• 最优者出现在第$i$个的概率为
  $$P(B) = \frac{1}{n}$$

• 最优者被选中的概率为

• 接下来的证明用到了调和级数的和,详情参考调和级数的和
  $$\begin{align} \sum_{i=1}^{n}\frac{1}{i} = ln(n) + \gamma + \epsilon_{n} \end{align}$$

  • $\gamma$为欧拉-马歇罗尼常数,近似值为γ≈0.57721,下面的推导都不需要精确解的,所以可以使用该公式
  • $\epsilon_{n}$约等于$\frac{1}{2n}$,随着n的不断增大,$\epsilon_{n}$趋于0
    $$\begin{align} P(B) &= \sum_{A}P(B,A) \\ &= \sum_{A}P(B|A)P(A) \\ &= \sum_{i=k+1}^{n}\frac{k}{i-1}\frac{1}{n} \\ &= \sum_{i=k+1}^{n}\frac{k}{n}\frac{1}{i-1} \\ &= \frac{k}{n}\sum_{i=k+1}^{n}\frac{1}{i-1} \\ &= \frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i} \\ &= \frac{k}{n}(\sum_{i=1}^{n-1}\frac{1}{i} - \sum_{i=1}^{k-1}\frac{1}{i}) \\ &\approx \frac{k}{n}((ln(n-1)+C)-(ln(k-1)+C)) \\ &= \frac{k}{n}ln(\frac{n-1}{k-1}) \\ \end{align}$$

• 当n和k足够大时有

  • (不能证明k也会足够大,但是直觉上n足够大k也会足够大,因为n足够大时往往需要拒绝更多的人)
    $$\frac{n-1}{k-1} = \frac{n}{k}$$

• 令$x=\frac{k}{n}$,则有
  $$\begin{align} f(x) &= xln\frac{1}{x} \\ {f}’(x) &= ln(\frac{1}{x})+(-\frac{1}{x^2}\cdot x \cdot x) \\ &= ln(\frac{1}{x})-1 \end{align}$$

• 求$f(x)$的最大值,令${f}’(x)=0$有
  $$ln(\frac{1}{x})-1 = 0$$

• 解方程得
  $$x = \frac{1}{e}$$

• 也就是说当$\frac{k}{n} = \frac{1}{e}$时,找到最优者的概率最大

策略描述

• 拒绝前$\frac{n}{e}$个人(也就是拒绝前37%的人),然后从第$\frac{n}{e}+1$个开始,只要优于前面的所有人,则接受
• 这种方式可以保证我们有最大的概率找到最优者