How to find the Mr. Right

Posted on | In

How to find the Mr. Right

作者：孔令坤，转载请注明出处

青春苦短，一个女性的青春假设为18到28岁，在10年期间内每半年假设可以找到一个男友，那么在这20次尝试的过程中应当采取怎样的策略才能从理论上找到Mr. Right呢？

前提条件

  1. 好马不吃回头草，优秀的妹子才不和前任继续往来。
  2. 每找到一个新的男友后，妹子可以根据其综合表现进行评分。

策略

假设尝试次数为n，妹子们可以在找完k个男友后，抛弃掉他们，然后选取这k个人中最高的综合评分，记为bestScore。

在之后的找男友大作战中，只要有人的综合评分大于bestScore，妹子就可以赶紧选择他。

接下来，我们需要从概率学的角度来计算，k取何值时，妹子可以在第k+1次选取中最大概率地选到n次尝试机会里分数最高的男友，即在k+1次时找到人群中最优秀的男友。

算法

1
2
3
4
5
6
7
8
9
10
# this function returns the index of the MrRight when having n shots
def findMrRight(k,n):
  bestScore = -1
  for i in range(k):
    if score(i) > bestScore:
      bestScore = score(i)
  for i in range(k,n):
    if score(i) > bestScore:
      return i
  return n

概率分析

记$S$为妹子成功的选择到了Mr. Right的事件，$S_i$表示Mr. Right是第\$i\$个男友时成功的事件，即$k<i\leq n$时妹子找到了Mr. Right。由于不同的$S_i$不相交，于是我们有：
$$
\text{Pr}(S) = \sum_{i=k+1}^{n}\text{Pr}(S_i)
$$
接下来我们来计算$\text{Pr}(S_i)$。为了使在第$i$个男友时找到Mr. Right，有两件事情必须发生：

  1. Mr. Right必须在第$i$次被找到，即所有$n$个男性中分数最高的男性在妹子的第$i$次尝试中被发现——记此事件为$A_i$。
  2. 妹子不能选择在第$k+1$到第$i-1$次尝试中的男友，即在第1次到第$i-1$次尝试中，综合评分最高的男友需要出现在前$k$次中——记此事件为$B_i$。

对于事件$A_i$，其相当于$n$个男性中分数最高的男性落在了第$i$个位置上，概率有$\text{Pr}(A_i)=\frac{1}{n}$。

对于事件$B_i$，其相当于$i-1$个男性中分数最高的男性落在了位置$1,2,…,k-1,k$中的某个位置，概率满足$\text{Pr}(B_i)=\frac{k}{i-1}$。

由于事件$A_i$、事件$B_i$相互独立，我们发现：
$$
\begin{align}
\text{Pr}(S) & = \sum_{i=k+1}^{n}\text{Pr}(S_i) = \sum_{i=k+1}^{n}\text{Pr}(A_i \cap B_i) \
&=\sum_{i=k+1}^{n}\text{Pr}(A_i) \text{Pr}(B_i)\
&=\sum_{i=k+1}^{n}\frac{k}{n(i-1)}\
&=\frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i}\
\end{align}
$$
根据放缩公式，我们可以得到：
$$
\int_{k}^{n}\frac{1}{x}\mathbf{d}x \le \frac{k}{n}\sum_{i=k}^{n-1}\frac{1}{i} \le \int_{k-1}^{n-1}\frac{1}{x}\mathbf{d}x.
$$
从而，我们解这个定积分，可以得到：
$$
\frac{k}{n}(\mathbf{ln}n - \mathbf{ln}k) \le \text{Pr}(S) \le \frac{k}{n}(\mathbf{ln}(n-1) - \mathbf{ln}(k-1)).
$$
其中，等式左边为妹子在第$i$个男友时找到Mr. Right的概率的下界。由于我们希望最大化成功的概率，我们希望能够最大化这个下界。因此，我们将下界表达式$\frac{k}{n}(\mathbf{ln}n - \mathbf{ln}k)$对$k$求导，得：
$$
\frac{1}{n}(\mathbf{ln}n - \mathbf{ln}k -1)
$$
在对$k$导函数单调递减的情况下，令此导数等于0，我们可以得到:
$$
\begin{align}
&\mathbf{ln}k = \mathbf{ln}n -1 = \mathbf{ln}\frac{n}{e}\
\Leftrightarrow \text{ } &k=\frac{n}{e},
\end{align}
$$
即当$k=\frac{n}{e}$时，概率的下界最大化为$\frac{1}{e}$。换句话说，假如一共可以尝试去和$n$个男性交往，妹子们可以选择交往过$k=\frac{n}{e}$男友来积累经验，然后遇到更好的人就从了。因为这样，妹子们有最大的几率——超过$\frac{1}{e}$会找到人群中最优质的男性。

以之前所说的20个理论中交男友的机会为例，妹子们可以先通过之前的$\frac{20}{e} \approx 7$ 个男友来积攒经验，并在之后如果遇到比前七个男友都优秀的男性就从了，将会有高于$36.7\%$的几率找到属于自己的Mr. Right.

以上皆为扯淡之谈。