马尔科夫链上吸收问题的期望和概率

前言

本来是游戏王中的概率问题系列文章的一部分，不过事无巨细的把所有理论全写出来篇幅太大了，所以干脆单独抽出来（顺便扩充一下）。

本文主要是以简单的一维随机游走作为例子，讨论一下怎么计算马尔可夫链上击中目标状态所需步数的期望，以及各个目标状态的吸收概率。复杂一些的案例请查看前述的文章中关于MD天梯和BoK连胜问题的计算。

问题表述

马尔科夫链

首先啥是马尔科夫链/马尔科夫过程呢？简而言之，可以理解为在一个状态机上发生的随机过程，并且状态转移概率只与当前在哪个状态有关，而与之前是从哪里来到这个状态无关。

我们记全部状态的集合为$S$，称之为状态空间。状态空间$S$可以是无限的，但一般要求是可数的。由转移概率的历史无关性，我们可以把所有状态的转移概率写成一个转移概率矩阵$\mathbf{P}=(p_{ij}:i,j\in S)$，其中，$p_{ij}$表示从状态$i$转移到状态$j$的概率。

再给定一个在状态空间上的分布向量$\lambda=(\lambda_i:i\in S)$作为初始分布，那么任意时刻$t=k$的新分布由$\lambda^{(k)}=\lambda\mathbf{P}^k$不难计算。

注：实际问题中，初始分布往往是one-hot向量

由初始分布$\lambda$和转移概率矩阵$\mathbf{P}$我们就定义了一个马尔科夫过程 $Markov(\lambda, \mathbf{P})$。

以下两个定义也等价地定义了$Markov(\lambda, \mathbf{P})$：

定义1

对任意的$n\geq 0$和$i_0, \cdots, i_{n+1} \in S$，

• $\mathbb{P}(X_0=i_0)=\lambda_{i_0}$
• $\mathbb{P}(X_{n+1}=i_{n+1}|X_1=i_1, \cdots, X_n=i_n)=\mathbb{P}(X_{n+1}=i_{n+1}|X_n=i_n)=p_{i_ni_{n+1}}$

定义2

对任意的$n\geq 0$和$i_0, \cdots, i_{n} \in S$，

$$\mathbb{P}(X_0=i_0, X_1=i_1, \cdots, X_n=i_n)=\lambda_{i_0}p_{i_0i_1}\cdots p_{i_{n-1}i_n}$$

吸收概率和平均吸收时间

很多时候，我们感兴趣的是到达某些状态就停止的情形。比如累计足够多的胜场升段，赌徒亏光了本金，模拟到达稳态等等。

一般来说，有两个方面需要考虑：

• 到达目标状态所用的平均转移次数，即平均吸收时间
• 到达目标状态的概率，即吸收概率

严格来讲，目标状态不一定是吸收态，不过这里为了方便还是用“吸收”这个词了

我们定义目标状态集合$A\subset S$，那么$T^{A}=\inf\{n\geq 0 : X_n \in A\}$是第一次到达$A$中状态的时刻。

用后文的定义，$T^A$也是马尔科夫过程的一个停时。

为了方便，我们把关于初始状态的条件概率和条件期望分别记为：

$$\begin{gather*} \mathbb{P}_i(\sim) = \mathbb{P}(\sim|X_0=i)\\ \mathbb{E}_i(\sim) = \mathbb{E}(\sim|X_0=i) \end{gather*}$$

从状态$i$出发，能够到达$A$的概率为

$$P_i = \mathbb{P}_i(T^A<\infty)$$

从状态$i$出发，到达$A$所需要的步数期望为

$$E_i = \mathbb{E}_i(T^A) = \sum_{n<\infty}n\mathbb{P}_i(T^A=n)+\infty\mathbb{P}_i(T^A=\infty)$$

例：带边界的一维随机游走

案例

粒子从$x=0$处出发。每次有$p$的概率向右移动1个单位，有$q=1-p$的概率向左移动1个单位。

