关于一个随机游走的马尔科夫链

题目

定义一个非对称的随机游走: 令$Y_1,Y_2,\cdots,Y_i,\cdots$独立同分布, 其中$Pr\{Y_i = 1\} = \frac{2}{3},Pr\{Y_i = -1\} = \frac{1}{3}$, 且定义$Z_0=0,Z_n = \sum_{i=1}^nY_i$ 的随机过程$\{Z_n,n\geq0\}$.

求这个过程从状态0到状态1的期望首达时间$\mu_{01}$

$$\mu_{01} = E\{T_{01}|Z_0 = 0\} = \sum_{i=1}^\infty nf_{01}^{(n)}$$

其中

• $T_{ij} = {\rm min}\{n | Z_0 = i,Z_n = j, n\geq1\}$为马尔科夫链 $Z_n$ 从状态 $i$ 出发首次到达状态 $j$ 的时间, 简称 首达时.

  $T_{ij}$是个随机变量, 并且对于 $k=1,2,\cdots$ 有$\{T_{ij} = k\} = \{ Z_0 = i, Z_1\neq j,\cdots,Z_{k-1}\neq j,Z_k = j\}$.

• $f_{ij}^{(n)} = Pr(T_{ij} = n | Z_0 = i)$为马氏链从状态 $i$ 出发恰好经过 $n$ 步转移后首次到达状态 $j$ 的概率, 简称 首达概率

• $\mu_{ij} = E(T_{ij}|Z_0=i)$ 表示从状态 $i$ 出发首次到达状态 $j$ 的平均转移时间, $\mu_{ij} = \sum_{i=1}^n nf_{ij}^{(n)}$, 称其为期望首达时

C-K方程的变式

C-K方程的变式 对于马尔科夫链$\{X_n,n\geq0\}$, 首达概率有如下关系

$$\begin{cases} f_{ij}^{(1)} = p_{ij}^{(1)}\\ f_{ij}^{(n+1)} = \sum_{k\neq j}f_{ik}^{(1)}f_{kj}^{(n)} \end{cases} \quad{eq(c-k)}$$

证明：

首先由一步转移概率和首达概率的定义可以得到第一个等式

$$p_{ij}^{(1)} = Pr\{X_{1}=j|X_{0}=i\}=f_{ij}^{(1)}$$

其次证明第二个等式

$$\begin{split} f_{ij}^{(n+1)} &= Pr\{X_{n+1} = j, X_{1,\cdots,n}\neq j | X_0=i\} \\ 贝叶斯公式\rightarrow &= \frac{Pr\{X_{n+1}=j,X_{1,\cdots,n}\neq j,X_0=i\}}{Pr\{X_0=i\}}\\ 全概率公式\rightarrow &= \sum_{k\neq j} \frac{Pr\{X_{n+1}=j,X_{1,\cdots,n}\neq j,X_0=i,X_1=k\}}{Pr\{X_0=i\}}\\ 构造f_{ik}^{(1)}\rightarrow &= \sum_{k\neq j} \frac{Pr\{X_1 = k,X_0=i\}}{Pr\{X_0=i\}} \cdot \frac{Pr\{X_{n+1}=j,X_{1,\cdots,n}\neq j,X_0=i,X_1=k\}}{Pr\{X_1 = k,X_0=i\}} \\ 贝叶斯公式\rightarrow &= \sum_{k\neq j} Pr\{X_1 = k|X_0=i\}\cdot Pr\{X_{n+1}=j,X_{1,\cdots,n}\neq j|X_0=i,X_1=k\} \\ 马尔可夫性\rightarrow &= \sum_{k\neq j}Pr\{X_1 = k|X_0=i\} \cdot Pr\{X_{n+1}=j,X_{1,\cdots,n}\neq j|X_1=k\}\\ &= \sum_{k\neq j}f_{ik}^{(1)}f_{kj}^{(n)} \end{split}$$

C-K方程变式的矩阵描述

上面的公式可以用矩阵描述, 令 $\{X_n,n\geq 0\}$ 的一步状态转移矩阵为

$$P = \begin{bmatrix} p_{00} & p_{01} & p_{02} & \cdots \\ p_{10} & p_{11} & p_{12} & \cdots \\ p_{20} & p_{21} & p_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$

另外由于$f_{ij}^{(1)} = p_{ij}^{(1)}$, 所以

$$\begin{bmatrix} p_{00} & p_{01} & p_{02} & \cdots \\ p_{10} & p_{11} & p_{12} & \cdots \\ p_{20} & p_{21} & p_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} = \begin{bmatrix} f_{00} & f_{01} & f_{02} & \cdots \\ f_{10} & f_{11} & f_{12} & \cdots \\ f_{20} & f_{21} & f_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}$$

