马尔可夫链的漂移与矩不等式 基本概念引入 马尔可夫链的漂移（Drift）是分析其长期行为的重要工具。漂移定义为链在相邻时刻状态变化的某种度量，通常通过一个 李雅普诺夫函数 （Lyapunov function）\( V: S \to [ 0, \infty) \) 来构造。对于状态空间 \( S \) 上的马尔可夫链 \( \{X_ t\} \，定义在状态 \( x \) 下的 单步漂移 为： \[ \Delta V(x) = \mathbb{E}[ V(X_ {t+1}) - V(X_ t) \mid X_ t = x ]. \] 漂移的正负与大小可推断链的稳定性、常返性等性质。 漂移条件的分类 根据漂移的不同形式，可建立以下典型条件： 负漂移条件 ：若存在有限集 \( C \subset S \) 及 \( \epsilon > 0 \)，使得 \[ \Delta V(x) \leq -\epsilon \quad \text{对所有 } x \notin C \text{ 成立}, \] 则链倾向于返回至集合 \( C \)，可用于证明正常返性。 正漂移条件 ：若 \( \Delta V(x) \geq \epsilon > 0 \) 对所有 \( x \notin C \) 成立，则链可能趋于发散。 矩不等式与漂移的结合 通过漂移条件可推导链的矩不等式（Moment Inequalities），从而控制状态函数的增长。例如，若存在 \( \lambda > 0 \) 使得： \[ \mathbb{E}[ e^{\lambda V(X_ {t+1})} \mid X_ t = x ] \leq e^{\lambda V(x) - \delta} \] 对 \( x \notin C \) 成立，则可通过切尔诺夫界得到 \( V(X_ t) \) 的尾部概率估计。此类不等式在分析随机算法的收敛时间、排队系统的稳定性中至关重要。 应用示例：等待时间矩的有界性 考虑一个排队系统的队列长度 \( Q_ t \)，取 \( V(x) = x^p \)（\( p \geq 1 \)）。若漂移满足： \[ \Delta V(x) \leq -a x^{p-1} + b \quad (a,b > 0), \] 通过数学归纳法可证 \( \mathbb{E}[ Q_ t^p ] \) 一致有界。此技巧将漂移条件转化为矩的稳定性。 推广至非马尔可夫过程 漂移与矩不等式的思想可扩展至更一般的随机过程。例如，对适应过程 \( \{Y_ t\} \)，若 \( \mathbb{E}[ V(Y_ {t+1}) \mid \mathcal{F}_ t] \leq (1-\eta)V(Y_ t) + B \)，则可用 漂移引理 证明 \( \mathbb{E}[ V(Y_ t) ] \) 的收敛性，此为随机梯度下降分析中的常用工具。