随机过程（1）——引入，有限状态马尔科夫链，状态转移，常返与瞬时状态

学弱猹

发布于 2021-08-10 11:31:02

1.9K0

发布于 2021-08-10 11:31:02

大家好！这是一个全新的系列，我们会给大家介绍随机过程（Stochastic Process）相关的内容。

随机过程是概率论的延伸，研究的主体是“随机的过程”，也就是说，如果研究对象具备这种“过程”的属性，往往随机过程就会有用武之地。比方说，对于一个随机变量而言，它自然会有一个具体的概率分布，但是随着时间的变化，它的概率分布出现变化，这个变化会导致这个随机变量的性质发生什么变化，就是随机过程的研究内容。严格来说，随机过程属于统计学的内容，但是对于一些应用数学的方向，或者说研究一些具备随机性的问题，随机过程依然是一门极为重要的学科。

不过随机过程的难度也是统计学课程中较大的，也是统计学中少有的非常理论的课程。在掌握这一个系列之前，我们需要大家了解数分高代的内容，并对概率论有一些掌握。这是因为随机过程所需要的概率论知识也已经算是概率论部分较难的知识点了，因此如果对于概率论的知识没有一个系统的体系，对随机过程相关的内容的掌握可能会出现困难，尽管我们一向会在系列中，会努力把证明的细节给大家掰碎了，说明白。

一个比较好的随机过程的参考书是Rick Durrett的 Probability: Theory and Examples，这一本书是国内外高等概率论的常见参考书。不过在这一个系列中，我们参考的是厦门大学的讲义以及Richard Durrett的Essentials of Stochastic Processes。这两本书总体上都还算不错，读者可以各取所需，各得所利。

废话说的足够多了，我们开始吧。

离散马尔科夫链

我们一开始和大家说，随机过程是研究“过程”的，因此我们很强调一个过程中，从这一个状态到下一个状态，会如何演变。而离散马尔科夫链（DIscrete Markov Chain）算是这中间最为简单，理想的一种情况。

Definition 1: Discrete Markov Chain 考虑随机变量序列

\{X_n\}

，如果

\forall i, j, i_{n - 1}, \ldots, i_0

，有

P(X_{n + 1} = j |X_n = i, X_{n - 1} = i_{n - 1}, \ldots, X_0 = i_0) = p(i, j)

那么称

X_n

是转移概率为

p(i,j)

的马尔科夫链。 Definition 2: Transition Probability, Transition Matrix

p(i, j)

定义为转移概率，而在离散马尔科夫链中，所有转移概率可以形成一个转移矩阵

，满足

P_{ij} = p(i, j)

。

这个概率是条件概率，翻译过来就是“在

X_n = i, \ldots

的情况下，

X_{n + 1} = j

的概率”。不难发现，如果可以用一个函数

p(i, j)

描述我们的概率关系，说明这个概率和

i_{n -1}, \ldots, i_0

无关，因此潜在意思就是“当前的状态，只会与上一个阶段的状态有关”。数学上的写法就是

P(X_{n + 1} = j |X_n = i, X_{n - 1} = i_{n - 1}, \ldots, X_0 = i_0) = P(X_{n + 1} = j | X_n = i)

在后面我们还会经常使用

来代替上面的

，因为

一般表示状态的阶段，所以很多时候会用时间这个概念来描述，

很多时候会更直观。

至于为什么说会有个“离散”，也正是因为我们需要

i, j

这些状态（states）是离散的，或者说是可数的（countable）（状态说白了就是随机过程序列

\{X_n\}

的样本空间）。从泛函分析这个角度来说，如果不满足这个条件，会导致后面研究转移概率函数

p(\cdot, \cdot)

的时候出现麻烦。但是在后面的话，我们会用“马尔科夫链”来指代这里的“离散马尔科夫链”，因为一般情况下，马尔科夫链说的就是离散情况。

多提一句，“可数”是集合论的一个概念，像

\mathbb Z

就是一个可数集，你可以制定一个规则，“数”出它的所有元素，但是

\mathbb R

就不是。具体的可以参考这一篇文章

https://zhuanlan.zhihu.com/p/33311995

不过在这里，简单理解为“离散”就可以了。

