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

基本概念

随机过程(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 的内容在上面已经包含了。

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

image-20211011185612207

我们发现每个常返类都是一个“黑洞”,进去就出不来(自行证明)。设 $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}^*$ ,所以和前面的结论是一致的。