是否有衡量马尔可夫链允许状态之间移动的程度?

机器算法验证 马尔科夫过程
2022-04-03 20:23:08

定义

A=(.5.5.5.5),B=(.99.01.01.99),C=(.01.99.99.01)

以马尔可夫链为例,显然更允许其状态之间的移动,而更允许其状态之间的移动。ABCA

在马尔可夫链的空间上是否有某种度量来衡量它们允许在状态之间移动的程度?某种拥塞或可访问性统计信息?

编辑:我知道混合率,但我想知道一个也适用于吸收马尔可夫链的统计数据。

2个回答

也许马尔可夫链的电导是正确的概念。是具有平稳分布的转移矩阵(在您的情况下,始终是均匀分布)。电导_P[0,1]n×nππP

Φ(P):=minS[n],π(S)12iS,jScπ(i)Pi,jπ(S).
例如,参见 James King 的“Conductance and Rapidly Mixing Markov Chains”。

您的示例产生Φ(A)=0.5Φ(B)=0.1Φ(C)=0.99

如果转移图是强连接的(即给定一个初始状态,任何其他状态都可以通过 p>0 到达,可能通过中间状态),那么随着时间趋于无穷大,在给定状态下找到系统的概率不取决于初始状态。也就是说,有机会在 i 步后找到处于状态 X 的系统,它收敛到某个常数,它只是转移矩阵的函数(Tobias 中的回答)。

pi(X)
p(X)
π

对于您的所有 3 个示例,此只是 (.5, .5) 因为两种状态的可能性相同。这是有道理的:但也但一般来说这不需要成立。并非所有州都必须具有同样的可能性。简单示例:π

(.5.5)(.5.5.5.5)=(.5.5)
(.5.5)(.9.1.1.9)=(.5.5)
(.5.50.25.5.250.5.5)
概率为 (.25, .5, .25)。您可以将其视为左<->中<->右三重状态,有 50% 的机会移动,但不是直接从左向右移动。由于您总是必须经过中间,因此很有可能。

现在,正如对问题的评论已经表明的那样,您可以使用此概率来衡量停留在每个不同状态的机会。

在您的简单示例中,相应的结果将是 0.5、0.99 和 0.1,这仅仅是因为保持相同状态的机会(对角线的值)在对角线上是相同的。对于非平凡矩阵,它将是对角线的加权平均值。

这意味着确切的非对角线值无关紧要。我相信这反映了问题的意图,也没有区分不同类型的状态转换。