【随机过程2】马尔可夫过程1 | 基本概念

6.1 基本概念

马尔科夫链的定义很常见了，在此不再赘述。简单而言就是 \[ P(X_{n+1}=s_{n+1}|X_0=s_0,...,X_{n}=s_n) = P(X_{n+1}=s_{n+1}|X_{n}=s_n) \] 还可以定义一步转移概率、转移概率矩。如果转移概率不随时间变化，就是时间齐次马尔科夫链。

定理 6.1：设随机过程 \(\{X_n,n\ge0\}\) 满足

1. \(X_n = f(X_{n-1},\xi_n)(n\ge1)\)，其中 \(f:S\times S\to S\)；
2. \(\{\xi_n,n\ge1 \}\) 为独立同分布随机序列，且 \(X_0\) 与 \(\{\xi_n,n\ge1\}\) 也相互独立；

则 \(\{X_n,n\ge0\}\) 是马尔科夫链，并且一步转移概率为 \(p_{ij}=P(f(i,\xi_n)=j)\).

证明：根据条件 1 可知 \(\xi_{n+1}\) 与 \(X_0,...,X_n\) 独立，从而有 \[ \begin{aligned} &P(X_{n+1}=s_{n+1} | X_0=s_0,...,X_n=s_n) \\ =& P(f(X_n,\xi_{n+1})=s_{n+1} | X_0=s_0,...,X_n=s_n) \\ =& P(f(s_n,\xi_{n+1})=s_{n+1}) = P(X_{n+1}=s_{n+1} | X_n = s_n) \end{aligned} \] 证毕。

Note：这个定理实际上是在说 \(X_n\) 只由 \(X_{n-1}\) 和一个与之完全独立的随机变量 \(\xi_n\) 决定，这与马尔可夫性质异曲同工。并且如果 \(\xi_n,n\ge1\) 同分布，那么这个马尔可夫过程是时间齐次的，否则是非齐次的。

如果把随机变量看作是信息的话，\(\xi_n\) 就可以看成是从 \(X_{n-1}\) 到 \(X_n\) 变化的信息量。

栗子 1：设 \(\{\xi_n,n\ge0\}\) 独立同分布，取值为非负整数，\(P(\xi_n=i)=a_i\)。令 \(X_0=0,X_n=\sum_{k=1}^n \xi_k\)，则易证 \(\{X_n,n\ge0\}\) 是一个马尔科夫链，因为有 \(f(X_n,\xi_{n+1}) = X_n+\xi_{n+1}\)。还可以得到转移概率为 \(p_{ij} = \begin{cases}a_{j-i}, & i\ge i \\ 0, & i < i \end{cases}.\)

栗子 2（带吸收壁的随机游动）：对称随机游动，每次只能向左或向右移动一个单位，或者原地不动，随机移动限制在 \(S=\{0,1,...,b\}\) 内。用 \(\xi_n\) 表示第 \(n\) 次移动的距离，\(X_n\) 为 \(n\) 次移动后的位置，则 \(X_{n+1} = f(X_n,\xi_{n+1}) = X_n + (1-\delta(X_n-b)-\delta(X_n))\xi_{n+1}\)。

栗子 3（G/M/1排队模型）：G表示顾客到达服务台的时间间隔，一般假设为独立同分布，分布函数为 \(G(x)\)；M表示服务时间，假设为独立同指数分布，且与顾客到达过程独立；1表示单个服务员。

记 \(X_n\) 表示第 \(n\) 个顾客到达服务台时系统内的顾客数，\(T_n\) 表示第 \(n\) 个顾客到达时刻。易证 \(X_n\) 为一个马尔科夫链。

各顾客服务时间独立，且服从参数为 \(\mu\) 的指数分布，\((0,t)\) 时间内服务完的顾客服从参数为 \(\mu\) 的泊松分布，因此 \[ P(X_{n+1}=i+1-j | X_n=i) = \int_0^\infty e^{-\mu t}\frac{(\mu t)^j}{j!} dG(t) \]

6.2 转移概率矩阵

定义：若 \(a_{ij}\ge0, ~ i,j\in S\) 且满足 \(\sum_{j\in S} a_{ij} = 1\)，则称矩阵 \(A=(a_{ij})\) 为随机矩阵。

记 \(\pi_i(n)=P(X_n=i)\)，向量 \(\pi(n)=(\pi_1(n),\pi_2(n),...)\) 表示 \(n\) 时刻的概率分布向量。一个马尔科夫链的性质完全由初始分布向量和一步转移概率矩阵决定。

定理 6.2（C-K方程）：\(P^{(m+n)} = P^{(m)} P^{(n)}\).

Remark：上面的C-K方程可以联想到卷积形式，即 \(P_{ij}^{(n)}=\sum_{k}P_{ik}^{(l)}P_{kj}^{(n-l)}\)，于是又可以联想到用傅里叶变换 / z变换进行处理，以避免卷积。

