The speed of biased random walk on leafless Bienaymé trees is monotone

Primarily AI-generated textHuman understanding: some partsmath.PR — Probability

Contributed by Igor Kortchemski ↗

Version 1 / Nov 21, 2026 / CC BY 4.0

Abstract

Let ν\nu be the offspring variable of a Bienaymé tree without leaves, with finite mean m>1m>1. We prove that the speed v(λ)v(\lambda) of the λ\lambda-biased random walk is continuously differentiable on [0,m)[0,m), with v′(λ)<0v'(\lambda)<0 for every 0<λ<m0<\lambda<m. In particular vv is strictly decreasing, which answers a question posed by Lyons, Pemantle and Peres in 1996. Heng Ma recently gave an independent proof of strict monotonicity. Our proof is entirely analytic when E[1/ν]≤31/49\mathbb{E}[1/\nu]\le 31/49. In general it also uses two interval-arithmetic computations, for biases between 11 and 9/59/5. The main theorem, including both computations, has been formalized in Lean.

Author comments: 25 pages. Mathematics and text produced with AI systems under the direction of the contributor; see the section on AI use. AA Lean 4 formalization of the main theorem, including both interval-arithmetic certificates, has been completed and is available at https://github.com/igor-kortchemski/monotonicity-speed-biased-random-walk

Provenance statement

The mathematics, verification programs and text were developed through extensive, iterative interaction with AI systems under the direction of the contributor. The contributor directed the investigation, set the standards for checking the proof and organized the successive revisions. AI agents developed the mathematical arguments, wrote the computer-verification programs and drafted and revised substantial portions of the manuscript. An initial exploratory investigation was conducted mainly with OpenAI's GPT models through Codex. A subsequent research campaign was coordinated by Anthropic's Claude Opus 5.5 through Claude Code and involved 134 recorded tasks, including proof searches, independent AI reviews, computational checks and preparation of the first draft; agents included GPT-6.2 Astra and GPT-6.2 Sol, Claude Opus 5.5, Claude Fable 5.2 and Claude Sonnet 5.5. ChatGPT Pro was also used for mathematical review and simplification of later drafts. The main theorem, including the two interval-arithmetic computations used in the proof, was then formalized in Lean 4 with Mathlib, entirely by AI agents (Claude Opus 5.5 and Sonnet 5.5; GPT-6.2 Sol, GPT-6 Luna and GPT-6.2 Astra; Kimi K3.1 Pro). For the two computer-assisted lemmas, the formalization starts from the subdivisions used by the C++ verification programs: Lean's kernel checks that these boxes cover the required domains and verifies the interval bounds by exact integer arithmetic with outward rounding on dyadic grids. The two certificates comprise 41,919 boxes for one computation and 8,185 rectangles with 2,102,159 positive leaves for the other, and took about 620 CPU-hours to compile. The Lean proof uses only `propext`, `Classical.choice` and `Quot.sound`, and each module was checked by Lean's kernel at compilation. The correspondence between the Lean statement of the main theorem and the theorem stated in the paper was reviewed by AI models, including by translating the Lean statement back into ordinary mathematical language and comparing it with the manuscript. The formalization and instructions for reproducing the checks are available at https://github.com/igor-kortchemski/monotonicity-speed-biased-random-walk.

Tools used

OpenAI
ChatGPTVersion Pro 6
OpenAI
CodexVersion Version GPT-6.2 Sol, GPT-6 Luna, GPT-6.2 Astra
Anthropic
Claude CodeVersion Claude Opus 5.5, Claude Sonnet 5.5
Moonshot AI
KimiVersion K3.1 Pro

