Answers · The mathematics underneath
What's the difference between a state the chain keeps returning to and one it eventually leaves forever?
In shortA state the chain keeps returning to is in a closed group it cannot leave; any other state is left forever after finitely many visits.
On a finite chain, a state is recurrent if, starting from it, the probability of ever returning is 1; otherwise it is transient. For a finite chain this is exactly the closed communicating class test: a state in a closed class is visited infinitely often, and a state outside every closed class is left forever after finitely many visits.
The return probability is the test
Take the article A in the five-situation chain. It has a self-loop of chance 0.5, an arrow to pricing P of chance 0.3, and an arrow to gone G of chance 0.2. From P the only arrow back to A has chance 0.4; the other arrows from P go to bought B with chance 0.1 and to G with chance 0.5, and neither ever returns.
The 0.5 term is the immediate return. The 0.12 term is the two-hop return A to P to A. The route A to G has chance 0.2 and never comes back, so it contributes nothing. Thus \(q=f_{AA}=0.62\), not 1. The chance of never returning is \(1-q=0.38\). Each return leaves the chain in exactly the same situation, so the chance of at least n returns is \(q^n=0.62^n\). The chance of at least ten returns is \(0.62^{10}\approx 0.0084\), and as n grows this tends to zero. The number of returns is therefore finite with probability 1. Its expectation is \(q/(1-q)=0.62/0.38\approx 1.63\) returns, so counting the first visit the expected number of visits is about 2.63.
Reachability is possibility, not certainty. A reaches itself through the self-loop, and it also reaches B and G, but those arrows are exits from the set {A, P}. The self-loop says a return can happen; it does not say a return must happen. A positive chance of leaving before returning, repeated indefinitely, is enough to make the exit certain in the long run. That is why the table of reachable pairs cannot be read as a table of returns.
Closed classes
Bought B has a single arrow, B to B with chance 1. Hence \(f_{BB}=1\) and \(P^n(B,B)=1^n=1\) for every n: B is visited at every hop, infinitely often. Gone G is the same. These singleton sets are closed because no arrow leaves them. They are closed communicating classes. Starting in either one, the chain can never get out, so the question of leaving forever does not arise. Starting in the middle pair, the chain may visit A or P several times, but with probability 1 it eventually enters B or G and then stays there.
If there are two or more closed classes, the chain has more than one possible destination. B and G are both closed, so the long run distribution is not a single vector until the starting state is fixed: a reader starting in B stays in B, a reader starting in G stays in G, and a reader starting in A or P reaches one of them with the chances set by the arrows. Recurrence is still a state by state property; it is the long run distribution that needs the start.
| Class | Closed? | Return from a state in it | Long run |
|---|---|---|---|
| {F} | no | 0 from F | left after one hop |
| {A,P} | no | 0.62 from A | visited finitely often, then left |
| {B} | yes | 1 from B | visited forever |
| {G} | yes | 1 from G | visited forever |
Where the finite assumption matters
All of that uses finiteness twice: it makes a positive chance of leaving into an eventual certainty, and it makes a closed class recurrent. On an infinite state space a closed communicating class can still be transient; a random walk on the whole numbers with a drift away from the origin is the standard warning. Then belonging to a closed class is not enough, and return probabilities or another argument have to be checked directly.
Returning forever is not settling
Recurrence answers whether the chain comes back, not whether its distribution settles. Two states with a rule that always moves to the other one are both recurrent: each is visited infinitely often. But the chance of being in the first state after k hops is 1 when k is even and 0 when k is odd. That is a period of 2. Adding a self-loop of any positive chance, however small, allows returns after odd and even numbers of hops and removes the oscillation. Thus a recurrent state can fail to have a limiting probability, and on a finite chain the only two ways the long run can fail to exist are more than one closed class, or a cycle like this.
Worth keeping
- On a finite chain, a state is visited infinitely often exactly when it lies in a closed communicating class.
- Being reachable from a state is only a possibility; recurrence requires the return to happen with certainty.
- A chain can return to every state forever and still fail to settle if its returns are locked to a cycle.
Where this goes next
This question is one step of Markov Chains, a course that works through its subject from the beginning. The page that teaches this part of it is What Is Reachable, and What Traps You, and it reads the whole way through whether or not you have an account.
What an account changes is the practice: problems standing under every idea, marked with a reason rather than a tick, in a copy of the course that is yours.
Read that pageThe whole courseOther questions people ask about this
- How do you build a random walk whose long-run distribution is a distribution you choose?Propose a symmetric random move; accept moves to heavier target weight outright and moves to lighter weight with probability equal to the weight ratio, then run the chain.
- Why does a Markov chain eventually forget which state it started in?A finite Markov chain forgets its starting point when it has one closed class and no cycle, because two runs from different starts share chance that the rule cannot separate again.
- What is the difference between variance and standard deviation?They measure the same spread: variance is the average squared distance from the mean, standard deviation is its square root, so you report the standard deviation and calculate with the variance.
- How do you make a vague claim precise enough to tell whether it's true?Fix what is being talked about, what is asserted, which cases are covered and the cut-off, then name an observation that would prove it false.
- How do you find the parabola that best fits a function near a point?Match the function's height, slope and bending at the chosen point; those three conditions single out exactly one parabola.
- Why does a test for a rare disease give so many false positives if the test is accurate?A positive result means the test fired, not that you are likely to be ill; when the disease is rare, healthy people vastly outnumber ill ones, so a small false-alarm rate on them swamps the few true cases.