Why a new characterization is needed
The previous note computed infinite hitting probabilities by solving gambler's-ruin problems on finite intervals and then taking a limit of events. That method depends on nearest-neighbor geometry. This note develops a general replacement that works on any finite or countable state space.
Hitting probabilities and expected hitting times satisfy first-step equations. Those equations often have many solutions. Among all nonnegative solutions, however, the probabilistic quantity is always the smallest. The probability is therefore selected by an order property, not by uniqueness. Both halves of that statement matter.
Setting and conventions
Let be finite or countable, and let satisfy and for every . Let be the Markov chain with these transitions, and write when . Fix a nonempty set and define
Thus takes values in , and exactly when . Define
The expectation of a -valued random variable is always defined. In particular, if , then . We never assume that hitting times are finite.
Extended arithmetic. On we set , for , and . For nonnegative extended terms , the sum is the supremum of its finite partial sums. This sum does not depend on the enumeration of , and it is monotone in each term. It also satisfies monotone convergence: if for each , then .
The convention is exactly what makes hold when . It also has a probabilistic meaning: a state the chain cannot jump to contributes nothing. For example, take , , . Then and . The first-step equation
is correct only under this convention.
First step. If , then and . Here denotes the hitting time of the shifted path . The Markov property at time one gives
and the same identity holds for expectations of nonnegative functions of .
Hitting probabilities are the least nonnegative solution
For define
A solution of the hitting system (H) is a function with . Equivalently, on and off .
Theorem 16.1.1
(Minimality of hitting probabilities)
The function is a nonnegative solution of (H). Every nonnegative solution of (H) satisfies for every .
Moreover, put . Then , , and for every .
Proof
(Iteration from the boundary indicator)
Finite horizons. We have .
- If , then .
- If , then . The Markov property gives .
Hence .
Limit. The events increase, and their union is . Continuity of probability from below therefore gives . Apply monotone convergence for series to the recursion . This yields , so solves (H).
Minimality. The operator is monotone: if pointwise, then , because all coefficients are nonnegative. Let satisfy .
- Since on and off , we have .
- If , then .
By induction, for every . Letting gives .
Proof X-ray
Which hypothesis does which job
The proof has three stages, and each uses a different ingredient. The finite-horizon recursion uses the Markov property at time one together with the convention that counts time : on every iterate equals one. The passage to the limit uses only that the events increase, so no finiteness or uniqueness assumption enters.
Minimality is the non-obvious stage. Nonnegative coefficients make monotone, and the competitor needs two properties to start the induction: on and off , which together give . A signed solution can lie below ; in the upward walk worked below, with is one. The comparison is therefore among nonnegative solutions only.
The iterate counts only paths that reach within steps. A competing solution may add value for paths that escape to infinity or stay in a closed set disjoint from ; the local averaging equations cannot detect this, and the iteration from never introduces it. Starting from instead is useless, because .
The boundary condition. The condition on records that a chain started in has already hit at time . This is why is defined with . No averaging equation is imposed on . Without the boundary condition, would satisfy the averaging equation everywhere and carry no information.
Least is not the same as unique
Rows of sum to one, so always solves (H). Consequently, whenever some , the system (H) has at least two bounded nonnegative solutions. The first-step equations alone therefore cannot identify .
Counterexample mode
A finite chain with a continuum of solutions
Let and , with , and . System (H) reads
Every gives a solution . The least is , giving . This agrees with the direct computation: from , the first step decides everything.
Write the off- unknowns as . The system becomes with
Here has zero second row and is singular. A finite state space does not guarantee an inverse. On an infinite space, a finite-dimensional inverse argument does not apply automatically: invertibility as an operator requires separate hypotheses.
Uniqueness can be recovered under an extra hypothesis, and only within a restricted class of functions.
Theorem 16.1.2
(Bounded uniqueness under sure hitting)
If for every , then the only bounded real-valued solution of (H) is .
Proof
(Bounded differences vanish under sure hitting)
Let be a bounded solution and set . Then for some , on , and off . We claim that
Base case . If , the event is empty and . If , the event is certain.
Inductive step. On we have . That event is determined by . The Markov property at time gives
The right side equals , because whenever . This proves the claim.
Hence for every . As , the bound tends to . So .
Proof X-ray
Where boundedness and sure hitting enter
The proof never compares with directly. Its key move is the representation : the averaging equation carries forward along paths that have not yet hit , and the boundary condition on removes each path at its hitting time. Boundedness turns this identity into the estimate , and sure hitting sends the estimate to zero. Without the bound the identity still holds but gives nothing: in the downward walk below, is a nonzero difference although .
Both hypotheses matter. Without sure hitting, and differ. Without boundedness, unbounded nonnegative solutions can still exist, as the second worked example shows.
Expected hitting times are the least extended solution
For define
using the extended conventions above. System (M) is .
Theorem 16.1.3
(Minimality of mean hitting times)
The function solves (M). Every solution of (M) satisfies .
With , we have , , and .
Proof
(Truncated means increase to the mean)
Finite horizons. Clearly .
- If , then , so .
- If , then . This is a bounded functional of the shifted path. The Markov property gives .
Every is finite and bounded by .
Limit. Pointwise on paths, in . This includes paths with , where . The monotone convergence theorem gives . Passing to the limit in the recursion, using series monotone convergence together with , yields . This derives the first-step equation for means without assuming any mean is finite.
Minimality. The operator is monotone. Any solution satisfies . If , then . Hence .
Equivalently, , the tail-sum form of .
Concept lensAlgebraic
Neumann series on the states outside the target
Let and for . Off the iterations read with , and . Hence, off ,
These nonnegative series always have sums in . They play the role of and even when is singular: in the three-state chain, .
System (M) also admits spurious solutions. Suppose every has some with . Then the function equal to on and off solves (M). The true mean may nevertheless be finite, and minimality is what rejects the infinite candidate. Note also that forces , but the converse fails.
Worked examples
Worked example 16.1.4
(Upward drift: hitting probability and infinite mean)
Let with , and for let and . Take .
Finite boundary. For and , let . Then , since . Also , since . For , both hitting times are at least , and first-step analysis gives .
The characteristic equation is . A second-order recurrence is determined by its first two values, so every solution has the form . The boundary conditions are
Their determinant is , so the solution is unique:
Event limit. Fix and let . On the path stays below before , so it cannot reach first. Thus , and the events increase.
The union of these events is . One direction: a strict inequality forces to be finite. The other direction: if , the path before has a finite maximum , and for we get . Continuity from below therefore gives
In particular and . No infinite-horizon optional stopping theorem was used.
Cross-check by minimality. Every finite-valued solution of (H) has the form . Such a solution is nonnegative exactly when :
- if , the values tend to ;
- if , each value is a convex combination of and ;
- if , each value is at least .
Since increases in , the least nonnegative finite-valued solution is , which agrees with the event limit. The extended solution with value at and at every positive state is larger still. The choice gives the constant bounded solution , which is not the hitting probability.
Mean. For , , so . Compare this with (M). The particular solution requires , so . Every finite solution with is therefore , which is eventually negative.
If some with , the equations at its positive neighbors force those neighbors to be infinite as well, because the relevant transition coefficients are positive. This propagates through all positive states; the boundary value remains . Hence the only nonnegative extended solution is . Here (M) has a unique nonnegative solution while (H) has a continuum of them.
Worked example 16.1.5
(Downward drift: sure hitting with finite mean )
Now let and for , with . The characteristic roots are and .
Hitting system. Finite-valued solutions of (H) are . Such a solution is nonnegative only if , because a negative drives the values to . The extended solution equal to at and at every positive state is larger still. The least is , so . By the bounded-uniqueness theorem, is the only bounded solution. The unbounded nonnegative solutions with remain.
Mean system. A particular solution needs , so . The finite solutions are . Nonnegativity for all requires for every . These bounds are negative and tend to , so .
The propagation argument from the previous example shows that the only non-finite solution is off . The least extended solution is therefore . This agrees with from the previous note and was obtained here without any stopping argument.
Sure hitting, finite mean, transience and limitations
Worked example 16.1.6
(Sure hitting with an infinite mean)
Consider states with . From the chain jumps to with probability ; these probabilities sum to one by telescoping. From the chain moves deterministically to , and is absorbing.
Then , so . However,
So the conditions and are genuinely different.
Common mistake
(A hitting probability below one does not mean transience)
In the upward walk, the return probability to is . Here is the chance of descending from to , a translate of . So state is transient: mass escapes to infinity. By contrast, in the three-state counterexample is caused by trapping in the absorbing state , which is recurrent. A hitting probability below one does not by itself indicate transience.
Common mistake
(Imposing a boundary condition at infinity)
On it is tempting to fix the free constant in (H) by demanding as . In the upward walk this happens to give . In the downward walk, however, , and no finite-valued solution tends to zero at all. The selection rule proved here is minimality among nonnegative solutions; behavior at infinity is a consequence of it, not an extra condition.
Domain of the theorems. The theorems concern nonnegative solutions; signed solutions of (H) or (M) play no role. Minimality identifies and but supplies no formula. Explicit answers came from solving the recurrences and then imposing nonnegativity.
Numerical limitations.
- The iterates and are monotone lower bounds, but the theorems give no error estimate.
- Truncation at gives the lower bound , because .
- Iterating (H) from stays at that fixed point; it gives the wrong value at any state where .
- Growing values of cannot distinguish a large finite mean from an infinite one in any finite computation.
Exercises
Quick check
(For the walk with , and absorbing, compute and . Then find and .)
Solution · Answer
The equations are and . Substituting gives , so and . The characteristic roots are and , so in general . The increasing-event limit gives . Since , we get .
Quick check
(In the upward example (), compute , , and , and compare them with .)
Solution · Answer
We have . Next, gives . Then gives ; this counts the paths and . From the walk can reach only after an odd number of steps, so as well. These values approach from below, slowly and without an error bound.
Quick check
(Let , , , and . Find , all nonnegative extended solutions of (M), and .)
Solution
Hitting probabilities. and , so .
Mean system. The equations are and . If either value is infinite, both are. If both are finite, then , so and .
Conclusion. The two solutions are and . The least is , so .
Check. Each attempt from succeeds with probability . A failed attempt lasts or steps, on average. There are expected failures, so the mean is .
Quick check
(For the walk with and , find by minimality.)
Solution · Answer
The characteristic roots are and . A particular solution requires , so . The finite solutions are . Nonnegativity requires for all ; these bounds are negative and tend to , so . The only other solution is off . The least solution is therefore .