第五章　随机过程与随机微积分（Stochastic Process and Stochastic Calculus）

量化学习 · 绿皮书

导出进度导入备份

本章目录

• 5.1　马尔可夫链（Markov Chain）
• 5.2　鞅与随机游走（Martingale and Random Walk）
• 5.3　动态规划（Dynamic Programming）
• 5.4　布朗运动与随机微积分（Brownian Motion and Stochastic Calculus）

本章讨论一些较为进阶的主题——马尔可夫链、随机游走、鞅与动态规划——这些内容通常不会出现在概率论的入门课程中。与基础概率论不同，这些工具或许不能算作量化面试的“标准必备知识”；但掌握随机过程与动态规划，能够简化很多面试题的解法，并在面试中形成一定优势。学会这些基础以后，你还会发现，许多面试题会从“需要灵机一动的谜题”变成“可以按方法系统求解的问题”。

5.1　马尔可夫链（Markov Chain）

马尔可夫链是一列随机变量 $X_0,X_1,\ldots,X_n,\ldots$，满足马尔可夫性质：给定当前状态后，未来状态与过去状态无关。也就是说，对任意 $n$，

$$P(X_{n+1}=j\mid X_n=i,X_{n-1}=i_{n-1},\ldots,X_0=i_0) =p_{ij} =P(X_{n+1}=j\mid X_n=i).$$

其中，$i$ 与 $j$ 是可能的状态。若状态空间为 $S=\{s_1,s_2,\ldots,s_M\}$，则一旦当前状态已知，过去的历史对未来就不再产生影响。

对于齐次马尔可夫链（homogeneous Markov chain），从状态 $i$ 转移到状态 $j$ 的概率与时间 $n$ 无关。具有 $M$ 个状态的马尔可夫链可用 $M\times M$ 的转移矩阵描述：

$$P=(p_{ij})= \begin{pmatrix} p_{11}&p_{12}&\cdots&p_{1M}\\ p_{21}&p_{22}&\cdots&p_{2M}\\ \vdots&\vdots&\ddots&\vdots\\ p_{M1}&p_{M2}&\cdots&p_{MM} \end{pmatrix},$$

其中 $p_{ij}$ 为从状态 $i$ 转移到状态 $j$ 的概率。

初始概率为

$$P(X_0=i),\qquad i=1,\ldots,M,\qquad \sum_i P(X_0=i)=1.$$

一条路径 $X_1=i_1,X_2=i_2,\ldots,X_n=i_n$（给定 $X_0=i_0$）的概率为

$$P(X_1=i_1,\ldots,X_n=i_n\mid X_0=i_0) =p_{i_0i_1}p_{i_1i_2}\cdots p_{i_{n-1}i_n}.$$

转移图（transition graph）常用来图形化表示转移矩阵：节点表示状态，边表示可能的转移，边上的数值表示相应的转移概率。

图5.1：一个四状态马尔可夫链的转移图与转移矩阵。

状态的分类（Classification of states）

若从状态 $i$ 出发，沿转移图中的有向路径可以到达状态 $j$，则称状态 $j$ 可由状态 $i$ 到达（accessible from $i$）。形式化地，若存在某个 $n$，使得 $p_{ij}^{(n)}>0$，则 $j$ 可由 $i$ 到达。令

$$T_{ij}=\min\{n:X_n=j\mid X_0=i\},$$

则当且仅当 $P(T_{ij}<\infty)>0$ 时，$j$ 可由 $i$ 到达。

若 $j$ 可由 $i$ 到达，且 $i$ 也可由 $j$ 到达，则称状态 $i,j$ 互通（communicate）。例如在图5.1中，状态1、2、3互通；状态4可由状态1到达，但状态1不能由状态4到达，因此状态1与4并不互通。

如果从状态 $i$ 出发，最终以概率1再次回到 $i$，则称 $i$ 为常返态（recurrent state）：

$$P(T_{ii}<\infty)=1.$$

若

$$P(T_{ii}<\infty)<1,$$

则称 $i$ 为暂态（transient state）。图5.1中的状态4是常返态；状态1、2、3都是暂态，因为从它们可以进入状态4，而从状态4无法回到1、2、3。

吸收马尔可夫链（Absorbing Markov chain）

如果一旦进入状态 $i$ 就不可能离开，即 $p_{ii}=1$ 且 $p_{ij}=0\ (j\ne i)$，则称 $i$ 为吸收态。若链中至少有一个吸收态，并且从任意状态出发都存在通往某个吸收态的路径，则称该马尔可夫链为吸收马尔可夫链。

在图5.1中，状态4是吸收态，因此该链是吸收马尔可夫链。

到达吸收态 $A$ 的概率方程。 设 $a_i$ 为从状态 $i$ 出发最终被吸收到状态 $A$ 的概率。对于吸收态，边界条件为：若 $i=A$，则 $a_i=1$；其他吸收态对应 $a_i=0$。对所有暂态，

$$a_i=\sum_j p_{ij}a_j.$$

这个方程可以理解为：先看下一步到达哪个状态，再对其后的吸收概率做全概率分解。

期望吸收时间方程。 设 $\mu_i$ 为从状态 $i$ 出发到达任意吸收态所需步数的期望。对于吸收态，$\mu_i=0$；对暂态，

$$\mu_i=1+\sum_j p_{ij}\mu_j.$$

这里额外的1表示走到下一状态所需的一步。

题目：赌徒破产问题（Gambler’s ruin problem）

玩家 $M$ 有1美元，玩家 $N$ 有2美元。每局游戏，胜者从败者处获得1美元。每一局 $M$ 以 $2/3$ 的概率获胜。游戏一直进行到其中一人破产为止。$M$ 最终获胜的概率是多少？

我的回答与笔记

查看解答⌄

马尔可夫链问题的关键通常在于选取合适的状态空间。一个自然的状态是记录 $M$ 的资金，因为总资金始终为3美元。于是状态空间可设为

$$S=\{0,1,2,3\},$$

其中状态 $m$ 表示 $M$ 拥有 $m$ 美元。状态0（$M$ 输光）与状态3（$M$ 赢得全部资金）都是吸收态。

图5.2：赌徒破产问题的转移图与转移矩阵。

初始状态为 $X_0=1$。在状态1时，下一步以 $1/3$ 的概率进入0，以 $2/3$ 的概率进入2；状态2同理，以 $1/3$ 的概率进入1，以 $2/3$ 的概率进入3。

令 $a_i$ 表示从状态 $i$ 出发最终到达吸收态3的概率。边界条件为

$$a_0=0,\qquad a_3=1.$$

对中间状态应用吸收概率方程：

$$\begin{aligned} a_1&=\frac13a_0+\frac23a_2,\\ a_2&=\frac13a_1+\frac23a_3. \end{aligned}$$

解得

$$a_1=\frac47,\qquad a_2=\frac67.$$

因此，从1美元起步时，玩家 $M$ 获胜的概率为

$$\boxed{\frac47}.$$

题目：骰子问题（Dice question）

