趣味题——寻找最优者

Posted on

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

题目描述

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