主要是按照讲义来的，课堂上讲得比较浅，所以这篇文章也不会讨论太深。如果发现错误欢迎指出~

基本概念

随机过程（stochastic processes）本质是一个二元函数 $X(\omega,t)$，它既可以看成一族随机变量的集合，也可以看成一族样本函数的集合。

例：扔三次傻子，样本空间是 ${1,2,3,4,5,6}^3$，$t$ 取值 $1,2,3$. 若是固定 $\omega=(2,5,1)$，则得到一个样本函数 $X((2,5,1),t)$. 若是固定 $t=2$，则得到一个随机变量 $X(\omega,2)=X_2$.

总之：

随机过程固定一个样本，得到一个样本函数（轨道）
随机过程确定一个时间，得到一个随机变量

注：这么一大坨随机变量，要定义在同一个概率空间上。概率空间的存在性不是那么显然。通常可以考虑用乘积概率空间。而当随机变量的个数是无穷个时，可以考虑 Kolmogorov 相容性定理。由于本课内容很浅，所以不过多讨论了。

离散时间的马尔可夫过程 ${X_n, n=0,1,\cdots}$ 叫做马尔可夫链。我们主要研究状态转移概率不随时间改变（stationary transition probabilities）的马尔可夫过程。可以写出状态转移矩阵 $P$.

从此刻起，若无特别说明，我们讨论的都是 Markov chain with stationary transition probabilities.

于是有如下记号：

$$ \begin{align} P_{ij}&=P(X_{1}=j|X_0=i),\\ P_{ij}^n&=P(X_{n}=j|X_0=i). \end{align} $$

为了和老师讲义的记号统一，这里用了 $P_{ij}^n$，但要注意 $n$ 不是指数运算。后面的 $f_{ij}^n$ 同理。

特别地，$P_{ij}^0=\delta_{ij}$.

接下来的概念可以结合图来理解。我们把马尔可夫链想象成一个加权有向图 $G(V,E)$，顶点是所有状态，$P$ 是邻接矩阵（图中可能存在自环）。

定义（accessible） 如果从状态 $i$ 到 $j$ 的概率不为 $0$ （$\exists n,P_{ij}^n>0$），则称 $j$ 可从 $i$ 到达（accessible）。

对应图论，accessible 等价于存在 $i$ 到 $j$ 的路径（path）。

定义（communicate） 如果 $i$ 可达 $j$ 且 $j$ 可达 $i$，称 $i$ 和 $j$ 互通（communicate），记作 $i\leftrightarrow j$.

对应图论，communicate 等价于双连通。显然 communicate 是一个等价关系，因此可以划分等价类。对应到图就是强连通分量。在同一个连通分量内的状态可以自由转移。后面我们将看到，对于常返类来说，而不在同一个连通分量则永世不得相见。

定义（irreducible） 如果任意两个状态都互通（即上述等价类只有一个），则称为不可约的（irreducible）。

对应图论，就是强连通图。

周期性

定义（period） 状态 $i$ 的周期（period）定义为 ${n\ge 1|P_{ii}^n>0}$ 的最大公约数（g.c.d.），记作 $d(i)$。特别地，若 $P_{ii}^n=0,n\geq 1$，则 $d(i)=0$.

定理如果 $i\leftrightarrow j$，则 $d(i)=d(j)$.

该定理表明，同一个互通分量周期是一样的，所以我们可以直接讨论互通分量的周期。证明留做习题。

定理设 $i$ 的周期为 $d(i)$，则 $\exists N,\forall n>N,P_{ii}^{nd(i)}>0$.

只要 $n$ 足够大，便可体现出“周期”的性质。

定义（aperiodic） 如果每个状态周期都是 1，则该马尔可夫链是非周期的（aperiodic）。

从分析的角度看，周期蕴含着震荡，而震荡往往是分析中不想看到的，所以我们主要关注非周期的马尔可夫链。我们很快就会发现非周期很多优秀的分析性质。

常返性

我们定义首达概率 $f_{ij}^n$ 为：“从状态 $i$ 出发，下一次到达状态 $j$ 的步数为 $n$ 步”的概率。即 $$ f_{ij}^n=P(X_n=j,X_v\ne j,v=1,\cdots,n-1|X_0=i). $$ 特别地，$f_{ij}^0=0$.