例如求 $f_{21}^{(n)}$, 首先我们令一步状态转移矩阵中 $j=1$ 的列全为 $0$, 并由公式 $eq(c-k)$ 得到下面等式

$$\begin{bmatrix} f_{01}^{(2)}\\ f_{11}^{(2)}\\ f_{21}^{(2)}\\ \vdots \end{bmatrix} = \begin{bmatrix} f_{00} & 0 & f_{02} & \cdots \\ f_{10} & 0 & f_{12} & \cdots \\ f_{20} & 0 & f_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} f_{01}\\ f_{11}\\ f_{21}\\ \vdots \end{bmatrix} = \begin{bmatrix} p_{00} & 0 & p_{02} & \cdots \\ p_{10} & 0 & p_{12} & \cdots \\ p_{20} & 0 & p_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} p_{01}\\ p_{11}\\ p_{21}\\ \vdots \end{bmatrix}$$

重复上面的公式可以得到$f_{i1}^{(3)}$

$$\begin{bmatrix} f_{01}^{(3)}\\ f_{11}^{(3)}\\ f_{21}^{(3)}\\ \vdots \end{bmatrix} = \begin{bmatrix} f_{00} & 0 & f_{02} & \cdots \\ f_{10} & 0 & f_{12} & \cdots \\ f_{20} & 0 & f_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} f_{01}^{(2)}\\ f_{11}^{(2)}\\ f_{21}^{(2)}\\ \vdots \end{bmatrix} = \begin{bmatrix} p_{00} & 0 & p_{02} & \cdots \\ p_{10} & 0 & p_{12} & \cdots \\ p_{20} & 0 & p_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}^2 \begin{bmatrix} p_{01}\\ p_{11}\\ p_{21}\\ \vdots \end{bmatrix}$$

如此循环可以得到$f_{i1}^{(n)}$

$$\begin{bmatrix} f_{01}^{(n)}\\ f_{11}^{(n)}\\ f_{21}^{(n)}\\ \vdots \end{bmatrix} = \begin{bmatrix} f_{00} & 0 & f_{02} & \cdots \\ f_{10} & 0 & f_{12} & \cdots \\ f_{20} & 0 & f_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \cdots \begin{bmatrix} f_{00} & 0 & f_{02} & \cdots \\ f_{10} & 0 & f_{12} & \cdots \\ f_{20} & 0 & f_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix} \begin{bmatrix} f_{01}\\ f_{11}\\ f_{21}\\ \vdots \end{bmatrix} = \begin{bmatrix} p_{00} & 0 & p_{02} & \cdots \\ p_{10} & 0 & p_{12} & \cdots \\ p_{20} & 0 & p_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}^{(n-1)} \begin{bmatrix} p_{01}\\ p_{11}\\ p_{21}\\ \vdots \end{bmatrix}$$

结论

$$\begin{bmatrix} f_{01}^{(n)}\\ f_{11}^{(n)}\\ f_{21}^{(n)}\\ \vdots \end{bmatrix} = \begin{bmatrix} p_{00} & 0 & p_{02} & \cdots \\ p_{10} & 0 & p_{12} & \cdots \\ p_{20} & 0 & p_{22} & \cdots \\ \vdots & \vdots & \vdots & \ddots \end{bmatrix}^{(n-1)} \begin{bmatrix} p_{01}\\ p_{11}\\ p_{21}\\ \vdots \end{bmatrix} \quad eq(c-k-2)$$

求解

几点说明

随机过程的 $Z_n$ 的状态空间是整数集 $\mathbb{Z}$.

为了方便描述, 我们计算状态 $-2$ 到状态 $-1$ 的平均首达时间, 由对称性可以知道 $\mu_{0\rightarrow1} = \mu_{(-2)\rightarrow(-1)}$; 并且只考虑全体负整数状态 $\{-1,-2,\cdots\}$ , 因为在讨论首达时间的时候, 状态走到 $-1$ 整个过程就停止了, 所以 $Z_n$ 取不到 $\{0,1,2,\cdots\}$ 这些状态了.

还是为了方便描述, 在后面我们用 $\{1,2,\cdots\}$ 来表示 $\{-1,-2,\cdots\}$ 这些状态 (这样可以少写负号), 即 $\mu_{21}$ 表示状态 $-2$ 到 $-1$ 的期望首达时间.

正式求解

由题设容易给出 $Z_n$ 的一步转移矩阵