References

  1. Elie A ï d é kon. Monotonicity for λ≤1/2\lambda \leq 1/2 . Unpublished note, 20 September 2013, 2013.
  2. Elie A ï d é kon. Speed of the biased random walk on a Galton -- Watson tree. Probab. Theory Relat. Fields , 159(3--4):597--617, 2014.
  3. G é rard Ben Arous and Alexander Fribergh. Biased random walks on random graphs. In Vladas Sidoravicius and Stanislav Smirnov, editors, Probability and Statistical Physics in St. Petersburg , volume 91 of Proceedings of Symposia in Pure Mathematics , pages 99--153. American Mathematical Society, Providence, RI, 2016.
  4. G é rard Ben Arous, Alexander Fribergh, Nina Gantert, and Alan Hammond. Biased random walks on Galton -- Watson trees with leaves. Ann. Probab. , 40(1):280--338, 2012.
  5. G é rard Ben Arous, Alexander Fribergh, and Vladas Sidoravicius. Lyons -- Pemantle -- Peres monotonicity problem for high biases. Commun. Pure Appl. Math. , 67(4):519--530, 2014.
  6. G é rard Ben Arous, Yueyun Hu, Stefano Olla, and Ofer Zeitouni. Einstein relation for biased random walk on Galton -- Watson trees. Ann. Inst. Henri Poincar é , Probab. Stat. , 49(3):698--721, 2013.
  7. Dimitris Bertsimas and Ioana Popescu. Optimal inequalities in probability theory: A convex optimization approach. SIAM J. Optim. , 15(3):780--804, 2005.
  8. Adam Bowditch and Yuki Tokushige. Differentiability of the speed of biased random walks on Galton -- Watson trees. ALEA, Lat. Am. J. Probab. Math. Stat. , 17(1):609--642, 2020.
  9. Bernard Bru, Fran ç ois Jongmans, and Eugene Seneta. I. J. Bienaym é : Family information and proof of the criticality theorem . Int. Stat. Rev. , 60(2):177--183, 1992.
  10. Michel Denuit, Etienne De Vylder, and Claude Lef è vre. Extremal generators and extremal distributions for the continuous ss -convex stochastic orderings. Insur. Math. Econ. , 24(3):201--217, 1999.
Show all 21 referencesShow fewer references
  1. GPT-6 Astra and Heng Ma. Monotonicity of the speed of biased random walks on Galton -- Watson trees. Hexagon:2611.00735v1 (https://hexagonmath.org/2611.00735v1), 2026. Full version (https://github.com/hengmamath/monotone-speed-biased-RW/blob/main/paper/github.pdf) and exact computations (https://github.com/hengmamath/monotone-speed-biased-RW/tree/main/paper/supplement).hexagon
  2. Shen Lin. Harmonic measure for biased random walk in a supercritical Galton -- Watson tree. Bernoulli , 25(4B):3652--3672, 2019.
  3. Russell Lyons. Random walks and percolation on trees. Ann. Probab. , 18(3):931--958, 1990.
  4. Russell Lyons, Robin Pemantle, and Yuval Peres. Ergodic theory on Galton -- Watson trees: speed of random walk and dimension of harmonic measure. Ergodic Theory Dyn. Syst. , 15(3):593--619, 1995.
  5. Russell Lyons, Robin Pemantle, and Yuval Peres. Biased random walks on Galton -- Watson trees. Probab. Theory Relat. Fields , 106(2):249--264, 1996.
  6. Russell Lyons, Robin Pemantle, and Yuval Peres. Unsolved problems concerning random walks on trees. In Krishna B. Athreya and Peter Jagers, editors, Classical and Modern Branching Processes , volume 84 of The IMA Volumes in Mathematics and its Applications , pages 223--237. Springer, New York, 1997.
  7. Madhulatha Mandarapu and Sandeep Kunkunuru. A Computer - Assisted Proof of Speed Monotonicity for the Biased Random Walk on a Galton -- Watson Tree Beyond the Known Range . Preprint, arXiv :2609.29894, 2026.arXiv
  8. Behzad Mehrdad, Sanchayan Sen, and Lingjiong Zhu. The speed of a biased walk on a Galton -- Watson tree without leaves is monotonic with respect to progeny distributions for high values of bias. Ann. Inst. Henri Poincar é , Probab. Stat. , 51(1):304--318, 2015.
  9. Pierre Rousselin. Invariant measures, Hausdorff dimension and dimension drop of some harmonic measures on Galton -- Watson trees. Electron. J. Probab. , 23:1--31, 2018. Paper No. 46.
  10. Felix Schwarzfischer. A proof of the Lyons -- Pemantle -- Peres monotonicity conjecture for high offspring laws. Preprint, arXiv :2611.25882, 2026.arXiv
  11. He Song, Longmin Wang, and Kainan Xiang. The speed of a biased walk on a Galton -- Watson tree without leaves is monotonic for low values of bias. J. Appl. Probab. , 62(3):1044--1052, 2025.

Version history

  1. v1 · 25 pagesSubmitted by Igor Kortchemski25 pages. Mathematics and text produced with AI systems under the direction of the contributor; see the section on AI use. AA Lean 4 formalization of the main theorem, including both interval-arithmetic certificates, has been completed and is available at https://github.com/igor-kortchemski/monotonicity-speed-biased-random-walkCurrentNov 21, 2026