C-K方程

1. 马尔可夫链与转移概率

为了理解C-K方程的用途，我们必须首先明确其应用的上下文：离散时间马尔可夫链。

一个马尔可夫链是一个随机过程 $\{X_t,t=0,1,2,\dots \}$，它描述了一个系统在一系列时间点上在不同状态之间的转移。其核心特性是马尔可夫性质（Markov Property），即“无记忆性”：系统在未来时刻 $t+1$ 的状态，只依赖于其当前时刻 $t$ 的状态，而与它如何到达当前状态的历史路径无关。

形式化而言，对于任意的状态 $i,j$ 和历史状态序列 $i_0,\dots ,i_{t-1}$：

$$P(X_{t+1}=j|X_t=i,X_{t-1}=i_{t-1},\dots ,X_0=i_0)=P(X_{t+1}=j|X_t=i)$$

这个条件概率 $P(X_{t+1}=j|X_t=i)$ 被称为一步转移概率，记作 $p_{ij}$。它是马尔可夫链最基本的组成部分，描述了系统从状态 $i$ 一步转移到状态 $j$ 的概率。所有这些概率可以组成一个转移概率矩阵 $\mathbf{P}$。

2. C-K方程的提出——解决多步转移问题

一步转移概率告诉了我们系统下一步的行为。一个自然而然的问题是：如果我们知道系统如何进行一步转移，我们如何计算系统经过n步之后从状态i转移到状态j的概率？

这个n步转移概率记作 $p_{ij}^{(n)}=P(X_n=j|X_0=i)$。C-K方程正是为了回答这个问题而提出的。

C-K方程的形式化表述： 对于任意的非负整数 $m,n$ 和任意状态 $i,j$，有：

$$p_{ij}^{(m+n)}=\sum _{k\in S}{p}_{ik}^{(m)}{p}_{kj}^{(n)}$$

其中 $S$ 是所有可能状态的集合。

这个方程的直观含义是：从状态 $i$ 经过 $m+n$ 步到达状态 $j$ 的总概率，等于从状态 $i$ 先经过 $m$ 步到达某个中间状态 $k$，再从这个中间状态 $k$ 经过 $n$ 步到达最终状态 $j$ 的所有可能路径的概率之和。 我们必须对所有可能的中间状态 $k$ 进行求和，以确保覆盖所有路径。

3. C-K方程的证明

现在，我们来逐步分析一下证明过程。

第一步：定义n步转移概率 证明的起点是 $p_{ij}^{(m+n)}$ 的定义。

$$p_{ij}^{(m+n)}=P\{X_{m+n}=j\mid X_0=i\}$$

这行公式仅仅是写出了 $m+n$ 步转移概率的数学定义，即在初始状态为 $i$ 的条件下，经过 $m+n$ 步后系统处于状态 $j$ 的概率。

第二步：应用条件概率的定义 根据条件概率的基本定义 $P(A|B)=\frac{P(A\cap B)}{P(B)}$，其中 $A=\{X_{m+n}=j\}$，$B=\{X_0=i\}$。

$$P\{X_{m+n}=j\mid X_0=i\}=\frac{P\{X_{m+n}=j,X_0=i\}}{P\{X_0=i\}}$$

这一步是将条件概率展开为其联合概率与条件事件概率的比值形式。

第三步：引入中间状态并应用全概率公式 这是证明中最关键的、最具创造性的一步。我们考虑系统在中间时刻 $m$ 的状态。系统在时刻 $m$ 必然处于某个状态 $k\in S$。根据全概率公式（Law of Total Probability），我们可以将事件 $\{X_{m+n}=j,X_0=i\}$ 的概率，分解为在所有可能的中间状态 $X_m=k$ 下的条件概率之和。

$$P\{X_{m+n}=j,X_0=i\}=\sum _{k\in S}P\{X_{m+n}=j,X_m=k,X_0=i\}$$

将此式代入分母不变，得到：

$$\frac{{\sum }_{k\in S}P\{X_{m+n}=j,X_m=k,X_0=i\}}{P\{X_0=i\}}$$

这一步的核心思想是“分情况讨论”：要计算从 $i$ 到 $j$ 的总概率，我们可以枚举在时刻 $m$ 可能的每一个落脚点 $k$，计算通过该落脚点的路径概率，然后将所有可能路径的概率相加。

