问题：假设你是一位大龄男士，准备参加 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}\)。正如梅艳芳在《似是故人来》这首歌中唱的那样：“但凡未得到，但凡是过去，总是最登对” — 得不到的才是最好的。

倒向归纳法

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

我们从最后的情形开始分析，假设只剩下一位女士可选，那么你只能去和她结婚，而她的期望值是 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 的女士。因此有两位女士可选时这个策略的期望分数为 \[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)(\frac{1+a_i}{2})+a_i\cdot a_i=\frac{1+a_i^2}{2}.\] 结合初值 \(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。不过可以用归纳法证明 \(\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.9812084\)，\(\frac{N-1}{N+1}\approx 0.98019801\) 而 \(\frac{N}{N+1}=100/101\approx 0.99099099\)，可见 \(a_{100}\) 与 \(\frac{N-1}{N+1}\) 更接近。这印证了之前说过的：和你结婚的往往不是你最中意的那个。

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

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\)。

但它确实是用严格的测度语言重新表述了上面的相亲问题：\(\mathcal{F}_n=\{X_1,\ldots,X_n\}\) 是前 \(n\) 位女士的分数（这是 \(n\) 个独立的随机变量）生成的 \(\sigma-\) 域，它包含了所有你第 \(n\) 次相亲后可能知道的信息，\(\mathcal{F}_n\) 显然是递增的。你的一个相亲策略对应一个停时 \(\tau\)，所有相亲策略构成的集合就是 \(\mathcal{M}\)。

我们把倒向递归的方法也翻译成概率的语言：定义 \(\{X_n\}\) 的 Snell 包络为 \[S_n=\left\{\begin{array}{ll}X_N&n=N\\\max\{X_n,\mathbb{E}[S_{n+1}|\mathcal{F}_n]\}& n=N-1,\ldots,0.\end{array}\right.\] 这里的 \(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\) 时刻对最佳分数的估计。

注意这里的条件期望不可少，一般来说 \(\{X_n\}\) 之间不是独立的，根据前 \(n\) 个时刻获得的信息不同，你在 \(n+1\) 时刻对最佳收益的估计也可能不同。

设 \(\tau=\inf\,\{n:\, S_n=X_n\}\)，则 \(\tau\) 是停时。注意由于 \(S_N=X_N\)，因此 \(\tau\) 的定义合理且 \(0\leq\tau\leq N\)。\(\tau\) 的直观意义就是我们应该采取的最优停止策略：在 \(\tau\) 时刻，由于这时 \(n\) 号女士的分数 \(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-1}\geq \mathbb{E}[Y_n|\mathcal{F}_{n-1}] \geq \mathbb{E}[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\}\) 的关系，给式子中间塞进去两项，搭一座桥： \[ \mathbb{E}X_\tau = \mathbb{E}S_\tau \geq \mathbb{E}S_T\geq \mathbb{E}X_T.\] 注意第一个等号是根据 \(\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}\}\) 是一个鞅。

证明：\[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]\)。

既然如此，那么就有 \(\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.

上一篇：有限群的不可约实表示和复表示

下一篇：三质点弹簧系统的简正模式