趣味题——寻找最优者

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

---

题目描述

• 由于无人知道缘分何时到来,假设人的一生会遇到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\)个开始,只要优于前面的所有人,则接受
• 这种方式可以保证我们有最大的概率找到最优者