数字花园

专栏⑰·第1篇：马尔可夫链——无后效性的力量（10 大板块深度专题）

17分钟阅读

专栏⑰·第1篇：马尔可夫链——无后效性的力量（10 大板块深度专题）

原始 Flomo：https://v.flomoapp.com/mine/?memo_id=MjQ3MzMwNjkw

专栏⑰·第1篇：马尔可夫链——无后效性的力量（10 大板块深度专题）

📎 专栏⑰导航 → https://v.flomoapp.com/mine/?memo_id=MjQ2Mzc0OTc2

▎从”无记忆”到”无后效”

  1. 指数分布的无记忆性和马尔可夫链的”无后效性”是同一个概念吗？指数分布说”已经用了t小时，再活s小时的概率跟新的一样”——马尔可夫说”下一个状态只取决于当前状态，跟之前怎么来的无关”。共享的核心直觉是—— 过去已经被当前状态”概括”了，知道历史不提供额外信息？

  2. 马尔可夫链最简单的例子——一维随机游走：在整数轴上，每一步以概率p向右走一步、概率q=1-p向左走一步。当前位置就是”状态”，下一步位置只取决于当前位置，跟之前走了多少步、从哪里起步完全无关——这就是马尔可夫性？

  3. “meme”这个词从何而来——理查德·道金斯《自私的基因》里说文化基因像生物基因一样复制传播。但马尔可夫链（Markov chain）是俄国数学家安德烈·马尔可夫（1856-1922）提出的——他当年研究的是普希金的《尤金·奥涅金》中元音和辅音的交替模式，发现可以用一个概率模型来描述字母序列的依赖关系。一个数学家分析诗歌发现了马尔可夫链？

  4. 马尔可夫性的严格数学定义：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}。用大白话说——给定”现在”，“未来”与”过去”独立。为什么这个条件既苛刻又强大（苛刻：现实世界几乎没有什么过程完全满足；强大：一旦满足，所有计算都大大简化）？

▎状态空间与转移矩阵

  1. 有限状态马尔可夫链——状态空间S={1,2,…,m}，转移概率矩阵P是一个m×m矩阵，其中P_{ij}=P{X_{n+1}=j|X_n=i}。为什么矩阵P的每一行之和都等于1（因为从状态i出发，一定会在下一时刻转移到某个状态——可能性总和是100%）？

  2. 转移概率矩阵的n次幂P^n有什么含义？(P^n){ij} = P{X{n+k}=j | X_k=i}—— 从状态i出发，恰好经过n步到达状态j的概率。这个性质为什么如此漂亮——因为矩阵乘法本身就在”复合”转移概率，每一步的转移都是独立的马尔可夫过程？

  3. 查普曼-科尔莫戈罗夫方程（Chapman-Kolmogorov方程）：P^{m+n} = P^m · P^n。它在说什么——从i出发经过m+n步到j的概率，等于”先经m步到某个中间状态k，再从k经n步到j”对所有可能中间状态k求和？

  4. 一个经典的转移矩阵例子——天气预报的朴素模型：如果今天下雨，明天有70%概率继续下雨、30%概率转晴；如果今天晴天，明天有60%概率保持晴天、40%概率转雨。写出转移矩阵P = [[0.7, 0.3], [0.4, 0.6]]。如果今天下雨，后天（两天后）下雨的概率怎么算——(P²)_{1,1}？

  5. 你之前笔记里记过的”人生努力马尔可夫链”——佩奇的模型思维课程中有一个观点：如果把人生看成”努力”和”不努力”两个状态，只要状态转移矩阵确定了，长期来看在每个状态下停留的时间比例也就确定了。如果一个人的”动力源泉”是固定的（从努力到不努力的转移概率恒定），那长期”努力比例”就是固定的——问题不在于你今天努不努力，而在于你的 源动力 有没有变过？