$$\begin{array}{rl} & \begin{matrix} \quad-1 & -2 & -3 & \cdots \end{matrix} \\ \begin{matrix} -1 \\ -2 \\ -3 \\ \vdots \end{matrix} & \begin{bmatrix} 0 & 1/3 & 0 & \cdots \\ 2/3 & 0 & 1/3 & \cdots \\ 0 & 2/3 & 0 & \ddots \\ \vdots & \vdots & \ddots & \ddots \end{bmatrix} \end{array}$$

记为 $\boldsymbol{P}$

由公式 $eq(c-k-2)$, 可以如下计算从状态$-2$到状态$-1$的 $n$ 步首达概率 $f_{21}^{(n)}$

$$\begin{split} f_{21}^{(n)} &= \begin{bmatrix} 0,&1,&0,&\cdots \end{bmatrix} \begin{bmatrix} 0 & 1/3 & 0 & \cdots \\ 0 & 0 & 1/3 & \cdots \\ 0 & 2/3 & 0 & \ddots \\ \vdots & \vdots & \ddots & \ddots \end{bmatrix}^{(n-1)} \begin{bmatrix} 0 & 1/3 & 0 & \cdots \\ 2/3 & 0 & 1/3 & \cdots \\ 0 & 2/3 & 0 & \ddots \\ \vdots & \vdots & \ddots & \ddots \end{bmatrix} \begin{bmatrix} 1 \\ 0 \\ 0 \\ \vdots \end{bmatrix} \\ &= \begin{bmatrix} 0,&1,&0,&\cdots \end{bmatrix} \begin{bmatrix} 0 & 1/3 & 0 & \cdots \\ 0 & 0 & 1/3 & \cdots \\ 0 & 2/3 & 0 & \ddots \\ \vdots & \vdots & \ddots & \ddots \end{bmatrix}^{(n-1)} \begin{bmatrix} 0 \\ 2/3 \\ 0 \\ \vdots \end{bmatrix} \end{split}$$

令

$$\begin{bmatrix} 0,&1,&0,&\cdots \end{bmatrix} \begin{bmatrix} 0 & 1/3 & 0 & \cdots \\ 0 & 0 & 1/3 & \cdots \\ 0 & 2/3 & 0 & \ddots \\ \vdots & \vdots & \ddots & \ddots \end{bmatrix}^{m} = \begin{bmatrix} g(m,1), & g(m,2), & g(m,3), & \cdots \end{bmatrix}$$

于是有

$$\begin{equation} \begin{bmatrix} g(m,1), & g(m,2), & \cdots \end{bmatrix} = \begin{bmatrix} g(m-1,1), & g(m-1,2), & \cdots \end{bmatrix} \begin{bmatrix} 0 & 1/3 & 0 & \cdots \\ 0 & 0 & 1/3 & \cdots \\ 0 & 2/3 & 0 & \ddots \\ \vdots & \vdots & \ddots & \ddots \end{bmatrix} \end{equation}$$

即

$$\begin{cases} g(m,1)=0, & i=1\\ g(m,i) = \frac{1}{3}g(m-1,i-1)+\frac{2}{3}g(m-1,i+1),&i\geq 2 \end{cases}$$

最后

$$\begin{gather} f_{21}^{n} = \frac{2}{3}g(n-1,2) \end{gather}$$

使用Python计算上述递归式

def g(m,i):
    if m == 0:        # 定义g(0)，即[0,1,0,...]
        if i == 2:
            return 1
        else:
            return 0
    else:             # 定义g(n)
        if i == 1:
            return 0
        else:
            return 1/3*g(m-1,i-1)+2/3*g(m-1,i+1)

E = 0.0  # 期望首达时
Pr = 0.0 # 前n个首达概率的和
for n in range(1,30): # 计算1到29步首达时的均值
    print('n = %d' % n)
    if (n%2) == 1:    # 当n为奇数时才有首达概率>0；n为偶数时首达概率=0，不计算
        f_n_21 = 2/3*g(n-1,2) # g(n,1)就是状态-2到状态-1的n步首达概率
        temp = n*f_n_21
        E += temp    # 计算期望首达时
        Pr += f_n_21 # 计算前n个首达概率的和
        print('Pr = %.4f' % Pr)
        print('ΔE = %.4f ' % temp)
        print('f_n_21 = %.4f' % f_n_21)
        print('E = %.4f \n' % E)
    else:
        print('f_n_21 = %.4f \n' % 0) # n为偶数的时候输出0

输出

n = 1
Pr = 0.6667
ΔE = 0.6667
f_n_21 = 0.6667
E = 0.6667

n = 2
f_n_21 = 0.0000

.
.
.

n = 28
f_n_21 = 0.0000

n = 29
Pr = 0.9941
ΔE = 0.0370
f_n_21 = 0.0013
E = 2.7568

$$\sum_{n=1}^{29} nf_{21}^{(n)} = 2.7568$$