Irreducible Chain

TL;DR

Every state can reach every other state using a finite sequence of transitions.
It is a property of Markov chains that ensures full connectivity among states.
Useful when modeling systems where any configuration can eventually lead to any other.

Definition

An irreducible Markov chain is a type of Markov chain in which it is possible to get from any state to any other state in a finite number of steps. A Markov chain represents transitions between a set of states.

Explanation

An irreducible chain describes a set of states and allowed transitions such that for every pair of states, there exists some finite-length sequence of transitions leading from the first to the second. This connectivity property means no state is isolated from the rest of the system and underlies why irreducible chains are suitable for modeling systems where movement between states is important.

Examples

Chess

A game of chess can be viewed as an irreducible Markov chain. The states include positions such as “white’s turn,” “black’s turn,” or “game over.” It is possible to move from any of these states to any other state in a finite number of steps. For example, if the game is in the state “white’s turn,” it is possible to move to the state “black’s turn” by making a move with one of white’s pieces.

Network of roads connecting different cities

Consider a network of roads where states are different cities. It is possible to move from any city to any other city in a finite number of steps by following the roads. For example, if the current state is the city of San Francisco, it is possible to move to the city of Los Angeles by following a series of roads that connect the two cities.

Use cases

The connectivity property of an irreducible Markov chain makes it a useful tool for modeling a wide variety of systems, including games, networks, and other types of systems where transitions between states are important.

Markov chain