吸收马尔可夫链中最大可能路径数及从瞬态出发路径数问询

嘿，这两个问题得先从吸收马尔可夫链的核心结构说起——它们由瞬态状态（可以转移到其他状态）和吸收状态（一旦进入就再也出不来）组成，我们默认讨论的路径是「有限长度、最终终止于吸收态的状态序列」，接下来分情况拆解：

答案取决于链的结构是否包含瞬态循环：

• 如果链里有至少一个由瞬态构成的循环（比如瞬态A→B→A），且这个循环能通向吸收态，那么路径数是无限的。举个例子：瞬态A可以直接到吸收态C，也可以先绕A→B→A循环1次再到C，绕2次再到C……每多一次循环就是一条新路径，数量没有上限。
• 如果链中的瞬态构成一个有向无环图（DAG，没有任何循环），那么路径数是有限的。要达到最大路径数，需要让每个瞬态都能直接或间接通向所有吸收态，且瞬态之间是完全有向连接（每个瞬态都能指向所有其他瞬态和吸收态）。假设总共有 ( t ) 个瞬态、( a ) 个吸收态：
  • 吸收态自身的路径：每个吸收态只有1条（停留在自身），共 ( a ) 条；
  • 从每个瞬态出发到吸收态的路径数：单个瞬态的路径包括直接到吸收态（( a ) 条）、经过1个其他瞬态再到吸收态（( (t-1)×a ) 条）、经过2个不同瞬态再到吸收态（( (t-1)(t-2)×a ) 条）……直到经过所有 ( t-1 ) 个瞬态再到吸收态（( (t-1)!×a ) 条）；
  • 总路径数就是 ( a + t×a×\sum_{k=0}^{t-1} P(t-1,k) )（其中 ( P(n,k) ) 是n个元素取k个的排列数，( P(n,0)=1 )）。

同样分两种情况：

• 如果这个瞬态属于某个瞬态循环，且循环能通向吸收态，那么路径数是无限的。比如瞬态A在循环A→B→A中，且A能到吸收态C，那么可以构造出无限多条不同路径：A→C、A→B→A→C、A→B→A→B→A→C……以此类推。
• 如果这个瞬态所在的瞬态子图是DAG（无循环），那么路径数是有限的。最大值出现在这个瞬态能通向所有其他瞬态和吸收态，且每个后续瞬态也能通向所有剩余瞬态和吸收态。假设总共有 ( t ) 个瞬态、( a ) 个吸收态，从该瞬态出发的路径数为 ( a×\sum_{k=0}^{t-1} P(t-1,k) )——简单说就是把所有“经过0个、1个……直到t-1个其他瞬态，最终到达吸收态”的路径数加起来，再乘以吸收态的数量。

内容的提问来源于stack exchange，提问作者Souvik