Markov Chains

accessibility and communicating classes

Look at the network of states and ask a simple geography question: starting here, which other states can the chain ever reach? And which states can reach you back? Sorting states by who can get to whom is the first thing you do to understand a chain's structure. It is like grouping rooms of a building into clusters you can freely wander within.

State j is accessible from state i (written i to j) if there is some number of steps n with P^(n)(i, j) greater than 0 — that is, some path of positive probability leads from i to j. Two states i and j communicate if each is accessible from the other (i to j AND j to i). Communication is an equivalence relation: every state communicates with itself, communication is symmetric, and it chains together transitively. So it partitions the state space into communicating classes — clusters within which the chain can roam back and forth, freely reaching every member from every member.

These classes reveal the skeleton of the dynamics. A class is closed if once you enter it you can never leave (no arrow escapes to another class); otherwise it is open or transient. The chain may drift through transient classes for a while, but eventually it gets trapped in a closed class and lives there forever. Identifying the classes and which are closed tells you, at a glance, where the long-run action will be.

States A, B, C with arrows A to B, B to A, B to C, C to C. Then A and B communicate (you can go A to B and B to A), forming one class {A, B}; C forms its own class {C}. {C} is closed (no arrow leaves C) and absorbing-like; {A, B} is open because B leaks to C. Long run: the chain ends up at C.

Communicating classes split the states into freely-mixing clusters; closed classes are where the chain ends up.

Accessibility can be one-way: i may reach j without j reaching i, so they do not communicate. Communication requires the round trip to be possible (both directions of positive-probability paths).

Also called
communication classesaccessibility可達互通通信類