Markov 链
考虑随机变量序列
每个随机变量都在同一个状态空间中取值。目前先假设该状态空间是有限集，并将它标记为
把
解释为系统在时刻 的状态。 如果存在一组固定的数
，其中每一对 都对应一个
，并且每当系统处于状态 时，系统下一步处于状态 的概率都是 ，就称该序列为 Markov 链。 更精确地说，
这是一种“近乎无记忆”的性质：下一状态的概率分布只依赖当前状态，而不依赖其余的状态历史。
矩阵表示
为了描述一个 Markov 链，需要对任意
定义
。 把所有转移概率
表示成矩阵会很方便： 为使这种表示有意义，要求对所有
都有 并且对每个
都有 也就是说，每一行的元素之和都等于一。
转移矩阵的幂
用
表示经过 步从状态 转移到状态 的概率。 从矩阵角度来看，
如果
是一步转移矩阵，那么 就是 步转移矩阵。
遍历 Markov 链
如果转移矩阵的某个幂的所有元素都非零，就称该 Markov 链是遍历的。
可以证明：如果链具有这一性质，那么
存在，并且
是满足下列方程、总和为一的唯一非负解： 这意味着行向量
是
对应于特征值 的左特征向量，即 称
为该 Markov 链的平稳分布。 可以通过求解线性方程组
来计算
。等价地，可以固定 ，求解 或求解
这会在相差一个乘法常数的意义下确定
，再由 确定该常数。
示例
上的随机游走。 分枝过程：
其中
是独立同分布、取非负整数值的随机变量。 更新链： 确定性地逐次减一；到达零时随机跳跃。
洗牌。
Ehrenfest 链： 两个容器中共有
个球，每次随机选择一个球并把它换到另一个容器。 生灭链： 每步改变
。它的平稳分布是什么？ 排队模型。 图上的随机游走。它的平稳分布是什么？
有向图上的随机游走，例如一条单向链。
蛇梯棋。
Markov 链：一般定义
考虑一个可测空间
如果函数
满足以下条件，就称它为转移概率：
对每个
，映射 是
上的概率测度； 对每个
，映射 是可测函数。
如果关于滤过
，序列 满足 就称
是以 为转移概率的 Markov 链。 如何构造一条无限 Markov 链？在
上选择转移概率 和初始分布 。对每个 ，定义 再由 Kolmogorov 延拓定理将其延拓到
。
Markov 链
再次给出定义： 如果关于滤过
，序列 满足 就称
是以 为转移概率的 Markov 链。 再次给出构造： 固定
上的初始分布 。对每个 ，定义 再由 Kolmogorov 延拓定理将其延拓到
。 记号： 该延拓在序列空间
上产生概率测度
。 定理： 按照
选出的 是 Markov 链。 定理： 如果
是任意一条初始分布为 、转移概率为 的 Markov 链，那么它的有限维概率就是上面给出的形式。
Markov 性质
Markov 性质： 取
令
为 Markov 链测度，并令 为 上的移位算子：它把序列向左移动 个位置，并丢弃被移出边界的元素。如果 有界且可测，那么
强 Markov 性质： 可以把
换成几乎必然有限的停时 ，而且函数 可以随时间变化。假设对每个 ， 可测，并且对所有
都有 。那么 其中右端表示：先计算
，再代入 、 。
性质
无限机会性质： 假设
是 Markov 链，并且在事件 上有 那么
反射原理： 对
上的对称随机游走，有 证明思路： 使用反射图像。
提纲
- 回顾
- 一般设定与基本性质
- 常返性与暂留性
问题
一个有趣的问题： 如果
是可数状态空间上的无限概率转移矩阵，那么当下列级数收敛时，无限矩阵 表示什么？
问题： 它是否描述了从
出发时到达 的期望次数？其他幂级数是否也有类似解释？ 或 又如何？ 它是否与经过 Poisson 分布的随机步数之后的分布有关？
常返性
考察从
出发的随机游走最终回到 的概率。 如果这个概率等于
，那么游走会无穷多次回到 ；否则就不会如此。如果游走无穷多次回到 ，就称 为常返状态。
