First-step races and boundary certificates

What you will learn

Derive first-step hitting probabilities with event-specific boundaries, certify them using disjoint finite-horizon path mass and diagnose nonunique harmonic solutions on closed classes.

Prerequisites: Transition kernels and two-step laws · Stationary laws and circulating flow · Stopping-time models

Define the race and fix its boundaries

Imagine a fictional inspection process with two unfinished states A and B, a success record S, a failure record F and a storage trap T. At each integer tick a fresh equally likely ticket selects the next state. In the ordinary mechanism, A has tickets A, B, S, F and B has tickets A, S, S, F. The three terminal states keep their own records forever. Assume the displayed state contains every relevant fact, tickets are independent across ticks and the conditional rules remain constant. These are exact teaching mechanisms, not estimated player behavior or a claim about real inspection reliability.

Define τS as the first tick at which S is visited, including tick zero, and define τF similarly. Our target is h(i)=P(τS<τF given X0=i). If a target is never reached, its hitting time is infinite. Starting at S therefore gives h(S)=1; starting at F gives h(F)=0. Starting at T also gives zero because neither destination can ever be reached and infinity is not strictly less than infinity. These values answer separate starting-state questions. They are not a probability allocation across states and need not sum to one. State this event before writing an equation.

Replace an infinite path tree with local equations

Starting at A, partition paths by their first ticket. An A ticket restarts the same question, a B ticket changes the starting state, an S ticket resolves success and an F ticket resolves failure. Thus a=(a+b+1+0)/4. Starting at B similarly gives b=(a+1+1+0)/4. The restart is justified by state sufficiency and fresh tickets; an omitted memory variable would invalidate this substitution. Rearrangement gives 3a=b+1 and 4b=a+2. These are boundary-value equations: prescribed terminal values feed into unknown interior values.

This calculation runs backward from an event value to each possible start. Distribution propagation instead moves a supplied starting law forward through the transition matrix. Stationary balance solves for a law reproduced by that forward movement. Mixing those directions creates plausible but wrong normalization conditions. A hitting value can equal one at several states simultaneously, because the associated experiments have different initial conditions. Likewise, a positive self-loop does not mean the process is stuck forever. It contributes another unknown value on the right side, which must be moved algebraically before division.

Solve and independently certify the race

Substitute b=3a−1 into 4b=a+2: 12a−4=a+2, hence 11a=6. Therefore a=6/11 and b=7/11. Check both original rows: (6/11+7/11+1)/4=24/44=6/11, and (6/11+2)/4=28/44=7/11. Their sum is 13/11, which is harmless: they refer to two different starts. The one-tick chance from A is only 1/4. An eventual race probability includes successful paths that first wait or visit B, so replacing it by that one-tick number discards genuine routes.

For an independent finite check, cross the first two tickets to make sixteen equally likely ticket pairs from A. Success by tick two occurs in seven pairs: four with S first, one with A then S, and two with B then S. Failure occurs in six pairs: four with F first, one with A then F and one with B then F. Three pairs remain unfinished: A then A, A then B and B then A. Thus 7/16≤a≤10/16. The exact 6/11 lies inside. Extending the ledger to tick three gives success 32/64, failure 27/64 and unfinished 5/64. The narrower interval [32/64,37/64] again contains 6/11. We counted disjoint first arrivals, not overlapping visits.

Slow the clock and expose a closed trap

The slow mechanism adds four self tickets to each unfinished row, making eight tickets per row. At A the new equation is a=(5a+b+1)/8; at B it is b=(a+4b+2)/8. After rearrangement the same two equations return. The eventual race probabilities are unchanged, although successful mass accumulates more slowly at a fixed tick. This invariance requires positive chances of leaving both unfinished states and the same conditional destination proportions when leaving. Setting an exit probability to zero would change reachability, so it cannot be justified as merely a slower clock.

In the trap mechanism, replace the last B ticket F by T. Because both destinations have success value zero, a and b remain 6/11 and 7/11. But failure is no longer the complement of success: from A, the eventual trap probability is 1/11 and failure is 4/11. To verify the trap mass, write uA=(uA+uB)/4 and uB=(uA+1)/4, yielding 3uA=uB and 4uB=uA+1. An arbitrary candidate c for T satisfies c=c, regardless of its value. Local residuals can therefore all vanish while the proposed hitting values are wrong. The event fixes c=0. More generally, finite-horizon success probabilities increase toward the least nonnegative boundary solution, excluding invented success in a closed class.

Build a boundary certificate in the workshop

Enter candidate eventual success values for A, B and T. S and F are pinned to one and zero. The live ledger compares each candidate with its row-weighted continuation value and displays a signed residual. First try T=1/2 in the trap mechanism, A=13/22 and B=17/22. Every residual vanishes, but the audit rejects the certificate because a process trapped at T cannot succeed. This is a purposeful counterexample to treating algebraic consistency as sufficient. Repair the event boundary, then solve the two interior equations again rather than normalizing the three inputs.

Advance the first-hit ledger from A one tick at a time. It separates accumulated success, accumulated failure, trapped mass and still-active mass. The success total is a lower bound. Adding only active mass gives an upper bound, because a trapped path has a proved zero chance of later success. The gap is an explicit uncertainty budget, not a simulation confidence interval. Change the mechanism to compare clock speed and destination routing; candidate entries and the horizon reset so a previous certificate cannot silently survive a changed experiment. Hints and reset support another attempt. Drafts last for this visit and do not award account credit. The workshop audits an exact model, while applying this method to data would require separate validation of the state and transition assumptions.

Hands-on: Certify a first-step race

Edit boundary values, compare local residuals and advance disjoint first-hit mass under holding and trap changes.

Common mistakes

• Adding one to a probability recurrence as if computing expected elapsed time.
• Normalizing hitting values across different starting states.
• Counting an absorbing success again on every later tick instead of tracking first arrivals.
• Treating a finite-horizon lower bound as an exact eventual probability.
• Accepting a harmonic value at an unreachable-success trap, or calling all nonsuccess paths failures.

Keep these ideas

• Specify the strict race and tick-zero convention before assigning terminal values.
• Condition on the first transition to obtain backward boundary equations.
• Use disjoint first-hit mass plus active mass for certified lower and upper bounds.
• Positive holding changes time horizons without changing the embedded destination race.
• Reachability and the least nonnegative solution exclude spurious values on closed classes.

Further reading

• UC Berkeley CS70: Probability of A before B ↗

  Read the race-event boundary equations and conditioning-on-first-transition argument. Original inspection-ticket examples and activity. Checked 2026-10-25.

• Cambridge Markov Chains: section 3.3, Theorem 3.4 ↗

  Read PDF page 14 and following remark: minimal nonnegative hitting solution, finite-horizon proof and absorbing-state boundary ambiguity. Applied to an original finite closed-trap counterexample. Checked 2026-10-25.