Motivation
A finite irreducible chain always has a stationary probability distribution. The same sentence is false on a countably infinite state space. Probability mass can drift toward arbitrarily distant states, and an invariant sequence of weights may have infinite total mass. Even a chain that returns to its starting point with probability one can have infinite expected return time.
Infinite nearest-neighbor walks make these distinctions concrete. We will use finite boundary calculations already established in the earlier unit, then justify the limiting events. Return cycles will connect pathwise behavior with stationary balance. The calculation is useful precisely because it shows which finite-state conclusions need new hypotheses.
Definitions
Definition 7.1.1
(Hitting and return times)
Let be a time-homogeneous Markov chain on a countable state space , with transitions and specified initial state or distribution. Write when . For a state , define the hitting time and the positive return time . The infimum of the empty set is infinity.
Definition 7.1.2
(Recurrence, transience and stationary probability)
A state is recurrent if , and transient if this probability is smaller than one. A recurrent state is positive recurrent when , and null recurrent when that expectation is infinite. These definitions separate the probability of returning from the duration of a return. A stationary probability is a sequence with and . Nonnegative invariant weights that cannot be normalized are not stationary probabilities.
For the nearest-neighbor walk on , each step is with probability and with probability , independently of earlier steps. Spatial translation makes all states have the same return behavior. Countability permits sums over states; it does not make those sums finite.
Main results
Theorem 7.1.3
(Hitting a lower level on an infinite line)
For the nearest-neighbor walk started at an integer ,
If , then . In the fair case , the hitting probability is one but .
Theorem 7.1.4
(Return probability and expected number of visits)
For a countable Markov chain started at , let and , including the initial visit. Then
If , this expectation is and is finite almost surely. If , there are infinitely many visits almost surely and the expectation is infinite.
Theorem 7.1.5
(A finite mean return cycle constructs a stationary law)
Suppose , almost surely, and . Define
Then is a stationary probability and . This construction requires finite mean return, not merely eventual return with probability one.
We prove this direction directly below. The general converse and uniqueness theorem for irreducible countable chains is not proved here. In the reflected-walk family we will instead derive all stationary candidates and classify every parameter case explicitly.
Proof sketch or proof idea
Taking a limit of gambler's ruin events
Proof
(Limits of gambler's ruin events)
Fix . The finite interval calculation gives the probability of hitting zero before :
As increases, the events increase. Their union is exactly : a path hitting zero in finite time has a finite maximum before that hit, so a sufficiently large upper boundary was not reached first. Continuity of probability from below now justifies the limit. When it is ; when divide numerator and denominator by to get one; the fair formula also tends to one.
For the fair walk, the time has expectation . It never exceeds , so for every . Letting grow proves the infinite expectation, although hitting occurs almost surely.
For , put . Since the expected increment is and depends only on the first steps,
The stopped position is nonnegative. Thus , and monotone convergence gives . Now the stopped sum of increments has absolute sum at most , an integrable variable. Interchanging expectation and that sum is justified, yielding and the claimed exact mean. This avoids assuming in advance that an infinite stopping time has a finite expectation.
Repeated returns restart the same experiment
Proof
(Restarting at each return)
At each finite return to , the probability of one further return is again . This is the strong Markov property at a stopping time. In discrete time it follows from the ordinary Markov property by splitting over the events that the stopping time equals and summing over . Induction therefore gives the displayed visit-tail formula. The tail-sum formula gives . Independently, Tonelli's theorem applied to the nonnegative visit indicators gives . These are two descriptions of the same quantity.
If , every fixed finite number of returns occurs almost surely. Intersecting these countably many probability-one events proves infinitely many returns. This does not yet say anything about their mean spacing.
Why cycle occupation balances flows
Proof
(Cycle occupations balance flows)
By Tonelli, , and , since a return cycle includes its initial state but excludes its final return. For a fixed , condition one step ahead on each event to obtain
The two sums differ only in their endpoints, and . All rearrangements are valid for nonnegative terms; finite then permits normalization. Dividing by proves stationarity and .
Proof X-ray
Where finiteness enters
The proof has two stages, and only the second needs . The balance identity uses the Markov property at each time through the event , which is determined by ; this is what allows conditioning one step ahead inside the random sum. The key move is the endpoint swap: shifting the cycle by one step drops the initial visit to and adds the final one, and these cancel because almost surely and , so the identity holds at as well. Every exchange of sums involves nonnegative terms, so this stage is valid even if some weights are infinite. Only the normalization divides by , and that is the single step where finite mean return enters. For the fair walk the cycles are almost surely finite but , so the normalization step has nothing finite to divide by.
Worked examples
Worked example 7.1.6
(The simple symmetric walk is null recurrent)
From state zero, the first step is to or . The hitting result and reflection symmetry show that either starting point returns to zero almost surely. Thus . But from the expected time to hit zero is infinite, so the return time from zero, one plus that further time, has infinite expectation. Hence every state is null recurrent. Infinite expected return is compatible with return probability one.
Counterexample mode
Certain return does not give a stationary probability
Claim: as in the finite irreducible case, a chain whose states are recurrent has a stationary probability. Take the symmetric walk on , which is recurrent. A stationary would satisfy , that is, for every , so . Nonnegativity for all forces , and constant weights sum to or , never to one. The claim fails. The repair is the cycle theorem's extra hypothesis , which this walk violates.
Worked example 7.1.7
(A biased walk is transient in either direction)
Suppose . Starting from , the probability of hitting zero is . Starting from , it is one, since the drift points toward zero on that side. First-step conditioning gives . For the symmetric argument gives . Therefore, for every biased walk, and the expected total visits to zero are . With , the return probability is and the expected total visits, including time zero, are two.
Worked example 7.1.8
(Reflection produces a positive recurrent chain)
On , let , and from every positive state move right with probability and left with probability . Assume and set . Detailed balance between neighbors gives the candidate
It sums to one. Since , summing the pairwise balances proves stationarity, including the self-loop at zero. The mean positive return time to zero is
For , and the expected return time is two. The holding step at zero counts as a return at time one.
Worked example 7.1.9
(The reflected family also shows failure of normalization)
The stationary equation at zero gives . At each interior state, stationarity says that the flux equals the previous flux. The initial flux is zero, so every stationary candidate must satisfy .
For , these are constant weights and no nonzero candidate is summable. The chain is recurrent by the hitting result, but has infinite mean return, so it is null recurrent. For , the weights grow and cannot normalize. First-step analysis gives return probability , so it is transient. Thus this single family exhibits positive recurrence, null recurrence and transience, with the boundary condition included rather than ignored.
Common mistakes
Common mistake
(Infinitely many visits do not mean finite mean return)
Both a positive recurrent chain and the symmetric walk return infinitely often almost surely. Their expected total visit counts are both infinite. To distinguish them, examine the time between returns, not the number of returns over an infinite horizon.
Common mistake
(Picking any solution of the infinite hitting equations)
For , the hitting probabilities satisfy and for . Both and solve these equations: for the second, with , and . Without a boundary at infinity the equations do not select the probability; the finite-boundary limit, or the fact that hitting probabilities form the minimal nonnegative solution, picks . For stationary laws, likewise verify nonnegativity, total mass one and every balance equation.
Recurrence is also different from convergence of time- distributions. The symmetric walk on is periodic with period two and has no stationary probability. Even positive recurrence does not remove periodicity in general. No universal countable-chain convergence theorem has been proved in this note.
Summary
Finite gambler's ruin becomes an infinite hitting theorem only after its events are shown to increase to the desired event. Repeated returns give a geometric visit count in the transient case. A finite mean cycle yields stationary probabilities through normalized occupation times. The reflected walk demonstrates why recurrence, positive recurrence and normalizable stationary balance must be distinguished on an infinite space.
Exercises
Quick check
(A walk on has and starts at . Find the probability of ever hitting zero, its return probability when started at zero, and its expected total visits to zero from zero.)
Solution · Answer
Here , so the hitting probability from two is . The return probability from zero is . The expected total visits are , including the starting visit. These three quantities concern different initial states or different events.
Quick check
(A downward-biased walk has and starts at . Find and . Explain why solving the mean recurrence without a finiteness argument is incomplete.)
Solution · Answer
Since , the hitting probability is one and . The stopped-increment argument first proves finite expectation, then justifies summing expectations through the random duration. A recurrence alone may have additional formal solutions and does not establish that the proposed expectation is finite.
Quick check
(For the reflected walk with , find the stationary distribution, its mean state, and the expected positive return time to zero.)
Solution · Answer
The ratio is , giving . Differentiate the geometric series or sum its tail to get mean state . The return mean is , also equal to .
Quick check
(In the symmetric walk started at , prove that is finite almost surely but has infinite mean using finite boundaries only.)
Solution · Answer
With an upper boundary , , and the increasing-event argument identifies the limit as . Meanwhile for every . Hence the expectation is infinite even though the time is almost surely finite.
Quick check
(Starting at the first state of a three-state recurrent class, the expected occupation weights before the first positive return are . Compute the mean return and stationary law obtained from the cycle construction. Separately, for a countably infinite recurrent class, explain why cycle weights of infinite total mass cannot be normalized by this construction.)
Solution · Answer
Summing cycle occupations gives mean return , so . Its coordinate at the recurrent starting state is . If the total occupation mass were infinite, division by that mass would not define a probability distribution; the finite-mean cycle construction would not apply. That failure alone is not a proof of every possible stationary-law statement for an arbitrary reducible chain.