我们举一个题目来温习一下这个概念。

Problem 1: 考虑随机变量序列

Y_0, Y_1, \cdots

表示每一次掷硬币得到的结果，正面为

，反面为

，且二者各自概率为

\frac 12

。设

X_n = Y_n + Y_{n - 1}, n \ge 1

，判断序列

\{X_n\}

是不是一个马尔科夫链。

从不严谨的层面来说，

X_n

好像是一个马尔科夫链，因为

X_n = Y_n + Y_{n - 1}

，而

X_{n - 2} =Y_{n - 2} + Y_{n - 3}

，与

Y_{n - 1}, Y_n

都没有什么交集。结合

Y_n

本身与生俱来的独立性（上一次掷硬币和这一次掷硬币的概率分布是一样的），好像还真有点那么回事，但真的是这样吗？

感兴趣的读者可以验证下面这两个结果

P(X_3 = 2| X_2 = 1, X_1 = 0) = \frac 12

P(X_3 = 2| X_2 = 1, X_1 = 2) = 0

因此这并不是一个马尔科夫链。一个比较好的解释是，

X_1

的改变会影响到

Y_1

，而这个

Y_1

是

X_2

的一部分，所以其实是影响到

X_2

的。那么

X_2

被影响到了，

X_3

自然就很有可能会被影响到，这就不算具备马尔科夫性了。

说回正题。如果说这个转移的过程与时间也没什么关系，那么还有下面的定义

Definition 3: Temporally homogeneous 如果

P(X_{n + 1} = j | X_n = i) = p(i, j)

对

\forall n

成立，则称马尔科夫链具有时间同质性。

接下来，就是转移矩阵的基本性质。

Proposition 1: 对一个转移矩阵

来说，我们有 (1)

p(i, j) \ge 0

(2)

\sum_{j} p(i, j) = 1

第一个不必多说，因为它们本质上都是概率。第二个的原因也不难解释，因为从上一个状态

X_n = i

变到所有状态的概率和肯定是1。

多步转移

有了转移矩阵，那么就可以计算从上一个状态，到下一个状态的变化情况了。一个自然的问题就是这个变化可不可以推广？当然是可以的。

Theorem 1:

P(X_{n + m} = j | X_n = i) = p^m(i, j)

，其中

p^m(i,j) = P^m_{ij}

解释一下，

p^m

并不代表它是

的

次幂，只是我们这么写而已，但是

P^m_{ij}

确实是表示把矩阵

做一个

次幂之后，取它的第

行，第

列元素。可以看出，这个公式其实就是相当于计算随机变量

X_n

，在经过

步演变之后，得到的

X_{m + n}

的概率分布情况。

这个证明还是具有一定难度的，首先根据条件概率公式，我们有

P(X_{n + m} = j|X_n = i) = \frac{P(X_{n + m} = j , X_n = i)}{P(X_ n = i)}

对于分子

P(X_{n + m} = j, X_n = i)

，中间经过了

步，因此一个简单的想法就是把这

步的所有的可能的情况都列出来。具体来说，就是

P(X_{n + m} = j, X_n = i) = \sum_{i_1, \ldots, i_{m - 1} \in S} P(X_{n + m} = j, X_{n + m - 1} = i_{m - 1}, \ldots, X_n = i)

这里的

表示的是所有的状态的集合。

有了这个之后，要想把它和转移概率扯上关系，就必须要考虑全概率公式，就是

P(X_{n + m} = j, X_{n + m - 1} = i_{m - 1}, \ldots, X_n = i)

= P(X_n = i) P(X_{n + 1} = i_1 | X_n = i)P(X_{n + 2}= i_2 |X_n = i, X_{n + 1} = i_1)\cdots P(X_{n + m} = j |X_{n + m - 1} = i_{m - 1}, X_{n + m - 2} = i_{m - 2} , \cdots)

（这一串公式写的很长，是为了展示一下全概率公式的逻辑，以作复习）

注意每一个

X_i

都是马尔科夫链的一部分，所以都具备马尔科夫性（也即当前状态仅仅与上一个状态有关），所以可以把它化简一下，得到

