The speed of biased random walk on leafless Bienaymé trees is monotone
Version 1 / Nov 21, 2026 / CC BY 4.0
Abstract
Let be the offspring variable of a Bienaymé tree without leaves,
with finite mean . We prove that the speed of the
-biased random walk is continuously differentiable on ,
with for every . In particular 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 . In general it also uses two
interval-arithmetic computations, for biases between and .
The main theorem, including both computations, has been formalized
in Lean.
Provenance statement
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
- Elie A ï d é kon. Monotonicity for . Unpublished note, 20 September 2013, 2013.
- 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.
- 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.
- 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.
- 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.
- 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.
- Dimitris Bertsimas and Ioana Popescu. Optimal inequalities in probability theory: A convex optimization approach. SIAM J. Optim. , 15(3):780--804, 2005.
- 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.
- 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.
- Michel Denuit, Etienne De Vylder, and Claude Lef è vre. Extremal generators and extremal distributions for the continuous -convex stochastic orderings. Insur. Math. Econ. , 24(3):201--217, 1999.
Show all 21 referencesShow fewer references
- 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
- Shen Lin. Harmonic measure for biased random walk in a supercritical Galton -- Watson tree. Bernoulli , 25(4B):3652--3672, 2019.
- Russell Lyons. Random walks and percolation on trees. Ann. Probab. , 18(3):931--958, 1990.
- 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.
- Russell Lyons, Robin Pemantle, and Yuval Peres. Biased random walks on Galton -- Watson trees. Probab. Theory Relat. Fields , 106(2):249--264, 1996.
- 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.
- 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
- 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.
- 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.
- Felix Schwarzfischer. A proof of the Lyons -- Pemantle -- Peres monotonicity conjecture for high offspring laws. Preprint, arXiv :2611.25882, 2026.arXiv
- 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
- 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