Platform 9.75

Life can only be understood going backwards, but it must be lived going forwards.

– Søren Aabye Kierkegaard (1813-1855)

0. 一碗鸡汤

有一天，柏拉图问老师苏格拉底：什么是爱情？

苏格拉底就让他先到麦田去，摘一颗全麦田里最大最金黄的麦穗来。期间只能摘一次，并且只能向前走不能回头。

柏拉图按照老师说的去做了，结果两手空空的走出了田地。老师问他为什么摘不到？他说：因为只能摘一次，又不能走回头路，期间即便看到又大又金黄的麦穗，因为不知道前面是否还会有更好的，所以就没有摘。

继续往前走时，又发觉前面的麦穗总是不如之前见到的好，原来最大最金黄的麦穗早就已经错过了，所以我什么都没有摘。

这时苏格拉底说：这就是“爱情”。

—— 佚名

1. 显而易见的策略

柏拉图要使用什么策略才能让自己选择到最好麦穗的概率最大化呢？一个显而易见的策略是把前面 k 个麦穗作为“训练集”，一旦出现比这 k 个麦穗都好的麦穗，就作出选择。

我们不妨来计算一下这一策略选择到最好麦穗的概率。事件「第一个比前 k 个都好的麦穗恰好为 N 个中最好的麦穗」好像并不好处理，但它可以分解为「最好的麦穗不在前 k 个里」和「前 k 个麦穗里最好的麦穗，恰好是最好的麦穗前面所有麦穗里最好的麦穗」这两个事件的交。假设最好的麦穗在第 i 个，则 i <= k 时，取得最好麦穗的概率为 0；i > k 时，概率自然就是 k/(i - 1)。¹于是：

2. 朴实无华的算法

很自然会想，如何使 P(k) 最大化呢？由于 k 只能取 1 到 N，只要一个一个取，选择使 P(k) 最大的那个 k 就好了。更进一步，注意到：

从而：

因此 ∇P 是单调递减的，故 P(k) 一定会在某个 k 值达到最大值，随后一直下降²。换而言之，我们希望找到能满足条件 ∇P >= 0 的最大的 k：

因此对给定的 N，只要从 1/(N-1) 倒过来开始加，总和刚好大于等于 1 时，就得到所求的 k。这个算法被称为 Odds algorithm，使用 Python 实现只要几行：

def stop_time(N):
    if N <= 1:
        return 0
    S = 0
    while S < 1:
        S = S + 1 / (N - 1)
        N = N - 1
    return N
# [stop_time(i) for i in range(1, 21)]

更进一步，注意到 P(k) = S * k / N，简单改写一下就可以同时输出 k 和 P(k)：

def stop_time(N):
    S, k = 0, N
    if N <= 1:
        return (0, 1)
    while S < 1:
        S = S + 1 / (k - 1)
        k = k - 1
    return (k, S * k / N)
# [stop_time(i) for i in range(1, 21)]

可以看到 P(k) 随着 N 的增长一直下降，并且 N 趋于正无穷时 P(k) 似乎趋近 0.37，而且 k / N 也在 0.37 附近上下波动，这是巧合吗？

3. 无聊的分析

回顾微积分知识，我们可以使用积分近似代替调和级数的求和³：

直觉告诉我们，N 很大的时候，两者会非常接近，因此 ln N/k 会在 1 附近，故 k/N 会在 1/e = 0.36787944117144233… 附近上下波动，从而 P(k) = S * k / N = 1 * 1/e = 1/e。但是直觉毕竟只是直觉～

首先我们来证明，N <- N + 1 时使 P(k, N + 1) 最大的 k 不是 k 就是 k + 1。使用反证法，S >= 1 => S + 1/N > 1，因此不可能是比 k 小的数；而如果是 k + 2，根据上面的推论显然有：

故也不可能是比 k + 1 大的数。其次我们证明 P(k, N) >= P(k, N + 1)：

最后我们证明 P(k, N) > P(k + 1, N + 1)：

因此最大的 P(k) 随着 N 递增单调递减，而 P(k) 显然有下界 0。回顾微积分知识，单调有界数列必有极限，我们来尝试证明这个极限就是 1/e，首先留意到 S 和 P(k) 可以联系起来：

由几何均值不等式：

去根号求倒数，于是有：