▎状态的分类

  1. 可达与互通——从i可达j（i→j）意味着存在某个n≥0使得(P^n)_{ij}>0。如果i和j互相可达，则称它们互通。互通关系有什么用—— 互通的状态属于同一个”类”（class），一个不可约的马尔可夫链意味着所有状态都在同一个类中（全连通）？

  2. 常返与瞬过——从状态i出发，如果最终返回i的概率是1，则称i为常返（recurrent）状态；如果返回概率小于1，则称i为瞬过（transient）状态。直觉上， 常返状态你”会不停回来”，瞬过状态你”走了就可能不回来”。一维随机游走（p=q=0.5）的每个状态都是常返的——但二维随机游走呢（也是常返），三维呢（ 不是——三维随机游走有正概率一去不返！）？

  3. 为什么三维随机游走跟一维二维有本质区别？因为在高维空间里，“回家”的路径选择太多了，你越走越容易走丢。 “醉汉在一维和二维能走回家，在三维会走丢”——这个结论有什么直观理解？

  4. 周期——从状态i出发，所有可能返回的步数n的最大公约数d(i)称为周期。如果d(i)>1称i为周期状态，d(i)=1称非周期。一个充分条件： 如果P_{ii}>0（一步就能回到自己），那么该状态一定是非周期的？

  5. 不可约且非周期的马尔可夫链为什么是最”好”的？因为这种链有唯一的平稳分布，且从任意初始分布出发都会收敛到这个平稳分布——这是马尔可夫链蒙特卡洛（MCMC）方法的理论基础？

▎平稳分布

  1. 平稳分布π：满足π = πP的分布。也就是说， 如果系统初始分布是π，那么任何时刻的分布都是π（分布不随时间变化）。为什么这叫做”平稳”——因为它站在那儿不动了？

  2. 一个不可约非周期有限状态马尔可夫链，为什么一定会收敛到一个唯一的平稳分布？不管你今天从哪个状态出发， 经过足够多步之后，处在每个状态的概率就固定了——系统”忘记了”初始条件？

  3. 平稳分布怎么算？解方程组π = πP，且Σπ_i = 1。以天气模型P=[[0.7,0.3],[0.4,0.6]]为例，解π₁=0.7π₁+0.4π₂、π₂=0.3π₁+0.6π₂、π₁+π₂=1→得π=(4/7, 3/7)。所以长期来看， 下雨的概率是4/7≈57%，晴天的概率是3/7≈43%——跟今天下不下雨完全无关了？

  4. 细致平衡条件（Detailed Balance）：π_i · P_{ij} = π_j · P_{ji}对所有i,j成立。这个条件比π=πP更强——它要求每对状态之间的”流量”是平衡的。 如果细致平衡成立，π一定是平稳分布。这个性质在什么算法中被大量使用——MCMC的Metropolis-Hastings算法？

  5. 你笔记里提过的”人生努力马尔可夫链”——如果从”努力”到”不努力”的转移概率是α，从”不努力”到”努力”是β，那么长期努力比例是多少？解π_努力 = β/(α+β)。比如α=0.3（30%概率从努力滑向不努力）、β=0.2（20%概率从不努力转向努力），那么长期努力比例 = 0.2/0.5 = 40%。你笔记里说”问题的根本不在于你的状态，而在于源动力”——源动力在这里对应的是什么—— 转移概率α和β的大小，它们才是决定长期行为的真正参数？

▎马尔可夫链蒙特卡洛（MCMC）

  1. MCMC要解决什么问题——从一个复杂的、高维的概率分布中采样。为什么直接采样不行？因为高维空间的归一化常数计算量太大（维数灾难）。MCMC绕过了这个问题：不直接算分布本身，而是 构造一条马尔可夫链，让它的平稳分布等于目标分布，然后沿着这条链”走”就能得到目标分布的样本？

  2. Metropolis-Hastings算法——怎么构造这样的链？从当前状态x出发，按提议分布q(y|x)生成候选状态y。以概率A=min(1, π(y)q(x|y)/π(x)q(y|x))接受y，否则留在x。为什么这个算法能保证平稳分布是π？因为 它满足细致平衡条件——接受概率A的构造恰好让两边的流量相等？

  3. Gibbs采样——什么时候用Gibbs比Metropolis-Hastings更方便？当你能写出 每个变量的条件分布，但不能写出联合分布。Gibbs采样每次只更新一个变量。 它不需要调接受概率的参数——但代价是什么？如果变量之间强相关，Gibbs采样会”移动得很慢”？

  4. 收敛诊断——你怎么知道MCMC链已经”烧完了”（burn-in结束）？多重链从不同初始值出发，观察链内方差和链间方差的比值——Gelman-Rubin统计量R̂<1.1表示收敛。为什么只看一条链不够？

