CS70Disc13B
CS70 Disc 13B
1 Markov Chain Terminology
背景介绍
马尔可夫链是描述系统在不同状态之间转移的随机过程，重要的相关术语包括不可约性、周期性、矩阵表示、不变分布等。
1. 马尔可夫链术语
(1) 不可约性 (Irreducibility)
- 定义：若马尔可夫链是不可约的，那么从任意状态 \(i\) 出发，经过若干步转移，可以到达任意另一个状态 \(j\)。
(2) 周期性 (Periodicity)
- 定义：对状态 \(i\)，其周期 \(d(i)\) 定义为： $ d(i) = {n > 0 |
P^n(i,i) = P[X_n = i | X_0 = i] > 0} $
- 若 \(d(i) = 1\) 对于所有 \(i \in X\) 成立，则该马尔可夫链是非周期的（即无周期性）；否则为周期的。
(3) 矩阵表示 (Matrix Representation)
- 定义：状态转移矩阵 \(P\) 是一个概率矩阵，其第 \(i\) 行第 \(j\) 列的元素表示从状态 \(i\) 转移到状态 \(j\) 的概率 \(P(i,j)\)。
(4) 不变分布 (Invariance)
- 定义：分布 $ $ 是转移矩阵 $ P $ 的不变分布，若满足以下平衡方程： $ = P $ 即 $ $ 在转移矩阵 $ P $ 作用下保持不变。
2. 问题解析
给定一个两状态的马尔可夫链，状态转移的概率矩阵如下：
$ P = \[\begin{bmatrix} 1 - b & b \\ a & 1 - a \end{bmatrix}\]$
(a) 在何种情况下，该马尔可夫链是不可约的？在何种情况下是可约的？
- 不可约性：若 \(a > 0\) 且 \(b > 0\)，则从任一状态可以通过若干步转移到另一状态，因此马尔可夫链是不可约的。
- 可约性：若 \(a = 0\) 或 \(b = 0\)，则某些状态间不能相互转移，马尔可夫链是可约的。
(b) 证明当 \(a = 1\)，\(b = 1\) 时，马尔可夫链是周期的。
- 周期性计算：假设从状态 0 开始，我们需要计算回到状态
0 的最小步数。
- \(d(0) = \text{gcd}\{n > 0 | P^n(0, 0) > 0\}\)
- 由于当 \(a = 1\)、\(b = 1\) 时，马尔可夫链只能在偶数步时回到状态 0（如 2 步、4 步、6 步），因此： $ d(0) = {2, 4, 6, } = 2 $ 所以该马尔可夫链是周期为 2 的。
(c) 证明当 \(0 < a < 1\)，\(0 < b < 1\) 时，马尔可夫链是非周期的。
- 非周期性计算：假设从状态 0 开始，我们计算回到状态 0
的最小步数。
- 由于存在 \(1 - b\) 和 \(1 - a\) 的自循环概率（即停留在原状态的概率不为 0），因此无论采取奇数步还是偶数步都可能回到初始状态。
- 于是： $ d(0) = {1, 2, 3, } = 1 $ 因此该马尔可夫链是非周期的。
(d) 构造转移概率矩阵
根据状态转移关系，构造的转移概率矩阵为：
$ P = \[\begin{bmatrix} 1 - b & b \\ a & 1 - a \end{bmatrix}\]$
(e) 写出平衡方程并解出不变分布
平衡方程组如下：
- 对于状态 0： $ (0) = (1 - b)(0) + a(1) $
- 对于状态 1： $ (1) = b(0) + (1 - a)(1) $
去掉冗余的方程，使用归一化条件 $ (0) + (1) = 1 $，可得：
$ (0) = , (1) = $
因此，不变分布为：
$ = \[\begin{bmatrix} a \\ b \end{bmatrix}\]$
2 Skipping Stones
背景介绍
我们要解决的是一个关于石头在河面上跳跃的马尔可夫链模型问题。问题目标是计算从状态 1 出发，在没有跳过目标（状态 3）之前，命中目标的概率。问题中的状态集合为 $ X = {1, 2, 3, 4, 5} $，具体的含义如下：
- 状态 3 表示目标；
- 状态 4 和 5 表示超过目标的情况（即石头跳过了目标）；
- 状态 1 和 2 表示石头在距离目标较远的状态。
我们假设在状态 1 和状态 2，石头可以以等概率向前跳跃 1、2 或 3 步。
问题描述
- 初始状态：石头从状态 1 出发；
- 目标：命中状态 3（目标）而不是跳过目标到达状态 4 或 5。
- 任务：计算从状态 1 出发，到达状态 3 的概率，即石头命中目标而不是跳过的概率。
1. 马尔可夫链结构
根据问题描述，马尔可夫链的状态转移可以表示如下：
$ X = {1, 2, 3, 4, 5} $
状态 3 是目标状态，命中目标的概率为 1： $ (3) = 1 $
状态 4 和状态 5 是失败状态，即跳过了目标，不可能再命中目标： $ (4) = 0, (5) = 0 $
状态 1 和状态 2 是在距离目标较远的状态，从这些状态可以以等概率跳 1、2 或 3 步。需要计算从这些状态出发最终命中目标的概率。
2. 递推关系
令 $ (i) $ 表示从状态 $ i $ 出发，命中目标 $ {3} $ 而不跳过 $ {4,5} $ 的概率。
对于状态 1，石头可以跳跃 1、2 或 3 步，因此可以递推为： $ (1) = (2) + (3) + (4) $
对于状态 2，石头也可以跳跃 1、2 或 3 步，递推关系为： $ (2) = (3) + (4) + (5) $
根据已知的初始条件： $ (3) = 1, (4) = 0, (5) = 0 $
因此，状态 2 的递推式可以简化为： $ (2) = + + = $
3. 求解状态 1 的概率
现在将 $ (2) = $ 代入状态 1 的递推方程：
$ (1) = (2) + (3) + (4) $
代入已知值 $ (2) = , (3) = 1, (4) = 0 $：
$ (1) = + + = + $
将两项合并：
$ (1) = + = $
3 Consecutive Flips
问题背景
我们研究一个抛硬币的随机过程，目标是连续抛出三次相同的结果（即连续三次正面或连续三次反面）。具体的任务包括：
- (a) 构建一个描述这一情况的马尔可夫链，从初始状态到结束状态；
- (b) 如果当前抛出的是“反面，正面”（即到达状态 \(H1\)），计算从此状态出发到达结束状态的期望抛掷次数；
- (c) 从初始状态出发，计算看到连续三次相同结果所需的期望抛掷次数。
(a) 马尔可夫链构建
为了描述抛硬币过程，我们构建了一个有 6 个状态的马尔可夫链：
- Start: 起始状态，即刚开始抛掷硬币。
- H1: 表示已经连续抛出 1 次正面（Heads）。
- H2: 表示已经连续抛出 2 次正面。
- T1: 表示已经连续抛出 1 次反面（Tails）。
- T2: 表示已经连续抛出 2 次反面。
- End: 表示已经连续抛出 3 次相同的结果，达到目标状态，过程结束。
- 状态转换规则：
- 从 Start 状态，以 $ $ 的概率转移到 H1 或 T1。
- 从 H1 状态，以 $ $ 的概率转移到 H2 或 T1。
- 从 H2 状态，以 $ $ 的概率转移到 End 或 T1。
- 从 T1 状态，以 $ $ 的概率转移到 H1 或 T2。
- 从 T2 状态，以 $ $ 的概率转移到 End 或 H1。
- End 状态为终止状态，过程结束。
马尔可夫链状态图：
每个状态的转移概率都为 $ $。
(b) 从状态 \(H1\) 出发的期望抛掷次数
现在假设当前的状态是 H1（即已经抛出 “反面，正面”），我们需要计算从这个状态到达 End 的期望抛掷次数。我们将使用递推方程求解每个状态的期望抛掷次数。
令 $ (i) $ 表示从状态 $ i $ 出发，到达 End 的期望抛掷次数。
根据马尔可夫链的转移关系，可以建立如下的方程组：
- 从状态 H1 出发： $ (H1) = 1 + 0.5 (T1) + 0.5 (H2) $
- 从状态 H2 出发： $ (H2) = 1 + 0.5 (End) + 0.5 (T1) $
- 从状态 T1 出发： $ (T1) = 1 + 0.5 (T2) + 0.5 (H1) $
- 从状态 T2 出发： $ (T2) = 1 + 0.5 (End) + 0.5 (H1) $
- End 是终止状态，抛掷次数为 0： $ (End) = 0 $
求解方程组
代入已知的 $ (End) = 0 $：
从 H2 出发的方程变为： $ (H2) = 1 + 0.5 + 0.5 (T1) = 1 + 0.5 (T1) $
从 T2 出发的方程变为： $ (T2) = 1 + 0.5 + 0.5 (H1) = 1 + 0.5 (H1) $
接下来，我们将方程逐步代入和求解：
将 $ (H2) = 1 + 0.5 (T1) $ 代入 $ (H1) = 1 + 0.5 (T1) + 0.5 (H2) \(：\) (H1) = 1 + 0.5 (T1) + 0.5(1 + 0.5 (T1)) = 1 + 0.5 (T1) + 0.5 + 0.25 (T1) $ $ (H1) = 1.5 + 0.75 (T1) $
将 $ (T2) = 1 + 0.5 (H1) $ 代入 $ (T1) = 1 + 0.5 (T2) + 0.5 (H1) \(：\) (T1) = 1 + 0.5(1 + 0.5 (H1)) + 0.5 (H1) = 1 + 0.5 + 0.25 (H1) + 0.5 (H1) $ $ (T1) = 1.5 + 0.75 (H1) $
将 $ (T1) = 1.5 + 0.75 (H1) $ 代入 $ (H1) = 1.5 + 0.75 (T1) \(：\) (H1) = 1.5 + 0.75(1.5 + 0.75 (H1)) = 1.5 + 1.125 + 0.5625 (H1) $ $ (H1) = 2.625 + 0.5625 (H1) $ $ 0.4375 (H1) = 2.625 $ $ (H1) = = 6 $
最终得到 $ (H1) = 6 $。同理可以求得：
$ (H2) = 4, (T1) = 6, (T2) = 4 $
(c) 从初始状态出发的期望抛掷次数
从初始状态 Start 出发，转移到 $ H1 $ 或 $ T1 $ 的概率均为 $ $，因此期望次数为：
$ (S) = 1 + 0.5 (H1) + 0.5 (T1) $
代入已知值 $ (H1) = 6 $ 和 $ (T1) = 6 $：
$ (S) = 1 + 0.5 + 0.5 = 1 + 3 + 3 = 7 $
