k 1 m
P (x n 1 k | x 0 i )P (x n j | x n 1 k ) rij (n 1)Pkj
k 1 k 1 m
m
n 步转移概率矩阵： rij (n ) 看成一个二维矩阵第 i 行第 j 列的元素。 讨论 n 时： 例 1 中，每一个 rij (n ) 都收敛于一个极限值，不依赖于初始状态 i。
Wj Wk pkj
k 1 m
1 Wk
k 1
m
3、另外有
Wj 0 ，对于所有的非常返状态 j Wj 0 ，对于所有的常返状态 j
1 Wm ] [0 0 1] ，可用 MATLAB 解决。 pm1 pmm 1 1
P(x 0 i0 , x1 i1, , x n in ) P(x 0 i0 )Pi i Pi i Pi
01 12 n 1 n
i
图形上，一个状态序列能表示为在转移概率图中的一个转移弧线序列。在给定初始状态下， 该路径的概率等于每个弧线上转移概率的乘积。 n 步转移概率 定义： rij (n ) P (x n i | x 0 i ) 计算在当前状态条件下，未来某个时期状态的概率分布。 当前状态 i，n 个时间段后的状态将是 j 的计算公式：C-K 方程
1 0 0 0 0.3 0.4 0.3 0 0 0.3 0.4 0.3 0 0 1 0
转移概率图
例 3：一个教授抽取测试卷子。卷子的难度分成 3 种：困难、中等和容易。如果本次抽到的 困难的卷子，则下次分别有 0.5 的概率抽中中等和容易的卷子。如果本次抽到的是中等的卷 子，则下次仍旧 0.5 的概率为中等难度，另外有 0.25 的概率抽中困难或容易的卷子。如果本 次抽到的是容易的卷子， 则下次仍旧 0.5 的概率为容易难度， 另外有 0.25 的概率抽中困难或 中等的卷子。 转移概率矩阵
0 0.5 0.5 0.25 0.5 0.25 0.25 0.25 0.5
转移概率图
-----------------------------------------------------------------------------------------路径的概率 计算未来任何一个给定状态序列的概率。
状态的分类 可达的 如果对于某一个 n，n 步转移概率 rij (n ) 是正的，则称状态 j 为从状态 i 可达的。 常返态：对于每个从 i 出发可达的状态 j，相应的从 j 出发也可达 i，那么状态 i 称为常 返的。如果一个状态不是常返的，我们称之为非常返的。 如果 i 是常返态，那么从 i 可达的状态集合 A(i ) 组成一个常返类。
单个常返类
一个非常返态(3)和一个常返类(1,2)
两个非常返态(2,3)和两个常返类 马尔可夫链的分解 一个马尔可夫链的状态集合可以分解成一个或多个常返类， 加上可能的一些非常返状态。 一个常返态从它所属的类里任何一个状态出发是可达的， 但从其他类里的常返状态出发 是不可达的。 从任何一个常返状态出发都不可到达非常返状态。 从一个非常返状态出发，至少有一个或多个常返态是可达的。 常返类的周期性：一个状态被回访时间是否出现周期性。 如果一个常返类的状态可被分成 d>1 个互不相交的子集， 且满足所有的转移都是从一个这样 的子集到下一个，我们称这个常返类是周期的。 如果一个常返类不具有周期，称为非周期的。
rij (n ) rij (n 1)Pkj ，其中 rij (1) Pij
k 1 m
表示为矩阵：
R(n) PP P Pn
C-K 公式证明，应用全概率公式：
P (x n j | x 0 i ) P (x n 1 k | x 0 i )P (x n j | x n 1 k, x 0 i )
Pij 的取值（取正值） 。
由该模型描述的马尔可夫链是一个随机变量序列 X0 , X1, ，它们取值于 S，并且满足： 对于任意的时间 n，所有状态以及所有之前可能的状态序列 i0 , , in ，均有
P(x n 1 j | x n i, x n 1 in 1,, x 0 i0 ) Pij
马尔可夫链
该模型里，过去对未来的影响归结于对状态的影响，它的概率分布随着时间变化。假设 变量取值的状态只取有限个值。 应用：几乎全部动力系统，通信、自动化控制、信息传输、制造业、经济、运筹学等。 离散时间的马尔可夫链 状态在确定的离散时间点上发生变化。 转移概率 Pij：当前状态 i，下一个状态 j 的概率。 核心假设：只要时刻 n 的状态为 i，不论过去发生什么，不论如何达到状态 i，下一个 时刻转移到状态 j 的概率一定是转移概率 Pij。 马尔可夫模型的性质： 一个马尔可夫链模型由以下特征确定： 1. 状态集合 S {1, 2, , m} 2. 3. 可能发生状态转移 (i, j ) 的集合，即由所有 Pij 0 的 i, j 组成。
稳态性质 研究对象：一个常返类，并且不是周期的。 单个常返类的链也可能是不收敛的，比如具有周期的常返类。 稳态收敛定理： 考虑一个非周期的，单个常返类的马尔可夫链，那么，状态 j 和它对应的稳态概率W j 具有 如下性质： 1、对于每个 j 有
n ij
lim r (n) Wj
2、 是下面方程组的唯一解：
马尔可夫链由转移概率矩阵刻画： 第 i 行，第 j 列的元素为 Pij
P P 1m 11 P P m 1 mm
转移概率图 1. 节点 nodes：表示状态 2. 连接节点的有向弧线 arcs：表示可能发生的转移 3. Pij：标在相应的弧线旁边 例 1：爱丽丝上一门课程，每周可能进步也可能落后。 如果给定的一周，她进步了，那么后一周进步的概率为 0.8，落后的概率为 0.2； 如果给定的一周，她落后了，那么后一周进步的概率为 0.6，落后的概率为 0.4； 假设这些概率都不依赖她之前的每周的进步落后情况。 转移概率矩阵
0.75 0.25 Pij () 0.75 0.25
例 2 中， rij (n ) 仍旧收敛，但是极限值依赖于初始状态，并且对于某特定的状态极限值可能 为 0。
1 2 / 3 Pij () 1 / 3 0 0 0 0 0 0 0 0 1 / 3 0 2 / 3 0 0
0.8 0.2 0.6 0.4
转移概率图
------------------------------------------------------------------------------------例 2：苍蝇和蜘蛛 一只苍蝇在一条直线上移动（共 4 个单位） ，每次移动一个单位长度。每单位时间，它以 0.3 的概率向左移动一个单位，以 0.3 的概率向右移动一个单位，以 0.4 的概率停留在原地。 两只蜘蛛等待在位置 1 和 4，如果苍蝇到达这两个位置，它将被蜘蛛捕获，过程结束。 转移概率矩阵