P(X_{n + m} = j, X_{n + m - 1} = i_{m - 1}, \ldots, X_n = i) = P(X_n = i)p(i, i_1)p(i_1, i_2)\cdots p(i_{m - 1}, j)

这就好办多了，我们把求和号代入，可以得到

P(X_{n + m} = j, X_n = i) = P(X_n = i)\sum_{i_1, \ldots, i_{m - 1} \in S} p(i, i_1)p(i_1, i_2)\cdots p(i_{m - 1}, j)

= P(X_n = i)p^m(i, j)

最后一步看起来很玄乎，但其实就是矩阵乘法的定义。所以我们事实上做到最后一行，就已经算是证明完成了。

好的，我们来看一个简单的题目吧。

Problem 2: 考虑一个不切实际的实际问题。如果我们设

X_n

表示第

天的天气情况，并且假设，如果今天下雨，第二天有50%可能性接着下雨，50%可能性变成晴天。同样，假设如果今天是晴天，第二天有50%可能性下雨，50%可能性继续放晴，那么这个时候，写出

X_n

的转移矩阵，并且判断在今天下雨的情况下，第5天放晴的概率。

如果我们假设下雨是1，放晴是2，那么

X_n \in \{1, 2\}

，那么转移矩阵就是

P = \begin{bmatrix}0.5 & 0.5 \\ 0.5 & 0.5\end{bmatrix}

，并且而如果我们要计算第5天放晴的概率，其实就是要计算

P^4

。使用编程软件不难算出结果为

P^4 = \begin{bmatrix}0.5 & 0.5 \\ 0.5 & 0.5 \end{bmatrix}

。也就是说，第1天下雨，第5天放晴的概率其实依然是50%。

一个比较快速计算的方法是观察矩阵本身的性质。是它的行列式为0，并且对角线和为1，所以特征值是0或1，也就是说它是一个投影矩阵，投影矩阵满足

P^2 = P

，因此无论怎么乘，结果都是一样的。

当然了，如果随机过程都是这种计算题，那简直是太让人开心了。然而并不是。很多时候，我们会希望考察一些极限状态下的随机变量分布。但给出一个好的结果不是那么容易，需要我们先做一些简单的定义。

有限状态马尔科夫链的状态分类与描述

在这一部分，我们设

P_x(A) = P(A|X_0 = x)

，

E_x(Y) = E(Y|X_0 = x)

，也就是说这里的下标

相当于表示一条马尔科夫链的起始状态。在这一节主要是一些枯燥的定义，阅读难度较大。不过它会用于后面更好的描述一些问题。

同样的，这里的状态分类也是“有限状态”下的，潜在意思就是样本空间（状态空间）是有限的。在可数但是无限的情况下，还有一个特殊状态，这个我们后面再提。

我们首先给出一个返回时间（return time）和返回次数（return count）的概念。

Definition 4: Return Time, Return Count 设

T_y = \min\{n \ge 1: X_n = y\}

，表示从

出发，下一次回到

的时间。

N(y)

表示返回

的次数。

很明显我们这里的

T_y

N(y)

都是一个随机变量。同时我们要假设

n \ge 1

，因为如果

n = 0

，那么这个式子没啥意义，它永远是0。

接下来我们定义一个返回时间概率（return time probability）的概念。

Definition 5: Return Time Probability 设

\rho_{yy} = P_y(T_y < \infty)

为从

出发，在有限时间能够回到

的概率。

我们关注这两个概念，主要是为了后期对状态进行分类。简单来说，对于有限状态的马尔科夫链，我们经过一个极限状态之后，它是否具备返回性，是我们后面会研究的内容。

一个很自然的问题是：有限时间内回到

至少两次的概率，应该是多少？这个问题解决之后，我们自然可以知道有限时间内，回到

至少

次的概率。

但是解决它不是很容易，我们要引入停时（stopping time）的概念。

Definition 6: Stopping Time 如果

满足性质：

\{T = n\}

的概率仅仅取决于从0开始的随机过程的到

X_n

为止的结果。也即仅仅取决于

\{X_0, \cdots, X_n\}

。

很明显，

T_y

是一个停时。因为不可能有

的时间的状态改变结果。比方说我知道

t= 5

的时候，从

开始的随机过程第一次回到

，那么

t > 5

的情况其实和我无关，不可能影响到

