• 赠券收集者问题
  • 问题
  • 思路
  • 证明
• 在线雇佣问题
  • 问题
  • 思路
  • 证明

---

赠券收集者问题

问题

把相同的球随机投到 $n$ 个盒子里，在每个盒子里至少有一个球之前，要投多少个球？

答案：大约要投 $n\ln(n)$ 次

思路

将盒子分为有球和没球的，投球分为$n$个阶段，分别为有$0,1,2…n$个盒子有球，按阶段分别计数。

证明

我们称一次投球投入到空盒子为“击中”，则称第$i$次击中到第$i+1$次击中之间的状态为$i$。则两个状态间转移概率为：

$$Pr(n_i \to n_{i+1}) = \frac{n-i}{n}$$

每个阶段到下个阶段投球数$n_i$是几何分布，所以

$$E[n_i] = \frac{n}{n-i}$$

因此总共期望的投球数量为：

$$E[ \sum_{i=0}^{n-1} n_i] = \sum_{i=0}^{n-1} E[n_i] = \sum_{i=0}^{n-1} \frac{n}{n-i} = n \sum_{i=1}^{n} \frac{1}{i} \approx n(\ln(n) + O(1))$$

---

在线雇佣问题

问题

有$n$个面试者，面试录取规则为：对前$k$个人，都不录取，取其最高值为阈值，之后从$k+1$开始，雇佣遇到的第一个高于阈值的人。求使得所雇佣的人是最好的人的k值。

答案：$n/e$，雇佣的人是最好的概率为$1/e$

思路

按照此法雇佣的人是最好的人的要求是：对第$i$位置而言，最好的人在该位置且前面出现的最大值在前$k$人中。

证明

令事件$S_i$为在第$i$个位置雇佣到最好的人的事件，它可以分成两个事件：$B_i$，最好的人在第$i$个位置；$O_i$，在第$i$个位置之前都不会选择雇佣人，即前$i-1$个数中最大值在前$k$中。事实上，$B_i$与$O_i$是相互独立的，所以：

$$Pr(S_i = 1) = P(B_i \cap O_i) = \frac{1}{n} \cdot \frac{k}{i-1}$$

则雇佣到最好的人的期望为：

$$E[\sum_{i=k+1}^{n} S_i] = \sum_{i=k+1}^{n} E[S_i] = \sum_{i=k+1}^{n} \frac{1}{n} \cdot \frac{k}{i-1} = \frac{k}{n} \sum_{i=k}^{n-1} \frac{1}{i}$$

因为有不等式

$$\int_k^n \frac{1}{x} dx \leq \sum_{i=k}^{n-1} \frac{1}{i} \leq \int_{k-1}^{n-1} \frac{1}{x} dx \ln{n} - \ln{k} \leq \sum_{i=k}^{n-1} \frac{1}{i} \leq \ln(n-1) - \ln(k-1)$$

我们关心其下界，对其求偏导为：

$$\frac{1}{n} (\ln{n} - \ln{k} + 1) = 0$$

解得$k = n/e$，概率下界为$1/e$