【状态的基本属性】

首达概率与迟早概率

设马尔可夫链 ${X_{n}, n \geq 0}$ ，当 $i, j \in S$ ，称：

f_{i j}^{(n)} = P (X_{n} = j, X_{k} \neq j, k = 1, 2, \dots, n - 1 | X_{0} = i)

为 ${X_{n}, n \geq 0}$ 在 $0$ 时刻从状态 $i$ 出发，经过 $n$ 步转移后，首次达到状态 $j$ 的概率，简称为首达概率，称

f_{i j} = \sum_{n = 1}^{\infty} f_{i j}^{(n)} = P (⋃_{n = 1}^{\infty} (X_{n} = j, X_{k} \neq j, k = 1, 2, \dots, n - 1) | X_{0} = i)

为 ${X_{n}, n \geq 0}$ 在 $0$ 时从状态 $i$ 出发，经过有限步转移后，迟早要达到状态 $j$ 的概率，简称为迟早概率，称

f_{i j}^{(+ \infty)} = P (X_{n} \neq j, n = 1, 2, \dots, n - 1) | X_{0} = i)

为 ${X_{n}, n \geq 0}$ 在 $0$ 时从状态 $i$ 出发，永远也无法达到状态 $j$ 的概率

对于首达概率和迟早概率，其与马尔可夫链的转移概率有如下关系：

\begin{aligned} 0 \leq & f_{i j}^{(n)} \leq p_{i j}^{(n)} \leq f_{i j} \leq 1 \\ p_{i j}^{(n)} & = \sum_{l = 1}^{n} f_{i j}^{(l)} p_{j j}^{(n - l)} \\ f_{i j}^{(n)} & = \sum_{i_{1} \neq j} \sum_{i_{2} \neq j} \dots \sum_{i_{n - 1} \neq j} p_{i i_{1}} p_{i_{1} i_{2}} \dots p_{i_{n - 1} j} \end{aligned}

首达时刻

设马尔可夫链 ${X_{n}, n \geq 0}$ ，当 $j \in S$ ，称

T_{j} = min {n | n \geq 1, X_{n} = j}

为 ${X_{n}, n \geq 0}$ 首次到达状态 $j$ 的时间，简称首达时刻，显然， $T_{j}$ 是一个随机变量

当 ${n | n \geq 1, X_{n} = j} = \emptyset$ ，即 $\forall n \geq 1, X_{n} \neq j$ 时，定义

T_{j} = + \infty

即系统在有限时间内，不可到达状态 $j$

首达时刻与首达概率和迟早概率有如下关系：

\begin{aligned} f_{i j}^{(n)} & = P (T_{j} = n | X_{0} = i) \\ f_{i j} & = P (T_{j} < + \infty | X_{0} = 0) \end{aligned}

平均转移步数与平均返回时间

设马尔可夫链 ${X_{n}, n \geq 0}$ ，当 $j \in S$ 时，其首达时刻为 $T_{j}$ ，称

μ_{i j} = E (T_{j} | X_{0} = i) = \sum_{n = 1}^{\infty} n f_{i j}^{(n)}

为从状态 $i$ 出发，首次到达状态 $j$ 的平均转移步数，称

μ_{j j} = E (T_{j} | X_{0} = j) = \sum_{n = 1}^{\infty} n f_{j j}^{(n)}

为从状态 $j$ 出发，首次返回状态 $j$ 的平均返回时间

周期

设马尔可夫链 ${X_{n}, n \geq 0}$ ，当 $i \in S$ ，若 ${n | n \geq 1, p_{i i}^{(n)} > 0} \neq \emptyset$ ，则称

d_{i} = GCD {n | n \geq 1, p_{i i}^{(n)} > 0}

为状态 $i$ 的周期，若 ${n | n \geq 1, f_{i i}^{(n)} > 0} \neq \emptyset$ ，则有

h_{i} = GCD {n | n \geq 1, f_{i i}^{(n)} > 0}

对于 $d_{i}$ 和 $h_{i}$ ，有如下性质：

1）若 $p_{i j}^{(n)} > 0$ ，则存在 $m \geq 1$ ，使得

