马尔可夫链
考虑随机变量序列
其中每个随机变量都在同一个状态空间中取值。目前先假设该状态空间是一个有限集，并把它标记为
把
解释为系统在时刻 的状态。 如果存在一组固定的数
，其中每一对 都对应一个
，并且每当系统处于状态 时，系统下一步处于状态 的概率都是 ，就称该序列为马尔可夫链。 更精确地说，
这是一种“近乎无记忆”的性质：下一状态的概率分布只依赖当前状态，而不依赖其余的状态历史。
简单例子
例如，设想一个只有两种状态的简单天气模型：雨天与晴天。
如果某一天是雨天，那么第二天仍是雨天的概率为
，变为晴天的概率也为 。 如果某一天是晴天，那么第二天仍是晴天的概率为
，变为雨天的概率为 。 在这种气候中，晴天往往比雨天持续得更久。
已知今天是雨天，预计需要等待多少天才能见到晴天？
已知今天是晴天，预计需要等待多少天才能见到雨天？
从长期来看，晴天占全部天数的比例是多少？
矩阵表示
为了描述一条马尔可夫链，需要为任意
定义
。 把这些转移概率
表示成矩阵会很方便： 为使这种表示有意义，要求对所有
，都有 并且对每个
， 也就是说，每一行的元素之和都等于
。
用矩阵表示转移
假设
是系统在时刻 处于状态 的概率。 下面的乘积表示什么？
答案： 时刻
的概率分布。 那么下面的乘积又表示什么？
答案： 时刻
的概率分布。
转移矩阵的幂
用
表示经过 步从状态 转移到状态 的概率。 从矩阵的角度看，
如果
是一步转移矩阵，那么 就是 步转移矩阵。
问题
如果矩阵的所有行都完全相同，这意味着什么？
答案： 状态序列
由相互独立且同分布的随机变量组成。 如果矩阵是单位矩阵，会怎样？
答案： 状态永远不会改变。
如果每个
都只能取 或 ，会怎样？ 答案： 状态的演化是确定性的。
简单例子
回到前面的简单天气例子：如果某一天是雨天，那么第二天仍是雨天的概率为
，变为晴天的概率为 ；如果某一天是晴天，那么第二天仍是晴天的概率为 ，变为雨天的概率为 。 令雨天为状态
，晴天为状态 ，把转移矩阵写成 可以计算出
情感关系状态具有马尔可夫性质吗？
图中给出了五种状态：
- 单身；
- 恋爱中；
- 情况很复杂；
- 已订婚；
- 已婚。
状态转移图中，每个状态都有一条指向自身的自环；任意两个不同状态之间也都画有两个相反方向的箭头。因此，图中允许从任一状态直接转移到任一状态。
能否为每一条箭头指定一个概率？
马尔可夫模型意味着：在离开任一状态之前处于该状态的时间，例如一段婚姻持续的时间，是一个几何随机变量。
但事实并非如此……我们能否使用更多状态建立一个更好的模型？
遍历马尔可夫链
如果转移矩阵的某个幂的所有元素都非零，就称该马尔可夫链是遍历的。
可以证明：若马尔可夫链具有这一性质，那么
存在，并且
是下列方程组唯一的非负解： 这意味着行向量
是
的特征值为 的左特征向量，即 称
为该马尔可夫链的平稳分布。 可以求解线性方程组
来计算
的值。这等价于固定 并求解 这会把
确定到一个乘法常数，而条件 则确定这个常数。
由于本页把
定义为行向量，和 等价的方程应为 。若把 改写成列向量，则应求解 。
简单例子
提纲
回顾你已掌握的有限状态马尔可夫链知识
有限状态情形的遍历性与平稳性
更一般的框架
马尔可夫链：一般定义
考虑一个可测空间
。 若函数
满足下列条件，就称它为一个转移概率：
对每个
，映射 是
上的概率测度； 对每个
，映射 是可测函数。
若
就称
是关于 、转移概率为 的马尔可夫链。 如何构造一条无限马尔可夫链？选择转移概率
，并在 上选择初始分布 。对每个 ，令 再利用柯尔莫哥洛夫（Kolmogorov）扩张定理把它扩张到
。
马尔可夫链
再次给出定义： 若
就称
是关于 、转移概率为 的马尔可夫链。 再次给出构造： 在
上固定初始分布 。对每个 ，令 再利用柯尔莫哥洛夫（Kolmogorov）扩张定理把它扩张到
。 记号： 这一扩张在序列空间
上生成概率测度
。 定理： 按
选取的 是马尔可夫链。
定理： 若
是初始分布为 、转移概率为 的任意马尔可夫链，那么它的有限维概率由上面的公式给出。
例子
上的随机游走。 分枝过程：
其中
是相互独立且同分布的非负整数值随机变量。 更新链。
洗牌。
埃伦费斯特（Ehrenfest）链。
