有意思的概率论问题

#

水塘抽样问题（Reservoir Sampling）

#

假设我们看到一连串项目，一次只出现一个。我们希望内存中保留 k 个项目，并且希望它们能从序列中随机选择。如果我们知道总项 n 的数量，并且可以任意访问这些项，那么解法很简单：以等概率选择 1 到 n 之间的 k 个不同的索引 i，并保留第 i 个元素。问题在于我们并不总是事先知道确切的 n。

-> 数据是一条“流”（链表），只能用 getNext() 顺着往后读，有多少个元素不知道，只能用 hasNext() 判断是否结束；目标是在只扫一遍的前提下，从中等概率地随机选出 K 个节点，且每个节点被选中的概率一样。

k = 1 时：

‍

k > 1 时：

‍

‍

Reference: https://en.wikipedia.org/wiki/Reservoir_sampling

‍

秘书问题（Secretary problem / 37%法则）

#

想象一位管理者想从排名靠 前的申请者中挑选最优秀的秘书。申请者会以随机顺序逐一接受面试。每位申请者将在面试后立即做出决定。一旦被拒，申请人将无法被召回。面试过程中，管理员获得的信息足以在所有面试者中排名申请人，但对尚未见面的申请者质量一无所知。问题在于如何制定最佳策略（ 停止规则 ）以最大化选中最佳申请者的概率。如果决策可以推迟到最后，这可以通过简单的最大选择算法解决：跟踪运行的最大值（以及谁达到了它），并在最终选择整体最大值。难点在于必须立即做出决定。

Answer：

前 37% 的人全部拒绝，只看他们当中的最佳评分作为“标杆”；
从第 37%+1 个开始，如果某人比之前所有人都强，就当场录用。

‍

‍

Reference：https://en.wikipedia.org/wiki/Secretary_problem