第四步：代数变形以构造条件概率 为了将上式重新整理成条件概率的形式，证明中使用了一个标准的代数技巧：乘以一个值为1的项 $\frac{P\{X_m=k,X_0=i\}}{P\{X_m=k,X_0=i\}}$。

$$=\sum _{k\in S}\frac{P\{X_{m+n}=j,X_m=k,X_0=i\}}{P\{X_m=k,X_0=i\}}\cdot \frac{P\{X_m=k,X_0=i\}}{P\{X_0=i\}}$$

这一步看起来是多余的，但其目的是为了在下一步中，将复杂的联合概率分解为两个更简单的条件概率的乘积。

第五步：再次应用条件概率的定义 现在，我们重新审视上式中的两部分：

• 第一部分：$\frac{P\{X_{m+n}=j,X_m=k,X_0=i\}}{P\{X_m=k,X_0=i\}}$，根据条件概率定义，这等于 $P\{X_{m+n}=j\mid X_m=k,X_0=i\}$。
• 第二部分：$\frac{P\{X_m=k,X_0=i\}}{P\{X_0=i\}}$，根据条件概率定义，这等于 $P\{X_m=k\mid X_0=i\}$。

所以，整个表达式变为：

$$=\sum _{k\in S}P\{X_{m+n}=j\mid X_m=k,X_0=i\}\cdot P\{X_m=k\mid X_0=i\}$$

第六步：应用马尔可夫性质 这是证明的第二个关键步骤，它利用了马尔可夫链的根本性质。我们来看第一项 $P\{X_{m+n}=j\mid X_m=k,X_0=i\}$。马尔可夫性质告诉我们，给定当前状态（时刻$m$为$k$），未来的状态（时刻$m+n$为$j$）与过去的状态（时刻$0$为$i$）无关。因此：

$$P\{X_{m+n}=j\mid X_m=k,X_0=i\}=P\{X_{m+n}=j\mid X_m=k\}$$

这一步是合法的，当且仅当过程具有马尔可夫性。

第七步：将条件概率还原为n步转移概率符号 现在，我们将简化后的表达式还原为 $p_{ij}^{(n)}$ 的形式。

• $P\{X_{m+n}=j\mid X_m=k\}$：这是从状态 $k$ 开始，经过 $(m+n)-m=n$ 步到达状态 $j$ 的概率，即 $p_{kj}^{(n)}$。
• $P\{X_m=k\mid X_0=i\}$：这是从状态 $i$ 开始，经过 $m$ 步到达状态 $k$ 的概率，即 $p_{ik}^{(m)}$。

将这些符号代回求和式，我们便得到了C-K方程：

$$=\sum _{k\in S}{p}_{ik}^{(m)}{p}_{kj}^{(n)}$$

证明完毕。

4. C-K方程的矩阵形式与意义

C-K方程 $p_{ij}^{(m+n)}={\sum }_{k\in S}{p}_{ik}^{(m)}{p}_{kj}^{(n)}$ 的形式，与矩阵乘法的定义完全一致。如果我们定义 n 步转移概率矩阵为 ${\mathbf{P}}^{(n)}$，其 $(i,j)$ 元为 $p_{ij}^{(n)}$，那么C-K方程可以被简洁地写作：

$${\mathbf{P}}^{(m+n)}={\mathbf{P}}^{(m)}{\mathbf{P}}^{(n)}$$

这是一个重要的结论。它告诉我们，两个转移矩阵的乘积，对应于其步数的相加。由此可以进行简单的推导：

$${\mathbf{P}}^{(n)}={\mathbf{P}}^{(n-1)}{\mathbf{P}}^{(1)}={\mathbf{P}}^{(n-2)}{\mathbf{P}}^{(1)}{\mathbf{P}}^{(1)}=\cdots =({\mathbf{P}}^{(1)}{)}^n={\mathbf{P}}^n$$

可以看到，马尔可夫链的n步转移概率矩阵，就是其一步转移概率矩阵的 n次幂。C-K方程为这一优雅的代数关系提供了坚实的概率论基础。它使得我们可以通过简单、高效的矩阵乘法运算，来分析和预测马尔可夫链的长期演化行为。