如何基于马尔可夫链底层图高效判断其是否为非周期链？

概率论里的马尔可夫链对应着一张底层图——每个顶点代表链的状态，边则表示状态之间的可能转移。本文讨论的是离散时间马尔可夫链，状态转移发生在自然数对应的离散时间点上。这类链里有一部分是非周期链：当时间步n足够大时，链可以处于任意状态。

• 周期链示例：只包含状态1和2的链，会被迫在两个状态间来回切换。如果从状态1出发，只有在偶数时间步能回到状态1，奇数时间步只能处于状态2。
  

反过来，只要链里存在带自环的状态，那它一定是非周期链。另外也存在没有自环的非周期链，示例如下：

因此我们需要一种算法，给定马尔可夫链底层图的邻接表或邻接矩阵，就能高效判断该链是否为非周期链。目前已有方法是通过邻接矩阵多次自乘观察状态切换，但我们希望仅基于图的结构来实现判断。

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