若粒子到达$x=-L$或者$x=R$时就停止（$L, R\geq0$），求平均吸收时间和被$x=R$吸收的概率。

平均吸收时间

状态空间$S=[-L, R]\cap \mathbb{Z}$，目标状态集合$\psi=\{-L, R\}$. 对于任意$i\notin \psi$，有

$$\begin{aligned} E_i &= \mathbb{E}_i(T^\psi) \\ &= q\mathbb{E}_i(T^\psi|X_1=i-1) + p\mathbb{E}_i(T^\psi|X_1=i+1) \\ &= q\left(1+\mathbb{E}_{i-1}(T^\psi)\right) + p\left(1+\mathbb{E}_{i+1}(T^\psi)\right)\\ &= 1 + qE_{i-1} + pE_{i+1} \end{aligned}$$

而显然有$E_{-L}=E_{R} = 0$，于是

$$\begin{dcases} E_{-L}=E_{R} = 0, &\\ E_i = 1 + qE_{i-1} + pE_{i+1}, & i=\{-L+1, \cdots, R-1\} \end{dcases}$$

为了求解这个方程组，我们可以把它看成一个二阶线性递推数列：第二行是递推关系，第一行则是边界条件。

首先需要消去多余的常数项，凑成齐次线性递推的形式：

① $p\neq q$

$$E_i + \dfrac{i}{p-q} = q\left[E_{i-1} + \dfrac{i-1}{p-q}\right] + p\left[E_{i+1} + \dfrac{i+1}{p-q}\right]$$

其特征方程为$px^2 - x + q = 0$，两个特征根分别为$x_1 = 1$和$x_2=\dfrac{q}{p}$，于是

$$E_i + \dfrac{i}{p-q} = \lambda_1 \left(\dfrac{q}{p}\right)^i + \lambda_2$$

代入边界条件

$$\begin{dcases} \lambda_1 \left(\dfrac{q}{p}\right)^{-L} + \lambda_2 = - \dfrac{L}{p-q}\\ \lambda_1 \left(\dfrac{q}{p}\right)^{R} + \lambda_2 = \dfrac{R}{p-q} \end{dcases}$$

解得

$$\begin{dcases} \lambda_1 &= - \dfrac{L+R}{p-q}\cdot\dfrac{q^Lp^R}{p^{L+R}-q^{L+R}}\\[1em] \lambda_2 &= \dfrac{1}{p-q}\cdot\dfrac{Lq^{L+R}+Rp^{L+R}}{p^{L+R}-q^{L+R}} \end{dcases}$$

所以

$$\begin{aligned} E_i &= \dfrac{(L+R)p^{L+R}}{(p-q)(p^{L+R}-q^{L+R})}\left[1-\left(\dfrac{q}{p}\right)^{i+L}\right] - \dfrac{i+L}{p-q}\\ \end{aligned}$$

② $p = q$

$$E_i+i^2 = \dfrac{1}{2}\left[E_{i-1} + (i-1)^2\right]+\dfrac{1}{2}\left[E_{i+1} + (i+1)^2\right]$$

类似地，特征方程为$(x-1)^2=0$，方程有重根$x=1$，进而

$$E_i+i^2 = ai+b$$

代入边界条件，不难解得

$$E_i = -i^2 + (R-L)i + RL$$

---

综上所述，我们有

$$E_i = \begin{dcases} -i^2 + (R-L)i + RL, & p=q\\ \dfrac{(L+R)p^{L+R}}{(p-q)(p^{L+R}-q^{L+R})}\left[1-\left(\dfrac{q}{p}\right)^{i+L}\right] - \dfrac{i+L}{p-q}, &p\neq q \end{dcases}$$

所以$x=0$处的平均吸收时间是

$$E_0 = \begin{dcases} RL, & p=q\\ \dfrac{Lq^{L+R}+Rp^{L+R} - (L+R)q^Lp^R}{(p-q)(p^{L+R}-q^{L+R})} , &p\neq q \end{dcases}$$