两名玩家押注掷两枚标准六面骰子的点数和。玩家 $A$ 赌“先出现12点”；玩家 $B$ 赌“先出现连续两个7点”。两人不断重复掷两枚骰子，直到某一条件先发生。哪一方胜率更高？$A$ 获胜的概率是多少？

我的回答与笔记

查看解答⌄

这道题可以直接用条件概率处理，但用马尔可夫链会更系统。

先给出条件概率方法。设 $P(A)$ 为玩家 $A$ 获胜的概率，按第一次掷出的点数和分类。记 $F$ 为第一次的点数和，则只有三类结果：$F=12$、$F=7$、或 $F\notin\{7,12\}$。因此

$$P(A)=P(A\mid F=12)P(F=12)+P(A\mid F=7)P(F=7)+P(A\mid F\notin\{7,12\})P(F\notin\{7,12\}).$$

其中

$$P(F=12)=\frac1{36},\quad P(F=7)=\frac6{36},\quad P(F\notin\{7,12\})=\frac{29}{36}.$$

显然

$$P(A\mid F=12)=1,$$

而若第一次既不是7也不是12，局面与开局完全相同，所以

$$P(A\mid F\notin\{7,12\})=P(A).$$

若第一次为7，则再看第二次。第二次为12时 $A$ 获胜；第二次为7时 $B$ 立即获胜；第二次既非7也非12时，局面又回到开局。因此

$$P(A\mid F=7)=\frac1{36}+\frac{29}{36}P(A).$$

代回原式：

$$P(A)=\frac1{36}+\frac6{36}\left(\frac1{36}+\frac{29}{36}P(A)\right)+\frac{29}{36}P(A).$$

解得

$$\boxed{P(A)=\frac7{13}}.$$

再看马尔可夫链方法。设置四个状态：

• $S$：起始状态，最近一次不是7；
• $7$：最近一次为7；
• $7\!- \!7$：连续两个7，$B$ 获胜；
• $12$：出现12，$A$ 获胜。

后两个是吸收态。

图5.3：骰子问题的转移图及到达吸收态12的概率方程。

令 $a_S$ 为从起始状态最终到达吸收态12的概率，$a_{12}=1$、$a_{7-7}=0$。由一步转移可得

$$\begin{aligned} a_S&=\frac1{36}+\frac6{36}a_7+\frac{29}{36}a_S,\\ a_7&=\frac1{36}+\frac{29}{36}a_S. \end{aligned}$$

解得 $a_S=7/13$。因此玩家 $A$ 胜率更高，胜率为 $7/13$。

题目：硬币三连序列 A（Coin triplets, Part A）

连续抛一枚公平硬币。得到连续三个正面 $HHH$ 之前，所需抛掷次数的期望是多少？得到序列 $THH$ 之前，所需抛掷次数的期望又是多少？

我的回答与笔记

查看解答⌄

对于 $HHH$，取以下状态：

• $S$：起始状态，或最近一次出现 $T$；
• $H$：最近连续出现1个 $H$；
• $HH$：最近连续出现2个 $H$；
• $HHH$：吸收态。

达到序列 HHH 的状态转移图。

设 $\mu_S,\mu_H,\mu_{HH},\mu_{HHH}$ 为从各状态到吸收态所需抛掷次数的期望。则

$$\begin{aligned} \mu_S&=1+\frac12\mu_S+\frac12\mu_H,\\ \mu_H&=1+\frac12\mu_S+\frac12\mu_{HH},\\ \mu_{HH}&=1+\frac12\mu_S+\frac12\mu_{HHH},\\ \mu_{HHH}&=0. \end{aligned}$$

解得

$$\mu_S=14,\qquad \mu_H=12,\qquad \mu_{HH}=8.$$

因此得到 $HHH$ 的期望等待时间是

$$\boxed{14}.$$

对于 $THH$，可使用状态 $S,T,TH,THH$。若在状态 $T$ 再抛到 $T$，仍保留一个可作为模式开头的 $T$，因此继续停留在 $T$。状态方程为

$$\begin{aligned} \mu_S&=1+\frac12\mu_S+\frac12\mu_T,\\ \mu_T&=1+\frac12\mu_T+\frac12\mu_{TH},\\ \mu_{TH}&=1+\frac12\mu_S+\frac12\mu_{THH},\\ \mu_{THH}&=0. \end{aligned}$$

解得

$$\mu_S=8,\qquad \mu_T=4,\qquad \mu_{TH}=2.$$

所以得到 $THH$ 的期望等待时间为

$$\boxed{8}.$$

题目：硬币三连序列 B（Coin triplets, Part B）

持续抛一枚公平硬币，直到 $HHH$ 或 $THH$ 中某个序列先出现。哪一个序列先出现的概率更大？$HHH$ 先出现的概率是多少？

我的回答与笔记

查看解答⌄

可以建立马尔可夫链。只需记录与两个目标序列有关的“最长有效后缀”，可用状态

$$S,\ H,\ HH,\ T,\ TH,\ HHH,\ THH.$$

其中 $HHH$ 与 $THH$ 为两个吸收态。

图5.4：抛硬币直到 HHH 或 THH 出现的状态转移图。

令 $a_i$ 为从状态 $i$ 出发最终先到达 $HHH$ 的概率，边界条件为

$$a_{HHH}=1,\qquad a_{THH}=0.$$

由转移关系得到

$$\begin{aligned} a_S&=\frac12a_T+\frac12a_H,\\ a_T&=\frac12a_T+\frac12a_{TH},\\ a_H&=\frac12a_T+\frac12a_{HH},\\ a_{TH}&=\frac12a_T+\frac12a_{THH},\\ a_{HH}&=\frac12a_T+\frac12a_{HHH}. \end{aligned}$$

解得

$$\boxed{a_S=\frac18}.$$

因此 $HHH$ 先出现的概率只有 $1/8$，$THH$ 先出现的概率为 $7/8$。

这道题其实还有一个更简洁的观察：如果最终先出现的是 $HHH$，那么在它之前不能出现 $T$；因为一旦出现过某个 $T$，之后第一次出现连续两个 $H$ 时，$THH$ 会在 $HHH$ 之前完成。因此，$HHH$ 想获胜，整个序列只能从一开始就连续得到三个 $H$，概率正好是 $(1/2)^3=1/8$。

题目：硬币三连序列 C（Coin triplets, Part C）

现在把游戏改成：玩家1先选择一个长度为3的硬币序列，玩家2看到后选择另一个不同的长度为3的序列。随后连续抛公平硬币，谁的序列先出现谁获胜。若两人都完全理性并希望最大化自己的胜率，你愿意先选还是后选？若后选，最大胜率是多少？

我的回答与笔记

查看解答⌄

一个常见误区是认为，总存在某个“最强”的三连序列可以压过其他序列。这种想法往往来自错误的传递性假设：如果序列 $A$ 比 $B$ 更可能先出现，序列 $B$ 又比 $C$ 更可能先出现，并不意味着 $A$ 一定比 $C$ 更可能先出现。本游戏中并不存在这种传递性。