6.3 Markov链状态的分类

6.3.1 状态分类

定义：对于 \(i,j\in S\)，若存在自然数 \(n\) 使得 \(p_{ij}^{(n)} > 0\)，则称自状态 \(i\) 出发可达状态 \(j\)，记为 \(i\to j\)。若 \(i\to j\) 且 \(j\to i\)，则称 \(i,j\) 相通，记为 \(i\leftrightarrow j\)。如果 Markov 链的任意两个状态都相通，则称为不可约链。

定义：首达时间 \[ \tau_{ij}=\min \{n:n\ge1,X_n=j,X_0=i \} \] 若右边为空集，则令 \(\tau_{ij}=\infty\)。

定义：首达概率 \[ f_{ij}^{(n)}=P(\tau_{ij}=n | X_0=i)=P(X_n=j,X_k\ne j,1\le k\le n-1 | X_0=i) \] \(f_{ij}=\sum_{n=1}^\infty f_{ij}^{(n)}\) 表示从 \(i\) 出发，经有限步首次到达 \(j\) 的概率。

定义：若 \(f_{ii}=1\)，则称 \(i\) 为常返态；若 \(f_{ii} < 1\)，称状态 \(i\) 为非常返态。

定义：若 \(f_{ii}=1\)，此时定义 \(\mu_i=\sum_{n=1}^\infty nf_{ii}^{(n)}\)，则 \(\mu_i\) 表示从状态 \(i\) 出发再回到状态 \(i\) 的平均回转时间。若 \(\mu_i < \infty\) 称 \(i\) 为正常返态；若 \(\mu_i=\infty\) 称为零常返态。

定义：若集合 \(\{n:n\ge1,p_{ii}^{(n)} > 0\}\ne\varnothing\)，称该数集的最大公约数 \(d(i)\) 为状态 \(i\) 的周期。若 \(d(i) > 1\) 称状态 \(i\) 为周期的；若 \(d(i)=1\) 称为非周期的。

定义：若状态 \(i\) 为正常返态且为非周期的，则称状态 \(i\) 为遍历状态（ergodic state）。

6.3.2 一些基本关系式

定理 6.3：对 \(\forall i,j\in S,n\ge1\) 有

1. \(p_{ij}^{(n)} = \sum_{l=1}^n f_{ij}^{(l)}p_{jj}^{(n-l)}\)
2. \(f_{ij}^{(n)} = \sum_{k\ne j}p_{ik}f_{kj}^{(n-1)}I_{\{n > 1\}} + p_{ij} I_{\{n=1\}}\).

下面给出一些关于该定理的讨论。

Discussion（常返性判定准则）：对于特殊情况 \(i=j\) 时，上面的第 1 条变成 \(p_{ii}^{(n)} = \sum_{l=1}^n f_{ii}^{(l)}p_{ii}^{(n-l)}\)，这是卷积的形式，取 z 变换 \(P_i(z)=\sum_{n=1}^{\infty} p_{ii}^{(n)}z^{-n}\)，\(F_i(z)=\sum_{n=1}^{\infty}f_{ii}^{(n)}z^{-n}\)，那么根据上式有 \(P_i(z)=1+F_i(z)P_i(z)\)，从而 \(P_i(z)=\frac{1}{1-F_i(z)}\)。当 \(z\to1\)时，有 \(P_i(z)\to\sum_{n=1}^{\infty}p_{ii}^{(n)}\)，\(F_i(z)\to \sum_{n=1}^{\infty}f_{ii}^{(n)} = f_{ii}\)。

推论 6.3.1：状态 \(i\) 为常返的充要条件为 \(\sum_{n=1}^{\infty}p_{ii}^{(n)}=+\infty\)；状态 \(i\) 非常返的充要条件为 \(\sum_{n=1}^{\infty}p_{ii}^{(n)} < \infty\)。

如果记 \(I_n(i)=\begin{cases}0,&X_n\ne i \\ 1,& X_n=i \end{cases}\)，\(S(i)=\sum_{n=1}^\infty I_n(i)\) 为到达状态 \(i\) 的次数，那么 \({\mathbb E}[S(i) | X_0=i]=\sum_{n=1}^{\infty}p_{ii}^{(n)}\) 即表示从状态 \(i\) 出发返回 \(i\) 的平均次数。当 \(i\) 为常返态，直观上即平均返回 \(i\) 的次数为无穷，与上面的推论是一致的。对于非常返态，平均返回次数有限。

Discussion（\(p_{ii}^{(n)}\)与正常返、零常返的关系）：