思考

在$p\to q$时，是否有$\dfrac{Lq^{L+R}+Rp^{L+R} - (L+R)q^Lp^R}{(p-q)(p^{L+R}-q^{L+R})} \to RL$呢？

吸收概率

状态空间$S=[-L, R]\cap \mathbb{Z}$，目标状态集合$\varphi=\{R\}$. 对于任意$i\notin \varphi$即$i\neq R$，有

$$\begin{aligned} P_i &= \mathbb{P}_i(T^\varphi<\infty) \\ &=p\mathbb{P}_i(T^\varphi<\infty|X_1=i+1)+q\mathbb{P}_i(T^\varphi<\infty|X_1=i-1)\\ &=p\mathbb{P}_{i+1}(T^\varphi<\infty)+q\mathbb{P}_{i-1}(T^\varphi<\infty)\\ &=pP_{i+1}+qP_{i-1} \end{aligned}$$

而显然$P_{-L}=0$以及$P_{R}=1$，因此

$$\begin{dcases} P_{-L}=0,& \\ P_{R}=1,& \\ P_i = pP_{i+1} + qP_{i-1},& i = \{-L+1, \cdots, R-1\} \end{dcases}$$

同样地，我们将上述方程组作为递推数列求解，特征方程和之前算期望时是一样的，而且已经是齐次的了，计算并不困难（留做习题）：

$$P_i = \begin{dcases} \dfrac{i+L}{L+R},& p=q\\ \dfrac{p^{L+R}-q^Lp^{R}\left(\dfrac{q}{p}\right)^i}{p^{L+R}-q^{L+R}},& p\neq q \end{dcases}$$

而从$x=0$处出发，被$x=R$吸收的概率则是

$$P_0 = \begin{dcases} \dfrac{L}{L+R},& p=q\\ \dfrac{p^{L+R}-q^Lp^{R}}{p^{L+R}-q^{L+R}},& p\neq q \end{dcases}$$

思考：$\mathbb{P}_i(T^\varphi<\infty)$和$\mathbb{E}_i(T^\psi)$的存在性

上述计算很好地得出了结果，但有个不很严密的地方：推导方程组的过程只说明了如果存在$\mathbb{P}_i(T^\varphi<\infty)$或者$\mathbb{E}_i(T^\psi)$，那么应该满足给定的方程，并没有说明待计算的$\mathbb{P}_i(T^\varphi<\infty) = \displaystyle \sum_{k=0}^\infty\mathbb{P}_i(T^\varphi = k)$和$\mathbb{E}_i(T^\psi) = \displaystyle \sum_{k=0}^\infty k \mathbb{P}_i(T^\psi = k)$的存在性。

该如何证明这两者的存在性呢？

• 提示：考虑$\left(px+\dfrac{q}{x}\right)^n$的展开式系数
• 在我们有了鞅这一工具后可以给出一个简明的证明
• 下一节我们会讨论一般情况下解的存在性

一般马尔科夫过程

我们很容易把上述在一维随机游走上使用的方法推广到一般的马尔可夫链上。得到下列两个定理：

定理一

若线性方程组

$$\begin{cases} E_i = 0, & i \in A\\ E_i = 1+\sum_{j\notin A} p_{ij}E_j, & i \notin A \end{cases} \tag{1}$$

有非负解，那么各状态到达$A$所需步数的期望$\mathbf{E}=(E_i: i\in S)$是上述线性方程组的最小非负解。

定理二

若线性方程组

$$\begin{cases} P_i = 1, & i \in A\\ P_i = \sum_{j\in S} p_{ij}P_j, & i \notin A \end{cases} \tag{2}$$

有非负解，那么各状态到达$A$的概率$\mathbf{P}=(P_i: i\in S)$是上述线性方程组的最小非负解。

最小非负解

