相亲问题与倒向归纳法
问题： 假设你是一位大龄男士，准备参加 100 场相亲 （别介意具体数字）。你打算依次与每个女士 \(i\) 约会，然后根据印象给她打一个分数 \(X_i\)，\(X_i\) 的值介于 \([0,1]\) 之间。如果你对女士 \(i\) 很满意，那么就和她结婚，否则就放弃她，参加下一场相亲，当然拒绝了人家可就没有回头的机会了。如果你拒绝了前 99 位女士，那么不论第 100 次相亲结果如何你都只能和最后这位女士结婚。在相亲之前，你对这些女士的情况一无所知，所以姑且假定她们的分数 \(X_i\) 都是 \([0,1]\) 上均匀分布的独立的随机变量。问题是：应该采取怎样的相亲策略，才能娶到你最中意的女士？
再费点笔墨解释下。每次相亲结束以后，你可以选择和当前的女士结婚，或者继续见下一位女士，这依赖于你已经相亲的结果：如果你挑挑拣拣到了 90 号女士还拿不定主意，最后发现“糟了，我快要变剩男了！”，那很可能接下来你就会放低择偶标准，遇到一个还凑合的就结婚了，即使她比你前面拒绝过的很多女士都有不如。当然也不排除你对第一位女士就一见钟情的可能，因此你最终选择的女士的编号 \(\tau\) 是一个随机变量，你要做的就是让你的未来太太的期望分数 \(\mathbb{E}X_\tau\) 尽可能的高。
那么应该采取怎样的策略为好呢？就像买东西讨价还价时总有一个心理价位一样，似乎可以先设定一个心理的期望值，如果遇到的女士的分数大于等于这个值，那就和她结婚；否则就继续下一位女士。这个思路很合理，但是问题是，期望值应该设定为多少呢？
在概率论里面我们学过如下关于顺序统计量的经典结论：设 \(X_1,\cdots,X_N\) 是 \([0,1]\) 上独立同分布的均匀随机变量，则 \(Y=\max_{1\leq i\leq N}X_i\) 的期望是 \(\frac{N}{N+1}\)。所以如果你把 100 次相亲全部进行完，得分最高的女士的期望值理论上应该是 \(\frac{100}{101}\)，于是你应该把心理门槛设置在 \(\frac{100}{101}\)，是这样吗？
答案是 NO！首先门槛值应该是一个随着相亲的进行而逐渐降低的数列，这才符合实际的情形：如果前面太挑剔，为了不当剩男你后面的标准就会放低。其次我们会用倒向归纳法计算出最优策略下初始的门槛值并不是最中意的女士的期望值 \(\frac{100}{101}\)，实际上它更接近于得分第二高的女士的期望值 \(\frac{99}{101}\)。正如梅艳芳在《似是故人来》中唱的那样：“但凡未得到，但凡是过去，总是最登对” — 得不到的才是最好的。
倒向归纳法
相亲问题是应用倒向归纳法的一个典型例子。
我们从最后的情形开始分析，假设只剩一位女士可选，那么你只能去和她结婚，而她的期望值是 1/2，我们记作 \(a_1=1/2\)。
假设还剩两位女士可选呢？这种情况下应该先和其中一个相亲，如果她的分数大于等于 1/2，那就应该和她结婚 （后者的期望只有 1/2，很可能不如她），而小于 1/2 的话则去和第二位女士相亲 （后者的期望是 1/2，所以我没道理现在娶一个分数小于 1/2 的）。而第一位女士分数大于等于 1/2 的概率是 1/2，在大于等于 1/2 的条件下她的分数服从 \([1/2,1]\) 上的均匀分布，期望值是 3/4；第二位女士的期望分数就是 1/2。所以你以 1/2 的概率娶到一个期望值为 3/4 的女士，以 1/2 的概率娶到一个期望值为 1/2 的女士。因此有两位女士可选时这个策略的期望分数为 \[a_2=\frac{1}{2}\cdot\frac{3}{4}+\frac{1}{2}\cdot\frac{1}{2}=\frac{5}{8}.\]
一般地，假设还剩下 \(i\) 位女士的时候你的心理期望值是 \(a_i\)， 我们来导出 \(a_i\) 和 \(a_{i+1}\) 之间的递推关系：首先和其中一位女士相亲，如果她的分数大于等于 \(a_i\) 那么就和她结婚，否则就拒绝她 （因为后面 \(i\) 个人的心理期望是 \(a_i\)，我没道理现在娶一个分数小于 \(a_i\) 的）。前一种情形的期望是 \(\frac{1+a_i}{2}\) 但是发生的概率是 \(1-a_i\)，后一种情形的期望是 \(a_i\) 发生的概率也是 \(a_i\)，因此 \[a_{i+1}=(1-a_i)\left(\frac{1+a_i}{2}\right)+a_i\cdot a_i=\frac{1+a_i^2}{2}.\] 结合初值 \(a_1=\frac{1}{2}\) 就可以算出整个序列来，因此我们的相亲策略应该是：
假设当前还剩 \(i\) 位女士。就把心里期望设定在 \(a_i\)，然后进行一次相亲。如果相亲结果大于等于 \(a_i\)，那就和这位女士结婚；否则就把心里期望降低为 \(a_{i-1}\)，然后继续去见下一位女士。这里序列 \(\{a_i\}\) 由 \(a_1=1/2\)，\(a_{i+1}=\frac{1+a_i^2}{2}\) 给出。
在这个策略下，你最终娶到的女士得分期望是 \(a_{100}\)。
序列 \(\{a_n\}\) 是所谓的 Quadratic Map，它的通项公式是求不出来的，只能用计算机来算。不过可以用归纳法证明 \(\frac{N-1}{N+1}<a_{N}<\frac{N-0.5}{N+1}\)，即 \(a_N\) 的值更接近于次优女士的期望值 \(\frac{N-1}{N+1}\)。当 \(N=100\) 时，\(a_{100}\approx0.981\)，\(\frac{N-1}{N+1}\approx 0.98\) 而 \(\frac{N}{N+1}=100/101\approx 0.99\)，可见 \(a_{100}\) 与 \(\frac{N-1}{N+1}\) 更接近。这印证了之前说过的：和你结婚的往往不是你最中意的那个。
请注意，虽然我们已经设计出了一个不错的策略，但这个策略到底是不是最优的呢？我们还没有严格证明。而且就算这个策略是最优的，是否只有这一种最优策略呢？没准还有其它最优策略能让你更省时省心地娶到好太太呢！要严格的解释这些，就要用到鞅的理论。
翻译为鞅的语言
用鞅的语言重新表述上面的问题，会给人一种画风突变的感觉，看起来非常晦涩，不像是在说人话：
问题： 设 \(N\) 是一个给定的正整数，\(\{\mathcal{F}_n\}_{n=0}^N\) 是某概率空间上的递增的 \(\sigma\)- 域流，\(\{X_n\}_{n=0}^N\) 是一列可积的随机变量且 \(X_k\in\mathcal{F}_k\)。设 \(\mathcal{M}\) 是所有满足 \(0\leq\tau\leq N\) 的停时 \(\tau\) 组成的集合。我们想求出值函数 \[V= \sup_{\tau\in\mathcal{M}} \mathbb{E}X_\tau\] 以及使得这个最大值取到的停时 \(\tau\)。
这里我把下标改成了 从 0 开始到 \(N\)，以符合大多数文献的习惯。\(\mathcal{F}_n=\{X_0,\ldots,X_n\}\) 是前 \(n+1\) 位女士得分生成的 \(\sigma\)- 域，它包含了所有你第 \(n+1\) 次相亲后可能知道的信息。\(\mathcal{F}_n\) 显然是递增的。你的一个相亲策略对应一个停时 \(\tau\)，所有停时构成的集合 \(\mathcal{M}\) 就是你所有可能的策略。
定义 \(\{X_n\}\) 的 Snell 包络为 \[S_n=\begin{cases}X_N&n=N,\\\max\{X_n,\,\mathbb{E}[S_{n+1}|\mathcal{F}_n]\}& n=N-1,\ldots,0.\end{cases}\] 这里的 \(S_n\) 是从 \(N\) 开始倒向递归定义的。注意 \(S_n\) 关于 \(\mathcal{F}_n\) 可测。
\(S_n\) 的直观意义很好理解，它就是在时刻 \(n\) 对当下女士的分数和后面所有女士期望分数的比较：如果和当前的女士 \(n\) 结婚，那么分数就是 \(X_n\)；否则继续前进到下一个时刻 \(n+1\)，未来太太的期望分数就是 \(\mathbb{E}[S_{n+1}|\mathcal{F}_n]\)，二者取最大值 \(\max\{X_n,\mathbb{E}[S_{n+1}|\mathcal{F}_n]\}\) 即为 \(n\) 时刻对最佳分数的估计。注意这里 \(\mathbb{E}[S_{n+1}|\mathcal{F}_n]\) 要取条件期望，因为一般情况下 \(\{X_n\}\) 之间不是独立的，从而对未来最佳收益的估计依赖于历史信息。
在相亲问题中，\(\{X_n\}\) 是 \(\mathrm{i.i.d}\) 序列，\(S_{n+1}\) 与 \(\mathcal{F}_n\) 独立（你可以倒着从 \(S_N\) 开始验证 \(S_{n+1}\) 完全由 \(X_{n+1},\ldots,X_N\) 决定），从而 \(\mathbb{E}[S_{n+1}|\mathcal{F}_n]=\mathbb{E}S_{n+1}\)，所以
\[S_n=\begin{cases}X_N&n=N,\\\max\{X_n,\,\mathbb{E}S_{n+1}\}& n=N-1,\ldots,0.\end{cases}\]
记事件 \(A_n=\{X_n>\mathbb{E}S_{n+1}\}\)，于是序列 \(\{\mathbb{E}S_n\}\) 满足倒向递推关系 \[\mathbb{E}S_n=\mathbb{E}\max\{X_n,\,\mathbb{E}S_{n+1}\}=\mathbb{E}[X_n\mathrm{1}_{A_n}] + \mathbb{E}S_{n+1}\cdot(1-\mathbb{P}(A_n)).\] 这正是我们前一节中看到的递推关系。
设 \(\tau=\inf\,\{n:\, S_n=X_n\}\)，则 \(\tau\) 是停时。由于 \(S_N=X_N\)，因此 \(0\leq\tau\leq N\)。\(\tau\) 就是我们采取的相亲策略：在 \(\tau\) 时刻，由于这时 \(\max\{X_n,\mathbb{E}[S_{n+1}|\mathcal{F}_n]\}=X_n\)，即 \(n\) 号女士的分数 \(X_n\) 大于等于后面所有女士的期望分数 \(\mathbb{E}[S_{n+1}|\mathcal{F}_n]\)，剩下的相亲就不必再进行了。
到目前为止，我们已经把相亲问题完整地翻译成了鞅的语言。我们来证明 \(\tau\) 确实是最优策略。为此我们需要做一些准备：
定理 2.1. \(\{S_n\}\) 是控制 \(\{X_n\}\) 的最小上鞅。
证明：由 \(S_n=\max\{X_n,\mathbb{E}[S_{n+1}|\mathcal{F}_n]\}\) 直接可见 \(S_n\geq X_n\) 并且 \(\{S_n\}\) 是上鞅。设 \(\{Y_n\}\) 是任意满足 \(Y_n\geq X_n\) 的上鞅序列，我们要证明必有 \(Y_n\geq S_n\)。这只要从最后一项 \(n=N\) 开始逐项验证即可。由定义 \(Y_N\geq X_N=S_N\)，这一项没问题。假设 \(Y_n\geq S_n\)，两边对 \(\mathcal{F}_{n-1}\) 取条件期望可得 \[Y_{n-1}\geq \mathbb{E}[Y_n|\mathcal{F}_{n-1}] \geq \mathbb{E}[S_n|\mathcal{F}_{n-1}].\] 其中第一个不等号是根据上鞅的定义，第二个不等号是根据条件期望的单调性。再结合 \(Y_{n-1}\geq X_{n-1}\) 可得 \(Y_{n-1}\geq \max\{X_{n-1},\mathbb{E}[S_n|\mathcal{F}_{n-1}]\}=S_{n-1}\)，所以 \(n-1\) 项也没有问题。这样倒着向前递推即得结论成立。\(\blacksquare\)
定理 2.2. \(\{S_{n\wedge\tau}\}\) 是一个鞅。
证明：\[S_{(n+1)\wedge\tau}-S_{n\wedge\tau}=1_{\{\tau>n\}}(S_{n+1}-S_n).\]
对上式右边求条件期望： \[\mathbb{E}[1_{\{\tau>n\}}(S_{n+1}-S_n)|\mathcal{F}_n]=1_{\{\tau>n\}}\mathbb{E}[(S_{n+1}-S_n)|\mathcal{F}_n]=0.\]
这是因为如果 \(\tau>n\) 的话那么由 \(\tau\) 的定义 \(S_n=\mathbb{E}[S_{n+1}|\mathcal{F}_n]\)。\(\blacksquare\)
推论 2.3. \(\mathbb{E}X_\tau=\mathbb{E}S_0\)。
证明：注意 \(X_\tau=S_\tau\)，利用 \(0\leq\tau\leq N\) 和鞅性质即可： \[\mathbb{E}X_\tau=\mathbb{E}S_\tau=\mathbb{E}S_{\tau\wedge N}=\mathbb{E}S_{\tau\wedge0}=\mathbb{E}S_0.\] \(\blacksquare\)
定理 2.4. 设 \(\mathcal{M}\) 是所有满足 \(0\leq T\leq N\) 的停时 \(T\) 组成的集合，则 \(\tau\) 是其中最优的： \[\mathbb{E}S_0=\mathbb{E}X_\tau=\sup_{T\in\mathcal{M}}\mathbb{E}X_T.\]
证明：设 \(T\) 是任意停时，我们要证明 \(\mathbb{E}X_\tau\geq \mathbb{E}X_T\)。为此只要注意到 \[ \mathbb{E}X_\tau =\mathbb{E}S_0\geq \mathbb{E}S_T\geq \mathbb{E}X_T.\] 第一个等号是根据 推论 2.3，中间的不等号是因为 \(\{S_n\}\) 是上鞅，所以对任何停时 \(T\) 都有 \(\mathbb{E}S_T\leq \mathbb{E}S_0\)。最后的不等号是因为 \(S_n\) 控制 \(X_n\)。\(\blacksquare\)
至此我们就从数学上严格论证了前面的相亲策略确实是最优的。
回顾上面的分析，可以发现我们实际上使用了 \(\tau\) 的两个性质：\(S_\tau=X_\tau\) 和 \(\{S_{n\wedge\tau}\}\) 是鞅。这两个性质保证了 \(\tau\) 是最优策略。那这是不是说明还有其它最优的策略呢？
定理 2.5. \(\nu\in\mathcal{M}\) 是最优停时的充要条件是：
- \(S_\nu=X_\nu\)。
- \(\{S_{n\wedge\nu}\}\) 是鞅。
定理 2.5 告诉我们，前面采用的相亲策略是所有最优策略中时间成本最低的：即若 \(\nu\) 是任意最优停时，则 \(\tau\leq\nu\) （回顾一下 \(\tau\) 的定义）。
我们还可以给出最优策略中最大的一个来：
定理 2.6. 设 \(S_n=M_n-A_n\) 是 Snell 包络 \(\{S_n\}\) 的 Doob-Meyer 分解，其中 \(\{M_n\}\) 是鞅，\(A_n\) 是可料递增过程，由 \[A_n=\sum_{k=1}^n (S_{k-1}-\mathbb{E}[S_k|\mathcal{F}_{k-1}]) \] 给出。定义
\[ \tau_\max = \begin{cases} N & A_N=0,\\ \min\{n\geq0 \mid A_{n+1}>0\} & A_N>0. \end{cases} \]
则 \(\tau_\max\) 是所有最优停时中最大的。
这个策略在现实很有用，它是以最优方式行使美式期权的最大停时。
定理 2.5 和 定理 2.6 的证明都不难，这里就省略了。读者可以参考 (Bingham and Kiesel 2004, sec. 3.6)。
我猜某些读者可能会对 \(\tau_\max\) 对应的相亲策略感兴趣，因为这个策略有点渣男：它会在保证娶到最优女士的前提下和尽可能多的女士相亲。不过在 \(\{X_n\}\) 是 \(\mathrm{i.i.d}\) 的情形，你还是死了这份心吧。因为这时 \[A_n=\sum_{k=1}^n (S_{k-1}-\mathbb{E}S_k)=\sum_{k=1}^n\max\{X_{k-1}-\mathbb{E}S_k,0\}.\] 所以使得 \(A_{n+1}>0\) 成立的最小 \(n\) 正是使得 \(X_n>\mathbb{E}S_{n+1}\) 成立的最小 \(n\)，即使得 \(X_n=S_n\) 成立的最小 \(n\)。这不就是前面见好就收的策略 \(\tau\) 嘛！换句话说，在 \(\{X_n\}\) 是 \(\mathrm{i.i.d}\) 的情形，只有一种最优相亲策略！