事实上，不论玩家1先选什么，玩家2总能选择一个胜率超过 $1/2$ 的响应序列。关键策略与上一问相同：利用玩家1序列的前两个字符与后缀重叠关系。

下面给出完整胜率表。行表示玩家2选择的序列，列表示玩家1选择的序列，表格中的数值为玩家2的胜率。

玩家2  玩家1	HHH	THH	HTH	HHT	TTH	THT	HTT	TTT
HHH	—	1/8	2/5	1/2	3/10	5/12	2/5	1/2
THH	7/8	—	1/2	3/4	1/3	1/2	1/2	3/5
HTH	3/5	1/2	—	1/3	3/8	1/2	1/2	7/12
HHT	1/2	1/4	2/3	—	1/2	5/8	2/3	7/10
TTH	7/10	2/3	5/8	1/2	—	2/3	1/4	1/2
THT	7/12	1/2	1/2	3/8	1/3	—	1/2	3/5
HTT	3/5	1/2	1/2	1/3	3/4	1/2	—	7/8
TTT	1/2	2/5	5/12	3/10	1/2	2/5	1/8	—

对玩家1来说，为了把玩家2能取得的最大胜率压到最低，最合理的选择是 $HTH$、$HTT$、$THH$ 或 $THT$。即便如此，玩家2仍然能取得

$$\boxed{\frac23}$$

的胜率。因此，理性玩家应选择后手。

原书同时指出，这一题较难；相关现象可参见 V. C. Hombas 的论文 Waiting Time and Expected Waiting Time—Paradoxical Situations（The American Statistician, Vol. 51, No. 2, May 1997, pp. 130–133）。本书这里只讨论直观思路。

题目：彩球同色（Color balls）

盒中有 $n$ 个球，初始时每个球颜色都不同。每一步随机选出一对球，把第一个球染成第二个球的颜色，再把这一对球放回盒中。问：直到所有球最终变成同一种颜色，所需步数的期望是多少？

我的回答与笔记

查看解答⌄

令 $N_n$ 为从 $n$ 个互不相同颜色的球开始，到所有球同色所需的步数。令 $F_i$ 表示最终所有球都变成颜色 $i$ 的事件。由全期望公式，

$$E[N_n]=\sum_{i=1}^{n}E[N_n\mid F_i]P(F_i).$$

由于颜色完全对称，$P(F_i)=1/n$，且各条件期望相同，因此只需计算例如 $E[N_n\mid F_1]$。

给定最终颜色是1，可以只记录当前有多少个球已经是颜色1。设状态 $i$ 表示有 $i$ 个颜色1的球，$i=1,2,\ldots,n$。状态 $n$ 是唯一吸收态。

图5.5：给定最终颜色为1时，颜色1球数的状态转移图。

令 $Z_i=E[N_n\mid X=i,F_1]$。为了得到条件转移概率，需要先算在 $F_1$ 条件下从 $i$ 到 $i\pm1$ 的概率。

由对称性，当前有 $i$ 个同色球时，各具体颜色成为最终颜色的概率与其当前球数成比例，因此

$$P(F_1\mid X=i)=\frac{i}{n}.$$

若不条件于 $F_1$，从状态 $i$ 到 $i-1$ 的概率是：第一个球来自这 $i$ 个颜色1球，第二个球来自其余 $n-i$ 个球，故

$$P(X_{t+1}=i-1\mid X_t=i)=\frac{i(n-i)}{n(n-1)}.$$

同理，

$$P(X_{t+1}=i+1\mid X_t=i)=\frac{(n-i)i}{n(n-1)}.$$

再应用贝叶斯公式，在给定最终到达颜色1的条件下可得

$$P_{i,i-1\mid F_1}=\frac{(i-1)(n-i)}{i(n-1)}, \qquad P_{i,i+1\mid F_1}=\frac{(n-i)(i+1)}{i(n-1)}.$$

其余概率对应停留在状态 $i$。于是期望吸收时间满足递推式

$$Z_i =1+Z_{i-1}P_{i,i-1\mid F_1}+Z_iP_{i,i\mid F_1}+Z_{i+1}P_{i,i+1\mid F_1},$$

整理为

$$(n-i)\,2i\,Z_i =n(n-1)+(n-i)(i+1)Z_{i+1}+(n-i)(i-1)Z_{i-1}.$$

配合边界条件 $Z_n=0$，可解得

$$\boxed{Z_i=(n-i)^2}.$$

初始时每种颜色只有一个球，即 $i=1$。因此

$$\boxed{E[N_n]=(n-1)^2}.$$

5.2　鞅与随机游走（Martingale and Random Walk）

随机游走（Random walk）

设 $\{X_i:i\ge 1\}$ 为独立同分布（IID）的随机变量序列，并令

$$S_n=X_1+\cdots+X_n,$$

则过程 $\{S_n:n\ge1\}$ 称为随机游走。这个名称来自把 $S_n$ 看作某个“行走者”在时刻 $n$ 的位置，其相邻时刻的位置由连续增量 $X_1,X_2,\ldots$ 决定。

若 $X_i$ 只取 $+1$ 与 $-1$，且概率分别为 $p$ 与 $1-p$，则 $S_n$ 是参数为 $p$ 的简单随机游走。进一步地，若 $p=1/2$，称为对称随机游走。对称随机游走中，

$$E[S_n]=0, \qquad \operatorname{var}(S_n)=E[S_n^2]-E[S_n]^2=E[S_n^2]=n.$$

对称随机游走是数量面试中经常出现的随机过程之一。题目常围绕：第一次达到某个阈值 $a$ 的时刻，或达到 $a$ 之前所需步数的概率与期望等。

鞅（Martingale）

随机过程 $\{Z_n:n\ge1\}$ 若满足

$$E[|Z_n|]<\infty,$$

且对所有 $n$，

$$E[Z_{n+1}\mid Z_n=z_n,Z_{n-1}=z_{n-1},\ldots,Z_1=z_1]=z_n,$$

则称其为鞅。更一般地，如果过程还依赖其他随机变量，可以把条件信息扩展为整个过去的信息集合；其含义仍是：在已知全部当前信息时，下一期的条件期望等于当前值，因此这个过程在条件期望意义下“没有趋势”。

对称随机游走本身就是鞅：

$$E[S_{n+1}\mid S_n]=S_n.$$

此外，

$$S_n^2-n$$

也是鞅。因为

$$E[S_{n+1}^2\mid S_n] =E[(S_n+X_{n+1})^2\mid S_n] =S_n^2+1,$$

故

$$E[S_{n+1}^2-(n+1)\mid S_n]=S_n^2-n.$$

停时（Stopping time）

对一列 IID 随机变量 $X_1,X_2,\ldots$，若一个正整数值随机变量 $N$ 满足：事件 $\{N=n\}$ 只依赖于 $X_1,\ldots,X_n$，而不依赖任何未来变量 $X_{n+1},X_{n+2},\ldots$，则称 $N$ 为停时。直观上，决定是否在时刻 $n$ 停止时，不能“偷看未来”。

Wald 等式（Wald’s Equality）

令 $N$ 为停时，并假设 $E[N]<\infty$。设