这里关于最小非负解$\mathbf{x}=(x_i:i\in S)$的定义是:

• 对任意$i\in S$，有$x_i\geq 0$
• 设$\mathbf{y}=(y_i:i\in S)$也是一个解，那么对任意$i\in S$，有$x_i\leq y_i$

方程组推导

如果$E_i$和$P_i$均存在，那么仿照之前的思路，不难推导出$(1)$式和$(2)$式：

$(1)$：$i\in A$时显然$E_i=0$，而$i\notin A$时则有

$$\begin{aligned} E_i &= \mathbb{E}_i(T^A) \\ &= \sum_{j\in S} \mathbb{E}_i(T^A|X_1=j)\mathbb{P}_i(X_1=j)\\ &=\sum_{j\in S} \left[1 + \mathbb{E}_j(T^A)\right]\mathbb{P}_i(X_1=j)\\ &=\sum_{j\in S} \mathbb{P}_i(X_1=j) + \sum_{j\in S} p_{ij}E_j\\ &=1+\sum_{j\notin A}p_{ij}E_j \end{aligned}$$

$(2)$：$i\in A$时显然$P_i=0$，而$i\notin A$时则有

$$\begin{aligned} P_i&=\mathbb{P}_i(T^A<\infty)=\sum_{j\in S}\mathbb{P}_i(T^A<\infty, X_1=j)\\ &=\sum_{j\in S}\mathbb{P}_i(T^A<\infty|X_1=j)\mathbb{P}_i(X_1=j)\\ &=\sum_{j\in S}\mathbb{P}_j(T^A<\infty)\mathbb{P}_i(X_1=j)\\ &=\sum_{j\in S}p_{ij}P_j \end{aligned}$$

唯一的问题是如何证明$E_i$和$P_i$的存在性。

存在性证明

为证明存在性，我们的思路是利用方程组的解构造$P_i$和$E_i$的一个上界，进而借助单调有界收敛定理得到$P_i$和$E_i$存在且有界。

期望

设$\mathbf{x}=(x_i:i \in S)$是$(1)$的一个非负解。

对于任意$i\in A$，易见$x_i = 0 = \mathbb{E}_i(T^A)$

对于任意$i\notin A$，我们有

$$\begin{aligned} x_i &= 1 + \sum_{j\notin A} p_{ij} x_j\\ &= 1+ \sum_{j\notin A} p_{ij} \left(1+\sum_{k\notin A} p_{jk} x_k\right)\\ &={\color{blue}1} +{\color{green} \sum_{j\notin A} p_{ij} }+ \sum_{j\notin A}\sum_{k\notin A}p_{ij}p_{jk}x_k\\ &={\color{blue}\mathbb{P}_i(T^A\geq 1)} + {\color{green}\mathbb{P}_i(T^A\geq 2)} + \sum_{j\notin A}\sum_{k\notin A}p_{ij}p_{jk}x_k \end{aligned}$$

重复把$x_{i_s}$展开的操作，我们可以得到

$$x_i = \mathbb{P}_i(T^A\geq 1) + \cdots \mathbb{P}_i(T^A\geq n)+\sum_{j_1\notin A}\cdots\sum_{j_n\notin A}p_{ij_1}p_{j_1j_2}\cdots p_{j_{n-1}j_n}x_{j_n}$$

由于$\mathbf{x}=(x_i:i \in S)$的各个分量均非负，因此对任意的$n$，均有

$$x_i \geq \mathbb{P}_i(T^A\geq 1) + \cdots \mathbb{P}_i(T^A\geq n)$$

令$n\to \infty$，即有

$$\begin{aligned} x_i &\geq \sum_{j=1}^\infty \mathbb{P}_i(T^A \geq j)\\ &=\sum_{j=1}^\infty\sum_{k=j}^\infty \mathbb{P}_i(T^A = k)\\ &=\sum_{w=1}^\infty w\mathbb{P}_i(T^A = w)\\ &= \mathbb{E}_i(T^A) = E_i \end{aligned}$$

