function is_connected

deeptime.markov.tools.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. [1].

Connectivity of a graph can be efficiently checked using Tarjan’s algorithm. [2].

References

[1]

Paul G Hoel, Sidney C Port, and Charles J Stone. Introduction to stochastic processes. Waveland Press, 1986.

[2]

Robert Tarjan. Depth-first search and linear graph algorithms. SIAM journal on computing, 1(2):146–160, 1972.

Examples

>>> import numpy as np
>>> from deeptime.markov.tools.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