no. 14 · Friday 13 November 2026
A Computer-Assisted Proof of Speed Monotonicity for the Biased Random Walk on a Galton-Watson Tree Beyond the Known Range
Abstract
The speed $v(λ)$ of the $λ$-biased random walk on a supercritical Galton–Watson tree without leaves is conjectured to be nonincreasing on $[0,m)$, where $m$ is the mean offspring. For non-constant offspring, monotonicity is known only for small bias: $λ\le 1/1160$, $λ\le 1/2$, and, when every vertex has at least $m_1\ge 2$ children, $λ\le m_1/(1+\sqrt{1-1/m_1})$. For offspring uniform on $\{2,3\}$ ($m=2.5$) the last bound is $2/(1+\sqrt{1/2})\approx1.1716$. We prove, with computer assistance, that $v$ is strictly decreasing on $[0,1.755]$ for this law. The proof has three parts. Aïdékon's speed formula gives $v=(R-λ)/(R+λ)$ for an explicit functional $R$, so $v$ decreases exactly when $R/λ$ does; we compare $R/λ$ at two biases directly, which avoids differentiating the conductance. A pathwise Lipschitz bound on the conductance in $λ$ turns that comparison into an inequality between expectations of explicit functions. A monotone sandwich of discretised laws gives two-sided bounds on the conductance law, and each $λ$-cell is checked in exact rational arithmetic over bounded floating-point error, with five cells re-checked in interval arithmetic; all reduction lemmas and an exact-integer certificate across $[1.17,1.755]$ are also formally verified in Lean 4. The method stops where the crude Lipschitz bound becomes too weak; sharper control of the derivative of the conductance is what the full range needs. Code and certificates are public.
- code
- github.com/samyama-ai/gw-speed-certificate ∎ Lean project (lean/lakefile.toml, lean/lean-toolchain) builds, no sorry at 7723b63, checked 2026-11-13 build details
- comments
- 9 pages, 1 figure. v3 adds a Lean 4 + mathlib formalisation of all reduction lemmas and an exact-integer certificate covering [1.17, 1.755]. Code: https://github.com/samyama-ai/gw-speed-certificate
- fields
- Probability