论证过程中的无穷级数都是正项级数，因此均绝对收敛，可以任意换序。

因为对任意的非负解$x_i$，都有$E_i \leq x_i$，而$\mathbf{E}=(E_i:i \in S)$是$(1)$的解，所以$\mathbf{E}$也是$(1)$的最小非负解。

概率

若$(2)$有非负解，设其中有一组解为$\mathbf{x}=(x_i:i \in S)$，那么对$i\in A$，有$x_i = 1 = P_i$；对$i\notin A$，有

$$\begin{aligned} x_i &= \sum_{j\in S} p_{ij}x_j = \sum_{j\in A} p_{ij} + \sum_{j\notin A} p_{ij}x_j\\ &=\sum_{j\in A} p_{ij} + \sum_{j\notin A} p_{ij} \left(\sum_{k\in A} p_{jk} + \sum_{k\notin A} p_{jk}x_k\right)\\ &={\color{blue} \sum_{j\in A} p_{ij} }+ {\color{green} \sum_{j\notin A} \sum_{k\in A} p_{ij}p_{jk}} + \sum_{j\notin A}\sum_{k\notin A}p_{ij}p_{jk}x_k\\ &={\color{blue}\mathbb{P}_i(X_1\in A)}+{\color{green}\mathbb{P}_i(X_1\notin A, X_2\in A)}+\sum_{j\notin A}\sum_{k\notin A}p_{ij}p_{jk}x_k \end{aligned}$$

重复展开$x_{i_s}$，我们有

$$\begin{aligned} x_i = &\mathbb{P}_i(X_1\in A)+\cdots+\mathbb{P}_i(X_1,\cdots,X_{n-1}\notin A, X_n\in A)\\ &+\sum_{j_1\notin A}\cdots\sum_{j_n\notin A}p_{ij_1}p_{j_1j_2}\cdots p_{j_{n-1}j_n}x_{j_n}\\ \geq & \mathbb{P}_i(X_1\in A)+\cdots+\mathbb{P}_i(X_1,\cdots,X_{n-1}\notin A, X_n\in A)\\ =&\mathbb{P}_i(T^A=1)+\cdots+\mathbb{P}_i(T^A=n)=\mathbb{P}_i(T^A\leq n) \end{aligned}$$

所以我们有

$$x_i\geq \lim_{n\to \infty} \mathbb{P}_i(T^A\leq n) = \mathbb{P}_i(T^A< \infty) = P_i$$

因此$P=(P_i: i\in S)$存在且有限，并且是$(2)$的最小非负解。

Off Topic: 马尔科夫链上的势能

平均吸收时间和吸收概率都是马尔科夫链上势函数的特殊情况。一般地，设$\partial D = A$，$D = S\setminus A$，势函数$\phi$是满足以下线性方程组的函数：

$$\begin{dcases} \phi = \mathbf{P}\phi + c, & \text{in}\ D\\ \phi = f, & \text{in}\ \partial D \end{dcases}$$

其中$c = (c_i: i \in D)$和$f = (f_i:i \in \partial D)$为非负函数（分别为内部cost和边界cost）。

我们能够证明：只要$\mathbb{P}_i(T^{\partial}< \infty) = 1$对任意$i\in S$成立，那么上述方程组至多有1个有界解。

对我们讨论的平均吸收时间（$f=0, c=1$）和吸收概率（$f=1, c=0$）而言，方程组有解自动保证了$\mathbb{P}_i(T^{\partial}< \infty) = 1$成立（思考：为什么？），进而由上述结论可知解得的是唯一解。

鞅与停时定理

求解$(1)$和$(2)$这两个方程组有时候并不容易。从更高的观点，我们引入鞅可以简化一些复杂的计算。

定义

定义3. 鞅

对于随机过程$\{X_n\}$和$\{M_n\}$。如果满足：

