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\inS\)，若存在自然数 \(n\) 使得\(p_{ij}^{(n)} > 0\)，则称自状态\(i\) 出发可达状态 \(j\)，记为...