1. 马氏过程
1.1. 马氏链
考虑离散时间的随机过程$~X_n(n = 1, 2, \cdots)~$，$~X_n~$在有限集合内取值。我们称$~X_n~$的所有可能取值为系统的状态。
定义转移概率为
$$ p_{n+1}(i, j) = \mathbb P(X_{n+1} = j\mid X_n = i, X_{n-1} = i_{n-1}, \cdots, X_0 = i_0) $$
转移概率是一个条件概率。
这是一个离散时间，离散状态的随机过程。
若$~p_{n+1}(i, j) = \mathbb P(X_{n+1} = j\mid X_n = i)~$，则称这个过程具有马氏性（马尔可夫性）。
马尔可夫性即是说，转移概率只与当前的状态有关，与先前任何时间的状态都无关。
若时刻$~n~$的取值与转移概率无关，即对任意$~n~$都有
$$ \mathbb P(X_{n+1} = j\mid X_n = i) = p(i, j) $$
则称转移概率具有时齐性，相应的马氏链称作时齐马氏链。
转移概率$~p(i, j)~$的相应数值，可以标注在矩阵$~\mathbf P~$的第$~i~$行，第$~j~$列。我们称这个矩阵为转移矩阵
$$ \mathbf P = \begin{pmatrix} p(0, 0) & p(0, 1) & \cdots & p(0, N) \\ p(1, 0) & p(1, 1) & \cdots & p(1, N) \\ \vdots & \vdots & \ddots & \vdots \\ p(N, 0) & p(N, 1) & \cdots & p(N, N) \end{pmatrix} $$
转移矩阵是一个$~(N+1)\times (N+1)~$矩阵。
马氏链有如下性质：
- 转移概率非负，即$~p(i, j) \ge 0~$.
- 转移矩阵每行元素之和均为$~1~$，即$~\displaystyle\sum_{j}p(i, j) = 1~$.
1.2. 多步转移概率
转移概率$~p(i, j) = \mathbb P(X_{n+1} = j\mid X_n = i)~$给出了从状态$~i~$到状态$~j~$的一步转移概率，类似地，从$~i~$到$~j~$的$~m~$步$~(m > 0)~$转移概率定义为
$$ p^m(i, j) = \mathbb P(X_{n+m} = j\mid X_n = i) $$
可以证明，$~m~$步转移矩阵$~\mathbf P^m~$是$~1~$步转移矩阵$~\mathbf P~$的$~m~$次幂，$~p^m(i, j)~$是$~m~$步转移矩阵$~\mathbf P^m~$第$~i~$行，第$~j~$列的元素。
我们有$~\text{C-K}~$方程，即$~\text{Chapman-Kolmogorov}~$方程：
$$ p^{m+n}(i, j) = \mathbb P(X_{m+n} = j\mid X_0 = i) = \sum_k p^m(i, k)\cdot p^n(k, j) $$
由$~\text{C-K}~$方程，可以得到如下不等式
$$ p^{m+n}(i, j) \ge p^m(i, k)\cdot p^n(k, j),\quad \forall k $$
1.3. 状态的分类
研究马氏链主要进行两类分析：瞬态分析和稳态分析。
- 瞬态分析是研究在某一固定时刻$~n~$，马氏链对应系统的概率特征，即求$~n~$步转移概率。
- 稳态分析则是研究当$~n\to \infty~$时，马氏链对应系统的概率特征。
记几个符号
- 初始时刻状态为$~x~$的条件下，事件$~A~$发生的概率$~\mathbb P_x(A) = \mathbb P(A\mid X_0 = x)~$.
- 首次返回状态$~y~$的最短时间$~T_y = \min\{n: n\ge 1, X_n = y\}~$. $~T_y~$可看作一个停时。
- 从初始时刻状态$~y~$经过有限步首次返回到状态$~y~$的概率$~\rho_{yy} = \mathbb P_y(T_y < \infty)~$.
由于当$~n = 0~$时$~\rho_{y}\equiv 1~$，故为避免此情况，我们规定$~n \ge 1~$. 不难看出，从初始时刻状态$~y~$返回状态$~y~$的次数为$~k~$的概率为$~\rho_{yy}^k~$.
当某事件在时刻$~n~$停止，记$~\{T = n\}~$为停时。若$~T_y~$是一个停时（首次返回状态$~y~$的最短时间），则可以表示为
$$ \{T_y = n\} = \{X_n = y, X_{n-1}\neq y,\cdots, X_1 \neq y\} $$
停时也可以满足马氏性。我们称这样的马氏性为强马氏性。设$~T~$是停时，假定$~T = n, X_T = y~$，则关于$~X_0, \cdots, X_T~$的其他信息与未来的预测无关，并且$~X_{T + k}, k \ge 0~$的行为与初始状态为$~y~$的马氏链相同。即：
$$ \begin{aligned} \mathbb P(X_{T+1} &= z\mid X_T = y, T = n) = \mathbb P(X_1 = z\mid X_0 = y) = p(y, z) \\ \mathbb P(X_{T+k} &= z\mid X_T = y, T = n) = \mathbb P(X_k = z\mid X_0 = y) = p^k(y, z), \quad k\ge 1 \end{aligned} $$
马氏性中，时间$~n~$的取值是确定的；在强马氏性中，停时$~T~$是随机的。对于随机的$~T~$，马氏性，仍成立，条件更强，故称强马氏性。
定义符号$~T_y^k = \min\{n : n > T_y^{k-1}, X_n = y\}~$为第$~k~$次返回状态$~y~$的最短时间；$~\mathbb P_y(T_y^k < \infty) = \rho_{yy}^k~$为经过有限时间返回状态$~y~$次数为$~k~$的概率。
- 若$~\rho_{yy} < 1~$，此时随着$~k\to \infty~$，有$~\rho_{yy}^k \to 0~$. 这意味着最终马氏链不再回到状态$~y~$，该状态$~y~$称为非常返态，也称暂态。
- 若$~\rho_{yy} = 1~$，此时$~\rho_{yy}^k = 1~$. 这意味着马氏链回到状态$~y~$的次数有无穷多次，该状态$~y~$称为常返态。
若$~\rho_{yy} < 1~$，则系统可能无法从状态$~y~$再次回到状态$~y~$；若$~\rho_{yy} = 1~$，则系统一定能在有限时间从状态$~y~$返回状态$~y~$.
常返态有一个特例，即吸收态：如果$~p(y, y) = 1~$，即$~\mathbb P_y(T_y = 1) = 1~$，则$~y~$是吸收态，此时$~y~$是非常强的常返态，因为链将会一直留在那里。
这两种性质有等价的表达式：
非常返：状态$~y~$有正的概率不返回$~y~$
$$ \rho_{yy} < 1 \iff \mathbb P_y(T_y < \infty) < 1 \iff \mathbb P_y(T_y = \infty) > 0 $$
常返：状态$~y~$在有限时间内返回$~y~$的概率为$~1~$
$$ \rho_{yy} = 1 \iff \mathbb P_y(T_y < \infty) = 1 \iff \mathbb P_y(T_y = \infty) = 0 $$
1.4. 状态的判定方法
若从状态$~x~$，有正的概率到达状态$~y~$，则称$~x~$可达$~y~$，记作$~x \to y~$，即
$$ \rho_{xy} = \mathbb P_x(T_y < \infty) > 0 $$
也可以表示为
$$ \exist ~n,\text{ s.t. } p^n(x, y) > 0 $$
即从状态$~x~$经过$~n~$步到达状态$~y~$的概率为正。
若$~x~$可达$~y~$，并且$~y~$可达$~x~$，则称$~x~$与$~y~$互通，记作$~x \leftrightarrow y~$. 也可以表示为
$$ \exist~m, n, \text{ s.t. }p^m(x, y)>0, p^n(y, x) > 0 \implies x \leftrightarrow y $$
即从状态$~x~$经过$~m~$步到达状态$~y~$的概率为正，且从状态$~y~$经过$~n~$步到达状态$~x~$的概率也为正。
若$~\rho_{xy} > 0~$，且$~\rho_{yx} < 0~$，则$~x~$是非常返态。互通具有传递性，自反性，对称性，可作为一种分类。对于任何互通类$~C~$而言，其中的所有状态均为常返态或非常返态。
对于状态集合$~A~$，若$~i\in A, j\notin A \implies p(i, j) = 0~$，则称$~A~$为闭集。状态空间的最小闭集称为不可约闭集。
若马氏链只有一个互通类，则称这个链不可约。若马氏链中的互通类超过一个，则称这个链可约。
若对有限状态空间中的任意两个状态$~x~$和$~y~$，存在$~n\in\mathbb Z^+~$，使得$~p^n(x, y) > 0~$，则由此构造的转移矩阵$~\mathbf P~$不可约。
记$~N(y)~$为访问状态$~y~$的次数；$~\mathbb P_x(X_n = y)~$表示初始状态为$~x~$、第$~n~$时刻状态为$~y~$的概率，则从状态$~x~$到$~y~$的访问次数期望值$~\mathbb E_x[N(y)]~$为：
$$ \mathbb E_x[N(y)] = \frac{\rho_{xy}}{1 - \rho_{yy}} = \sum_{n = 1}^{\infty}p^n(x, y) $$
1.5. 平稳分布
如果增加非周期性的假定条件，则一个有限状态的不可约马氏链会收敛于一个平稳分布，即
$$ \lim_{n\to\infty} p^n(x, y) = \pi(y) $$
这个分布$~\pi (y)~$与期初状态是无关的。
用条件概率的定义，有
$$ \begin{aligned} \mathbb P(X_n = j) &= \sum_i \mathbb P(X_0 = i, X_n = j) \\ &= \sum_i\mathbb P(X_0 = i)\mathbb P(X_n = j\mid X_0 = i) \\ &= \sum_i q(i)p^n(i, j) \end{aligned} $$
其中$~q(i) = \mathbb P(X_0 = i)~$是初始概率，由$~q(i), i\in S~$组成的向量$~\mathbf q~$构成初始概率分布。
写成矩阵形式为
$$ \begin{aligned} \mathbf q\mathbf P^n &= \begin{pmatrix} q(1) & q(2) & \cdots & q(k) \end{pmatrix}\begin{pmatrix} p^n(1, 1) & p^n(1, 2) & \cdots & p^n(1, k) \\ p^n(2, 1) & p^n(2, 2) & \cdots & p^n(2, k) \\ \vdots & \vdots & \ddots & \vdots \\ p^n(k, 1) & p^n(k, 2) & \cdots & p^n(k, k) \end{pmatrix} \\ &= \begin{pmatrix} \displaystyle\sum_{i = 1}^k q(i)p^n(i, 1) & \displaystyle\sum_{i = 1}^k q(i)p^n(i, 2) & \cdots & \displaystyle\sum_{i = 1}^k q(i)p^n(i, k) \end{pmatrix} \\ &= \mathbf q^n \end{aligned} $$
记$~\mathbf q\mathbf P^n = \pi~$，若$~\pi \mathbf P = \pi~$，则称$~\pi~$为平稳概率向量，其中的各元素组成平稳概率分布。若$~\displaystyle\lim_{n\to\infty}\mathbb P(X_n = i) = \bar\pi(i)~$，则称此$~\bar\pi(i)~$组成的是极限分布。
对于不可约、非周期的马氏链，其平稳分布和极限分布是相等的。
设$~(k\times k)~$转移矩阵$~\mathbf P~$不可约，则$~\pi\mathbf P = \pi~$存在唯一解，其中$~\displaystyle\sum_k \pi_k = 1,~\forall x, \pi_x > 0~$.
1.6. 极限行为
如果$~y~$是一个非常返态，则对$~\forall x~$，均有
$$ \sum_{n = 1}^\infty p^n(x, y) < \infty $$
从而
$$ p^n(x, y)\to 0 $$
这意味着我们只需要将注意力集中在常返态上，集中在马氏链只包含一个不可约常返集的情形。
一个状态$~x~$的周期是$~I_x = \{ n\ge 1: p^n(x, x) > 0 \}~$的最大公约数，即$~\mathrm{ged}(I_x)~$.
集合$~I_x~$是加法封闭集。
若$~x~$的周期为$~1~$，则$~\exist n_0~$，使得$~n \ge n_0~$时，$~n\in I_x~$，即：$~x~$的周期为$~1~$时，$~I_x~$包含某个数值$~n_0~$之后的所有整数。
若$~p(x, x) > 0~$，则状态$~x~$的周期为$~1~$.
若$~\rho_{xy} > 0~$，且$~\rho_{yx} > 0~$，则状态$~x~$和$~y~$具有相同的周期。
收敛定理：假设$~\mathbf P~$不可约、非周期且具有平稳分布$~\pi~$，则有
$$ \lim_{n\to\infty}p^n(x, y) = \pi(y) $$
假设$~\mathbf P~$不可约，且所有状态均常返，则存在平稳测度$~\mu(x)~$，使得$~\forall x,~\mu(x) > 0~$.
渐进频率：假设$~\mathbf P~$不可约，且所有状态均常返，记$~N_n(y)~$为在时刻$~n~$之前访问$~y~$的总次数，则
$$ \frac{N_n(y)}{n} \to \frac{1}{\mathbb E_y[T_y]},\qquad \text{a.s.} $$
假设$~\mathbf P~$不可约，且具有平稳分布$~\pi~$，则
$$ \pi(y) = \frac{1}{\mathbb E_y[T_y]} $$
这说明状态$~y~$下的平稳分布对应的概率$~\pi(y)~$等于首次返回状态$~y~$期望步数的倒数；并且在状态期间$~n\to\infty~$时等于返回状态$~y~$的次数占整个状态步数$~n~$的比例。
假设$~\mathbf P~$不可约，且具有平稳分布$~\pi~$，并且对$~\forall f: S\to \mathbb R~$，有$~\displaystyle\sum_x|f(x)|\pi(x) < \infty~$（绝对收敛），则
$$ \frac{1}{n}\sum_{m = 1}^n f(X_m) \to \sum_{x\in S}\pi(x)f(x),\qquad \text{a.s.} $$
其中$~f(X_m)~$是状态空间$~S~$下的一个函数，对应的是状态$~m~$下的取值。上式可以理解为：$~n~$各状态下随机变量的平均值，等于平稳状态下随机变量的期望值。
大数定律的前提是随机变量独立同分布，并且随机变量的期望值存在。包含两类：
- 弱大数定律：采样次数$~n~$越大，样本平均值接近随机变量真实期望值的可能性越来越大（即依概率收敛）。
- 强大数定律：采样次数$~n~$越大，样本平均值几乎一定越来越接近随机变量真实期望值（即几乎确定收敛）。
1.7. 一些例子
双随机链：弱转移矩阵格列元素之和均为$~1~$，则称该矩阵$~\mathbf P~$是双随机的。即
$$ \sum_{y}p(x, y) = 1 $$
若$~\mathbf P~$是$~N~$状态马氏链的双随机转移概率，则均匀分布$~\pi(x) = 1 / N,~\forall x~$是其平稳分布。
若$~\mathbf P~$是$~N~$状态马氏链的转移概率，且均匀分布$~\pi(x) = 1/ N,~\forall x~$是其平稳分布，则$~\mathbf P~$是双随机的。
细致平衡条件：如果$~\pi(x)p(x, y) = \pi(y)p(y, x)~$，则称$~\pi~$满足细致平衡条件。
该条件比之前的$~\pi\mathbf P = \pi~$更严格。$~\pi\mathbf P = \pi~$说明在所有的转移结束后，每个状态的概率与初始时的概率相等。而在细致平衡条件下，从$~x~$状态一步转移到$~y~$状态的概率，刚好等于$~y~$状态一步转移至$~x~$状态的概率。
满足细致平衡条件的马氏链一定存在平稳分布，但是具有平稳分布的马氏链不一定满足细致平衡条件。
1.8. 离出分布
离出分布考察的是：对于至少存在两个不同常返类的马氏链，从给定的非常返态$~j~$开始，该马氏链最终进入某一特定常返态$~i~$的概率是多少。换句话说，离出分布考察的是从一个非常返态$~j~$最终被某一状态$~i~$吸收的概率。
非常返态$~x~$最终被状态$~z~$吸收的概率为$~h(x) = \mathbb P(X_T = z\mid X_0 = x)~$，根据$~\text{C-K}~$方程，有
$$ \begin{aligned} \mathbb P(X_T = z \mid X_0 = x) &= \sum_y\mathbb P(X_T = z \mid X_1 = y)\mathbb P(X_1 = y\mid X_0 = x) \\ &= \sum_y p(x, y)\mathbb P(X_T = z\mid X_1 = y) \\ h(x) &= \sum_y p(x, y)h(y) \end{aligned} $$
离出时刻考察的是：对于至少存在两个不同常返类的马氏链，从给定的非常返态$~j~$开始，该马氏链最终进入常返态$~i~$的期望步数是多少。换句话说，离出时刻考察的是从一个非常返态$~j~$最终被吸收态吸收的期望时间。
非常返态$~x~$最终被吸收的期望时间为$~g(x) = \mathbb E_x(T)~$，根据马氏性，对任意非常返态$~y~$，有
$$ \begin{aligned} \mathbb E_x(T) &= 1 + \sum_y \mathbb P(X_1 = y \mid X_0 = x)\mathbb E_y(T) \\ &= 1 + \sum_y p(x, y)\mathbb E_y(T) \\ g(x) &= 1 + \sum_y p(x, y)g(y) \end{aligned} $$
无限状态空间马氏链遇到的新问题是常返并不能保证平稳分布的存在。无限状态空间马氏链也称可数状态马氏链。在无限状态空间中，常返分为两类：
- 正常返：$~\mathbb P_x(T_x < \infty) = 1,~ \mathbb E_x(T_x) < \infty~$.
- 零常返：$~\mathbb P_x(T_x < \infty) = 1,~\mathbb E_x(T_x) = \infty~$.
正常返的马氏链，一定可以找到其对应的平稳分布；若马氏链不存在平稳分布，则其可能为零常返或非常返。
对于一个不可约链，下面的结论等价：
- 某状态是常返的；
- 存在一个平稳分布$~\pi~$；
- 所有的状态都是正常返的。
2. 连续时间马氏链
离散时间马氏链：对任意状态$~i, j, i_0, \cdots, i_{n-1}~$，有
$$ \mathbb P(X_{n+1} = j\mid X_n = i, X_{n-1} = i_{n-1}, \cdots, X_0 = i_0) = \mathbb P(X_{n+1} = j\mid X_n = i) $$
连续时间马氏链：对于任意状态$~i, j, i_0, \cdots, i_{n}~$以及任意时间$~0 \le s_0 < s_1 <\cdots < s_n < s~$，有
$$ \begin{aligned} \mathbb P(X_{t+s} = j\mid X_s = i, X_{s_n} = i_n, \cdots, X_{s_0} = i_0) &= \mathbb P(X_{t+s} = j\mid X_s = i) \\ &= \mathbb P(X_t = j\mid X_0 = i) \end{aligned} $$
这里的$~s_i~$可以取任意的正实数。从时刻$~s~$的状态$~i~$到时刻$~(t + s)~$的状态$~j~$的概率，只依赖于时间间隔$~t~$.
在离散时间马氏链中，时间和状态均是离散的。从状态$~i~$一步转移到状态$~j~$的概率记为$~p(i, j)~$，即
$$ p(i, j) = \mathbb P(X_{t + 1} = j \mid X_t = i) $$
在连续时间马氏链中，时间是连续的，状态是离散的。在$~h > 0~$时间段，从状态$~i~$转移到状态$~j~$的概率记为$~p_h(i, j)~$，即
$$ p_h(i, j) = \mathbb P(X_{t + h} = j\mid X_t = i) = \mathbb P(X_h = j \mid X_0 = i) $$
连续时间马氏链的$~\text{Chapman-Kolmogorov}~$方程为
$$ \sum_k p_s(i, k)p_t(k, j) = p_{s + t}(i, j) $$
当$~h \to 0~$时，我们引入转移速率$~q(i, j)~$，即
$$ q(i, j) = \lim_{h\to 0}\frac{p_h(i, j)}{h} = \lim_{h\to 0}\frac{\mathbb P(X_{t + h} = j\mid X_t = i)}{h},\qquad i\neq j $$
在连续时间马氏链中，我们除了要考虑某一时刻马氏链处于什么状态，还关心它在离开这个状态之前会停留多久。这个停留时间具有无记忆性，服从指数分布。
转移速率$~q(i, j)~$有如下性质
- $~q(i, i) \le 0,~i = 1, 2, \cdots, n~$
- $~q(i, j) \ge 0,~i \neq j,~~i,j = 1, 2, \cdots, n~$
- $~\displaystyle\sum_j q(i, j) = 0,~i = 1, 2, \cdots, n~$
对于$~N~$各状态的连续时间马氏链，其转移速率往往以矩阵形式表示
$$ \mathbf Q = \begin{pmatrix} q(1, 1) & q(1, 2) & \cdots & q(1, N) \\ q(2, 1) & q(2, 2) & \cdots & q(2, N) \\ \vdots & \vdots & \ddots & \vdots \\ q(N, 1) & q(N, 2) & \cdots & q(N, N) \end{pmatrix} $$
降$~[0, t + h]~$拆分成$~[0, h]~$和$~[h, t + h]~$，则
$$ \begin{aligned} p_{t + h}(i, j) - p_t(i, j) &= \left[ \sum_k p_h(i, k)p_t(k, j) \right] - p_t(i, j) \\ &= \left[ \sum_{k \neq i}p_h(i, k)p_t(k, j) \right] + [p_h(i, i) - 1]p_t(i, j) \end{aligned} $$
两端同时除以$~h~$，并令$~h\to 0~$，得到
$$ \lim_{h\to 0}\frac{p_{t + h}(i, j) - p_t(i, j)}{h} = \lim_{h\to 0}\left[ \sum_{k \neq i}\frac{p_h(i, k)}{h}p_t(k, j) \right] + \left[ \lim_{h\to 0}\frac{p_h(i, i) - 1}{h} \right]p_t(i, j) $$
即
$$ \begin{aligned} p'_t(i, j) &= \sum_{k\neq i}q(i, k)p_t(k, j) + \left[ \lim_{h\to 0}\frac{p_h(i, i) - 1}{h} \right]p_t(i, j) \\ &= \sum_{k\neq i} q(i, k)p_t(k, j) - \left[ \lim_{h\to 0}\frac{1 - p_h(i, i)}{h} \right]p_t(i, j) \\ &= \sum_{k\neq i} q(i, k)p_t(k, j) - \lambda_i p_t(i, j) \\ &= \sum_k Q(i, k)p_t(k, j) \end{aligned} $$
其中
$$ Q(i, k) = \begin{cases} q(i, k), & i\neq k \\ -\lambda_i, & i = k \end{cases} $$
这个式子可以用矩阵表示，即
$$ \frac{\mathrm d \mathbf P_t}{\mathrm d t} = \mathbf Q\mathbf P_t $$
该方程称为$~\text{Kolmogorov}~$向后方程。其中$~\mathbf Q~$称为转移速率矩阵。在这里我们将$~[0, t + h]~$拆分成了$~[0, h]~$和$~[h, t + h]~$.
类似地，如果将$~[0, t + h]~$拆分成$~[0, t]~$和$~[t, t + h]~$，就得到向前方程。用矩阵可以简写为
$$ \frac{\mathrm d \mathbf P_t}{\mathrm d t } = \mathbf P_t \mathbf Q $$
2.1. 极限行为
如果对任意状态$~i~$和$~j~$，都有可能从$~i~$经过有限步转移到$~j~$，则称马氏链是不可约的，即
$$ \exist k_0 = i, k_1, \cdots, k_n = j,\quad\text{s.t.}\quad q(k_{m - 1}, k_m) > 0, 1 \le m \le n $$
若$~X_t~$不可约，且$~t > 0~$，则$~p_t(i, j) > 0~$.
随机停留时间满足指数分布，这意味着我们不再需要考虑时间的非周期性，因此连续时间马氏链的极限行为比离散时间马氏链更简单。
在离散时间下，平稳分布是$~\pi\mathbf P = \pi~$的一个解，而在连续时间下，对$~\forall t > 0~$，都有$~\pi\mathbf P_t = \pi~$成立。但在实际操作中，$~\mathbf P_t~$可能难以计算。
分布$~\pi~$是一个平稳分布，当且仅当$~\pi\mathbf Q = 0~$.
如果一个连续时间马氏链$~X_t~$不可约，且具有平稳分布$~\pi~$，则
$$ \lim_{t\to\infty}p_t(i, j) = \pi(j) $$
相应的细致平衡条件为对$~\forall j \neq k~$，满足$~\pi(k)q(k, j) = \pi(j)q(j, k)~$. 若时间连续马氏链满足细致平衡条件，则$~\pi~$是一个平稳分布。我们可以根据此定理，用细致平衡条件来求得平稳分布。