• $M_n$可积，即$\mathbb{E}|M_n|< \infty$
• $M_n$是$\mathscr{F_n}$上的适应过程，即$M_n$只与$X_0, \cdots, X_n$有关
• 对任意$n\in \mathbb{N}$，$\mathbb{E}(M_{n+1}|\mathscr{F_n}) = M_n$

则称$\{M_n\}$是一个关于$\{X_n\}$的鞅。

其中条件3也可以等价地写成$\mathbb{E}(M_{n+1}-M_n|\mathscr{F_n}) = 0$，如果将等号改为大于等于/小于等于，那么过程$\{M_n\}$就称为上鞅/下鞅。

上鞅和下鞅的定义也有反过来的，可能是因为和函数凹凸性相关，于是和凹函数/凸函数一样成了笔糊涂账。Anyway，这里我们只用鞅，并不涉及上鞅与下鞅。

$\mathscr{F_n}$是所谓的filteration，即只与$X_0, \cdots, X_n$有关的事件集。这里可以简单地认为$\mathbb{E}(M_{n+1}|\mathscr{F_n})$是$\mathbb{E}(M_{n+1}|X_0=i_0,\cdots,X_n=i_n), \forall i_0, \cdots, i_n$的简写。

按照定义容易得知，

$$\mathbb{E}(M_{n}) = \mathbb{E}(\mathbb{E}(M_{n+1}|\mathscr{F_n})) = \mathbb{E}(M_{n+1})$$

于是由归纳法，对任意有限的$n$，我们有

$$\mathbb{E}(M_{n}) = \mathbb{E}(M_{0})$$

直观地来讲，如果一个随机过程它每一步的期望都保持恒定不变，是一个平稳的过程，那么就称它为鞅。

---

若$T$是$\{M_n\}$的一个停时，记$T\wedge n = \min\{T, n\}$，那么显然有

$$\mathbb{E}(M_{T\wedge n}) = \mathbb{E}(M_{0})$$

停时定理所讨论的是：在什么情况下有$\mathbb{E}(M_T) = \mathbb{E}(M_0)$成立？

定理3. 停时定理（Optional Stopping Theorem）

$\{M_n\}$是关于$\{X_n\}$的鞅，$T$是$\{M_n\}$的一个停时，那么以下均为$E(M_T) = E(M_0)$的充分条件：

1. 存在$K<\infty$，使得$\mathbb{P}(T\leq K)=1$
2. $\mathbb{E}(T)<\infty$，并且$\mathbb{E}(|M_{n+1}-M_n|)\leq K < \infty$
3. $\mathbb{P}(T < \infty)=1$，并且$M_{T\wedge n} \leq K < \infty$

NOTE

OST的成立条件其实就是在问$M_{T\wedge n}$是否一致可积，也就是能否交换积分和极限的顺序。如果答案是肯定的，那么显然就有

$$\mathbb{E}(M_{0}) = \lim_{n\to\infty}\mathbb{E}(M_{T\wedge n})=\mathbb{E}\left(\lim_{n\to\infty}M_{T\wedge n}\right)=\mathbb{E}(M_T)$$

一般马尔科夫链上的鞅

为了使用停时定理，我们首先得需要一个鞅。然而$\{X_n\}$在一般情况下并不是鞅，所以我们得自己构造一个。在马尔科夫链上构造鞅需要一些技巧，但还是有一般规律可循的。

设待构造的鞅为$M_n = f(n, X_n)$，那么按照马尔科夫链和鞅的性质，应当有

$$\begin{aligned} f(n, i)&=\mathbb{E}(M_{n}|X_n = i) = \mathbb{E}(M_{n+1}|X_n = i) \\ &= \sum_{j\in S} p_{ij} f(n + 1, j)\\ &=(\mathbf{P}f)(n, i) \end{aligned}$$

由此，我们有如下定理：

定理4. （马尔科夫链上的鞅）