（1）当状态是非周期的，定义 \(v_n=p_{ii}^{(n)} - p_{ii}^{(n-1)},n > 1\)，\(v_0=p_{ii}^{(0)}\)，于是有 \(V(z)=\sum_{n=0}^{\infty} v_nz^{-n} = \frac{1-z^{-1} }{1-F_i(z)}\)，利用洛必达法则有 \(\lim_{z\to 1}V(z) = -1/F_i'(1) = 1/\mu_i\)。另一方面 \(\lim_{z\to1}V(z)=\lim_{n\to\infty}\sum_{k=0}^\infty v_k=\lim_{n\to\infty} p_{ii}^{(n)}\)，因此有 \[ \lim_{n\to\infty} p_{ii}^{(n)}=1/\mu_i \]

根据正常返和零常返的定义知道：

当 \(i\) 是正常返时，\(\lim_{n\to\infty} p_{ii}^{(n)}=1/\mu_i\ne0\)；

当 \(i\) 是零常返时，\(\lim_{n\to\infty} p_{ii}^{(n)}=1/\mu_i=0\)。

（2）当状态是周期的，记状态 \(i\) 的周期为 \(T\)，当 \(n\) 不是 \(T\) 的整数倍时有 \(f_{ii}^{(n)}=0\)，\(F_i(z)=\sum_{k=0}^\infty f_{ii}^{(kT)}z^{-kT}=\psi(z^T)\)，相应的 \(P_i(z)=\frac{1}{1-\psi(z^T)}\)。类似非周期情况的讨论可以得到 \[ p_{ii}^{(nT)}\to T/\mu_i \]

当 \(i\) 是正常返时，\(\lim_{n\to\infty} p_{ii}^{(nT)}=T/\mu_i\ne0\)，\(\lim_{n\to\infty} p_{ii}^{(nT+k)}=0,0 < k < T\)；

当 \(i\) 是零常返时，\(\lim_{n\to\infty} p_{ii}^{(n)}=1/\mu_i=0\)。

Discussion（\(p_{ij}^{(n)}\)与正常返、零常返的关系）：由于 \(p_{ij}^{(n)} = \sum_{l=1}^n f_{ij}^{(l)}p_{jj}^{(n-l)}\)，定义相应的 z 变换可以得到 \(P_{ij}(z)=F_{ij}(z)P_j(z) = \frac{F_{ij}(z)}{1-F_j(z)}\)。当 \(j\) 为常返态时，利用洛必达法则有 \(\lim_{z\to1+}(1-z^{-1})P_{ij}(z) = \lim_{z\to1+}\frac{1}{F_j'(z)}\lim_{z\to1+}F_{ij}(z) = f_{ij}/\mu_j\)，而左端等于（利用Hardy-Littlewood引理） \(\lim_{z\to1+}(1-z^{-1})P_{ij}(z) = \lim_{n\to\infty} \frac{1}{n+1}\sum_{k=0}^\infty p_{ij}^{(k)}\)，因此有 \[ \lim_{n\to\infty} \frac{1}{n+1}\sum_{k=0}^\infty p_{ij}^{(k)} = \frac{f_{ij} }{\mu_j} \]

当 \(j\) 是正常返时，\(\lim_{n\to\infty} \frac{1}{n+1}\sum_{k=0}^\infty p_{ij}^{(k)} = {f_{ij} }/{\mu_j}\) 为有限值；

当 \(j\) 是零常返时，\(\lim_{n\to\infty} \frac{1}{n+1}\sum_{k=0}^\infty p_{ij}^{(k)}=0\)。

6.3.3 状态间的等价关系

对马尔科夫链而言，状态互通是一种等价关系，对于状态进行归类有助于简化后续分析过程。

定理 6.4：

1. 若状态 \(i\) 常返，并且 \(i\to j\)，则状态 \(j\) 也是常返的，并且 \(f_{ji}=1\)；
2. 如果 \(i\leftrightarrow j\)，则状态 \(i,j\) 同为常返或非常返态；若为常返态，则他们同为正常返或零常返；
3. 如果 \(i\leftrightarrow j\)，则状态 \(i,j\) 有相同的周期。

证明：（1）存在 \(N\) 使得 \(p_{ij}^{(N)} > 0\)，从 \(i\) 出发到 \(j\) 不返回 \(i\) 的概率为 \(p_{ij}^{(N)}(1-f_{ji})=0\)，因此 \(f_{ji}=1\)。由于 \(i\leftrightarrow j\)，存在 \(N_1,N_2\) 有 \(p_{ij}^{(N_1)} > 0,p_{ji}^{(N_2)} > 0\)，那么 \(p_{jj}^{(N_1+n+N_2)} \ge p_{ij}^{(N_1)}p_{ii}^{(n)}p_{ji}^{(N_2)}=abp_{ii}^{(n)}\)，因此有 \(\sum_{n=0}^{\infty} p_{jj}^{(n)} = \infty\)，因此状态 \(j\) 是常返的。

（2，3）略。