当 N 趋于正无穷时，S 趋于 1，N - k 趋于正无穷，故 P 的极限为 S / e^S = 1/e，lim k / N = P / S = 1/e。上一节挖的坑终于填上了（苦笑）

证明的补充

虽然「当 N 趋于正无穷时，S 趋于 1，N - k 趋于正无穷」是显然的，但为了证明的完整性，还是有必要进行补充说明。首先我们可以证明 N > 2 时，N - k > k：

其次我们证明 N 趋于正无穷时，k 也趋于正无穷。还是使用放缩法，注意到 N > 4, N’ = 2N 的时候 k’ >= k + 1：

上面我们已经证明 N’ = N + 1 时，k’ 只能为 k 或者 k + 1，所以 k(N) 单调递增，当 N 趋于正无穷时，k 也趋于正无穷，而由 N > N - k > k，N - k 也趋于正无穷。

最后回顾数列极限的定义，要证明「当 N 趋于正无穷时，S 趋于 1」，等于证明「对任意的 ε，总存在一个 N，使得当 n > N 时 S - 1 < ε 总能成立」。对任意的 ε，我们总能找到一个正整数 k，使得 1/k < ε，并能找到 k 对应的一个 N，从而有：

因此对任意的 n > N，k(n) >= k，S = 1 + ε(n) < 1 + 1/k(n) <= 1 + 1/k < 1 + ε 总能成立，证毕。

4. 休息一下

看到这里你大概会觉得这篇文章快要结束了吧，毕竟问题得到了完美的解决（还开了透视锁头挂😂）。可惜的是，前面只是引子，正文才刚刚开始。

仔细回想一下，其实还有两个问题没有解决：

1. 这种策略是最优解吗？如果是，为什么？
2. 如果想不到这个算法，怎么办？

刷过算法题的人，看到「最」字，多少会意识到，很可能是动态规划题！

5. 最短路径问题

作为对动态规划的回顾，我们来重温最短路径问题。

得益于科技的进步，导航 App 的出现让我们不再迷路，并且能在没人指路的情况下顺利到达目的地。然而，你是否曾好奇，导航 App 里的最佳路线，是怎么算出来的呢？

如图所示，我们希望求从 A 点到 J 点的最短路径（所有权重加起来最小）。虽然不知道哪一条路径才是最短的，但是我们知道，如果这条最短的路径经过 G 点，那这条路径从 A 到 G 段，一定也是从 A 点到 G 点的最短路径。假如 f(X) 表示从 A 点到 X 点最短路径的总权重大小，那么：

因此我们可以从 A 点开始，一层一层计算下去，最后就能得到 A 点到 J 点的最短路径：

「导航正式开始！」

6. 应用到秘书问题

要使用动态规划解决问题，我们需要先确定所有可能的状态，并确定状态之间的联系，最后把问题分解为子问题开始处理。回顾上面的选择过程，可以看到所有的状态，由三个变量构成：

• 当前麦穗的序号 k
• 当前麦穗是否为（已经看到的所有麦穗中的）最好的麦穗
• 是否已经做出了选择

我们这里沿用 Venkat Anantharam 老师使用的记号，如果已作出选择，就记为 ∆，如果是最优，则记为 1，否则记为 0。于是在第 k 个麦穗时，一共有四种状态：

• (k, 1) 表示当前的第 k 个麦穗是目前最好的麦穗，且还没有作出选择；
• (k, 0) 表示当前的第 k 个麦穗并不是目前最好的麦穗，且还没有作出选择；
• (∆, k, 1) 表示当前是第 k 个麦穗，已经做出了选择，且 选择的麦穗是目前最好的麦穗；
• (∆, k, 0) 表示当前是第 k 个麦穗，已经做出了选择，且 选择的麦穗并不是目前最好的麦穗。

k = 1 时必然是最好的，故 (k, 0) 和 (∆, k, 0) 并不存在。

接下来我们确定状态之间的联系。

