CS70 Disc 13A

1 Markov Chain Basics

背景： 马尔可夫链是一系列随机变量 $ X_n $, $ n = 0,1,2,... $，可以用来描述一个粒子在时间 $ n $ 时的状态。粒子每经过一个时间步都会跳到另一个状态，且马尔可夫链满足马尔可夫性质：

$ P[X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0] = P[X_{n+1} = j | X_n = i] $

这意味着未来状态仅依赖于当前状态，与过去的状态无关。

(a) 三个基本组成部分：$ X $, $ P $, 和 $ _0 $

$ X $：状态集，表示可能的状态范围。在此场景下，我们仅讨论有限的 $ X $。
**$ P $**：转移概率矩阵，$ P(i, j) $ 表示从状态 $ i $ 转移到状态 $ j $ 的概率。需要满足： $ _{j X} P(i, j) = 1 i X $ 即从一个状态必须转移到某个状态的概率和为 1，且所有概率非负，$ P(i, j) $。 - **$ _0 $**：初始状态分布，表示 $ X_0 $ 处于状态 $ i $ 的概率。即 $ _0(i) = P[X_0 = i] $。它也是一个概率分布，因此 $ 0 $ 的所有项必须非负，且概率和为 1，$ {i X} _0(i) = 1 $。

(b) $ X $, $ P $, 和 $ _0 $ 如何定义马尔可夫链

根据马尔可夫性质和转移矩阵 $ P $，我们可以定义出随机变量序列 $ X_n $：

初始状态 $ X_0 $ 的分布由 $ _0 $ 给定，即 $ P[X_0 = i] = _0(i) $。
$ X_{n+1} $ 的分布只依赖于 $ X_n $，具体为：$ P[X_{n+1} = j | X_n = i, X_{n-1} = i_{n-1}, ..., X_0 = i_0] = P[X_{n+1} = j | X_n = i] = P(i, j) $

这说明，如果我们指定了转移矩阵 $ P $ 和初始分布 $ _0 $，就隐含定义了满足马尔可夫性质的随机变量序列 $ X_n $。

(c) 计算 $ P[X_1 = j] $ 并用矩阵形式表示

根据全概率公式，可以表示：

$ P[X_1 = j] = {i X} P[X_1 = j, X_0 = i] = {i X} P[X_0 = i] P[X_1 = j | X_0 = i] = _{i X} _0(i) P(i, j) $

如果我们将 $ _1(j) = P[X_1 = j] $ 记为向量形式，则有： $ _1 = _0 P $

即经过一步转移后的状态分布等于初始分布与转移矩阵的乘积。经过 $ n $ 次转移后，状态分布为： $ _n = _0 P^n $

这说明马尔可夫链的计算本质上是矩阵乘法。由于计算过程可以自然地表达为矩阵运算，因此马尔可夫链模型非常适合通过计算机处理。

2 Can it be a Markov Chain?

(a) 苍蝇在直线上以单位长度移动

背景：一个苍蝇每秒向左、向右或停留的概率分别为 0.3、0.3 和 0.4。它在位置 1 和位置 $ m $ 处会被蜘蛛捕获。苍蝇从 1 和 $ m $ 之间的某个位置开始移动，需要将这个过程建模为马尔可夫链。

问题分析：
- 状态：苍蝇的位置可以视为状态。
- 转移概率：苍蝇在每个时间步都有三种可能性：向左移动、向右移动或停留。
- 边界条件：当苍蝇处于位置 1 或位置 $ m $ 时被捕获，因此不再发生状态转移。

解答：我们可以将苍蝇的移动过程建模为一个马尔可夫链。设状态集 $ X = {1, 2, ..., m-1, m} $。在每个位置，转移概率如下：

对于位置 $ 2 i m-1 $，
- 向左移动的概率为 0.3，即 $ P(i, i-1) = 0.3 $；
- 向右移动的概率为 0.3，即 $ P(i, i+1) = 0.3 $；
- 停留的概率为 0.4，即 $ P(i, i) = 0.4 $。
对于边界位置 1 和 $ m $，一旦苍蝇到达这些位置，它将被捕获，因此这些状态是吸收状态：
- $ P(1, 1) = 1 $，即苍蝇被捕获并留在位置 1；
- $ P(m, m) = 1 $，即苍蝇被捕获并留在位置 $ m $。

此时，该过程满足马尔可夫链的定义，转移只依赖当前状态，不依赖历史状态。

(b) 更改后的场景

背景：现在设定 $ m = 4 $。定义 $ Y_n $ 为新的随机过程：

当苍蝇在位置 1 或 2 时，设 $ Y_n = 0 $；
当苍蝇在位置 3 或 4 时，设 $ Y_n = 1 $。

问题：此过程 $ Y_n $ 是否为马尔可夫链？

解答：这个新过程 $ Y_n $ 不是马尔可夫链，因为它不满足马尔可夫性质，即未来状态不仅仅依赖于当前状态，还依赖于历史状态。

示例反证：设 $ P[X_0 = 2] = P[X_0 = 3] = 1/2 $，且 $ P[X_0 = 1] = P[X_0 = 4] = 0 $。
- 对于 $ Y_2 = 0 $，我们计算两种不同的历史下的条件概率：
  1. 当 $ Y_0 = 0 $ 且 $ Y_1 = 1 $ 时： $ P[Y_2 = 0 | Y_1 = 1, Y_0 = 0] = P[X_2 {1, 2} | X_1 = 3, X_0 = 2] = P[X_2 = 2 | X_1 = 3] = 0.3 $
  2. 当 $ Y_0 = 1 $ 且 $ Y_1 = 1 $ 时： $ P[Y_2 = 0 | Y_1 = 1, Y_0 = 1] = = = $

这两个概率不相等，分别为 0.3 和 $ $，这表明 $ P[Y_2 = 0 | Y_1 = 1, Y_0 = 0] P[Y_2 = 0 | Y_1 = 1, Y_0 = 1] $。如果 $ Y_n $ 是一个马尔可夫链，那么条件概率只应依赖于当前状态 $ Y_1 $，不依赖于之前的状态 $ Y_0 $，但在此例中不成立，因此 $ Y_n $ 不是马尔可夫链。