记 $f_{ij}^=\sum_{n=1}^{\infty}f_{ij}^n$, 表示状态 $i$ 能在有限步之内到达状态 $j$ 的概率。容易发现： $$ \begin{align} i\rightarrow j&\Leftrightarrow f_{ij}^>0,\\ i\leftrightarrow j&\Leftrightarrow f_{ij}^>0, f_{ji}^>0. \end{align} $$ 我们可以递归地计算 $f_{ij}^n$： $$ P_{ij}^n=\sum_{k=0}^nf_{ij}^kP_{jj}^{n-k}.\ (n\ge1) $$ 稍有常识的人应该已经发现了，这不就是离散卷积嘛！于是考虑母函数： $$ F_{ij}(s)=\sum_{n=0}^\infty f_{ij}^n s^n,\ P_{ij}(s)=\sum_{n=0}^\infty p_{ij}^n s^n. $$ 易证 $F_{ij},P_{ij}$ 收敛半径为 $1$，并且在 $1$ 处“左连续”（允许函数值为 $+\infty$）。将上面的卷积写成母函数的形式，即得 $$ F_{ij}(s)P_{jj}(s)=P_{ij}(s)-\delta_{ij},\ 0\leq s\leq 1. $$ 定义（recurrence） 我们称状态 $i$ 是常返的（recurrence），如果 $f_{ii}^*=1$. 反之称其为非常返态或过渡态（transient）。

常返是一个非常浪漫的概念。一个状态是常返的，意味着每一次别离都不会是永别，尽管暂时离开了这个状态，在有限的时间内它几乎必然会再次和我们相见。

关于常返，我们有以下两条重要结论。

定理

$\sum_{n=0}^\infty P_{ii}^n=\dfrac{1}{1-f_{ii}^*},\ (1/0=+\infty)$, 特别地，$i$ 常返当且仅当 $\sum P_{ii}^n=\infty$.
如果 $i\leftrightarrow j$，则 $i$ 和 $j$ 常返性相同。

$\sum_{n=0}^\infty P_{ii}^n$ 可以理解为状态 $i$ 出现的次数的期望。常返状态一定会在有限步之内返回，返回之后过有限步再次返回，子子孙孙无穷尽也，所以状态 $i$ 要出现无穷多次。

定理定义 $Q_{ij}$ 为从状态 $i$ 出发无限多次到达状态 $j$ 的概率，可以得到以下结论（证明作为练习）：

若 $j$ 非常返，对任意 $i$，$Q_{ij}=0$,
若 $j$ 常返，对任意 $i$，$Q_{ij}=f_{ij}^*$,
特别地，若 $i\leftrightarrow j$ 且常返，$Q_{ij}=f_{ij}^*=1$.

我们再来介绍两个常返过程的判定定理。

定理设 $B$ 是不可约马尔科夫链，状态空间是自然数。$B$ 过渡（即每个状态都是过渡态）的充要条件是方程组 $$ \sum_{j=0}^\infty P_{ij}y_j=y_i,i\ne0 $$ 有有界的非常数解（即 $y_i$ 不全相等）。

定理不可约马尔科夫链常返的充分条件是：存在一列 ${y_i}$，使得得得得得得得得得得得得，十七张牌你能秒我（~~？抽什么疯~~）；存在一列 ${y_i}$，使得 $$ \sum_{j=0}^\infty P_{ij}y_j\le y_i,i\ne 0, $$ 且 $y_i\to\infty$.

极限性态

我们考虑三个问题：

$\lim_{n\to\infty}P_{ij}^n$ 的值
是否存在一个分布 $\pi$，使得 $\pi P=P$
给定起始分布 $\pi(0)$, 其极限分布 $\lim_{n\to\infty}\pi_0P^n$ 是多少

这部分的讨论比较繁杂，但结论却出奇地简洁。为了防止考试的时候用了不该用的结论，这里直接放讲义中的结论，详细讨论见附录。

结论令 $\mu_j={\sum_{k=1}^\infty kf_{jj}^k},\ \pi_j=\dfrac{1}{\mu_j}$ （若 $\mu_j=\infty$ 则 $\pi_j=0$）. 对于一般情况，有结论：

若 $j$ 非常返，则 $\lim_{n\to\infty} P_{ij}^n=0$,
若 $j$ 非周期且常返，则 $\lim_{n\to\infty} P_{ij}^n=\dfrac{f_{ij}^*}{\mu_j}.$