• 由于我们希望选到最好的麦穗，(k, 0) 时我们并不会做出选择，因此接下来的状态可能是 (k + 1, 0) 和 (k + 1, 1)。由于我们不知道所有麦穗的大小分布情况，k + 1 个麦穗中，最好的麦穗在前 k 个中的概率显然是 k / (k + 1)，因此转移到 (k + 1, 0) 的概率是 k / (k + 1)，转移到 (k + 1, 1) 的概率是 1 / (k + 1)。
• 而对于 (k, 1) 的情况，可以做出选择：做出选择会跳转到 (∆, k, 1)，不做出选择的话和 (k, 0) 一样，转移到 (k + 1, 0) 的概率是 k / (k + 1)，转移到 (k + 1, 1) 的概率是 1 / (k + 1)。
• (∆, k, 1) 也是类似，转移到 (∆, k + 1, 1) 的概率是 k / (k + 1)，转移到 (∆, k + 1, 0) 的概率是 1 / (k + 1)。
• (∆, k, 0) 显然是传递性的，因此只会转移到 (∆, k + 1, 0)。

我们以 N = 4 为例，画出示意图（部分转移概率未标出，使用蓝色和紫色表示此时可以做出选择或者不做）：

可以看到和上面的最短路径问题基本一致，虽然还是有点区别：

• 最短路径问题是最小化权重，选麦穗问题是最大化可能；
• 最短路径问题是确定的，选麦穗问题带有随机性，需要计算期望（均值）；
• 最短路径问题是正向的，选麦穗问题是反向进行的。

最后自然是各状态可能性大小的计算（从右到左反向进行），令 J(X) 表示在 X 状态下选到最好的麦穗的最大概率，则显然有：

因此只计算 J(k, 1) 与 J(k, 0) 就足够了，依然是分层计算：

竟然和 Odds algorithm 的结果完全一致！

7. 两个算法的等价性

没错，这两个算法确实是等价的，因此开头的策略，确实是使选到最好的麦穗概率最大化的最优策略。

首先显然 J(x, 0) 从 x = N 开始（倒过来看）是单调递增的，且最小值为 1/N，而 x / N （倒过来看）单调递减，且最后会降到 1/N，必然存在临界点 k，当 x <= k 时，x/N <= J(x, 0)，因此不作出选择；当 x > k 时，x/N > J(x, 0)，因此每次见到最好的麦穗都会做出选择。这和 Odds algorithm 对应的策略完全一致。

接下来我们来证明这个临界点 k 就是 Odds algorithm 里的 k。注意到：

因此：

Q.E.D.

8. 今回はここまで

本来打算 2 月 14 号写完的，🐦到了现在……

写正经的文章果然很累，不过 EE 真有意思，如果重新选专业大概会选 EE 吧～不过也是叶公好龙😂

8.1 历史与变形

这个选麦穗的故事有很多版本（苏格拉底与徒弟、禅师与失恋青年、……），还登上了小学语文教科书，但是真实性显然是无法考证的。根据 Thomas S. Ferguson 的 考证，最早有记载的「秘书问题」，是 1875 年 Cayley 给 Educational Times 投稿的一个数学问题：

有一种彩票玩法如下：每次可以取一把奖励大小不同的彩票，只能领取最后一张刮开的彩票的奖励。如果采用最优的策略，拿到奖励的期望是多少？

Cayley 使用了动态规划，并以 N = 4 为例进行了说明。此后这个问题出现了很多种不同的形式：

• 秘书问题：一位经理要从 N 位候选人中雇佣一位秘书，见面之后决定是否录用，拒绝了之后就不再召见了。经理要怎么做才能使得选中最好的一位的概率最大？
• 相亲问题
• 卖房问题：稍微进行了一点变形，房子卖出后立刻买入利率为 r% 的理财产品。可以使用动态规划解决。
• 群面问题：把所有面试者分成 N 组面试，只留下每一组的最优者，然后依次面试，拒绝后不再召见。被证明与秘书问题等价。
• ……

直到 2000 年，F. Thomas Bruss 研究「最后一次成功是第几次」（最优停时问题）的时候，Odds theorem 才被发现，并被应用到秘书问题上（秘书问题的“成功”，自然是超过前面的所有人）。

8.2 わたし、气になります！

欢迎来到随机控制（Stochastic control）与优化理论的世界！很多大学都有相应的课程，比如 Stanford EE365、MIT OCW、Berkeley EECS、ETH Zurich……

教材方面自然是厚厚两卷的 Dynamic Programming & Optimal Control by Dimitri P. Bertsekas。书里有非常多的习题，而且都很有意思，然而并没有解答😂（MIT OCW 上能找到一部分解答）。可惜 Dimitri P. Bertsekas 教授现在转教 Reinforcement learning 了……