Expected time to expand a random-walk range Created 2026-10-05 Updated 2026-11-05
For a simple symmetric random walk on the integers, let be the first time that distinct vertices have been visited. The visited set is an interval, and at the walk is at an endpoint. The Strong Markov property turns the time to add one vertex into gambler's ruin between the two immediately exterior vertices, starting one step from a boundary. The expected duration of symmetric gambler's ruin is therefore . This also holds at .
Five-state harmonic absorption example 2026-10-14
Take a birth-death chain on . At each interior state, move up one state with probability and down one state with probability . The endpoints are absorbing states: . This is a small gambler's ruin model in which the state can represent capital, and reaching is success.
Five states with fair interior transitions and absorbing endpoints; each displayed value is the probability of reaching 4 before 0.
Details. Let be the hitting time of endpoint , and let be the first endpoint hitting time. The desired hitting probability is . First-step analysis and the Markov property giveThe interior equation says adjacent differences are equal. Four equal increments must bridge the boundary values and , soFor example, from state the hitting probability is , and its one-step average is . Individual sample paths can wander back and forth, but the same averaging rule already accounts for all of them.
Now ask how long it takes to reach either endpoint. The expected hitting time counts steps, including the transition that first reaches an endpoint. First-step analysis givesThis is a discrete Poisson equation, in the interior. The extra counts the step just taken. The quadratic valuessatisfy the equations; from state , steps. The hitting probability is harmonic, whereas the expected hitting time has a nonzero source term. These are special cases of expected duration of symmetric gambler's ruin; see Hao Wu's MIT lecture 16, gambler's ruin, slide 9.
For a biased random walk with upward and downward, keep the same absorbing states. The interior harmonic equation becomes . Using biased gambler's ruin probability with these boundary values givesThe three interior hitting probabilities are approximately , , and . Thus starting at now succeeds about of the time. A direct check is . The curved profile reflects the unequal transition weights: its successive increments shrink by the factor . The formula, with the endpoint denoted there, is verified in Karger and Lynch's MIT lecture 26, sections 2.3-2.4; the five-state numbers here are direct substitutions.
Hitting 4 before 0 for fair and upward-biased walks, compared with the fair walk's expected number of steps to either endpoint; lines join discrete state values.
Details. Why does harmonic averaging produce the correct hitting probability? With the natural filtration , the Markov property gives the conditional expectation identityFor a function harmonic everywhere, this makes a martingale whenever it is integrable. For a function harmonic only in the interior, is a stopped martingale. In either five-state example, . Also, from any interior state at most three consecutive upward steps reach , with probability at least . Repeated three-step blocks give , so is almost surely finite and has finite expected value; compare finite-interval exit times have geometric tails. Applying optional stopping at and then the bounded convergence theorem givesThe boundedness and finite hitting time justify this passage to the limit. See Steven Lalley's notes, harmonic functions and stopped expectations, theorem 1, and stopped martingale in discrete time for this bounded version of optional stopping.
Uniqueness has a short maximum principle explanation. On a finite state space, the difference of two harmonic extensions with the same boundary conditions is zero on the boundary. If its positive maximum occurs inside, the weighted average forces every successor with positive transition probability to have the same maximum. A path to the boundary propagates that maximum to zero, a contradiction. Applying the argument to the negative of the difference proves uniqueness. Reachability of the boundary is essential: an interior closed communicating class can retain an arbitrary constant.
// Target: markov-process.bigb
Gambler's ruin Created 2026-09-24 Updated 2026-11-05
Gambler's ruin is the absorption problem for a fortune that changes by one unit per game. Let , with independent wins of Probability and losses of Probability . Stop when the fortune reaches zero or the target . Zero is ruin; reaching is success.
The success Probability has boundary values , and satisfies . Solving this second-order recurrence givesFinite-interval exit times have geometric tails, so absorption occurs almost surely and ruin has Probability . The fair case is linear because the fortune itself is harmonic; the biased case uses the harmonic exponential .
For a fair game with initial fortune three and target ten, success has Probability . The Expected duration of symmetric gambler's ruin is , giving 21 steps in this example. The same local first-step method produces expected durations, discounted absorption probabilities and conditional durations; their different boundary conditions encode different questions about the same paths.
Past exam of the mathematics course of the University of Cambridge 2015 ia Paper 2 9F Solution Created 2026-09-24 Updated 2026-10-06
Let and measure Lionel's fortune in unit stakes. This is gambler's ruin: the fortune moves by with probability and with probability , stopping at or . Let be the expected value of the absorption time starting at . It is finite: from any interior state, a run of wins or losses has a fixed positive probability of absorption within steps, giving a geometric bound on survival over successive blocks. First-step analysis therefore givesFor , the homogeneous solution of the recurrence is , and a particular solution is . Put . Imposing the two endpoint boundary conditions gives the expected duration of biased gambler's ruinConsequently the expected number of games isThe denominator and numerator have matching signs, so this is positive. As a check its continuous limit at is , the expected duration of symmetric gambler's ruin.
Past exam of the mathematics course of the University of Cambridge 2017 ia Paper 2 12F a Solution Created 2026-09-24 Updated 2026-10-05
Write and . The expected duration of symmetric gambler's ruin satisfies and, by conditioning on the first step,These expected values are finite: from any interior state, consecutive right steps ensure absorption, an event of probability at least . Blocks of steps therefore bound the survival probability by a decreasing geometric sequence. The candidate has the required boundary values and satisfies . HenceFor completeness, the difference of two solutions of this linear recurrence relation has zero second difference and is affine in ; its two zero boundary values force it to vanish.
Past exam of the mathematics course of the University of Cambridge 2017 ia Paper 2 12F b Solution Created 2026-09-24 Updated 2026-10-05
The vertices visited by a simple symmetric random walk form an integer interval: nearest-neighbour steps cannot skip a vertex. At the stopping time , write that interval as , with . The walk is at one of its endpoints, because the th new vertex must extend the earlier interval. This also covers , when both endpoints coincide.
The Strong Markov property restarts the walk from this endpoint. Visiting a new vertex is exactly exiting , or reaching or . Translate these absorbing boundaries to . The starting point becomes either or , so the expected duration of symmetric gambler's ruin is in both cases. Taking conditional expectations and then expected values gives the expected time to expand a random-walk range:
Let . Time is accumulated in each transient chamber before the next move; arrival at either terminal state ends the trial immediately. Thus . A block of identical rightward choices forces absorption, so the geometric tail bound from a uniform escape probability gives finite expected value of .
First-step analysis now givesThe quadratic has the correct boundary values and second difference , so it solves this system. The difference of two solutions would be linear in with zero values at both endpoints, hence zero. ThereforeThis is the expected duration of symmetric gambler's ruin. It includes the first minute in the starting transient chamber and does not add a minute after absorption.