$$S_N=X_1+X_2+\cdots+X_N.$$

则在适当条件下，Wald 等式给出

$$\boxed{E[S_N]=E[X]E[N]}.$$

一个简洁的证明如下。令 $I_n$ 为事件 $\{N\ge n\}$ 的示性函数，则

$$S_N=\sum_{n=1}^{\infty}X_nI_n.$$

由于 $I_n$ 只由 $X_1,\ldots,X_{n-1}$ 决定，所以 $I_n$ 与 $X_n$ 独立。因此

$$E[X_nI_n]=E[X_n]E[I_n]=E[X]P(N\ge n).$$

于是

$$E[S_N] =\sum_{n=1}^{\infty}E[X_nI_n] =E[X]\sum_{n=1}^{\infty}P(N\ge n) =E[X]E[N].$$

另一个常用结论是：鞅在合适的停时处停止后，仍然保持鞅性质。本章后面的题目会多次利用这一点。

题目：醉汉走桥（Drunk man）

一个醉汉站在一座100米长的桥上，当前位置距离左端17米。每一步他都有50%的概率向前或向后移动1米。问：他先走到100米处而不是0米处的概率是多少？到达任一端点所需步数的期望是多少？

我的回答与笔记

查看解答⌄

这类问题在马尔可夫链里可以看作带两个吸收边界的随机游走。用鞅方法更简洁。

把当前位置平移，使初始点为0。则左端变为 $-17$，右端变为 $83$。令

$$S_n=X_1+\cdots+X_n,$$

其中 $X_i=\pm1$，各以概率 $1/2$ 取值。令 $N$ 为第一次到达 $-17$ 或 $83$ 的停时。对称随机游走的 $S_n$ 和 $S_n^2-n$ 都是鞅，因此在此停时上应用停止性质。

设

$$p=P(S_N=83),$$

则

$$P(S_N=-17)=1-p.$$

由 $E[S_N]=E[S_0]=0$，

$$83p-17(1-p)=0,$$

所以

$$\boxed{p=0.17}.$$

再由 $S_n^2-n$ 是鞅，

$$E[S_N^2-N]=E[S_0^2]=0.$$

因此

$$E[N]=E[S_N^2] =83^2\times0.17+17^2\times0.83.$$

原书在此处给出的数值是

$$\boxed{1441}.$$

需要注意：按上面的等式直接计算，结果为 $83\times17=1411$。因此原书此处的“1441”与其随后给出的通式 $E[N]=\alpha\beta$ 并不一致；本译文保留原书数值，同时标出这一算术差异。

更一般地，如果对称随机游走从0出发，在上边界 $\alpha>0$ 或下边界 $-\beta$（$\beta>0$）处停止，则

$$P(\text{先到 }\alpha)=\frac{\beta}{\alpha+\beta}, \qquad E[N]=\alpha\beta.$$

题目：骰子游戏（Dice game）

反复掷一枚公平六面骰。每次掷出的点数就是当次获得的金额；若掷出4、5或6，可以继续掷；一旦掷出1、2或3，游戏立即结束。问这场游戏的期望收益是多少？

我的回答与笔记

查看解答⌄

第四章曾用全期望公式求过这道题。这里用 Wald 等式。

每一次掷骰的点数期望为

$$E[X]=\frac{1+2+3+4+5+6}{6}=\frac72.$$

每次继续游戏的概率为 $1/2$，停止概率也是 $1/2$，因此总掷骰次数 $N$ 的期望为

$$E[N]=\frac{1}{1/2}=2.$$

于是由 Wald 等式，

$$E[S_N]=E[X]E[N]=\frac72\times2=\boxed{7}.$$

题目：售票队伍（Ticket line）

售票处前排着 $2n$ 个人，其中 $n$ 人只有5美元纸币，另外 $n$ 人只有10美元纸币。每个人购买一张5美元的票，售票员一开始没有零钱。问：随机排列这 $2n$ 个人时，所有人都能顺利买票且售票过程中从不出现找不开钱的概率是多少？

我的回答与笔记

查看解答⌄

把持5美元的人记为 $+1$，持10美元的人记为 $-1$。从原点出发，按队伍顺序做一条随机游走。售票员始终有足够零钱，当且仅当任意前缀中5美元人数不少于10美元人数，也就是随机游走在整个过程中从不低于0。

总共有

$$\binom{2n}{n}$$

条由 $n$ 个 $+1$ 和 $n$ 个 $-1$ 组成的路径。

要计算“坏路径”的数量，即至少一次到达 $-1$ 的路径。使用反射原理（reflection principle）：对一条第一次到达 $-1$ 的路径，在第一次到达 $-1$ 之后，把剩余路径关于直线 $y=-1$ 反射。这样得到一一对应的路径，其终点相当于把某个 $-1$ 变成 $+1$，因此坏路径的数量为

$$\binom{2n}{n-1}.$$

图5.6：反射原理。虚线为实线路径在第一次到达 −1 后的反射。

所以好路径数量为

$$\binom{2n}{n}-\binom{2n}{n-1}.$$

所求概率为

$$\frac{\binom{2n}{n}-\binom{2n}{n-1}}{\binom{2n}{n}} =\boxed{\frac1{n+1}}.$$

题目：连续正面序列（Coin sequence）

有一枚公平硬币。为了首次得到连续 $n$ 个正面，需要抛掷多少次？求其期望。

我的回答与笔记

查看解答⌄

设 $E[f(n)]$ 为首次出现连续 $n$ 个正面所需抛掷次数的期望。前几项容易求得：

$$E[f(1)]=2, \qquad E[f(2)]=6, \qquad E[f(3)]=14.$$

自然猜测

$$E[f(n)]=2^{n+1}-2.$$

下面用归纳思路证明。假设

$$E[f(n)]=2^{n+1}-2.$$

为了达到连续 $n+1$ 个正面，先花费期望 $E[f(n)]$ 次得到 $n$ 个连续正面。此后再抛一次：

• 以 $1/2$ 的概率得到正面，过程结束；
• 以 $1/2$ 的概率得到反面，此时前面的连续正面全部失效，回到起始状态，需要重新花费期望 $E[f(n+1)]$ 次。

因此

$$E[f(n+1)] =E[f(n)]+\frac12\cdot1+\frac12\bigl(1+E[f(n+1)]\bigr).$$

整理得

$$E[f(n+1)]=2E[f(n)]+2.$$

代入归纳假设，

$$E[f(n+1)]=2(2^{n+1}-2)+2=2^{n+2}-2.$$

于是

$$\boxed{E[f(n)]=2^{n+1}-2}.$$

原书还给出一个更一般的鞅方法，可以用于任意硬币序列的期望等待时间。

设赌局按如下方式进行：每个时刻都会有一名新赌徒带着1美元入场，并将全部资金依次押在某个给定目标序列的下一位上。每次押中，资金翻倍；押错则归零并退出。所有赌徒相互独立。

以目标序列 $HH\cdots H$（共 $n$ 个 $H$）为例。设在第 $i$ 次抛掷后，所有仍存活赌徒的总资金为 $x_i$，则

