Motivation
A Markov chain forgets its past when its present state is known. The familiar formula applies at a fixed time, but many useful questions start at a time discovered while watching the chain: the first visit to a state, for example. Can we treat what follows that visit as a fresh chain? The answer is yes when the time is a stopping time, and the distinction matters because a time chosen using future observations can bias what follows.
Throughout, is a time-homogeneous Markov chain on a finite or countable state space , with transition matrix and natural history . The notation means that .
Definitions
Definition 2.11.1
(A decision made from the observed past)
A random time taking values in is a stopping time if for every finite . Equivalently, at time the observed history determines whether stopping has occurred by then. For , the first hitting time is , with .
The two random times used most often in this chapter are stopping times.
Lemma 2.11.2
(Hitting and return times are stopping times)
For every , the first hitting time is a stopping time. For every , the first return time is a stopping time.
Proof
(Each event reads only the path up to time n)
The event says that all lie outside and lies in ; it is a finite intersection of events in . Likewise for says that differ from and , while .
The last visit before a fixed horizon generally is not a stopping time: knowing that a visit is the last requires looking ahead.
The information available at a random time is represented by : an event belongs to it when for every finite . The theorem below concerns only ; no value of or post- path is asserted when .
Theorem and proof
Theorem 2.11.3
(Restarting at a stopping time)
Let be a stopping time, , and with . Then
When the factor on the right before the product is positive, this is the conditional distribution of the next states given the indicated past event and . Thus the future has the law of a fresh chain started at , even if is unbounded or has positive probability of being infinite.
Proof
(Split on the value of the stopping time)
For each , the event is determined by the history up to . Applying the ordinary Markov property repeatedly at the fixed time gives
Sum over the disjoint values . All summands are probabilities, so countable additivity applies without assuming . On the displayed are exactly , proving the identity. Finite-path probabilities determine the law of the subsequent discrete-time path.
Proof X-ray
Why the stopping-time condition enters
The proof has one idea and one bookkeeping step.
- The idea is to replace the random time by fixed times. On the statement is about the fixed time , where the ordinary Markov property is available. That property needs the conditioning event to lie in , and this is the only place where the hypotheses are used: and a stopping time together give exactly .
- The bookkeeping is the sum over . It is a countable sum of nonnegative terms, so no integrability of is needed, and the value is simply never included.
Two things the proof does not say: it does not say that is independent of the path, which it normally is not; and it does not say that the future is independent of , since its law explicitly depends on the state reached. The look-ahead counterexample below shows the first step failing when .
Worked examples
Worked example 2.11.4
(Successive returns have geometric tails)
Start at state and let . Define and , with if . These are stopping times. The restart theorem gives the following recursion, including when a previous-return event has probability zero: . Consequently
If is the number of visits including time zero, then . The tail-sum formula gives for , and infinity for . In the latter case by continuity of probability for the decreasing events . This does not imply a finite mean return time: recurrence and positive recurrence remain separate properties.
Worked example 2.11.5
(A repeated attempt after hitting a state)
Let the states be , with absorbing; from move to with probability one, and from move to or with probability each. Starting at , each visit to begins a new attempt. The next transition succeeds by reaching with probability . By the restart theorem, the attempt outcomes are independent for as long as they are made, so the number of attempts through the first success has
Each attempt takes two steps from through to its next destination. A failed attempt returns to , so the absorption time is and has mean . This conclusion uses the specified transitions; it is not a general formula for all hitting times.
The third example shows how the restart theorem is used when the hit can occur at different states, and when it may not occur at all.
Worked example 2.11.6
(Entering a set through two different states)
Take states with absorbing. From move to each of with probability ; from move to or with probability each; from move to with probability one. Start at and let with . Before the chain waits at , so
and likewise . Hence ; on the remaining event of probability the chain is absorbed at first, , and is undefined. Apply the theorem with separately for each entry state and add:
Given this is , which is neither the value for a fresh chain from nor the value for a fresh chain from , but their average weighted by the entry law . Note that is unbounded here, and the theorem needs no bound on it.
A look-ahead counterexample
The stopping-time hypothesis cannot be replaced by the weaker requirement that the random time be finite.
Counterexample mode
A random time need not be a restart time
Claim: if is a finite random time and , then the path after is a fresh chain from . Let be independent fair bits, a Markov chain whose every transition has probability . Define if , and if . Then is finite and is defined, but is not determined by , so is not a stopping time. Compute: and , so conditional on and the next value is with probability , whereas a fresh chain from gives probability . This does not contradict the ordinary Markov property: conditioning on supplies information about itself. The repaired statement is the theorem: the timing rule must be inspectable from the history at the moment it stops.
Common mistakes
Common mistake
(Dividing by the probability of a hit that may not happen)
A hitting time can equal infinity. Apply the restart statement on the event that the hit occurs, and divide by its probability only when that probability is positive. A quantity such as has no meaning until a convention on is fixed.
Common mistake
(Thinking a stopping time must ignore the past)
A stopping time can depend strongly on the past: first hitting is a standard example, and the time itself is usually far from independent of the path. What is forbidden is using information unavailable at the moment of the decision.
Common mistake
(Discarding the final excursion)
Restart at a state does not make whole return cycles independent without specifying the successive return times and the event on which those cycles exist. When , the last excursion from never returns, and it must not be silently discarded or treated as a completed cycle.
Practice
Quick check
(For and , show that is a stopping time.)
Treat and separately.
Solution · Answer
If , . If , it is the intersection of with for ; all are in .
Quick check
(Suppose . Find the probability of at least three returns after time zero and the expected total number of visits to , including time zero.)
Use the first worked example.
Solution · Answer
The three-return probability is . The expected number of visits is . The initial visit is included.
Quick check
(In the repeated-attempt example, compute the probability that absorption takes more than four steps and the probability that it occurs at exactly six steps.)
The absorption time is .
Solution · Answer
The first two attempts must fail for , giving . Exactly six steps means : two failures then a success, with probability .
Quick check
(A chain starts at and has . Given and , find . Is it legitimate to write without further conventions?)
Compare with the third worked example.
Solution
The theorem gives . On the symbol has not been defined, and even conditional on the state reached need not be . One must specify the event and include contributions from other possible hit states.