T_y

的情况。

当然，也可以举出“非停时”的例子。比方说“最后一次回到

的时间

S_y

”，因为我们可以写出

S_y = \max \{n \ge 1: X_n = y\}

这个很明显取决于

X_{n + 1}

及以后的状态（要求它们都不能是

），那就违背停时的定义了。

当然，这并不足够帮助我们解决这个问题。不过我们还是先把这个性质放在这里。

Proposition 2: 给定

\rho_{yy}

，有限时间内回

至少

次的概率为

\rho_{yy}^n

。

我们换个思路，先看看这个性质要满足，需要什么条件。如果两次是

\rho_{yy}^2

，那么相当于前后两个事件相互独立，也就是说第一次回到了

之后，从新的

出发的马尔科夫链，性质应该要与之前的马尔科夫链一模一样。具体可以看下面这张图。

性质一模一样，其实就是我们下面要说的强马尔科夫性（strong Markov property），它也是停时的一个关键定理。

Theorem 2: Strong Markov Property 设

是一个停时，并且假设

T = n, X_n = y

，也就是说

T_y = n

。那么从

开始，后面的每一步表现都和之前的马尔科夫链一模一样。

这个定理的证明其实归根到底就是下面这个式子

P(X_{T + 1} = z | T = n, X_T = y) = p(y, z)

因为根据马尔科夫链的性质，其实我们只要说明，从

（也就是

，因为

T = n

）开始的第一步的转移矩阵与从0开始的一样，后面就自然都一样了。

这个式子的证明不难。我们有

P(X_{T + 1} = z | T = n, X_T = y)

= P(X_{n + 1} = z | X_n = y, X_{n - 1} = x_{n - 1}, \ldots, X_0 = x_0)

=p(y, z)

所以这就证明完了。

停时的概念用在了第二行，如果

不是一个停时，我们是没有办法只在后面写上

X_0, \ldots, X_{n - 1}

这些随机变量的取值的，因为

还有可能与

X_{n+1}

等有关。这样自然没有办法使用马尔科夫性。

通过这个，我们可以得到下面的推论。

Corollary 1:

P(X_{T + 1} = z | T < \infty, X_T = y) = p(y, z)

我们证明一下，根据条件概率公式，我们有

P(X_{T + 1} = z | T < \infty, X_T = y)

= \frac{P(X_{T + 1} = z, T < \infty, X_T = y)}{P(T < \infty, X_T = y)} = \frac{\sum_{n = 1}^\infty P(X_{T + 1} = z, T = n, X_T = y)}{\sum_{n = 1}^\infty P(T = n, X_T = y)} = p(y, z)

最后一个式子的关键是用到上面的推论，也即在

是停时的情况下满足的强马尔科夫性，这样的话每一个项都是相同的。

这个推论的潜在的意思是，只要

T < \infty

就可以，换句话说只要

是一个停时，并且这个停时有限（也就是说，对于一个状态而言，经过有限步它可以返回原状态），那么从这个停时重新开始的马尔科夫链，就和原始的一模一样。这个很像指数分布的无记忆性。

现在我们终于可以开始证明Proposition 2了。我们定义

T_y^k

表示从

出发，第

次返回

的结果，也就是说

T_y^k = \min\{n > T_y^{k - 1}: X_n = y\}

很明显它也是一个停时。

在这个情况下，我们考虑使用递推。注意到有

P_y(T_y^k < \infty) = P_y(T_y^k < \infty | T_y^{k - 1} < \infty)P(T_y^{k - 1} < \infty)

并且注意到

P_y(T_y^k < \infty | T_y^{k - 1} < \infty) = P(T_y^k < \infty | T_{y}^{k - 1} < \infty, X_{T_y^{k -1}} = y) = P_y(T_y < \infty)

最后一个等号使用了强马尔科夫性。代入就可以得到

P_y(T_y^k < \infty) = \rho_{yy} P(T_y^{k - 1} < \infty)

这就足够证明结论了。

可以看出，虽然只是一个简单的推广，但要说明起来还是要依赖挺多重要的性质的。我们到后面还会经常使用强马尔科夫性和停时等概念。

事实上，我们还可以刻画一些与

N(y)

