二节离散时间马尔可夫链的几个质

StochasticProcesses离散时间马尔可夫链的几个性质随机过程·状态分类·极限行为·遍历性理论Contents课程目录马尔可夫链的理论框架与核心分析方法01基本概念回顾与马尔可夫性02状态的分类与结构分析03极限定理与平稳分布04遍历性与首达时间CHAPTER01基本概念回顾与马尔可夫性从随机过程出发，理解无后效性的数学本质StochasticProcess·Foundations离散时间马尔可夫链的数学定义离散时间马尔可夫链（DTMC）是定义在可数状态空间上的随机过程，其核心特征是马尔可夫性——系统在下一时刻的状态概率仅取决于当前状态，与历史路径无关，这一"无后效性"是后续所有性质推导的出发点。01可数状态空间：状态空间S为有限集或可数无穷集，如S={0,1,2,...}，系统在每个离散时刻n处于某个确定状态Xₙ∈SS={0,1,2,...}02马尔可夫性：P(Xₙ₊₁=j|Xₙ=i,Xₙ₋₁=iₙ₋₁,...,X₀=i₀)=P(Xₙ₊₁=j|Xₙ=i)，条件概率仅与当前状态有关无后效性03一步转移概率：pᵢⱼ=P(Xₙ₊₁=j|Xₙ=i)描述从状态i转移到状态j的概率，是构建整个理论体系的基石pᵢⱼ04齐次性假设：转移概率pᵢⱼ不随时间n变化，即对任意n均相同，这使得矩阵分析工具可以直接应用∀n恒定MARKOVPROPERTY马尔可夫性的深层含义马尔可夫性的本质是条件独立性——在给定当前状态的条件下，系统的未来演化与历史路径条件独立。这一性质将复杂的随机过程分析简化为对当前状态的条件概率研究，是DTMC可解析求解的根本原因。01条件独立表述给定Xn，未来{Xn+1,Xn+2,…}与过去{X0,…,Xn-1}条件独立，历史信息被当前状态"充分统计"P(Future|Present)02与有记忆过程对比若系统下一步行为依赖最近k步历史，则为k阶马尔可夫链；可通过扩展状态空间转化为一阶DTMCk阶→1阶03实际意义在天气预测、股价模型等场景中，马尔可夫性假设虽不完全精确，但提供了可计算的近似框架近似可计算04路径概率分解P(X0=i0,…,Xn=in)=P(X0=i0)·pi₀i₁·…·piₙ₋₁iₙ，联合概率简化为连乘∏连乘分解TransitionMatrix转移概率矩阵的结构与性质转移概率矩阵P是DTMC的完整数学描述，它是一个随机矩阵（每行元素非负且行和为1），完全刻画了系统的动态演化规律。通过矩阵运算可以计算任意步数的转移概率，是连接概率论与线性代数的关键桥梁。01矩阵定义：P=(pᵢⱼ)ₘₓₘ，pᵢⱼ=P(Xₙ₊₁=j|Xₙ=i)，行对应出发状态，列对应目标状态。02随机矩阵性质：0≤pᵢⱼ≤1且Σⱼpᵢⱼ=1（行和归一），保证概率完备性。03天气预测实例：S={晴,多云,雨}，P=[[.7,.2,.1],[.3,.4,.3],[.1,.3,.6]]展示转移关系。04多步转移：P⁽ⁿ⁾=Pⁿ，Chapman-Kolmogorov方程P⁽ᵐ⁺ⁿ⁾=P⁽ᵐ⁾·P⁽ⁿ⁾建立递推关系。气象观测站—天气预测的DTMC应用场景MARKOVCHAINSChapman-Kolmogorov方程与多步转移C-K方程P⁽ᵐ⁺ⁿ⁾=P⁽ᵐ⁾·P⁽ⁿ⁾是马尔可夫性的直接推论，揭示了多步转移概率的矩阵乘法结构，将概率递推转化为矩阵运算。01n步转移概率pᵢⱼ⁽ⁿ⁾=P(Xₘ₊ₙ=j|Xₘ=i)，从状态i出发经n步到达状态j的概率，与起始时刻m无关（齐次性）。pᵢⱼ⁽ⁿ⁾02C-K核心公式pᵢⱼ⁽ᵐ⁺ⁿ⁾=Σₖpᵢₖ⁽ᵐ⁾·pₖⱼ⁽ⁿ⁾，先m步到中间态k，再n步到j，对所有中间状态求和。Σₖ03矩阵对角化P⁽ⁿ⁾=Pⁿ，若P可对角化为P=UDU⁻¹，则Pⁿ=UDⁿU⁻¹，计算复杂度大幅降低。UDⁿU⁻¹04信用评分应用通过多步转移矩阵预测客户未来多个周期后的信用等级分布，为风险管理提供量化依据。信用风险DISCRETE-TIMEMARKOVCHAIN状态转移图与可达性分析状态转移图是DTMC的有向图表示，通过图的连通性可以直观判断状态之间的可达关系。可达性是状态分类的基础——如果从状态i可以通过有限步正概率路径到达状态j，则称i可达j，这一关系决定了状态空间的分解结构。有向图表示节点集=状态空间S，有向边(i→j)存在当且仅当pij>0，边权为转移概率值，自环表示停留在当前状态的概率。pij>0可达性定义若存在n≥1使得pij(n)>0，则称状态i可达状态j（记为i→j），意味着存在一条从i到j的正概率路径。i→j互通关系若i→j且j→i同时成立，则称i与j互通（记为i↔j），互通是等价关系，可将状态空间划分为若干互通类。i↔j赌徒破产模型状态空间{0,1,...,N}中，0和N为吸收态（自环概率为1），中间状态形成单一互通类，但无法到达后返回。{0,1,…,N}CHAPTER02状态的分类与结构分析常返与瞬过、周期与遍历——理解状态的内在属性MarkovChain·StateClassification首达时间与首返概率首返时间Tᵢ和首返概率fᵢᵢ是状态分类的核心工具。首返概率衡量系统从状态i出发后最终返回i的可能性，它直接决定了状态的常返性：fᵢᵢ=1意味着必然返回（常返），fᵢᵢ<1意味着可能永不返回（瞬过），这一二分法构成状态分类的第一层划分。首达时间定义Tⱼ=min{n≥1:Xₙ=j}，表示系统首次到达状态j的时刻，若永远不到达则Tⱼ=∞，它是一个取正整数值的随机变量Tⱼ=min{n≥1:Xₙ=j}首返概率fᵢᵢ⁽ⁿ⁾=P(Tᵢ=n|X₀=i)表示恰好第n步首次返回i的概率；总首返概率fᵢᵢ=Σₙ₌₁^∞fᵢᵢ⁽ⁿ⁾，即最终返回i的总概率fᵢᵢ=Σₙ₌₁^∞fᵢᵢ⁽ⁿ⁾首返概率与转移概率pᵢᵢ⁽ⁿ⁾=Σₖ₌₁ⁿfᵢᵢ⁽ᵏ⁾·pᵢᵢ⁽ⁿ⁻ᵏ⁾，这是一个卷积方程，将n步返回概率分解为首次返回与后续返回的组合pᵢᵢ⁽ⁿ⁾=fᵢᵢ*pᵢᵢ直觉理解fᵢᵢ=1好比"回家的路永远存在"，系统虽可能走很远但必然返回；fᵢᵢ<1好比"存在一条不归路"，系统有正概率一去不返常返vs瞬过DTMC·StateClassification常返态与瞬过态的定义及判定常返态和瞬过态是DTMC状态的基本二分法：常返态意味着系统必然无限次返回，瞬过态意味着系统仅有限次访问后永久离开。RECURRENT常返态定义fᵢᵢ=1，系统从i出发以概率1返回；由Borel-Cantelli引理，常返态将被无限次访问。P(Xₙ=i,i.o.)=1TRANSIENT瞬过态定义fᵢᵢ<1，出发后有正概率永不返回；访问总次数服从几何分布，期望次数为有限值。E=1/(1−fᵢᵢ)SERIESCRITERION级数判据Σpᵢᵢ⁽ⁿ⁾=∞则常返，Σpᵢᵢ⁽ⁿ⁾<∞则瞬过，将常返性问题转化为级数敛散性问题。敛散性判定FINITETHEOREM有限状态空间定理有限状态DTMC至少存在一个常返态，系统最终必然进入某个常返类并永留其中。∃常返类CLASSIFICATION正常返与零常返的进一步细分常返态按平均首返时间μᵢ的有限性进一步分为正常返（μᵢ<∞）和零常返（μᵢ=∞）。正常返态在长期运行中占据非零比例的时间，是平稳分布存在的充要条件。平均首返时间μᵢ=E[Tᵢ|X₀=i]=Σₙ₌₁^∞n·fᵢᵢ⁽ⁿ⁾，衡量常返态i两次连续访问之间的平均间隔长度μᵢ正常返μᵢ<∞，系统频繁返回状态i，长时间运行中访问时间比例趋于1/μᵢ>0，具有明确的稳态意义μᵢ<∞零常返μᵢ=∞，fᵢᵢ=1保证必然返回，但返回间隔期望为无穷大，长期占比lim(n→∞)pᵢᵢ⁽ⁿ⁾=0，不贡献稳态概率μᵢ=∞有限状态空间有限状态DTMC中不存在零常返态，所有常返态都是正常返的，这大大简化了有限链的分析DTMCPeriodicity状态的周期性分析周期性描述了状态i被访问的时间节拍规律：周期d(i)>1意味着系统只能在d(i)的整数倍步数上返回，d(i)=1则为非周期。Definition周期定义d(i)=gcd{n≥1:pᵢᵢ⁽ⁿ⁾>0}，即所有可能返回步数的最大公约数。若d(i)=1则状态i为非周期的。d(i)=1Example周期为2的经典例子简单随机游走在偶数格点上，每步向左或向右移动1格，从任意点出发只能在偶数步返回原点。d=2Breaking自环打破周期性若pᵢᵢ>0（状态有自环），则1属于可返回步数集合，d(i)=1，状态一定非周期。pᵢᵢ>0Ergodic遍历态定义非周期且正常返的状态称为遍历态，极限概率存在且为正：limpᵢᵢ⁽ⁿ⁾=1/μᵢ>0。lim=1/μᵢMARKOVCHAIN·CLASSSTRUCTURE互通类与状态空间分解互通关系将状态空间划分为若干等价类，同一互通类内的状态共享常返性、正常返性和周期性。系统的长期行为由常返类主导。类属性一致性定理若i↔j，则i和j同为常返或同为瞬过；若均为常返则同为正常返或同为零常返；且d(i)=d(j)，所有分类属性在互通类内保持一致。证明核心：互通意味着存在r,s使得pᵢⱼ⁽ʳ⁾>0且pⱼᵢ⁽ˢ⁾>0，利用不等式pᵢᵢ⁽ʳ⁺ⁿ⁺ˢ⁾≥pᵢⱼ⁽ʳ⁾·pⱼⱼ⁽ⁿ⁾·pⱼᵢ⁽ˢ⁾建立级数敛散性的等价关系。状态空间分解结构分解定理：S=C₁∪C₂∪...∪Cₖ∪T，其中C₁,...,Cₖ是互不相交的常返互通类，T是所有瞬过态的集合。常返类是闭集：一旦系统进入某个常返类Cₖ，将永远留在Cₖ内，不会被"吸出"；瞬过态集合T则不具有封闭性。有限DTMC的终极归宿：有限链中系统最终以概率1进入某个常返类并永远停留，瞬过态仅是过渡阶段，长期行为完全由常返类决定。MarkovChain·Classification状态分类实例：四状态DTMC分析通过一个四状态DTMC的完整分类演示，展示了从画转移图、判断互通关系、识别闭集到确定常返性和周期性的系统分析流程。四状态DTMC的转移概率矩阵出发状态→状态1→状态2→状态3→状态4状态10.40.600状态20.50.500状态3001.00状态40.20.30.10.4RecurrentClassI状态{1,2}：常返类互通且构成闭集，一旦进入则永不离开该集合RecurrentClassII状态{3}：吸收态P₃₃=1.0，自转移概率为1，进入后永不离开TransientState状态{4}：瞬过态可到达所有状态但无法被任何状态返回Discrete-TimeMarkovChain状态分类体系总览DTMC状态分类体系包含两个独立维度：常返性与周期性。遍历态=非周期+正常返，是唯一具有非零极限概率的状态类型。有限状态空间中不存在零常返态，分类结构大幅简化。按常返性分类RECURRENT常返态(fᵢᵢ=1)：系统必然返回，无限次访问。分为正常返(μᵢ<∞)和零常返(μᵢ=∞)TRANSIENT瞬过态(fᵢᵢ<1)：有正概率永不返回，仅有限次访问，最终进入某个常返类fᵢᵢ=1按周期性分类APERIODIC非周期态(d=1)：可在任意步数返回，极限概率limpᵢᵢ⁽ⁿ⁾存在PERIODIC周期态(d>1)：仅在d的整数倍步数返回，极限不存在但Cesàro平均存在d=1最重要的组合：遍历态ERGODICSTATE遍历态=非周期+正常返，limpᵢᵢ⁽ⁿ⁾=1/μᵢ>0，唯一具有非零稳态概率的状态ERGODICCHAIN不可约且所有状态为遍历态时，链具有唯一平稳分布πⱼ=1/μⱼπⱼ=1/μⱼChapter03极限定理与平稳分布探索马尔可夫链的长期行为与稳态特征STATIONARYDISTRIBUTION平稳分布的定义与计算平稳分布π是满足πP=π的概率向量，描述了DTMC在稳态下处于各状态的概率。平稳分布的存在性与唯一性取决于链的不可约性和常返性：不可约正常返链存在唯一的平稳分布，且πⱼ=1/μⱼ。定义概率向量π满足πP=π（即πⱼ=Σᵢπᵢ·pᵢⱼ对所有j成立）且Σⱼπⱼ=1，则π称为DTMC的平稳分布。πP=π物理含义若X₀的初始分布为π，则Xₙ的分布对所有n均为π，系统进入"统计平衡"状态，宏观统计量不再随时间变化。统计平衡计算方法求解线性方程组π(P−I)=0加上归一化约束Σπⱼ=1，对于m个状态的链，这是m+1个方程、m个未知数的系统。π(P−I)=0与平均首返时间的关系对不可约正常返链，πⱼ=1/μⱼ，即平稳概率恰好等于平均首返时间的倒数，建立了概率与时间的深刻联系。πⱼ=1/μⱼEXISTENCE&UNIQUENESS平稳分布的存在性与唯一性定理平稳分布的存在性与唯一性由链的结构决定：不可约链存在平稳分布当且仅当所有状态正常返，且分布唯一；可约链的平稳分布不唯一，其集合由常返类上的局部分布构成凸集。1不可约+正常返若DTMC不可约且所有状态正常返，则存在唯一的平稳分布π，且πⱼ=1/μⱼ>0对所有j∈S成立。此时链是遍历的，长期行为稳定。2不可约+零常返或瞬过若不可约链的所有状态为零常返或瞬过，则不存在平稳分布。任何满足πP=π的非负解都无法归一化，概率质量发散或趋于零。3可约链的平稳分布若链有k个常返类C₁,...,Cₖ，每个类上有各自的平稳分布π⁽¹⁾,...,π⁽ᵏ⁾，则任何凸组合Σαₖπ⁽ᵏ⁾（αₖ≥0,Σαₖ=1）都是平稳分布，解构成凸集。4有限不可约链的简化有限状态+不可约⟹所有状态正常返⟹平稳分布必然存在且唯一。这是最重要的实用结论，无需额外检验正常返性。MARKOVCHAIN·REVERSIBILITY细致平衡条件与可逆链细致平衡条件πᵢpᵢⱼ=πⱼpⱼᵢ是平稳性的充分条件，它要求任意两状态间的概率流量完全对称。满足此条件的链称为可逆链，其时间反转过程与原过程统计等价。细致平衡方程πᵢ·pᵢⱼ=πⱼ·pⱼᵢ对所有i,j∈S成立，意味着稳态下每对状态之间的"流入=流出"达到微观平衡πᵢpᵢⱼ=πⱼpⱼᵢ充分性证明对细致平衡方程关于i求和得Σᵢπᵢpᵢⱼ=πⱼ·Σᵢpⱼᵢ=πⱼ，即πP=π，细致平衡自动蕴含全局平衡πP=π可逆性定理若不可约DTMC满足细致平衡，则时间反转过程{Xₙ,Xₙ₋₁,...,X₀}与原过程具有相同转移概率矩阵统计不可区分应用价值Metropolis-Hastings算法通过构造满足细致平衡的转移矩阵采样目标分布π，是贝叶斯计算与统计物理的基石M-H算法MARKOVCHAIN平稳分布计算实例通过三状态天气模型的平稳分布计算，展示了从建立方程组πP=π到求解归一化的完整流程。计算结果表明长期来看晴天和雨天的占比相近（约35%），多云天气占比约30%，与直觉和转移概率结构一致。三状态天气模型的平稳分布求解求解步骤具体内容