$$E[x_i-x_{i-1}]=0,$$

因此 $x_i-i$ 是鞅。令停时 $I$ 为目标序列首次出现的时刻。停下时，最后 $n$ 个入场的赌徒分别得到

$$2^n,2^{n-1},\ldots,2$$

的收益，所以总资金是

$$2+2^2+\cdots+2^n=2^{n+1}-2.$$

由停止后的鞅性质，

$$E[x_I-I]=0,$$

故

$$E[I]=2^{n+1}-2.$$

这个方法还可处理任意指定的硬币序列。原书举例：目标序列为 $HHTTHH$。假设该序列在第 $i$ 次抛掷时首次完成。最早参与并完整匹配6位序列的赌徒得到 $2^6$；第 $i-4$ 位进入的赌徒会在第二次下注时遇到 $HT$ 而输光；第 $i-3$ 与第 $i-2$ 位进入的赌徒第一下注就遇到 $T$ 而输光；第 $i-1$ 位进入的赌徒匹配到末尾的 $HH$，得到 $2^2$；第 $i$ 位进入的赌徒匹配最后一个 $H$，得到 $2^1$。因此

$$E[x_i-i]=2^6+2^2+2^1-E[i]=0,$$

从而

$$\boxed{E[i]=70}.$$

这里的核心思想是：某个目标模式首次出现时，仍然存活的赌徒正好对应于该模式与自身前缀之间的重叠结构；把这些存活赌徒的终值相加，就得到等待时间期望。

5.3　动态规划（Dynamic Programming）

动态规划（Dynamic Programming, DP）是一组用于求解序贯决策问题或多阶段决策问题的通用方法。它应用非常广泛，例如金融、供应链管理和航空排班等领域。虽然理论框架并不复杂，但真正掌握动态规划通常需要较强的数学基础与严密的逻辑，因此在研究生课程中往往被认为是较难的一类内容。

面试中遇到的动态规划问题通常比较基础，而且很多时候题目并不会明确告诉你“这是动态规划”。本节重点介绍动态规划的基本逻辑，并用几道面试题展示这种方法的核心思想与威力。

一个离散时间的动态规划模型通常包含两个基本组成部分。

1. 底层离散时间动态系统

动态规划问题总可以划分为若干阶段（stages），并在每个阶段做出决策。每个阶段都有与之对应的状态。当前阶段的决策会把系统从当前状态转移到下一阶段的某个状态；在某些状态下，如果只有一个选择，那么决策本身可能是平凡的。

假设问题共有 $N+1$ 个阶段，按惯例记为

$$0,1,\ldots,N-1,N.$$

在阶段 $k$（$0\le k\le N-1$）时，状态转移可以写成

$$x_{k+1}=f(x_k,u_k,w_k),$$

其中：

• $x_k$：阶段 $k$ 的系统状态；
• $u_k$：阶段 $k$ 选择的决策；
• $w_k$：随机参数，也称扰动（disturbance）。

基本思想是：下一阶段的状态 $x_{k+1}$ 由当前状态 $x_k$、当前决策 $u_k$ 与随机变量 $w_k$ 共同决定。我们在状态 $x_k$ 下从可行决策中选择 $u_k$；随机扰动 $w_k$ 的分布可能依赖于 $x_k$ 与 $u_k$。

2. 随时间可加的成本（或收益）函数

除最后一个阶段 $N$ 外，每个阶段都会产生阶段成本

$$g_k(x_k,u_k,w_k),$$

终端阶段的成本为 $g_N(x_N)$。因此总成本可以写成

$$g_N(x_N)+\sum_{k=0}^{N-1}g_k(x_k,u_k,w_k).$$

动态优化的目标，是选择一组策略（policy）

$$\pi^*=\{\mu_0^*,\ldots,\mu_{N-1}^*\}$$

来最小化期望成本，或者等价地最大化期望收益：

$$J_{\pi^*}(x_0) =\min_{\pi}E\left[g_N(x_N)+\sum_{k=0}^{N-1}g_k(x_k,u_k,w_k)\right].$$

动态规划算法（Dynamic programming algorithm）

动态规划的核心是最优性原理（Principle of Optimality）：如果从当前状态出发的一整套策略是最优的，那么从任意后续状态出发，它剩余部分的策略也必须对那个子问题最优。

因此，求解有限期动态规划问题时，通常从终点向前递推。

首先定义终端价值函数

$$J_N(x_N)=g_N(x_N).$$

随后对 $k=N-1,N-2,\ldots,0$，递推计算

$$J_k(x_k) =\min_{u_k} E\left[g_k(x_k,u_k,w_k)+J_{k+1}(f(x_k,u_k,w_k))\right].$$

最终的 $J_0(x_0)$ 就给出初始状态下的最优价值。

虽然这个公式看起来复杂，但实际做题时最关键的往往是两点：

1. 找到合适的状态变量；
2. 从终止状态往回倒推。

原书指出，本节只触及动态规划的表面。若希望系统学习现代动态规划，可参考 Dimitri P. Bertsekas 的 Dynamic Programming and Optimal Control。

题目：动态骰子游戏（Dice game）

你最多可以掷一枚公平六面骰3次。第一次或第二次掷完后，你可以选择：

• 立即停止，并获得当前这次掷出的点数对应的美元金额；
• 放弃当前点数，继续掷骰。

如果掷到第三次，则必须接受第三次的点数并结束游戏。问：最优策略是什么？游戏开始时的期望收益是多少？

我的回答与笔记

查看解答⌄

这是一个最简单的动态规划问题。关键是从最后一个阶段往前推。

第三次掷骰时已经没有选择，因此第三次的期望收益为

$$E[X_3]=\frac{1+2+3+4+5+6}{6}=3.5.$$

于是，在第二次掷骰后：

• 若点数为4、5、6，立即停止更好；
• 若点数为1、2、3，继续掷第三次更好。

因此从第二次掷骰前看，最优期望收益为

$$\frac36\times3.5+\frac16(4+5+6) =\frac{17}{4}=4.25.$$

再往前看第一次掷骰。第一次出现5或6时应立即停止；出现1、2、3、4时继续，因为继续的期望价值 $4.25$ 更高。于是初始期望收益为

$$\frac46\times4.25+\frac16(5+6) =\boxed{\frac{14}{3}}.$$

所以最优策略为：

• 第一次：5或6就停，否则继续；
• 第二次：4、5、6就停，否则继续；
• 第三次：必须接受。

题目：世界大赛下注（World series）

波士顿红袜队与科罗拉多洛矶队进行世界大赛决赛。系列赛最多7场，先赢4场者夺冠。你目前有100美元，并计划把资金押在红袜队上。遗憾的是，你只能逐场下注，不能直接下注整个系列赛。

假设每场比赛红袜与洛矶获胜的概率都是50%。问：怎样下注，才能保证如果红袜最终夺冠，你最终拥有200美元；如果红袜最终输掉系列赛，你最终拥有0美元？

我的回答与笔记

查看解答⌄