有关的性质，也即量化的去刻画究竟一个随机变量能够返回多少次。

Proposition 3:

E_x(N(y)) = \rho_{xy}\sum_{k = 1}^\infty \rho_{yy}^{k -1}

这里

\rho_{xy} = P_x(T_y < \infty)

，证明主要用到也是纯概率论的知识。

首先我们注意到

E(X) = \sum_{n = 1}^\infty n P(X= n) = \sum_{n = 1}^\infty \sum_{k = 1}^\infty I(k \le n) P(X = n)

= \sum_{k = 1}^\infty \sum_{n = 1}^\infty I(n \ge k) P(X = n) = \sum_{k = 1}^\infty P(X \ge k)

第二行的求和交换顺序需要用到级数的知识，但这里我们默认这个交换是成立的，当一把物理系的学生。

把这个结果代入，就可以得到

E_x(N(y)) = \sum_{k =1}^\infty P_x(N(y) \ge k) = \rho_{xy} \sum_{k = 1}^\infty \rho_{yy}^{k -1}

最后一个等号直觉上很显然，但要严格的说明还是需要一点笔墨。这个我们留给读者了。

最后我们要强调的是，其实我们推导的期望与概率公式之间的关系，事实上是一个常用结论，可以把它背下来。

Lemma 1: 若

E(X) < \infty

，则

E(X) = \sum_{k = 1}^\infty P(X \ge k)

有了这些保障，我们便可以考虑为不同的状态做分类了。

常返状态与瞬时状态

如果是有限状态马尔科夫链，一般来说根据

\rho_{yy}

的取值，可以把它区分为两种情况。

Definition 7: Recurrent State, Transient State 若

\rho_{yy} = 1

，则称

是一个常返状态，否则

是一个瞬时状态。

我们来看看为什么可以叫“常返“和“瞬时”。

如果说

\rho_{yy} < 1

，那么

\rho_{yy}^k \to 0, k \to \infty

。也就是说

P_y(N(y) \ge k) = \rho_{yy}^k \to 0

。这里要引入一下高等概率论的Borel-Cantelli引理。也就是说通过这个，可以得到

\sum_{k} P_y(N(y) \ge k) = E_y(N(y)) < \infty

根据级数的性质，可以得到

P_y(N(y) = \infty) = 0

也就是说，从

出发，回到

仅仅是有限次的概率为1，说明一定会在某个时候，出现

再也不会回到

的情况。这也就是“瞬时”的含义，一瞬而逝，再无可能相见。

反过来，如果

\rho_{yy} = 1

，那么有

\rho_{yy}^k = 1, \forall k

。这就说明

P_y(N(y) = \infty) = P(\bigcap_k \{N(y) \ge k\}) = 1

也就是说，从

出发，无论返回几次，概率都是1，那自然就是“常返”所表达的意思。同样的我们还可以得到

E_y(N(y)) = \infty

。

关于Borel-Cantelli引理，感兴趣的可以看一下这篇笔记总结

https://zhuanlan.zhihu.com/p/69550246

好的，我们来看两个例子吧。

Problem 3: 考虑下面的转移矩阵

P = \begin{bmatrix}1 & 0 & 0 & 0 & 0 \\ 0.6 & 0 & 0.4 & 0 & 0 \\ 0 & 0.6 & 0 & 0.4 & 0 \\ 0 & 0 & 0.6 & 0 & 0.4 \\ 0 & 0 & 0 & 0 & 1\end{bmatrix}

，五个状态分别为

0, 1, 2, 3, 4

（从左到右，从上到下）。判断常返与瞬时状态。

因为停时所具备的强马尔科夫性，所以我们不需要关心我们的每个状态究竟是一条马尔科夫链中的“第几个”，一个转移矩阵就足够描述问题的全部了。

不难看出

0, 4

应该是符合要求的两个状态。但为了让大家熟悉这些符号，我们这里好好的写一遍公式。

如果要说明

是一个常返状态，就是要说明

\rho_{00} = 1

。又因为

\rho_{00} = P_0(T_0 < \infty) \ge P_0(T_0 =1 < \infty) = 1

所以根据概率不能超过1的性质，不难得到结论。类似可以得到

\rho_{44} = 1

