A Markov chain is irreducible when you can go from any state to any other state.
In general directed graphs, this is called strongly connected. A set of vertices that is strongly connected is a strongly connected component. A directed graph can be decomposed into what’s called a SCC metagraph, which is a graph where each vertex represents a strongly connected component in the original graph.
This is why a Markov chain that doesn’t satisfy the above property is called reducible.
If a Markov chain is finite and irreducible, then there exists a unique stationary distribution.
A Markov chain is periodic with period d if the greatest common divisor of all tour lengths is d.
If a Markov chain is finite, irreducible, and aperiodic, then the distribution of Xn approaches the stationary distribution as n increases.
Absorption Probabilities
What’s the probability of reaching state A before state B?
Define α(i) as the probability of reaching A before B if you start at i. Then α(i)=∑jPi,jα(j).
This can be extended to deal with sets of states A and B.
Hitting Times
What’s the expected number of transitions required to reach state A?
Define β(i) as the expected number of transitions required to reach A if you start at i. Then β(i)=∑jPi,j(1+β(j))=1+∑jPi,jβ(j).
This can be extended to deal with a set of states A.
Markov Chains
Absorption Probabilities
Hitting Times