相亲问题与倒向归纳法

问题：假设你是一位大龄男士，准备参加 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\limits_{1\leq i\leq N}X_i 的期望是 \frac{N}{N+1}。在我们的场景中 N=100，所以如果你把 100 次相亲全部进行完，得分最高的女士的期望值理论上应该是 \frac{100}{101}，于是你应该把心理门槛设置在 \frac{100}{101}，是这样吗？

答案是 NO！首先门槛值应该是一个随着相亲的进行而逐渐降低的数列，这才符合实际的情形：如果前面太挑剔，为了不当剩男你后面的标准就会放低。其次我们会用倒向归纳法计算出最优策略下初始的门槛值并不是最中意的女士的期望值 \frac{100}{101}，实际上它更接近于得分第二高的女士的期望值 \frac{99}{101}。这也和现实相符：和你结婚往往不是你最中意的那一个，这就是为什么有那么多婚外情的故事。（The story of the other woman）

倒向归纳法

相亲问题是应用倒向归纳法的一个典型例子。

我们从最后的情形开始分析，假设只剩下一位女士可选，那么你只能去和她结婚，而她的期望值是 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 的概率娶到一个期望值为 3/4 的女士，以 1/2 的概率娶到一个期望值为 1/2 的女士。因此有两位女士可选时这个策略的期望分数为

同理，假设还剩下 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_1=\frac{1}{2} 就可以算出整个序列来，因此我们的相亲策略应该是：

如果当前女士（假设编号为 i）的得分大于等于 a_{101-i}，那么就和她结婚；否则就继续去见下一位女士。这里序列 \{a_i\} 由 a_1=1/2，a_{i+1}=\frac{1+a_i^2}{2} 给出。

在这个策略下，你最终娶到的女士得分期望是 a_{100}。

序列 \{a_n\} 的通项公式是求不出来的，只能用计算机来算，这种序列叫做所谓的 Quadratic Map。不过可以估计出 a_{N} 的值小于最优女士的期望值 \frac{N}{N+1} 而且更接近于次优女士的期望值 \frac{N-1}{N+1}，这印证了之前说过的：和你结婚的往往不是你最中意的那个。

请注意，虽然我们已经设计出了一个不错的策略，但这个策略到底是不是最优的呢？我们还没有严格证明。而且就算这个策略是最优的，是否只有这一种最优策略呢？没准还有其它最优策略能让你更省时省心地娶到好太太呢！要严格的解释这些，就要用到鞅的理论。

FBI Warning: 接下来的内容要用到概率论中鞅的知识，这通常属于数学专业研究生阶段的内容。

转换为鞅的语言

问题：设 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。

 

定义 \{X_n\} 的 Snell 包络为

这里的 S_n 是从 N 开始倒向递归定义的。注意 S_n 关于 \mathcal{F}_n 可测。

S_n 的直观意义很好理解，就是在时刻 n 对最佳收益的估计：如果过程在当前时刻结束，那么收益就是 X_n；否则继续前进到下一个时刻 n+1，其期望收益是 \mathbb{E}[S_{n+1}|\mathcal{F}_n]（注意这里的条件期望不可少，一般来说 \{X_n\} 之间不是独立的，根据前 n 个时刻获得的信息不同，你在 n+1 时刻对最佳收益的估计也可能不同），二者取最大值即为 n 时刻对最佳收益的估计。

设 \tau=\inf\,\{n:\, S_n=X_n\}，则 \tau 是停时。注意由于 S_N=X_N，因此 \tau 的定义合理且 0\leq\tau\leq N。\tau 的直观意义就是我们应该采取的最优停止策略：每个时刻，用当前的 X_n 与未来的期望收益 \mathbb{E}[S_{n+1}|\mathcal{F}_n] 比较，见好就收。

定理 1：\{S_n\} 是控制 \{X_n\} 的最小上鞅。

证明：由 S_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\} 是一个上鞅。再结合 Y_{n-1}\geq X_{n-1} 便有 Y_{n-1}\geq S_{n-1}，这样递推下来就有 Y_n\geq S_n 对所有 n＝N,N-1,\ldots,0 成立。证毕。

那么怎么证明 \tau 确实是最优的停止策略呢？想法是这样的：设 T 是任意停时，我们要证明 \mathbb{E}X_\tau\geq \mathbb{E}X_T，为此我们利用 \{S_n\} 和 \{X_n\} 的关系，给式子中间塞进去两项，搭一座桥：

注意第一个等号是根据 \tau 的定义，最后一个不等号是根据定理 1。所以我们只要证明中间的不等号 \mathbb{E}S_\tau\geq \mathbb{E}S_T 即可。

我们已经知道 \{S_n\} 是一个上鞅，那么自然不管什么停时 T，统统都有 \mathbb{E}S_T\leq \mathbb{E}S_0。但是关于 \tau 我们可以说的更多：

定理 2：\{S_{n\wedge\tau}\} 是一个鞅。

证明：

对上式右边求条件期望，

这是因为如果 \tau>n 的话那么由 \tau 的定义 S_n=\mathbb{E}[S_{n+1}|\mathcal{F}_n]。

既然如此，那么就有 \mathbb{E}S_\tau=\mathbb{E}S_0，这样就证明了 \tau 的最优性：

定理 3：设 \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.

 

至此我们就从数学上严格的论证了为什么前面相亲问题中我们设计的策略是最优的。

如果你回顾一下上面的分析就会发现，我们实际上使用了 \tau 的两个性质：S_\tau=X_\tau和 \{S_{n\wedge\tau}\} 是鞅。这两个性质就保证了 \tau 是最优的停时。那么这是不是说明还有其它最优的策略呢？

定理 4：\nu\in\mathcal{M} 是最优停时的充要条件是： 1. S_\nu=X_\nu。 2. \{S_{n\wedge\nu}\} 是鞅。

定理的必要性告诉我们前面采用的 “见好就收” 策略是所有最优停时中最小的：设 \nu 是任一最优停时，则 \tau\leq\nu（回顾一下 \tau 的定义）。换句话说，我们之前设计的相亲策略是所有最优策略中时间成本最低的！

我们还可以给出最优停止策略中 “最大” 的一个来：

定理 5：设 S_n=M_n+A_n 是 \{S_n\} 的 Doob - Meyer 分解，其中 \{M_n\} 是鞅，A_n 是可料递增过程，定义

\tau_\max = \begin{cases}N & A_N=0,\\ \inf\{n\ |\ A_{n+1}>0\} & A_N>0.\end{cases}

则 \tau_\max 是所有最优停时中最大的。

 

定理 4，5 的证明都不难，这里就省略了。

参考文献

Risk-Neutral Valuation: Pricing and Hedging of Financial Derivatives. By Nicholas H. Bingham, Rüdiger Kiesel.