令状态 $(i,j)$ 表示红袜已经赢了 $i$ 场、洛矶已经赢了 $j$ 场。设

$$f(i,j)$$

为处在该状态时，为完成目标所需要的净财富价值。

终止边界很清楚：

• 若红袜先达到4胜，即状态 $(4,j)$，最终净收益应为 $+100$；
• 若洛矶先达到4胜，即状态 $(i,4)$，最终净收益应为 $-100$。

也就是说，系列赛结束时，起始100美元加上净收益 $f$ 后，要么得到200，要么得到0。

现在考虑某个非终止状态 $(i,j)$。如果下一场在红袜上下注 $y$ 美元，那么：

$$f(i+1,j)=f(i,j)+y,$$

而如果红袜输球，

$$f(i,j+1)=f(i,j)-y.$$

两式相加与相减得到

$$\boxed{ \begin{aligned} f(i,j)&=\frac{f(i+1,j)+f(i,j+1)}{2},\\ y&=\frac{f(i+1,j)-f(i,j+1)}{2}. \end{aligned}}$$

这正体现了动态规划的“从终点往回算”。例如

$$f(3,3)=\frac{f(4,3)+f(3,4)}{2} =\frac{100-100}{2}=0.$$

逐步倒推即可得到所有状态下的价值 $f(i,j)$，并进一步由

$$y=\frac{f(i+1,j)-f(i,j+1)}{2}$$

得到每个状态下一场应该下注的金额。

图5.7：各系列赛状态对应的价值与下注金额。

如果更习惯树状表示，也可以把同一递推过程画成二叉树：每走一步，红袜胜场数或洛矶胜场数增加1。

图5.8：世界大赛状态价值的二叉树表示。

原书进一步指出：如果把边界值看成衍生品到期收益，把每一步的胜负看作标的资产的上/下变动，那么这一结构与二叉树定价非常接近；每一步的下注额对应动态对冲中的 delta。欧洲期权与美式期权都可以用类似的动态规划方法进行数值求解。

题目：无限次数骰子游戏（Dynamic dice game）

赌场设计了一个骰子游戏。你可以不限次数地掷一枚公平六面骰。每次掷骰后：

• 掷出1：赢1美元；
• 掷出2：赢2美元；
• 掷出5：赢5美元；
• 掷出6：此前累积的所有奖金全部损失，游戏结束；
• 掷出3或4：既不增加也不减少奖金。

在每次掷骰之后，如果点数是1–5，你都可以选择停止并领取当前累积奖金，或者继续掷。假设你风险中性，最多愿意支付多少钱来玩这场游戏？

我的回答与笔记

查看解答⌄

设当前已累积 $n$ 美元，记继续玩下去的最优期望价值为 $E[f(n)]$。在该状态下，如果再掷一次，则下一次之后的奖金分别是

$$n+1,n+2,n+3,n+4,n+5,0,$$

每种概率都是 $1/6$。因此，如果决定继续，下一次掷骰后的期望“当前奖金”是

$$\frac16(n+1)+\frac16(n+2)+\frac16(n+3)+\frac16(n+4)+\frac16(n+5)+\frac16\cdot0 =\frac56n+2.5.$$

当

$$\frac56n+2.5>n$$

时，直觉上继续值得；这等价于 $n<15$。原书据此指出，当累积金额超过约14美元时应停止，继续掷骰的价值不再高于立即退出。

对于低于停止阈值的状态，最优价值满足

$$E[f(n)] =\frac16\sum_{i=1}^{6}E[f(n+i)],$$

其中在越过停止区域后，$E[f(m)]$ 就等于立即停止所得的 $m$。从高状态向低状态递推，可得到原书表5.2中的数值。

$n$	19	18	17	16	15	14	13	12	11	10
$E[f(n)]$	19.00	18.00	17.00	16.00	15.00	14.17	13.36	12.59	11.85	11.16

$n$	9	8	7	6	5	4	3	2	1	0
$E[f(n)]$	10.52	9.91	9.34	8.80	8.29	7.81	7.36	6.93	6.53	6.15

因此在一开始 $n=0$ 时，游戏的最优期望价值为

$$\boxed{E[f(0)]\approx 6.15}.$$

所以风险中性玩家最多愿意支付约6.15美元参加游戏。

题目：动态扑克牌游戏（Dynamic card game）

使用一副标准52张扑克牌，其中26张红牌、26张黑牌。牌充分洗匀后，庄家逐张翻牌，翻出的牌不放回。你可以在任意时刻要求庄家停止。

每翻出一张红牌，你获得1美元；每翻出一张黑牌，你损失1美元。问：最优停止策略是什么？这场游戏最多值多少钱？

我的回答与笔记

查看解答⌄

这是一个标准的动态规划最优停止问题。

设 $(b,r)$ 表示牌堆中还剩 $b$ 张黑牌与 $r$ 张红牌。已经翻出的牌中，红牌数减去黑牌数等于

$$(26-r)-(26-b)=b-r.$$

因此，如果此刻立即停止，收益是

$$b-r.$$

如果继续翻下一张牌：

• 以 $b/(b+r)$ 的概率翻到黑牌，状态变为 $(b-1,r)$；
• 以 $r/(b+r)$ 的概率翻到红牌，状态变为 $(b,r-1)$。

设 $E[f(b,r)]$ 是状态 $(b,r)$ 的最优期望收益，则 Bellman 方程为

$$\boxed{ E[f(b,r)] = \max\left\{ b-r, \frac{b}{b+r}E[f(b-1,r)] + \frac{r}{b+r}E[f(b,r-1)] \right\}. }$$

边界条件为

$$f(0,r)=r, \qquad f(b,0)=b,$$

并且当 $b-r$ 已经大于等于继续游戏的期望价值时就应停止，否则继续。

从边界开始递推所有 $(b,r)$ 状态，可得到原书图5.9给出的完整价值表。

图5.9：不同剩余黑牌数 $b$ 与红牌数 $r$ 下的最优期望收益。

初始状态为 $(26,26)$。原书给出的结果是

$$\boxed{E[f(26,26)]\approx 2.62}.$$

因此这场游戏在最优停止策略下的价值约为2.62美元。

原书指出，这个递推结构与美式期权定价中的“立即执行价值 vs. 继续持有价值”非常相似；本质上每一步都在比较这两种选择。

5.4　布朗运动与随机微积分（Brownian Motion and Stochastic Calculus）

本节简要讨论随机微积分中的一些问题。它可以看作连续空间随机过程的对应理论。由于布朗运动和随机微积分的基本定义、性质与定理本身就经常直接以面试题的形式出现，原书并没有先单独列出一套完整定义，而是把这些知识穿插到问题与解答中。

布朗运动（Brownian motion）

题目：布朗运动的定义与性质（Brownian motion A）

定义布朗运动，并列举它的一些性质。

我的回答与笔记

查看解答⌄

这是最基础的布朗运动问题之一。原书特别提醒：像 $W(0)=0$ 这样的定义细节，往往因为看起来太显然而容易漏掉。

一个连续随机过程 $W(t),\ t\ge0$ 若满足以下条件，则称为布朗运动（Brownian motion，也称 Wiener process）：

