CorollaryStatement: Literature-sourcedProof: AI-adaptedPipeline-generatedjudge pass (gpt-5.6-terra)audited 2026-09-14

How statement and proof provenance work

The first chip identifies the source of the statement or construction; the second identifies the source of its local proof or verification.

Literature-sourced: the exact statement appears in a cited source; only wording and notation differ.
AI-adapted: a semantically identical restatement of literature-sourced material, modulo indexing, notation, and boundary cases adopted by the library.
AI-generated: a genuinely novel statement formulated by AI, with no source for the claim itself.

These labels describe origin, not correctness: citations and verification chips remain separate evidence.

Gambler's ruin hitting probability from optional stopping

Statement

Assume AC. Let $N \geq 2$ and $i \in {1, \dots, N - 1}$ be integers, let $S_{n} = i + \sum_{k = 1}^{n} ξ_{k}$ , where the independent increments take $1$ and $- 1$ with probability $1 / 2$ , and use the natural filtration $F_{n} = σ (ξ_{1}, \dots, ξ_{n})$ , with $F_{0}$ trivial. For $τ = \inf {n : S_{n} \in {0, N}},$ $τ$ is almost surely finite; use the cemetery value $S_{τ} = 0$ on ${τ = \infty}$ . Then $P (S_{τ} = N) = i / N$ .

Facts & Assumptions

Given: The hypotheses, objects, and conventions in the Statement.

[F1]

First hitting time of an adapted process is a stopping time makes $τ$ a stopping time.

[F2]

Conditioning a known variable and an independent variable verifies that $S$ is a martingale.

[F3]

Optional stopping with a dominating integrable variable passes from the bounded stopped times to $τ$ .

[F4]

The Axiom of Choice is inherited from martingale conditioning and optional stopping.

Proof

1.1F1

Adaptedness and F1 make $τ$ a stopping time. At the start of any block of $N$ fresh increments, conditional on not yet having exited, the event that all $N$ increments are $+ 1$ has probability $2^{- N}$ and forces an upper exit within that block. Independence of successive increments therefore gives inductively $P (τ > m N) \leq (1 - 2^{- N})^{m} ⟶ 0.$ Thus $τ < \infty$ almost surely.

2.1F2F3step 1.1

Since $E ξ_{k} = 0$ and $ξ_{k}$ is independent of the past, F2 gives $E [S_{k} ∣ F_{k - 1}] = S_{k - 1}$ . Before and at exit the nearest-neighbour path stays in $[0, N]$ , so $∣ S_{τ \land n} ∣ \leq N$ . F3 with dominator $N$ yields $E S_{τ} = E S_{0} = i$ .

3.1F4step 2.1∎

At the finite exit time, $S_{τ} \in {0, N}$ ; the chosen value zero on the null event ${τ = \infty}$ preserves this assertion everywhere. Therefore $i = E S_{τ} = N P (S_{τ} = N),$ which gives the result. AC is used exactly through F4.

Depends on

Used by

Expected duration of symmetric gambler's ruin Corollary
Optional stopping fails for an unbounded simple-random-walk hitting time Counterexample

Dependency tree · two levels

14 results within two dependency steps of this one, each drawn at its shortest distance from it. An arrow runs from a result to what uses it, so the chart reads left to right and ends at this result, which carries a heavier outline. Every node is a link to that result. Click elsewhere on the chart to enlarge it.

Sources

van der Vaart, Martingales, Diffusions and Financial Mathematics, optional-stopping examples in §2.3 (standard reference, not scraped)