　　在赌博界，阿笨的策略（输了就把赌注翻倍）早就有了一个专门的名字，叫martingale。这个词同时也指一种马具，这两种意思的关系扑朔迷离，直到现在都没有定论（参见http://www.jehps.net/juin2009/Mansuy.pdf）。而在汉语中，这种策略就也照搬了马具的名字，叫做“鞅”。

　　作为赌博策略的“鞅”的概念，也被引进到了数学中，用来指一类随机过程。它有许多种不同程度的推广，在本文中，下面这种定义就足够了。

鞅是一种离散时间的随机过程 $X_0, X_1, X_2, \ldots$ ，满足：
★ $E(|X_t|) < \infty, \quad \forall\, t \ge 0$
★ $E(X_{t+1} - X_t|X_0, \ldots, X_t) = 0, \quad \forall\, t > 0, \forall\, X_0, \ldots, X_t$

　　用通俗的语言来解释一下这个定义。 X_t 可以看成是赌完局之后的赌本。第一条说的是，在任意有限时刻，赌本的绝对值的期望都是有限的。需要注意，这并不是说在任意时刻，赌本的绝对值的期望都要小于同一个界。事实上第一个条件基本是废话：赌完局之后只有有限种可能的结果，每种结果中赌本的绝对值都是有限的，期望当然也有限。

　　第二条说的是，不管前局结果如何，第 t+1 局赌完后，赌本的期望跟赌完局后相等。换句话说，就是不管前局结果如何，第 t+1 局的期望收益为0。注意“不管前局结果如何”这个条件是不能省略的，否则条件会变弱：假设硬币具有记忆，第1局赌完后，以后硬币永远是同一面朝上，那么整体来看每一局的期望收益确实为0，但给定第1局的结果之后，第2局的期望收益就不是0了。由 $E(X_{t+1} - X_t|X_0, \ldots, X_t) = 0$ 能够推出 $E(X_{t+1} - X_t) = 0$ ，但反之则不然。

　　在鞅的定义中，随机过程 $X_0, X_1, X_2, \ldots$ 是无限进行下去的，但我们研究的各种策略，都有停止条件。没关系，我们可以认为触发停止条件后，赌博仍在进行，只不过每局的赌注都是0，赌本不再变化而已。

　　显然，阿笨、阿聪、小白、大白的策略都满足“不管前局结果如何，第 t+1 局的期望收益为0”（因为硬币是均匀的嘛），所以，他们的赌本变化都是鞅。他们的初始赌本都是确定的，所以 X_0 是一个确定的数，而不是随机变量。容易证明，对于任意有限时刻，赌本的期望都等于初始赌本，即 $E(X_t) = X_0, \forall\, t > 0$ 。然而我们感兴趣的，是赌博停止时赌本的期望 E(X_T) ，其中停止时间是随机变量，且可能没有上界。 E(X_T) 可不能随随便便地说等于 X_0 。

　　鞅过程有一个停时定理。针对不同广度的鞅的定义，停时定理的叙述也有不同。其中维基百科英文版页面的叙述用到了filtration的概念，顺藤摸瓜下去很快就涉及了σ-algebra等等非常底层的数学概念，我也没有看懂。但是意大利语页面的叙述居然通俗易懂（哈哈，又一个会多种语言有什么好处的例子，尽管我其实并不会意大利语）。@Jack Diamond给出的一份英文讲义的第8页中，也有一样的通俗叙述，摘录如下：

鞅的停时定理：设是鞅过程的停止时间，则当下面三个条件之一成立时，有：
1. 几乎一定有界；
2. 赌注 $|X_{t+1} - X_t|$ 一致有界，且的期望有限；
3. 赌本一致有界，且几乎一定有限。

　　还是要解释一下定理中的术语。“几乎一定”，指的是概率为1，如果理解困难，可以忽略这个词组。“有限”指是的不能取无穷，但取多大都可以；“有界”比“有限”强一些，取值必须在一个有限的范围内，不能想多大就多大。“一致有界”指的是，不管取多少，赌注或者赌本必须在一个与无关的有限范围内。停时定理的三个条件，对 X_t 的要求越来越强，对停止时间的要求则越来越弱。“几乎一定有限”这个条件是最弱的：如果取无穷的概率非零，那么 E(X_T) 就无法定义了。

　　既然阿笨、阿聪、小白、大白的策略都是鞅，那么就来小试牛刀一下吧：