结论对于**非周期，不可约，正常返（$\mu_j>0$）**状态，有结论：

$\lim_{n\to\infty}P_{ij}^n=\pi_j$, 即从任意起始分布出发，都会收敛到这个极限分布
$\pi_j$ 是唯一的平稳分布，也是唯一的极限分布。

附录

极限性态的讨论

$1. \lim_{n\to\infty}P_{ij}^n$

定理（Markov 链的极限性态） 若 $j$ 是非常返状态，则 $\lim_{n\to\infty} P_{ij}^n=0$. 若 $j$ 非周期且常返，则 $$ \lim_{n\to\infty} P_{ij}^n=\dfrac{f_{ij}^*}{\sum_{k=1}^\infty kf_{jj}^k}. $$ 特别地，若等式右边分母不收敛则定义为 $0$.

该命题的证明已经超出本课程要求。我查阅了许多教材，似乎没找到完美的证明，都在互相踢皮球。所以我也不给证明了。如果有哪位大佬知道初等的证明欢迎补充！

$j$ 是周期常返状态的情况过于复杂，这里不介绍。

尽管证明复杂，但结论非常直观。这是因为 ${\sum_{k=1}^\infty kf_{jj}^k}$ 表示从 $j$ 出发首此回到 $j$ 的时间期望，也就是下一次回来的平均时间，而 $f_{ij}^*$ 是从 $i$ 出发能到达 $j$ 的概率。

我们令 $\mu_j={\sum_{k=1}^\infty kf_{jj}^k}$. 若 $i$ 和 $j$ 同属一个非周期的常返类，易证 $\mu_i<\infty\Leftrightarrow\mu_j<\infty$. 于是有以下定义。

定义对于非周期常返类，若 $\mu_j<\infty$, 则称为正常返（positive recurrent）或强遍历（strong ergodic），否则称之为零常返（null recurrent）或弱遍历（weak ergodic）。

注意：这个定义和一些国内教材有细微差别！许多国内教材称 $\mu_j<\infty$ 为正常返，非周期且正常返称为遍历。

2. 平稳分布

定义若概率分布 $\pi={\pi_1,\cdots}$ 满足 $\pi=\pi P$, 则称其为马氏链的平稳分布。

以下定理揭示了平稳分布和平稳过程的关系，请自行证明。

定理马氏链为平稳过程的充要条件是起始状态 $\pi(0)$ 是平稳分布。

对于强遍历类，我们有非常漂亮的结论将转移矩阵的极限和平稳分布联系起来。证明留作练习。

定理对于强遍历类， $\pi_j=\lim_{n\to\infty}P_{jj}^n=\dfrac{1}{\mu_j}$ 是唯一的平稳分布，即 $$ \pi_j=\sum_{i}\pi_i P_{ij},\ \sum_i \pi_i=1 $$ 且 $\pi_i$ 是方程 $$ \pi_i\ge 0,\ \sum_i \pi_i=1,\ \pi_j=\sum_i \pi_i P_{ij} $$ 的唯一解。

3. 极限分布

仍然是强遍历类才有这么优良的性质。证明仍旧略。

定理强遍历类的平稳分布就是极限分布。

4. 讲义上的 3.2

其实 3.2 的内容在上面已经包含了。

相联通的两个状态的常返性相同，因此我们可以直接考虑强连通分量，画出更简洁的图示：

我们发现每个常返类都是一个“黑洞”，进去就出不来（自行证明）。设 $T$ 为所有过渡态的集合，我们记 $\pi_i(C)$ 为从状态 $i\in T$ 在有限步之内进入常返类 $C$ 的概率，有以下结论：

定理设 $C$ 是非周期常返类，且 $j\in C$，则对 $i\in T$，有 $$ \lim_{n\to\infty}P_{ij}^n=\pi_i(C)\lim_{n\to\infty} P_{jj}^n. $$ 注意之前说过，对非周期常返状态，$\lim_{n\to\infty} P_{jj}^n=\dfrac{1}{\mu_j}$，相当于其停留在这一状态的概率。所以这一定理就很直观了：第一步是进入常返类，概率是 $\pi_i(C)$，第二步是在常返类中选一个状态，选到 $j$ 的概率是 $\lim_{n\to\infty} P_{jj}^n$.

这里的 $\pi_i(C)$ 其实就是 $f_{ij}^*$ ，所以和前面的结论是一致的。