01

列方程

π₁=0.7π₁+0.3π₂+0.1π₃π₂=0.2π₁+0.4π₂+0.3π₃π₃=0.1π₁+0.3π₂+0.6π₃

02

化简

0.3π₁−0.3π₂−0.1π₃=0−0.2π₁+0.6π₂−0.3π₃=0π₁+π₂+π₃=1

03

求解

π₁≈0.352，π₂≈0.296，π₃≈0.352三个分量之和为1，归一化条件满足

04

验证

代入πP验证πP=π成立，且各分量均大于0，平稳分布存在且唯一三状态天气模型不可约且有限，平稳分布必然存在唯一，长期来看晴天和雨天占比约35%，多云约30%ERGODICTHEOREM遍历定理：DTMC的核心极限定理遍历定理是DTMC理论的基石：不可约+非周期+正常返的链，其n步转移概率pᵢⱼ⁽ⁿ⁾收敛到平稳分布πⱼ=1/μⱼ，且极限与初始状态无关。这一定理保证了长期统计行为的确定性，是蒙特卡洛模拟和稳态分析的理论依据。01定理陈述设DTMC不可约、非周期、正常返，则lim(n→∞)pᵢⱼ⁽ⁿ⁾=πⱼ=1/μⱼ>0，极限存在、为正、且与初始状态i无关02与初始状态无关无论系统从哪个状态出发，经足够长时间后处于状态j的概率都趋向πⱼ——"初始条件的记忆被完全洗掉"03时间平均等于空间平均lim(N→∞)(1/N)Σₙ₌₁ᴺI{Xₙ=j}=πⱼ(a.s.)，长时间中处于状态j的时间比例等于平稳概率04收敛速度收敛速率由转移矩阵P的第二大特征值λ₂决定，|λ₂|越小收敛越快，谱间隙1−|λ₂|是衡量mixing速度的关键指标ConvergenceTheory周期性对极限行为的影响周期性破坏了pᵢⱼ⁽ⁿ⁾的逐点收敛性，但不影响Cesàro平均的收敛。通过"懒惰化"等技巧可将周期链转化为非周期链，恢复逐点收敛性。01周期链的振荡现象当d(i)>1时，pᵢᵢ⁽ⁿ⁾在n不是d的倍数时为零，极限不存在，概率分布在d个子集间循环振荡。d(i)>102Cesàro收敛定理即使链是周期的，只要不可约且正常返，算术平均(1/n)Σpᵢⱼ⁽ᵏ⁾→πⱼ=1/μⱼ仍然成立。πⱼ=1/μⱼ03懒惰化技巧构造新链P'=(I+P)/2，以1/2概率停留、1/2概率转移，新链必然非周期且保持原平稳分布。P'=(I+P)/204实际影响：PageRankGoogle引入阻尼因子d=0.85本质上是懒惰化，确保转移矩阵非周期且不可约，保证排序向量收敛。d=0.85MARKOVCHAIN·ERGODICTHEORY耦合法：极限定理的优雅证明耦合法通过构造两个独立DTMC副本并分析其首次相遇时间T来证明遍历定理，初始分布差异在相遇后被完全"遗忘"。01耦合构造：设{Xₙ}从X₀=i出发，{Yₙ}从平稳分布π出发且独立运行，定义首次相遇时间T=min{n≥0:Xₙ=Yₙ}T=min{n}02相遇后同步：定义新过程Zₙ，当n<T时Zₙ=Xₙ，当n≥T时Zₙ=Yₙ。由强马尔可夫性，{Zₙ}也是合法的DTMC且与{Xₙ}同分布强马尔可夫性03收敛证明：P(Xₙ≠Yₙ)≤P(T>n)→0，因此|P(Xₙ=j)−P(Yₙ=j)|→0，而P(Yₙ=j)=πⱼ，故P(Xₙ=j)→πⱼP→πⱼ04耦合时间界限：收敛速度取决于E[T]的大小，E[T]有限保证指数收敛，与谱间隙方法给出的收敛速率估计一致E[T]<∞CHAPTER04遍历性与首达时间从时间平均到首达概率，掌握DTMC的高级分析工具Ergodicity·Theorem遍历性的严格定义与遍历定理遍历性是不可约+非周期+正常返的综合性质，遍历定理保证了时间平均与空间平均的等价性，是MCMC方法的理论基石。01遍历链定义不可约+非周期+正常返的DTMC称为遍历链，是DTMC中性质最完备、应用最广泛的类型。02遍历定理对任意f使Σ|f(j)|πⱼ<∞，时间均值(1/N)Σf(Xₙ)几乎必然收敛于空间均值Σπⱼf(j)。03MCMC理论基础构造以π为平稳分布的遍历链并模拟长轨迹，用样本均值近似Eπ[f]，无需直接计算π。04Burn-in期处理实际MCMC中需丢弃前B步，待链接近平稳后再采样，(1/(N−B))Σf(Xₙ)是更稳健的估计量。MarkovChain·FirstPassage首达时间的分布与矩方程首达时间Tⱼ的矩可通过线性方程组递推计算：mᵢⱼ=1+Σₖ≠ⱼpᵢₖmₖⱼ。这一方程将条件期望分解为一步转移的贡献，将概率问题转化为线性代数问题。01平均首达时间方程mᵢⱼ=E[Tⱼ|X₀=i]=1+Σₖ≠ⱼpᵢₖ·mₖⱼ（i≠j），直观含义是"走一步再看从哪继续"的全期望公式应用mᵢⱼ=1+Σpₖmₖⱼ02平均首返时间μᵢ=mᵢᵢ=1+Σₖ≠ᵢpᵢₖ·mₖᵢ，与平稳分布的关系为πᵢ=1/μᵢ，建立了首返时间与稳态概率的桥梁πᵢ=1/μᵢ03高阶矩计算二阶矩mᵢⱼ⁽²⁾满足类似递推方程，可逐步求得首达时间的方差，完整刻画分布形态特征Var[Tⱼ]04赌徒破产应用mₖ₀（从资金k到破产的平均时间）满足mₖ₀=1+p·mₖ₊₁,₀+q·mₖ₋₁,₀，可用差分方程求解Gambler'sRuinAbsorbingChains·核心方法吸收链的吸收概率与基本矩阵吸收链的分析围绕基本矩阵N=(I-Q)⁻¹展开：Nᵢⱼ表示吸收前访问瞬过态j的期望次数，NR给出吸收概率，N的行和给出平均吸收时间。标准形分块将状态重排使吸收态在后，P=[[Q,R],[0,I]]。Q为t×t瞬过态间转移矩阵，R为t×r瞬过态到吸收态转移矩阵。P=[[Q,R],[0,I]]基本矩阵N=(I-Q)⁻¹=I+Q+Q²+…，Nᵢⱼ表示从瞬过态i出发在被吸收前访问瞬过态j的期望次数，级数收敛因Qⁿ→0。N=(I−Q)⁻¹吸收概率B=NR，Bᵢₖ表示从瞬过态i出发最终被吸收态k吸收的概率，每行之和为1——有限吸收链必然被吸收。B=N·R平均吸收时间t=N·1（N的行和向量），tᵢ表示从瞬过态i出发到被吸收的平均步数，在产品寿命分析和博弈论中有直接应用。t=N·1GeneratingFunctionMethod首达时间的母函数方法概率母函数将首达时间的离散分布编码为解析函数，通过Fᵢᵢ(s)与Pᵢᵢ(s)的代数关系Pᵢᵢ(s)=1/(1−Fᵢᵢ(s))，可以在不逐项计算概率的情况下获得首达时间的全部信息。母函数在s=1处的值和导数分别给出首返概率和平均首返时间。01母函数定义Fᵢⱼ(s)=Σₙ₌₁^∞fᵢⱼ⁽ⁿ⁾sⁿ（|s|≤1），将首达时间分布编码为s的幂级数，是离散Laplace变换的一种形式Fᵢⱼ(s)02核心关系式Pᵢᵢ(s)=1+Fᵢᵢ(s)·Pᵢᵢ(s)，解出Pᵢᵢ(s)=1/(1−Fᵢᵢ(s))，将转移概率母函数与首返概率母函数联系起来P=1/(1−F)03常返性判据令s→1⁻，Fᵢᵢ(1)=fᵢᵢ，Pᵢᵢ(1)=Σpᵢᵢ⁽ⁿ⁾，故fᵢᵢ=1⟺Pᵢᵢ(1)=∞，与级数判据一致但提供了更系统的分析框架fᵢᵢ=104矩的提取μᵢ=F′ᵢᵢ(1)，Var(Tᵢ)=F″ᵢᵢ(1)+F′ᵢᵢ(1)−[F′ᵢᵢ(1)]²，通过对母函数求导可系统地获得首达时间的各阶矩F′ᵢᵢ(1)DTMC·判定方法不可约性的判定方法不可约性等价于转移图的强连通性，正则链（存在n使Pⁿ>0）是不可约+非周期的充分条件，决定了平稳分布唯一性和极限定理是否适用。图论方法01构造转移图邻接矩阵A（aᵢⱼ=1当pᵢⱼ>0），用Tarjan或BFS/DFS检查强连通分量数量，仅一个则不可约02可达性矩阵R=(I+A)ᵐ⁻¹，若R的所有元素为正，则任意状态对互通，链不可约GraphTheory代数方法01正则链判定：若存在n使Pⁿ的所有元素严格为正（pᵢⱼ⁽ⁿ⁾>0），则链不可约且非周期02Perron-Frobenius定理：不可约非负矩阵P的最大特征值为1，对应唯一正左特征向量即平稳分布Algebra实际应用检验01PageRank模型中，网页链接图通常非强连通（存在悬挂节点），需通过添加随机跳转使其不可约02编程实践中，可计算(I+P)ᵐ⁻¹或用稀疏矩阵连通分量算法快速判定，时间复杂度为O(m²)ApplicationReversibilityCriteria可逆链的判定与Kolmogorov循环条件Kolmogorov循环条件是可逆性的充要条件：对任意闭环路径，正向概率积等于反向概率积。生灭过程因转移图的树状结构天然满足此条件，是最常见的可逆链类型。01Kolmogorov循环条件：DTMC可逆⟺对任意循环i₀→i₁→⋯→iₙ=i₀，沿任何闭环的正向概率积等于反向概率积充要条件02生灭过程的可逆性：状态空间{0,1,2,…}上仅允许相邻状态转移（pᵢ,ᵢ₊₁=pᵢ，pᵢ,ᵢ₋₁=qᵢ），转移图无长度>2的循环，天然满足可逆条件树状结构03生灭过程平稳分布：由细致平衡πᵢpᵢ=πᵢ₊₁qᵢ₊₁递推得πₙ=π₀·∏(pₖ/qₖ₊₁)，归一化后得完整分布，形式简洁优美细致平衡04物理意义：在统计力学中，可逆性对应微观可逆性原理——系统在平衡态下任何微观过程与其逆过程发生的频率相同平衡态CASESTUDY·DTMC应用案例：PageRank算法中的DTMC性质PageRank将互联网建模为DTMC并用平稳分布衡量网页重要性。原始链接图的可约性和周期性通过阻尼因子d=0.85的随机跳转修正：修正后的转移矩阵G=dP+(1-d)E/n严格为正，保证不可约+非周期+正常返，平稳分布（PageRank向量）存