1. 初始条件

$$W(0)=0.$$

2. 独立增量：对于

$$0\le t_1\le t_2\le\cdots\le t_n,$$

随机变量

$$W(t_1)-W(0),\quad W(t_2)-W(t_1),\quad\ldots,\quad W(t_n)-W(t_{n-1})$$

相互独立。

3. 正态增量：

$$W(t_{i+1})-W(t_i)\sim N(0,t_{i+1}-t_i).$$

由此可得到常用性质：

• 路径连续，没有跳跃；
• $E[W(t)]=0$；
• $E[W(t)^2]=t$；
• $W(t)\sim N(0,t)$；
• 鞅性质：

$$E[W(t+s)\mid W(t)]=W(t);$$

• 对 $0<s<t$，

$$\operatorname{cov}(W(s),W(t))=s;$$

• 满足连续时间版本的马尔可夫性质。

与布朗运动密切相关的两个重要鞅为：

$$Y(t)=W(t)^2-t,$$

以及指数鞅

$$Z(t)=\exp\left\{\lambda W(t)-\frac12\lambda^2t\right\},$$

其中 $\lambda$ 为任意常数。

原书在后文利用 Itô 引理证明第一个鞅。指数鞅可用正态分布的矩母函数直接验证。利用独立增量，

$$W(t+s)=W(t)+[W(t+s)-W(t)],$$

其中增量服从 $N(0,s)$ 且与 $W(t)$ 独立。于是

$$\begin{aligned} E[Z(t+s)\mid\mathcal F_t] &=\exp\left\{\lambda W(t)-\frac12\lambda^2t\right\} \exp\left\{-\frac12\lambda^2s\right\} E\left[e^{\lambda (W(t+s)-W(t))}\right]\\ &=Z(t)\exp\left\{-\frac12\lambda^2s\right\} \exp\left\{\frac12\lambda^2s\right\}\\ &=Z(t). \end{aligned}$$

因此指数过程确实是鞅。

原书在本节中交替使用 $B_t$ 与 $W(t)$ 来表示布朗运动，以便读者熟悉两种常见记号。

题目：布朗运动与其平方的相关系数（Brownian motion B）

布朗运动 $B_t$ 与它的平方 $B_t^2$ 的相关系数是多少？

我的回答与笔记

查看解答⌄

在固定时刻 $t$，

$$B_t\sim N(0,t).$$

由于正态分布关于0对称，

$$E[B_t]=0, \qquad E[B_t^3]=0.$$

因此

$$\operatorname{Cov}(B_t,B_t^2) =E[B_t^3]-E[B_t]E[B_t^2] =0.$$

所以其相关系数也为

$$\boxed{0}.$$

题目：$P(B_1>0,B_2<0)$（Brownian motion C）

设 $B_t$ 为布朗运动。求

$$P(B_1>0,\ B_2<0).$$

我的回答与笔记

查看解答⌄

标准方法利用

$$B_1\sim N(0,1), \qquad B_2-B_1\sim N(0,1),$$

且 $B_1$ 与 $B_2-B_1$ 相互独立。

如果 $B_1=x>0$，要让 $B_2<0$，就必须满足

$$B_2-B_1<-x.$$

直接积分可以写成

$$P(B_1>0,B_2<0) = \int_0^\infty\frac{1}{\sqrt{2\pi}}e^{-x^2/2} \int_{-\infty}^{-x}\frac{1}{\sqrt{2\pi}}e^{-y^2/2}\,dy\,dx.$$

利用极坐标积分，原书得到

$$\boxed{P(B_1>0,B_2<0)=\frac18}.$$

其实无需真正做积分。由于 $B_1$ 与 $B_2-B_1$ 是两个独立同分布的标准正态变量，平面被直线

$$x=0,\quad y=0,\quad y=x,\quad y=-x$$

分成8个对称区域，每个区域的联合密度概率质量相同。所求事件正好对应其中一个区域，因此概率是 $1/8$。

也可以写成直观的条件概率分解：

$$P(B_1>0,B_2<0) =P(B_1>0)P(B_2-B_1<0)P(|B_2-B_1|>|B_1|) =\frac12\times\frac12\times\frac12 =\frac18.$$

图5.10：$(B_1,B_2-B_1)$ 的联合密度及其对称区域。

停时／首达时间（Stopping time / first passage time）

题目：首次到达 $-1$ 或 $1$ 的平均时间（Stopping time A）

标准布朗运动从0出发，首次到达 $-1$ 或 $1$ 的停时，其期望是多少？

我的回答与笔记

查看解答⌄

已知

$$B_t^2-t$$

是鞅。用 Itô 引理可以验证：

$$\begin{aligned} d(B_t^2-t) &=2B_t\,dB_t-dt+dt\\ &=2B_t\,dB_t, \end{aligned}$$

因此没有漂移项。

令

$$T=\inf\{t:B_t=1\text{ 或 }B_t=-1\}.$$

在满足适当条件时，停止后的鞅仍然是鞅，所以

$$E[B_T^2-T]=E[B_0^2]=0.$$

而布朗运动最终以概率1到达 $1$ 或 $-1$，因此

$$B_T^2=1.$$

所以

$$\boxed{E[T]=1}.$$

题目：布朗运动的首达时间分布（Stopping time B）

设 $W(t)$ 是标准 Wiener 过程，$x>0$。定义首次到达水平 $x$ 的时间

$$\tau_x=\inf\{t:W(t)=x\}.$$

求 $\tau_x$ 的概率密度函数，并求 $E[\tau_x]$。

我的回答与笔记

查看解答⌄

这是一道经典的反射原理问题。

对任何在时刻 $t$ 之前到达过 $x$ 的路径，如果它在时刻 $t$ 位于 $x$ 上方，则把首次到达 $x$ 之后的路径关于水平线 $x$ 反射，就得到一条在时刻 $t$ 位于 $x$ 下方的等概率路径。因此

$$P(\tau_x\le t) =2P(W(t)\ge x).$$

由于 $W(t)\sim N(0,t)$，

$$P(\tau_x\le t) =2\int_x^\infty\frac{1}{\sqrt{2\pi t}}e^{-w^2/(2t)}\,dw.$$

令 $v=w/\sqrt t$，得到

$$P(\tau_x\le t) =2\int_{x/\sqrt t}^{\infty}\frac1{\sqrt{2\pi}}e^{-v^2/2}\,dv =2-2\Phi\left(\frac{x}{\sqrt t}\right),$$

其中 $\Phi$ 为标准正态分布的累积分布函数。

对 $t$ 求导得到密度

$$\boxed{ f_{\tau_x}(t) =\frac{x}{\sqrt{2\pi}}t^{-3/2}\exp\left(-\frac{x^2}{2t}\right), \qquad t>0. }$$

图5.11：标准 Wiener 过程的一条样本路径及其在首次到达水平 $x$ 后的反射路径。

虽然

$$P(\tau_x<\infty)=1,$$

但其期望却是无穷大：

$$\boxed{E[\tau_x]=\infty}.$$

