Why a boundary problem?
A state can represent the number of available units in a reserve. At each step one unit is gained with probability or lost with probability . We stop when the reserve reaches zero or a target . How likely is the target to be reached first, and how long must one wait? These are different questions: a probability satisfies a homogeneous first-step equation, while a duration accumulates one unit of time at every interior step.
We assume independent steps with , integer , and initial state . Once a boundary is reached the process stops.
Definition 2.9.1
(Exit time, hitting probability and mean duration)
For the walk on stopped at the boundary, set
The subscript on probability or expectation specifies the starting state. In particular , and : starting at a boundary means stopping at time zero.
First-step equations and their solutions
Theorem 2.9.2
(Two absorbing boundaries)
Let . For the probability of reaching before zero and the mean duration are
One of the two boundaries is reached in finite time almost surely, and .
Proof
(Finiteness, first-step equations and a maximum principle)
Finiteness. From any interior state, at most consecutive losses reach zero. Their probability is at least , independent of the previous history. Conditional on survival to time , the probability of surviving another block of steps is at most . Hence . This tends to zero, and the tail-sum formula bounds by a finite geometric sum. Thus the first-step equations below are legitimate.
Equations. Condition on the first step. For ,
The first equation rearranges to . If , successive differences form a geometric sequence with ratio , giving ; the two boundary values determine the displayed expression. If , the differences are constant, so .
For the duration, when a particular solution is : substituting gives . Adding the general homogeneous solution and imposing zero at both endpoints gives . When , the second difference of is , so a quadratic particular solution is ; the boundary values give .
Uniqueness. Why do these algebraic solutions represent the desired quantities uniquely? If two solutions have the same boundary values, their difference satisfies . A positive interior maximum would force both neighbors to have that maximum, since ; propagating this to a boundary contradicts the zero boundary value. Apply the same argument to . Therefore .
Proof X-ray
Three separate jobs in one proof
The proof does three different things, and each uses a different hypothesis.
- Finiteness uses only: a block of losses has a fixed positive probability. Without , the expectation equation could hold in the useless form .
- Solving is pure algebra on second-order linear recurrences. The one non-obvious move is the extra in the duration equation: the first step also consumes one time unit. Omitting it produces a homogeneous equation whose zero-boundary solution is zero, not the mean duration.
- Uniqueness uses and together: the maximum principle needs both neighbors to carry positive weight, so that an interior maximum spreads to the boundary.
The argument closes because the recurrence solutions have two free constants and there are exactly two boundary values, while the maximum principle rules out any second solution with the same boundary data.
Worked calculations
Worked example 2.9.3
(An upward-biased walk)
Let , , and . Then and
Check directly: and give , so . An upward drift does not make the target more likely than ruin from every starting point: here zero is one step away and the target is two steps away. The expected duration is measured in steps, not in units of reserve.
Worked example 2.9.4
(A fair walk)
With , and , the chance of reaching the upper boundary first is , and the expected duration is . Moving the starting point to changes these to and ; symmetry of the duration is symmetry under exchanging the two boundaries, not a claim that every starting position has the same duration. The fair case is the degenerate case of the formula: there and both vanish, and the separate formula is the limit of as .
The third calculation reverses the drift and then moves the upper boundary away, which anticipates the next section.
Worked example 2.9.5
(A downward-biased walk and a distant target)
Let , , and . Then and
Direct check: and give , so . As with fixed, , so and ; therefore . Removing the target lengthens the mean duration from to , because paths that previously stopped at now continue until they reach zero.
Removing the upper boundary
Now let an independent-step walk start at on the integers and write . There is no upper absorbing boundary.
Proposition 2.9.6
(Hitting zero from above)
For the walk started at ,
where on paths that never hit zero.
Proof
(Increase the upper boundary)
Stop first at or . The events of hitting zero before increase to as : any finite path to zero has a finite maximum. Continuity from below and the finite-boundary formula give , which equals when and when .
For the means, let be the first hit of . As increases, increases to , so monotone convergence gives . When , with , so and . When , . When , the event has positive probability, so the extended expectation is infinite.
The fair case is worth isolating, because it breaks a tempting inference.
Counterexample mode
Almost surely finite does not mean finite mean
Claim: if a hitting time is finite almost surely, then its expectation is finite. Take the fair walk, , started at . The proposition gives . But , and
So the claim fails. A limit of probabilities alone says nothing about the limit of means; one needs a separate argument such as monotone convergence. The repaired statement requires a strict drift toward zero: for , .
Common mistakes
Common mistake
(Judging the winner by the drift alone)
A positive drift does not mean the upper boundary is reached first with probability above from every start. In the upward-biased example, because zero is one step away and the target two. The probability depends on both and the distances to the two boundaries.
Common mistake
(Substituting into the biased formula)
At the expression is , and has a zero denominator. The fair case needs its own solution of the recurrences, and , which are also the limits of the biased formulas as .
Practice with solutions
Quick check
(For a fair walk on started at , find the probability of hitting first and the mean stopping time.)
Use the fair-case formulas with .
Solution · Answer
The formulas give and steps.
Quick check
(Take , , , . Find and by the formulas and verify them directly.)
Here .
Solution · Answer
Here , hence and . Directly, the first step reaches one of the two boundaries, so ; it reaches the upper one with probability .
Quick check
(For a walk on the half-line started at with and , find the chance of ever reaching zero. Is the extended mean hitting time finite?)
Compare with first.
Solution · Answer
Since , the chance is . With probability the hitting time is infinite, so its extended expectation is infinite.
Quick check
(A student substitutes into the mean equation for a fair walk. Identify the failure.)
Check the boundary values and the interior equation.
Solution · Answer
The function is harmonic and has boundary values ; it solves the hitting-probability problem. A mean time has boundary values and must satisfy the extra in its interior equation. Its correct value is .