▎隐马尔可夫模型（HMM）

  1. HMM跟普通马尔可夫链的区别——普通马尔可夫链的”状态”是直接可观测的；HMM的 状态是隐藏的，你只能观测到跟状态相关的”输出”。为什么这个模型在语音识别、手写识别、生物信息学中如此流行？

  2. HMM的三个基本问题——（1） 评估：计算P(O|λ)；（2） 解码：找出最可能的状态序列Q*（Viterbi算法）；（3） 学习：估计模型参数λ（Baum-Welch/EM）。三个问题分别对应什么实际需求？

  3. Viterbi算法——用动态规划找最可能的隐藏状态序列。它跟前向算法的核心区别？前向算法 求和 所有路径，Viterbi算法 取最大值。为什么”取最大”仍然是合理的？

  4. 前向-后向算法——为什么需要”后向概率”β_t(i)=P(O_{t+1},…,O_T | X_t=i, λ)？因为E步你需要计算”在时刻t处于状态i的概率”，而这个概率需要知道”之前的观测”和”之后的观测”？

  5. HMM的三个假设——马尔可夫假设、输出独立假设、平稳假设。这三个假设在实际中几乎全被违反——为什么HMM仍然有效（模型”足够好”时就有实用价值）？

▎PageRank：改变世界的马尔可夫链

  1. Google的PageRank本质上是一个马尔可夫链。网页是状态，链接是转移概率。 PageRank值就是这个马尔可夫链的平稳分布——“一个随机冲浪者长期浏览每个网页的概率”？

  2. 网络中存在”悬挂节点”和”循环陷阱”——PageRank的解决方案？ 加入”跳转因子”（damping factor，通常α=0.85）：以85%的概率按链接浏览，15%的概率随机跳转到任意网页——这个”随机跳转”使链变得不可约且非周期，保证了平稳分布的唯一存在？

  3. 为什么说PageRank的成功证明了”马尔可夫链在超大规模问题上的可行性”？解几十亿×几十亿的线性方程组不可能——但用 幂迭代法 只需要几十次迭代就能收敛？因为转移矩阵是稀疏的，每次迭代的计算量只有O(边数)？

▎你笔记里的马尔可夫链

  1. 你记过佩奇《模型思维》的观点：“在离散状态马尔科夫过程中，如果把人生看成努力和不努力两个状态，只要状态转移矩阵确定了，长期来看，在每个状态下所停留的时间比例也就都确定了。“——这个观点是不是在说， 与其纠结”今天我努力不努力”，不如想办法改变转移概率本身（通过改变环境、习惯设计来降低”努力→不努力”的概率α，提高”不努力→努力”的概率β）？

  2. 你还记过：“如果人生的动力源泉是固定的，努力的百分比就是固定的，那么短期内努力或者不努力并不会有什么影响。也就是说，问题的根本不在于你的状态，而在于源动力！”——“源动力”可以被理解成马尔可夫链的哪个参数？转移矩阵本身？还是那个唯一能改变转移矩阵的东西？

  3. 如果把你的”堆问题学习法”建模成一个马尔可夫链——你的状态是”对某个知识点的理解深度”（没见过→听说过→能解释→能应用→能教别人），每一步的转移概率取决于什么——是否刻意练习、是否回顾笔记。长期来看， 在哪个深度上花的时间最多，取决于你从”浅层”跳到”深层”的概率——你是通过什么行为来提高这个转移概率的？

📎 第8篇：马尔可夫链工程应用 → https://v.flomoapp.com/mine/?memo_id=MjUwNzc0MDg1
📎 第2篇：矩阵变换 = 坐标系转换 → https://v.flomoapp.com/mine/?memo_id=MjQ5MDI4Mjc5
📎 专栏⑰导航 → https://v.flomoapp.com/mine/?memo_id=MjQ2Mzc0OTc2

专栏⑰进度：1/10篇

数学

关系图谱

反向链接