msmtools.analysis.is_connected

msmtools.analysis.is_connected(T, directed=True)

Check connectivity of the given matrix.

Parameters:

• T ((M, M) ndarray or scipy.sparse matrix) – Matrix to check
• directed (bool (optional)) – If True respect direction of transitions, if False do not distinguish between forward and backward transitions

Returns:

is_connected – True, if T is connected, False otherwise

Return type:

bool

Notes

A transition matrix \(T=(t_{ij})\) is connected if for any pair of states \((i, j)\) one can reach state \(j\) from state \(i\) in a finite number of steps.

In more precise terms: For any pair of states \((i, j)\) there exists a number \(N=N(i, j)\), so that the probability of going from state \(i\) to state \(j\) in \(N\) steps is positive, \(\mathbb{P}(X_{N}=j|X_{0}=i)>0\).

A transition matrix with this property is also called irreducible.

Viewing the transition matrix as the adjency matrix of a (directed) graph the transition matrix is irreducible if and only if the corresponding graph has a single connected component. Connectivity of a graph can be efficiently checked using Tarjan’s algorithm.

References

[1]	Hoel, P G and S C Port and C J Stone. 1972. Introduction to Stochastic Processes.

[2]	Tarjan, R E. 1972. Depth-first search and linear graph algorithms. SIAM Journal on Computing 1 (2): 146-160.

Examples

>>> import numpy as np
>>> from msmtools.analysis import is_connected

>>> A = np.array([[0.9, 0.1, 0.0], [0.5, 0.0, 0.5], [0.0, 0.0, 1.0]])
>>> is_connected(A)
False

>>> T = np.array([[0.9, 0.1, 0.0], [0.5, 0.0, 0.5], [0.0, 0.1, 0.9]])
>>> is_connected(T)
True