。

现在看一下其它三个状态。比如说

\rho_{11}

。注意到

\rho_{11} = P_1(T_1 < \infty)

我们反其道而行之，考察

P_1(T_1 = \infty)

。这说明从

开始，有限状态下不可能回到

，那么第一步可以走到除了

以外的任何地方。因此我们有

P_1(T_1 = \infty) \ge P_1(X_1 = 0) = 0.6 > 0

这就足够说明

\rho_{11} < 1

了，也就说明了

是一个瞬时状态。而这个放缩也比较显而易见。类似可以说明，状态

2, 3

也是瞬时状态。

Problem 4: 考虑转移矩阵

P = \begin{bmatrix}0.7 & 0.2 & 0.1 \\ 0.3 & 0.5 & 0.2 \\ 0.2 & 0.4 & 0.4\end{bmatrix}

，状态分别为

0,1 , 2

（从上到下，从左到右）。判断常返与瞬时状态。

对于这个矩阵而言，其实所有的状态都是常返状态。我们以状态

为例，容易看出

1 - \rho_{00} = P_0(T_0 = \infty) = \lim_{n \to \infty}P_0(T_0 >n) \le \lim_{n \to \infty} 0.8^n = 0

0.8

这个数是因为，无论从哪里开始，到达

的概率都至少是

0.2

。所以根据

\rho_{00} = 1

就可以得到结论。

事实上，我们这里用到的放缩也可以做一些适当的拓展。

Proposition 4: 设

P_x(T_y \le k) \ge \alpha > 0, \forall x \in S

，这里

是状态空间，也即每一步随机变量的样本空间。那么我们有

P_x(T_y > nk) \le (1- \alpha)^n

这个性质的证明也需要利用到强马尔科夫性。首先注意到我们之前如何证明Proposition 2的？很明显是利用到全概率公式，根据此来加一些条件。

注意到

P_x(T_y >nk) = P_x(T_y > nk | T_y > (n - 1) k )P_x(T_{y} > (n - 1) k )

另外我们根据强马尔可夫性，把时间往回推一推，又可以得到

P_x(T_y > nk | T_y > (n - 1) k ) = P_x(T_y > k | T_y > 0) \le 1 - \alpha

剩下的事情递推就可以了。

状态之间的可达性

这么一通分析之后，其实不难看出，在有限状态的随机过程中，我们除了希望做计算以外，更希望知道状态与状态之间，相互转移的情况。有些时候对于状态转移的分析，会使得我们对一条随机过程（在这里就是有限状态马尔科夫链）有更深的了解。

下面这些概念就是为了这个服务的。

Definition 8: Accessible, Communicable 如果

\rho_{x y} = P_x(T_y < \infty)> 0

，那么称

可由

到达，写成

x \to y

。如果

x \to y, y \to x

同时满足，那么称

x, y

相互可交流。写成

x \leftrightarrow y

。

再次强调一遍，这里的

p^n

不是对

p(x, y)

求

次幂的意思。具体的可以往前翻翻找找答案。

定义里所提到的

\rho_{xy} > 0

其实可能有的时候不太好用，不过有一个等价的结论。

Proposition 4:

\rho_{xy} > 0

\Leftrightarrow \exists n > 0, p^n(x, y) > 0

我们来证明一下。

首先，假设

\rho_{xy} > 0

，那么会有

\rho_{xy} = P_x(T_y < \infty) = \sum_{n = 1}^\infty P_x(T_y = n) > 0

那么这就说明

\exists n, P_x(T_y = n) > 0

这说明什么？这说明

\exists n, P_x(X_1 \ne y, \ldots, X_{n - 1} \ne y, X_n = y) > 0

这也就是我们的结论。

反过来，假如说

\exists n > 0, p^n(x, y) > 0

，那么潜在意思是

\exists n, \sum_{x_1, \ldots, x_{n - 1}} P_x(X_1 = x_1, \ldots, X_{n -1} = x_{n - 1}, X_n = y) > 0

那么自然地，可以找到一组

x_1, \ldots, x_{n-1}

，使得

P_x(X_1 = x_1, \ldots, X_{n -1} = x_{n - 1}, X_n = y) > 0

，取

i = \min\{k : x_k = y\}