设$\{X_n\}$是状态转移矩阵为$\mathbf{P}$的马尔科夫链，如果函数$f: S\times \mathbb{N} \to \mathbb{R}$满足：

• $\mathbb{E}(|f(n, X_n)|)<\infty$
• $(\mathbf{P}f)(n, i) = \sum_{j\in S} p_{ij} f(n + 1, j) = f(n, i)$

那么$M_n = f(n, X_n)$是鞅。

接下来，我们将从鞅的观点重新发现定理1和定理2，并且给出势能函数这一工具。

平均吸收时间的势能函数

我们首先考虑一个简单的例子：$f(n, i) = n + \varphi(i)$，其中$\varphi:S\to \mathbb{R}$。假设停时定理的条件满足，那么我们有

$$\begin{aligned} \varphi(i)&=f(0, i) = \mathbb{E}_i(f(0, X_0))\\ &= \mathbb{E}_i(f(T, X_T))\\ &= \mathbb{E}_i(T+\varphi(X_T))\\ &= \mathbb{E}_i(T)+\mathbb{E}_i(\varphi(X_T)) \end{aligned}$$

于是停时的期望可以表示为

$$\begin{aligned} E_i = \mathbb{E}_i(T) &= \varphi(i) - \mathbb{E}_i(\varphi(X_T))\\ &= \varphi(i) - \sum_{j\in \partial D} P^{(j)}_i \varphi(j) \end{aligned}$$

其中$P^{(j)}_i$表示从状态$i$出发，最终被状态$j$吸收的概率。从上面的式子来看，$\varphi$可以理解为一种势，而$E_i$就是当前状态$i$到全体吸收状态的势差。

在一些OI的资料里面，$\varphi$被称为势能函数，这很形象。一般意义的势能函数在前一节最后的Off Topic中已经提到过了。

另一方面由定理4，我们有

$$\begin{aligned} n+\varphi(i) &= f(n, i) = \sum_{j\in S} p_{ij} f(n + 1, j) \\ &= \sum_{j\in S} p_{ij} (n + 1 + \varphi(j)) \\ &= n + 1 + \sum_{j\in S} p_{ij} \varphi(j) \end{aligned}$$

于是我们有

$$\varphi(i) = 1 + \sum_{j\in S} p_{ij} \varphi(j)$$

由于$\varphi$实质上是任意的，如果令各个吸收态的势为0，就有$E_i = \varphi(i)$，这样我们就重新得到了定理1. 但由上述推理过程我们可以发现，如果我们知道如何求解$P^{(j)}_i$，我们可以任意重新选择边界上的$\varphi$值，从而简化$E_i$的计算（类似重新选定零势能面）。

吸收概率的势能函数

吸收概率的势能函数更简单些，我们考虑鞅$\psi: S\to \mathbb{R}$，那么应用停时定理，我们有

$$\begin{aligned} \psi(i) &=\mathbb{E}_i(\psi(X_0))\\ &= \mathbb{E}_i(\psi(X_T)) \\ &= \sum_{j\in \partial D} P^{(j)}_i \psi(j) \end{aligned}$$

另一方面由定理4，不难得到

$$\psi(i) = \sum_{j\in S} p_{ij} \psi(j)$$

进而重新得到了定理2.

$\psi$是一个在$D$上调和的势能函数，它由边界的值唯一确定。

随机游走：Revision

我们回到之前的随机游走问题，看看怎么用停时定理来计算吸收概率和平均吸收时间。

先来考虑吸收概率的势$\psi(X_n)$（它也是个鞅）：

$$\begin{gather*} \psi(i) = p\cdot \psi(i+1)+q\cdot \psi(i-1) \end{gather*}$$

熟悉的二阶线性递推数列又出现了，由于势能的初值无关性，为了便于计算，不妨取$\psi(0)=0$，并使剩下一个参数为1. 于是

$$\psi(i) = 1 - \left(\dfrac{q}{p}\right)^i$$

