动机
有限马尔可夫(Markov)模型可以用不同方式完成:任务可能成功终止、永久失败,或进入一组永远互相切换的闭模式。前两者是吸收状态,后者是吸收目的类,却不是单一吸收状态。若太早把它们混为一谈,计算会回答错误的概率问题。
正确次序是先看结构,再作代数。找出互通类及其中的闭类,然后分开仍可离开的状态与最终到达的目的地。所得区块矩阵使占用次数、完成时间及目的概率,成为使用同一个逆矩阵的不同计算。
预备知识是有限随机矩阵、条件概率及前文已证的击中时刻马尔可夫性。以下会证明逆为何存在及其分量的意义,而非以数值求逆代替理由。
定义
定义 2.7.1
(互通类与分块形式)
若某有限步转移概率正,称一状态可达另一状态。互相可达把有限空间分成互通类;没有转移离开的类称闭类。列出闭不可约类 ,并集为 ,其余状态组成 。重排次序得
描述 内转移, 进入 的个别状态, 是 内随机矩阵。若每个闭类都是单一吸收状态,;闭目的类若仍切换, 一般不是单位矩阵。
定义 2.7.2
(离开时间与类指示矩阵)
令 。由 开始时,计算时刻 的所有暂态到访,不包括时刻 的入口到访。若闭状态 属于 ,令 ,否则为零。因此 是一步进入目的类的概率, 则保留精确入口状态。 空是已在闭类的平凡情形,以下逆矩阵计算针对非空 。
定理/命题
定理 2.7.3
(几何区段界保证离开)
每个 中状态都几乎必然到达 ,且 各矩有限。更确切地,存在有限 及 ,使
因此 ,且
是分量非负、数值有限的矩阵。
定理 2.7.4
(占用、目的与所需时间)
对 ,基本矩阵满足
精确入口矩阵为 ,目的类矩阵为 ,两者每行都是和为一的概率。 的均值及二阶矩列为
若每次暂态到访支付代价列 ,终端类报酬列为 ,期望总值为 。
概念视角分析
把目的地概率看成边值问题
固定一个类 ,对 令 ,对 令 。首步条件化使 在每个暂态状态上调和,即 ,边界值在 上为一、在其他闭类上为零。在 上这就是 ,其中 是第 个单位列向量; 可逆,使 成为唯一解。因此目的地概率是边界数据唯一的调和延拓;平均持续时间则求解同一问题,只是加上源项 ,并取零边界值。
证明思路
求逆以前先找最终目的地
证明
(由类图得到一致的离开路径)
互通类的有向图不能在不同类之间有有向循环,否则循环中的类互相可达,应属同一类。有限有向无环图的每个顶点,都有路径到某个终端顶点,终端类正是闭类。因此每个暂态候选都有正概率有限路径通往 。
从 各状态选一条此类路径。有限性提供共同长度上界 及共同正概率下界 。给定仍在 外的任意历史,往后 步内进入 的概率至少 ,反复条件化便得区段尾界。这也证明 各状态暂态:在 外的期望总时间有限,个别状态的期望到访次数因而有限;不是单凭它不吸收便称暂态。
的行和是至第 步仍在 外的概率,尾界因此证矩阵级数收敛。有限部分和乘 裂项相消成 ,余项趋零,证左右逆均成立,无须先假设谱计算。同一几何界给某个正参数的指数矩有限,故普通矩全部有限。
证明透视
有限性为何给出几何离开界
有限性用了两次。它令类图成为有限无环图,因此每个类都有路径到达终端类,即闭类;它也令同一个长度 和同一个概率 适用于 中每个起点。关键一步是在每段 步之后重新应用路径下界:给定任何仍在 外的历史,链正处于 的某个状态,由该处沿所选路径成功的概率至少为 。把这些条件失败上界相乘便得 。论证以代数而非谱方法闭合: 的行和是生存概率,几何尾界使 收敛,裂项恒等式再确认此和为 。
没有有限性,一致常数可以失效。在 上,令状态 以概率 进入 ,否则移到 。每个状态都有一步到达 的路径,但由状态 出发,链永远留在 的概率是 。
解释逆及其乘积
证明
(把逆矩阵解读为次数、入口与时长)
是尚未进入 且第 步在 的概率。 闭,进入后不能回来。对非负指示变量求和并用 Tonelli,得到 的占用意义。
在第 步进入闭状态 的概率是 。各入口时刻互斥,除零概率外穷尽路径,加总得 。再按类合并入口状态得 。代数检查是 ,故 。非负性与行和共同验证真正概率,而不只是线性方程的解。
从暂态开始,无论下一步到暂态还是目的地,都先经过一步。首步条件化得 ;暂态续程的一加剩余时间平方,给 。乘 ,用 即得矩公式。有限性已先证明,所以二阶矩方程合法。代价及终端报酬则满足 ,解为 ,不假设相邻到访独立。
入口不是目的类内的平衡
完整有限时间转移矩阵为
各项选择首次进入的时间,再于闭类演化,可归纳或按互斥路径证明。相比之下, 只记录首次进入哪里,一般并非最终状态的极限分布。
若每个闭不可约类皆非周期,前文已证的有限链收敛定理可用于各类。给定有限入口时刻与状态,未来收敛至该类平稳分布。把晚于 入口的尾部界为 ,先对截至 的有限多个入口时刻令观察时间增大,再令 增大,便证极限混合权重为 。闭类有周期时,入口概率仍正确,但普通收敛须另查,不能由 推出。
截止时间与给定目的地
截止时间需保留已完成及未完成之别。截至第 步的目的类概率矩阵为
所以 :先在目的地外生存 步,再最终到指定类。对类求和得 ,正是未完成概率。这能精确检查截止计算,无须模拟。若把已完成概率除以其行和,则改为给定截止前完成的条件实验。
时间与目的亦可同时保留。首步条件化给矩阵母函数
几何离开界保证在一附近可微分。逆的导数给 ,用 得 。若 ,给定该目的类的平均时间就是 ;零概率目的地没有此条件均值。这里先求时间与目的地的联合量,并非直接把它当成条件母函数;要条件化,必须再除以正的目的概率。稀有目的地与常见目的地可能需时不同,无条件均值并不能回答条件问题。
以下首例由 出发,给定目的 的均值三步,给定 为四步;加权平均 ,符合无条件均值。条件化改变路径分布,不能不加目的权重就沿用原链的普通均值公式。
例题详解
例题 2.7.5
(两暂态、两目的的完整计算)
状态次序 ,后两者吸收,取
各行和一,各目的类只有一状态,所以 ,此例类矩阵为 。逆及入口概率为
由 开始,完成前期望到访 共 次,终到 的概率 。均值列 ,再乘得 ,方差为 。检查 、目的概率各行和一、以及 ;三项验证不同叙述,而非重复同一算术。
下面的交互图对第一个例题、赌徒破产及一条把闭类误标为暂态的链,精确计算 N = (I − Q)⁻¹、B = NR 以及持续时间的均值与方差,并以另一条恒等式逐项核对。
基本矩阵、目的概率与持续时间
选一个有限链,其暂态区块为 Q,入口区块为 R。本图以有理数精确求 I − Q 的逆;N 读作期望占用次数,B = NR 读作到达各目的的概率,h = N1 为平均持续时间,s = 2Nh − h 为二阶矩,Var = s − h² 为方差。每项读数再由另一条独立恒等式核对。
| 状态 | 角色 | Q(T 内) | R(进入目的) / D(目的内) | ||
|---|---|---|---|---|---|
| u | v | a1 | a2 | ||
| u | 暂态 | 1/2 | 1/4 | 1/4 | 0 |
| v | 暂态 | 1/4 | 1/4 | 1/4 | 1/4 |
| a1 | 目的 | 0 | 0 | 1 | 0 |
| a2 | 目的 | 0 | 0 | 0 | 1 |
| 起点 | u | v |
|---|---|---|
| u | 12/5 | 4/5 |
| v | 4/5 | 8/5 |
| 起点 | a1 | a2 |
|---|---|---|
| u | 4/5 | 1/5 |
| v | 3/5 | 2/5 |
| 起点 | h = N1 | s = 2Nh − h | Var = s − h² |
|---|---|---|---|
| u | 16/5 | 16 | 144/25 |
| v | 12/5 | 52/5 | 116/25 |
部分和 S_K = I + Q + … + Q^K(四舍五入至 8 位小数), K = 12
| 起点 | u | v |
|---|---|---|
| u | 2.39152843 | 0.79476428 |
| v | 0.79476428 | 1.59676415 |
N − S_K 的最大分量 = 0.00847157 (四舍五入至 8 位小数)
独立核对
- (I − Q)N = I
- 成立
- B 各行和为 1
- 成立
- h = 1 + Qh
- 成立
- s = 1 + 2Qh + Qs
- 成立
- N − S_K = Q^(K+1) N
- 成立
- det(I − Q)
- 5/16
- I − Q 可逆
- 成立
- 全部核对成立
- 成立
- N − S_K 的最大分量
- 0.00847157
- 由第一个状态出发的期望占用
- 12/5, 4/5
工作例子, K = 12. I − Q 可逆,N 为有限矩阵;上列每条恒等式都精确成立。
读数为何正确
(Q^n)_ij 是时刻 n 在 j 而尚未进入目的的概率,对 n 求和即得期望占用次数;几何退出界保证级数有限,且等于 (I − Q)⁻¹。
对第一步取条件,得 h = 1 + Qh 与 s = 1 + 2Qh + Qs,因此 h = N1、s = 2Nh − h;本图把两条方程当作恒等式核对,而不是重复同一个乘法。
有限和乘以 I − Q 会望远相消为 I − Q^(K+1),故 N − S_K = Q^(K+1) N。其最大分量即所示差距,只有当 T 的每个状态都是暂态时才趋于 0。
若 T 含闭类,Q 在该类上的各行和为 1,I − Q 因而奇异。修正须看结构:把闭类改为另一个目的。
各链有限,分量为精确有理数。赌徒破产取界 0 与 n,n 介于 3 至 6;截断 K 由 0 至 60。小数经四舍五入,其余数值皆精确。目的类的周期性不在本图范围。
例题 2.7.6
(闭类仍可移动)
暂态 以概率 留下, 到 , 到吸收 ;另一闭类内 确定性交替。则 ,到 的精确入口概率为 ,两目的类概率为 ,平均入口时间二。进入 后并不留在 ,由 开始的分布永远交替。目的类计算未承诺 吸收,也未承诺类内普通收敛。
例题 2.7.7
(错把陷阱留在暂态区块)
以概率 留下,否则到吸收 ; 永留自身。若错把两者放入暂态区块,, 奇异,由 的拟定完成时间无限。修正必须看结构: 是另一闭目的类。只留 暂态, 合法,且由 到 的概率为一。任意一组未指定目的的状态,不自动全是暂态。
常见错误
常见错误
(漏计初始暂态到访)
基本矩阵包括初始暂态到访。省略会把 变成 ,破坏均值与代价;终端到访属目的地,则不计入暂态占用。状态次序及行分布约定亦决定乘法方向。
常见错误
(先求逆再分类)
先求逆、后查互通结构,是把次序颠倒了。数值工具可能报奇异,但真正理由是仍包含闭类。
常见错误
(把截止前概率重新归一化)
目的概率回答最终发生什么;截止前概率则用有限和 ,须保留未完成质量。把已完成的概率除以其行和,回答的是“给定已在截止前完成”这个不同问题。
总结
有限类图找出目的地并提供共同几何离开界;暂态矩阵幂的收敛产生基本矩阵。占用、时间、代价及多目的入口,各由不同乘积解释得到,闭类内运动仍须分开处理。
练习
快速检查
(一个暂态以概率 留下, 到 , 到 。求 、目的概率、离开时间均值及方差。)
只有一个暂态时, 是标量。
解答 · 答案
,乘出口概率得 。均值 ,二阶矩 ,故方差 。
快速检查
(首例每次到 的代价为 ,终到 的额外代价为 。求两初态的期望总值。)
用第一个例子的矩阵代入 。
解答 · 答案
暂态代价 ,终端代价 ,合共 。每次转移前计暂态代价,入口后只计一次终端代价。
快速检查
(第二例中,分清精确入口分布、目的类分布及由 开始的单时刻分布,哪一个不收敛?)
分清链从何处进入,以及进入后如何移动。
解答
由 到 的精确入口为 ,到 的类入口为 。由 的单时刻分布在 点质量间交替,没有极限;入口概率并非此时间演化的叙述。
快速检查
(对暂态 证明 ,并求首例由 在完成前访问 的概率。)
在首次到访 时使用击中时刻马尔可夫性。
解答
不击中 时占用为零;首次击中后,由击中时刻马尔可夫性,包含首次在内的期望后续占用是 。故 。因 可相除,所求为 。