原书用前一问作直观说明：到达单边界 $x$ 可以看作到达 $x$ 或一个不断向 $-\infty$ 移动的负边界；双边界问题中期望停时为 $\alpha\beta$，当负边界的绝对值趋于无穷时，期望也趋于无穷。

题目：先到3还是先到−5（Stopping time C）

设 $X$ 是无漂移布朗运动，即

$$dX(t)=dW(t),$$

且 $X(0)=0$。问：它先到达3而不是−5的概率是多少？如果过程带漂移 $m$，即

$$dX(t)=m\,dt+dW(t),$$

结果又是多少？

我的回答与笔记

查看解答⌄

先看无漂移情形。布朗运动本身是鞅。设

$$p_3=P(\text{先到 }3\text{ 而不是 }-5).$$

停止时 $X_T$ 只能等于3或−5。由停止后的鞅性质，

$$E[X_T]=0,$$

因此

$$3p_3-5(1-p_3)=0.$$

解得

$$\boxed{p_3=\frac58}.$$

更一般地，对于无漂移布朗运动，若上边界为 $\alpha>0$、下边界为 $-\beta$（$\beta>0$），从0出发，则

$$P(\text{先到 }\alpha)=\frac{\beta}{\alpha+\beta},$$

且到任一边界的期望时间为

$$E[T]=\alpha\beta.$$

现在考虑带漂移过程

$$dX=m\,dt+dW.$$

此时 $X$ 不再是鞅，但仍然是马尔可夫过程。令 $P(x)$ 表示从当前位置 $x\in(-5,3)$ 出发先到3而不是−5的概率。由 Feynman–Kac 方程，$P$ 满足

$$mP'(x)+\frac12P''(x)=0, \qquad -5<x<3,$$

边界条件为

$$P(3)=1, \qquad P(-5)=0.$$

特征根为

$$r_1=0, \qquad r_2=-2m,$$

因此一般解为

$$P(x)=c_1+c_2e^{-2mx}.$$

代入边界条件可得

$$\boxed{ P(0)=\frac{e^{10m}-1}{e^{10m}-e^{-6m}}. }$$

原书还给出了更简洁的指数鞅方法。注意

$$W(t)=X(t)-mt$$

是标准布朗运动，因此

$$Z(t)=\exp\left\{\lambda W(t)-\frac12\lambda^2t\right\}$$

是鞅。取 $\lambda=-2m$，时间项恰好消去，得到

$$E[e^{-2mX_T}]=1.$$

于是若 $P_3$ 表示先到3的概率，

$$P_3e^{-6m}+(1-P_3)e^{10m}=1,$$

解得与上式相同的结果。

题目：带正漂移的过程是否会到达−1（Stopping time D）

设

$$dX=dt+dW(t),$$

其中 $W(t)$ 为布朗运动，且从 $X(0)=0$ 出发。问：$X$ 在未来某个时刻到达 $-1$ 的概率是多少？

我的回答与笔记

查看解答⌄

利用上一问中的指数鞅结果，令漂移 $m=1$，则

$$E[e^{-2X_T}]=1.$$

这里只有一个显式负边界 $-1$。为了把问题写成双边界停时，可把正边界取为 $+\infty$。设 $P_{-1}$ 为最终到达 $-1$ 的概率，则在负边界上

$$e^{-2(-1)}=e^2,$$

而沿正方向趋于 $+\infty$ 时

$$e^{-2X}\to0.$$

因此

$$P_{-1}e^2+(1-P_{-1})\cdot0=1.$$

所以

$$\boxed{P_{-1}=e^{-2}}.$$

Itô 引理（Itô’s lemma）

Itô 引理是普通微积分链式法则在随机微积分中的对应形式。

设 $X(t)$ 是一个 Itô 过程：

$$dX(t)=\beta(t,X)\,dt+\gamma(t,X)\,dW(t),$$

并且 $f(X(t),t)$ 对 $X$ 和 $t$ 二阶可微。则

$$\boxed{ df =\left( \frac{\partial f}{\partial t} +\beta(t,X)\frac{\partial f}{\partial x} +\frac12\gamma^2(t,X)\frac{\partial^2f}{\partial x^2} \right)dt +\gamma(t,X)\frac{\partial f}{\partial x}\,dW(t). }$$

其中漂移项为

$$\frac{\partial f}{\partial t} +\beta(t,X)\frac{\partial f}{\partial x} +\frac12\gamma^2(t,X)\frac{\partial^2f}{\partial x^2}.$$

对于一个广义 Wiener 过程

$$dX=a(x,t)dt+b(x,t)dW(t),$$

若过程本身要成为鞅，其漂移系数必须为0；同样地，对 $f(X,t)$ 来说，Itô 展开中的漂移项为0是其成为局部鞅的关键条件。

题目：$Z_t=\sqrt t\,B_t$ 是否为鞅（Itô A）

令 $B_t$ 为布朗运动，定义

$$Z_t=\sqrt t\,B_t.$$

求 $Z_t$ 的均值与方差，并判断 $Z_t$ 是否为鞅。

我的回答与笔记

查看解答⌄

在时刻 $t$，

$$B_t\sim N(0,t).$$

因此

$$Z_t=\sqrt t\,B_t \sim N(0,t^2).$$

所以

$$\boxed{E[Z_t]=0}, \qquad \boxed{\operatorname{Var}(Z_t)=t^2}.$$

虽然对每个固定 $t$，无条件期望都为0，但这并不能推出它是鞅。

对

$$Z(t,B)=\sqrt t\,B$$

应用 Itô 引理：

$$\frac{\partial Z}{\partial B}=\sqrt t, \qquad \frac{\partial Z}{\partial t}=\frac12t^{-1/2}B, \qquad \frac{\partial^2Z}{\partial B^2}=0.$$

因此

$$dZ_t =\frac12t^{-1/2}B_t\,dt+\sqrt t\,dB_t.$$

除 $B_t=0$ 外，漂移项一般不为0；而 $B_t\neq0$ 几乎处处成立。因此

$$\boxed{Z_t=\sqrt t\,B_t\text{ 不是鞅}}.$$

题目：$W(t)^3$ 是否为鞅（Itô B）

令 $W(t)$ 为布朗运动。过程

$$W(t)^3$$

是否为鞅？

我的回答与笔记

查看解答⌄

取

$$f(W,t)=W^3.$$

则

$$\frac{\partial f}{\partial W}=3W^2, \qquad \frac{\partial^2f}{\partial W^2}=6W, \qquad \frac{\partial f}{\partial t}=0.$$

由 Itô 引理，

$$d(W^3) =3W^2\,dW+\frac12\cdot6W\,dt =3W^2\,dW+3W\,dt.$$

漂移项为

$$3W\,dt,$$

通常不为0，因此

$$\boxed{W(t)^3\text{ 不是鞅}}.$$

掌握状态与复习

关掉资料独立完成后记 A；提示后完成记 B；需要重学记 C。

A · 独立完成B · 提示后会C · 需重学待学

记录尽量保存在当前浏览器，建议定期导出备份。