，那么可以得到

P_x(X_1= x_1, \cdots, X_i = y) \ge P_x(X_1 = x_1, \ldots, X_{n -1} = x_{n - 1}, X_n = y) >0

这也就说明了

P_x(T_y < \infty) > P_x(T_y = i) \ge P_x(X_1= x_1, \cdots, X_i = y) > 0

也就证明了

\rho_{xy} > 0

。

这个等价关系的证明有助于我们发现一些其他的“可到达”相关性质。

Proposition 5: 若

x \to y, y \to z

，那么

x \to z

。

如果使用等价求解，这个命题就简单很多。首先前两个表达式说明了

\exists n_1, p^{n_1} (x, y) > 0

，

\exists n_2, p^{n_2}(y, z) > 0

，所以综合在一起，意思就是

p^{n_1 + n_2}(x, z) \ge p^{n_1} (x, y) p^{n_2}(y, z) > 0

这是因为

到

可以不只是经过

，也可以经过其它步骤。

使用这两个概念，我们也可以分析状态究竟是常返的，还是瞬时的。

Proposition 6: 如果存在

，满足

\rho_{xy} >0, \rho_{yx} < 1

，那么

是一个瞬时状态。如果

\rho_{yx} = 1

，那么

就是一个常返状态。

一个非常明显的直觉是，在这个情况下，

x \to y

，但是因为

\rho_{yx} \ne 1

，所以不一定能够从

回到

。

但是如果要严谨的说明

是一个瞬时状态，我们需要说明的是

P_x(T_x = \infty) > 0

。首先根据

\rho_{xy} > 0

，我们可以得到

\exists x, y_1, \ldots, y_n , y \quad s.t. p(x,y_1)\ldots p(y_n, y) >0

那么自然的，可以找到一个子集

z_1, \ldots, z_m

，满足

z_i \ne x

，且

p(x,z_1)\ldots p(z_m ,y) > 0

。因为我们可以在已有的子序列中找到最后一个

，看那个

之后到

的一个转移路径，并且重新命名为

z_1, \ldots, z_m

，并且这个不等式依然是成立的。

那么注意到

P_x(T_x = \infty) \ge p(x, z_1)\ldots p(z_m ,y)(1- \rho_{yx} ) >0

（想想为什么？）所以命题就证明结束了。

同样的，我们可以反证法证明相反的情况，也就是说，如果

\rho_{yx} = 1

但不是一个常返状态的话，那就是瞬时状态，产生矛盾。

这个定理的作用便在于，对于有限状态的马尔科夫链，我们可以通过画图的方式，来区分出两种状态。很多时候，这会很方便。

Problem 5 考虑下面的图，其中如果

p(i, j) > 0

，就连一条

i \to j

的有向边，区分出内部的常返状态与瞬时状态。

这张图中，我们顺便框起来了两个部分。框起来的都是自环，且没有通向外界的边。并且都是常返状态。

为什么？这是因为，如果是自环的话，说明它只能够在这个环内进行状态转移，那么不难发觉到，它无论怎么移动，都只能移动到这个环内的元素，同时每一个元素一定有机会被访问无数次，因为如果某个状态

只会被访问有限次，那么从那一次开始，就不能够再返回到

，但是这很显然是不可能的。

没有自环的部分就会惨一些，说明它们有可能逃出去之后就逃不回来了，这也就是“瞬时”的含义。

好的，关于状态的分类，我们先说这么多。

小结

本节在一开始，通过马尔科夫链的性质说明了转移矩阵的作用，并且说明了随机过程研究问题与传统概率统计的区别和联系。在之后则主要是为了讨论极限状态下的概率分布而引入的一些状态分类相关的知识点。这一部分理论部分繁多，名词比较多，讨论相对复杂，需要大家对概率论的基本知识点琢磨透彻，同时要结合更高层次的，感性的理解，以更好掌握每一个定理，性质所希望表达的道理。

在下一节，我们会继续讨论这些理论知识，并用于引出极限状态下的概率分布的计算和讨论。

本文参与腾讯云自媒体分享计划，分享自微信公众号。

原始发表：2020-12-08，如有侵权请联系 cloudcommunity@tencent.com 删除

definition