n = m d_{i}

2）若 $f_{i j}^{(n)} > 0$ ，则存在 $m^{'} \geq 1$ ，使得

n = m^{'} h_{i}

3）若 $d_{i}$ 和 $h_{i}$ 中一个存在，则另一个也存在，且

d_{i} = h_{i}

【状态】

可约与不可约

设马尔可夫链 ${X_{n}, n \geq 0}$ ，对任意 $i, j \in S$ ，若存在任一时刻 $t > 0$ ，满足：

P (X_{t} = i | X_{0} = j) > 0

即在 $0$ 时刻从状态 $j$ 出发，在 $t$ 时刻到达状态 $i$ 的概率大于 $0$ ，则称马尔可夫链 ${X_{n}, n \geq 0}$ 是不可约的，否则称是可约的

直观上，一个不可约的马尔可夫链，从任意状态出发，当经过充分长时间后，可以到达任意状态

如下马尔可夫链状态转移图所示，其转移概率矩阵

[\begin{matrix} 0 & \frac{1}{2} & 0 \\ 1 & 0 & 0 \\ 0 & \frac{1}{2} & 1 \end{matrix}]

其平稳分布 $π = (0, 0, 1)^{T}$ ，即该马尔可夫链转移到状态 $3$ 后，就在该状态上循环，无法到达状态 $1$ 与状态 $2$ ，故该马尔可夫链是可约的

周期与非周期

设马尔可夫链 ${X_{n}, n \geq 0}$ ，对任意 $i \in S$

若状态 $i$ 的周期 $d_{i} > 1$ ，则称状态 $i$ 为周期为 $d_{i}$ 的周期状态，称该马尔可夫链为周期的
若状态 $i$ 的周期 $d_{i} = 1$ ，则称状态 $i$ 为非周期状态，称该马尔可夫为非周期的

直观上，一个非周期性的马尔可夫链，不存在一个状态，从这个状态出发，再返回到这个状态时所经历的时间呈周期性

如下马尔可夫链状态转移图所示，其转移概率矩阵

[\begin{matrix} 0 & 0 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}]

其平稳分布 $π = (\frac{1}{3}, \frac{1}{3}, \frac{1}{3})^{T}$ ，即该马尔可夫链从每个状态出发，返回该状态的时刻都是 $3$ 的倍数，具备周期性，最终停留在每个状态的概率都是 $\frac{1}{3}$ ，故该马尔可夫链是周期的

常返与非常返

设马尔可夫链 ${X_{n}, n \geq 0}$ ，对任意 $i \in S$

若从状态 $i$ 到状态 $i$ 的首达概率 $f_{i i} = 1$ ，则称状态 $i$ 为常返状态或返回状态，称该马尔可夫链为常返的
若从状态 $i$ 到状态 $i$ 的首达概率 $f_{i i} < 1$ ，则称状态 $i$ 为非常返状态或滑过状态，称该马尔可夫链为非常返的

正常返与零常返

设马尔可夫链 ${X_{n}, n \geq 0}$ ，对任意 $i \in S$

若状态 $i$ 为常返状态，且状态 $i$ 的平均返回时间 $μ_{i i} < + \infty$ ，则称状态 $i$ 为正常返状态，称该马尔可夫链为正常返的
若状态 $i$ 为常返状态，且状态 $i$ 的平均返回时间 $μ_{i i} = + \infty$ ，则称状态 $i$ 为零常返状态或消极常返状态，称该马尔可夫链为零常返的

直观上，一个正常返的马尔可夫链，其中任意一个状态，从其他任意一个状态出发，当时间趋于无穷时，首次转移到这个状态的概率不为 $0$

对于不可约、非周期且正常返的马尔可夫链，有唯一平稳分布存在

如下马尔可夫链状态转移图所示，其转移概率矩阵

[\begin{matrix} p & p & 0 & 0 & \dots \\ q & 0 & p & 0 & ⋱ \\ 0 & q & 0 & p & ⋱ \\ 0 & 0 & q & 0 & ⋱ \\ ⋮ & ⋱ & ⋱ & ⋱ & ⋱ \end{matrix}]

当 $p > q$ 时，其平稳分布 $π = (\frac{q}{p})^{i} (\frac{p - q}{p}), i = 1, 2, \dots$ ，即当时间趋于无穷时，转移到任何一个状态的概率不为 $0$ ，故该马尔可夫链是正常返的

当 $p \leq q$ 时，不存在平稳分布，故该马尔可夫链是零常返的

遍历与非遍历

设马尔可夫链 ${X_{n}, n \geq 0}$ ，对任意 $i \in S$

若状态 $i$ 为不可约、正常返，且是非周期的，则称状态 $i$ 为正常返非周期状态或遍历状态，称该马尔可夫链为遍历的
若状态 $i$ 为不可约、正常返，且是周期的，则称状态 $i$ 为正常返周期状态或非遍历状态，称该马尔可夫链为非遍历的

不可约、正常返、非周期保证了当时间趋于无穷时，到达任一状态的概率不为 $0$

【遍历定理】

对于马尔可夫链的遍历状态，有如下的遍历定理

设马尔可夫链 ${X_{n}, n \geq 0}$ ，若其是不可约、非周期、正常返的，即该马尔可夫链是遍历的，那么该马尔可夫链有唯一分布 $π = (π_{1}, π_{1}, \dots)^{T}$ ，且转移概率的极限分布是马尔可夫链的平稳分布，即：

lim_{t \to \infty} P (X_{t} = i | X_{0} = j) = π_{i}, i = 1, 2, \dots; j = 1, 2, \dots

若 $f (X)$ 是定义在状态空间 $S$ 上的函数，且 $f (X)$ 关于平稳分布 $π = (π_{1}, π_{1}, \dots)^{T}$ 的数学期望 $E_{π} [| f (X) |] = \sum_{i} f (i) π_{i} < \infty$ ，则该函数的样本均值 $\hat{f_{t}} = \frac{1}{t} \sum_{s = 1}^{t} f (x_{s})$ 以概率 $1$ 收敛于 $E_{π} [| f (X) |]$ ，即：

P {\hat{f_{t}} \to E_{π} [| f (X) |]} = 1

遍历定理的直观解释是：满足不可约、非周期、正常返的马尔可夫链，当时间趋于无穷时，马尔可夫链的状态分布趋于平稳分布，随机变量的函数的样本均值以概率 $1$ 收敛于该函数的数学期望

遍历定理实际上表达了马尔可夫链遍历性的含义：样本均值可以认为是时间均值，数学期望可以认为是空间均值，当时间趋于无穷时，时间均值等同于空间均值

实际应用时，通常是取一个足够大的整数 $m$ ，经过 $m$ 次迭代后便认为状态分布就是平稳分布，此时从第 $m + 1$ 次迭代到第 $n$ 次迭代的均值，被称为遍历均值，即：

\hat{E} f = \frac{1}{n - m} \sum_{i = m + 1}^{n} f (x_{i})

【状态的可达与互通】

设马尔可夫链 ${X_{n}, n \geq 0}$ ，当 $i, j \in S$ ，若存在 $n \geq 1$ ，使得

p_{i j}^{(n)} > 0

则称状态 $i$ 可达状态 $j$ ，记为 $i \to j$

若状态 $i$ 可达状态 $j$ ，且状态 $j$ 可达状态 $i$ ，即

i \to j, j \to i

则称状态 $i$ 与状态 $j$ 互通，记为 $i \leftrightarrow j$

对于状态的可达与互通，有：

可达的传递性：若 $i \to j, j \to k$ ，则 $i \to k$
互通的传递性：若 $i \leftrightarrow j, j \leftrightarrow k$ ，则 $i \leftrightarrow k$
互通的对称性：若 $i \leftrightarrow j$ ，则 $j \leftrightarrow i$

此外，对于互通的两个状态 $i, j \in S$ ，他们有相同的类型，即设 $i, j \in S$ ，且 $i \leftrightarrow j$ ，则 $i, j$ 有：

两者同为非常返状态
两者同为零常返状态
两者同为遍历状态
两者同为非遍历状态且周期相同