万物科技 学,以致用

概率论 9. 离散马尔科夫链

2017-06-16
Geng

与之前所述的伯努利过程和泊松过程不同, 马尔科夫过程是有记忆的. 不过马尔科夫过程记忆力也没有特别好: 未来的状态只与现在状态有关系, 而与过去的状态无关.

离散马尔科夫链简介

我们可以把它看成这个公式:

也就是说, 在考虑到噪声影响下, 未来状态部分程度上取决于现在状态.

我们假设所有可能的状态组成一个状态空间: \(S, \ S = {1, 2, … , m}\). 随着时间的推移,状态转换, 也就是空间转换. 那么, 从旧空间转移到新空间的概率为:

因为这是一个空间变换的过程, 所以上面这个公式也称作转移概率: \(p_{旧新}\). 更正式地:

即从 \(i\) 状态转换到 \(j\) 状态的概率. 可见, 这其实就是我们之前接触过的条件概率问题. 因为任意时间 n 的下一个状态 n+1 只与 n 时的状态有关, 所以:

根据全概率原理, 我们可以得到:

描述马尔科夫链

可以用转移概率矩阵描述:

也可以用转移概率图描述:

n步转移概率

上面介绍的是经过一步, 就能从旧空间转移到新空间. 那么, 如果需要多步, 就是n步转移的问题了:

这个问题可以由迭代公式, * Chapman-Kolmogorov (C-K)*公式计算:

它可以由全概率公式证明, 但是下图更加直观:

我们通过不同路径, 走了 n-1 步, 从 i 走到了 n-1 , 最后我们只需要计算在第 n-1 这一步所有的可能性到达 j 的全概率即可.

n 足够大的时候, 很多情况下我们会到达一个稳态, 此时不管初始条件如何, 到达每一个状态的概率是恒定的.

状态分类

可达的

在转移状态图上, 如果可以画出一条从状态 j 到状态 i 的路径, 那么状态 j 到状态 i可达的(accessible):

常返类

\(A(i)\)为所有从状态 i 可达的集合, 组成一个常返类. \(A(i)\)之外的状态不是从\(A(i)\)之内的状态可达的.

常返的(recurrent)和暂时的(transient)

i 到了 j, 又能从 j 回到 i, 那么状态 i 就是常返的. 如果是非常返的, 那么就是暂时的.

周期性

一个常返类有若干不想交的子集, 每次转换都从一个子集依次转移到下一个子集, 那么这个常返类就是周期的, 比如:


Similar Posts

Comments

你可以请我喝喝茶,聊聊天,鼓励我

Wechat Pay
wechat

Thanks!