$\psi(i)$有界，而显然$\mathbb{P}(T<\infty)=1$（思考：为什么？），因此满足停时定理的条件。

按照停时定理，我们有

$$\begin{aligned} \psi(i) &= P_i\psi(R) + (1-P_i)\psi(-L) \end{aligned}$$

从而得到

$$P_i = \dfrac{\psi(i) - \psi(-L)}{\psi(R)-\psi(-L)} = \dfrac{\left(\dfrac{q}{p}\right)^{-L}-\left(\dfrac{q}{p}\right)^{i}}{\left(\dfrac{q}{p}\right)^{-L} - \left(\dfrac{q}{p}\right)^{R}} = \dfrac{p^{L+R}-p^Rq^L\left(\frac{q}{p}\right)^{i}}{p^{L+R}-q^{L+R}}$$

这样就算出了吸收概率。

思考：这里假定了$p\neq q$，如果$p=q$那么计算又该如何进行呢？

此时取ψ(i)=i即可

而对于平均吸收时间$\mathbb{E}(T)$，我们考虑对应的势能$\varphi(i)$，按照前一节的推导，我们有

$$\varphi(i) = 1 + p\varphi(i+1) + q\varphi(i-1)$$

这也是我们熟悉的递推关系式，因为没有初值要求，可以怎么简单怎么来：

$$\varphi(i) = \begin{dcases} -\dfrac{i}{p-q}, & p\neq q\\ -i^2,& p=q \end{dcases}$$

由于$\varphi$有界，且$\mathbb{P}(T<\infty)=1$，因此满足停时定理的条件。所以我们有势差公式：

$$\begin{aligned} \mathbb{E}_i(T) &= \varphi(i) - \sum_{j\in \partial D} P^{(j)}_i \varphi(j)\\ &=\begin{dcases} -\dfrac{i}{p-q}+\dfrac{R}{p-q} P_i+\dfrac{-L}{p-q}(1-P_i),& p\neq q\\ -i^2+P_i R^2+(1-P_i)(-L)^2, & p=q \end{dcases}\\ &=\begin{dcases} \dfrac{(L+R)p^{L+R}}{(p-q)(p^{L+R}-q^{L+R})}\left[1-\left(\dfrac{q}{p}\right)^{i+L}\right] - \dfrac{i+L}{p-q}, & p\neq q\\ -i^2 + (R-L)i + RL, & p=q \end{dcases} \end{aligned}$$

关于存在性

借助鞅并不难说明$\mathbb{E}(T)<\infty$以及$\mathbb{P}(T<\infty)=1$.

首先若$\mathbb{P}(T<\infty)=1-\varepsilon < 1$，即$\mathbb{P}(T=\infty)=\varepsilon > 0$，那么$\mathbb{E}(T)\geq \infty\cdot \mathbb{P}(T=\infty) = \infty$. 因此只要证明了$\mathbb{E}(T)<\infty$，就可用反证法推出$\mathbb{P}(T<\infty)=1$。

我们知道$G(n, X_n) = n + \varphi(X_n)$是鞅，对任意有限的$k$，我们考虑有界停时$T\wedge k$. 应用停时定理，我们有

$$\begin{aligned} \mathbb{E}_i(T\wedge k) &= \varphi(i) - \mathbb{E}_i(\varphi(X_{T\wedge k}))\\ &\leq | \varphi(i) | + | \mathbb{E}_i(\varphi(X_{T\wedge k})) |\\ &\leq | \varphi(i) | + \max \{|\varphi(-L)|, |\varphi(R)|\}\\ &\leq 2\max \{|\varphi(-L)|, |\varphi(R)|\} = M < \infty \end{aligned}$$

而$\mathbb{E}_i(T\wedge k)$随$k$单调递增，从而由单调收敛定理知$\mathbb{E}_i(T\wedge k)\uparrow \mathbb{E}_i(T) \leq M < \infty$