某公司要招聘一名员工, 有 $N$ 人报名面试。假设 $N$ 位报名者所具有该职位相关的 能力值两两不同, 且招聘委员会能观察到的能力值排名与其真实能力值排名吻合。委员会决 定采取如下招聘程序:
1. 招聘委员会按随机顺序逐个面试候选人, 且他们能观察到当时所见候选人的相对排 名。比如委员会面试到第 $m$ 位候选人时, 他们拥有的信息是前 $m$ 位面试者的相对排 名, 但不知后 $N-m$ 位候选人的能力情况。
2. 每面试完一位候选人, 委员会需当即决定是否给他/她发工作offer。
3. 如果委员会决定给某位候选者发offer, 那么这位候选者以概率 $p$ 接受, 以概率 $1-p$ 拒 绝, 且独立于(之前) 所有其他面试者的决定。如果该候选人接受offer, 那么委员会将 不再继续面试接下去的候选人。如果该候选人拒绝offer, 那么委员会将继续面试下一 位。
4. 如果委员会决定不给某位面试者发offer, 那么他们将继续面试下一位候选人, 且不能 再回头去找前面已经面试过的人。
5. 反复该面试程序, 直到有候选者接受offer。如果没有候选者接收该工作, 那么委员会 面试完所有的 $N$ 位候选者。
由于 $N$ 位面试者的顺序是完全随机的, 因此他们能力的排名在 $N$ ! 的可能性中是均匀分布。 且委员会所具有的全部信息是当前面试过的候选人的相对排名。委员会的任务是, 在遵守如 上程序的前提下, 找到一个策略, 使得招到 $N$ 位候选者中能力最优者的概率最大化。
问题如下:
(a) 考虑如下策略。委员会先面试前 $m-1$ 位候选者, 不管其能力排名如何, 都不发 工作offer。从第 $m$ 位开始, 一旦看到能力在所面试过候选人中的最优者, 即发工 作offer。如对方拒绝, 则继续面试直到下一位当前最优者 ${ }^1$ 出现。试证明：对于任意 的 $N$, 都存在一个 $m=m_N$, 使得依靠上述策略找到(所有 $N$ 位候选人中) 最优者的概 率值, 在所有可能的策略所给出的概率值中是最大的。
(b) 假设 $p=1$ 。当 $N \rightarrow+\infty$, 求 $\frac{m_N}{N}$ 的极限。
(c) 对一般的 $p \in(0,1)$, 当 $N \rightarrow+\infty$, 求 $\frac{m_N}{N}$ 的极限。