阿笨的策略（输则赌注翻倍），必然在有限局内结束，满足条件1。事实上，它满足全部三个条件。
小白的策略（赢到5则见好就收），可能进行任意多局，并不是有界的，不满足条件1。但上一篇中计算了，故满足条件2中的“的期望有限”，当然也满足条件3中的“几乎一定有限”。在方面，因为赌注一直为1，赌本最少为0，最多为5，所以“赌注一致有界”和“赌本一致有界”都成立。这样，小白策略就满足条件2和条件3。
大白的策略（三连胜则见好就收），跟小白策略一样不满足条件1。它也不满足条件3，因为“赢、赢、输”的循环可以无限进行下去，每次赌本加1，赌本做不到一致有界。条件2的前一半“赌注一致有界”是成立的，因为赌注始终为1，后一半“的期望有限”则需要检验。用上一篇文章中的递推法，加上这个隐藏条件，可以求出，的确是有限的，满足条件2。

阿聪的策略就复杂了。显然条件1不满足，所以需要寻找关于的条件。不满足条件3——因为一输一赢可以使赌本增加1块钱，赌本不一致有界。甚至都不满足条件2——赌本越多，阿聪就越有资本一输到底，而输的过程中赌注也在不断增加，并不一致有界。

　　我们又一次认识到，阿聪策略比大白策略更复杂，复杂到连鞅的停时定理都不能证明阿聪策略的期望收益为0。但是，鞅的停时定理，说的是“期望收益为0”的充分条件而不是必要条件，不满足这3个条件的情况下，期望收益也可能为0。阿聪策略，会不会正好属于这种情况呢？要如何放宽停时定理的条件，既能使得阿聪策略满足它们，又依然能得出期望收益为0呢？这个线索，要到停时定理的证明过程中去找。

　　前面说过，一个鞅过程在任意有限时刻的期望等于初始值： $E(X_t) = X_0, \forall\, t > 0$ 。这其实已经证明了条件1（有界）成立时的停时定理：只要把取为的上界就可以了，因为这样 X_T = X_t 。而当无界时， X_T 和 X_t 只有在 T>t 时才不同。把取得足够大， T>t 的概率就足够小，如果 X_T 和 X_t 的差距不大，那么 E(X_T) 和 E(X_t) 的差距就可以忽略。这正是证明条件2、3成立时的停时定理的思路。

　　先来推一下 E(X_T) 和 E(X_t) 的差距：

★ $E(X_T) - E(X_t) = P(T \le t) E(X_T - X_t | T \le t) + P(T > t) E(X_T - X_t | T > t)$

这里面，右边第一个期望为0，所以只需关注右边第二项。现在看条件3：“几乎一定有限”，说明随着的增大， P(T>t) 是趋于0的；而“赌本一致有界”，就说明了 E(X_T - X_t | T>t) 一致有界。这样， E(X_T) 和 E(X_t) 的差距随着的增大就趋于0，而 E(X_t) 一直等于 X_0 ，故 E(X_T) 也等于 X_0 。条件3的情形证毕。

　　与条件3相比，在条件2对 X_t 的要求“赌注一致有界”变弱了。这样就不再能把 E(X_T - X_t | T>t) 限制在一个固定范围内了，而只能把 $E(X_\tau - X_t)$ 限制在一个随 $\tau-t$ 线性增长的范围内，即 $|E(X_\tau - X_t)| \le C(\tau-t)$ ，为常数。我们来限定一下右边的第二项的范围。

$\begin{align} & |P(T>t) E(X_T - X_t | T>t)| \\ \le\,& P(T>t) \sum_{\tau = t+1}^\infty |E(X_\tau - X_t)| P(T = \tau | T>t) \\ =\,& \sum_{\tau = t+1}^\infty |E(X_\tau - X_t)| P(T = \tau) \\ \le\,& \sum_{\tau = t+1}^\infty C(\tau-t) P(T = \tau) \\ \le\,& C \sum_{\tau = t+1}^\infty \tau P(T = \tau) \end{align} \\$

条件2的另一部分“ E(T) 有限”，意思就是级数 $\sum_{\tau=1}^\infty \tau P(T=\tau)$ 收敛。而上式中的求和是这个级数的余项和，随着的增大是趋于0的。 E(X_T) 和 E(X_t) 的差距趋于0，故 E(X_T) = X_0 。

　　回顾一下条件2的证明过程，我们发现，“赌注一致有界”这个条件，可以放宽为“赌本线性增长”。阿聪的策略中，尽管赌注并不一致有界，但赌本确实是线性增长的——在“赢”的一端，由于赢的次数不能超过输的次数（否则游戏就结束了），赌本增长的最快方式也就是不停重复“一输一赢”的循环，而每次循环赌本固定增长1块钱；在“输”的一端，最终输光时欠的债也不会超过一次赌注，也就不会超过赌的总局数。这样就有 $|E(X_\tau)| \le C\tau$ ，上面的证明过程依然成立。

　　这样，要证明阿聪策略的期望收益为0，就只需证明停止时间的期望 E(T) 有限了。然而这个证明依然不简单，留待下回分解。

更新日志：

2015/12/15：经@玩儿的就是心跳归来指正，修改了鞅的停时定理的三个条件的顺序。

ITPub博客

10036 赌徒的长征(3)——鞅的停时定理

最新文章