On the Monotonicity of the Speed of Biased Random Walks on GW Trees

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

Contributed by Heng Ma ↗

Version 1 / Nov 20, 2026 / CC BY 4.0

Abstract

On a Galton--Watson tree without leaves, the λ\lambda-biased random walk (Xn)(X_n) chooses its next step with weight λ>0\lambda>0 for the parent and weight one for each child. When λ\lambda strictly less than the mean offspring mm, the walk is transient, with a positive speed v(λ):=lim⁡n→∞∣Xn∣/n.v(\lambda): =\lim_{n\to\infty}|X_n|/n. We study the monotonicity of v(⋅)v(\cdot), and prove that: \begin{itemize} \item If the GW tree has at least two children, then v(⋅)v(\cdot) is decreasing on (0,m)(0,m); \item v(⋅)v(\cdot) is decreasing on (0,1)∪(3+52,m)(0,1) \cup (\frac{3+\sqrt{5}}{2}, m). \end{itemize} We also sketch a computer-assisted proof of strict decrease on (0,m)(0,m) using exact checks of about 750,000750{,}000 rational coefficients. The full proof appears in the companion GitHub version~\cite{FullVersion}.

Provenance statement

The initial proof was found by OpenAI's GPT-6 Astra through extensive interaction with the author. During the conversation, the model frequently lost in short-term rewards: it proved local lemmas that did not lead to the main result, checked special cases numerically, or carried out long computations without real progress. It also tended to keep pushing one approach instead of stepping back. In these cases, the author either chose among directions proposed by the model or asked it to try a different approach.

Tools used

OpenAI
ChatGPTVersion 6 Astra

References

  1. Aïdékon, Élie. Speed of the biased random walk on a Galton–Watson tree. Probability Theory and Related Fields, vol. 159, pp. 597–617. 2014. Theorem numbering follows arXiv:1111.4313v4 (https://arxiv.org/abs/1111.4313v4)arXivDOI
  2. Bowditch, Adam; Tokushige, Yuki. Differentiability of the speed of biased random walks on Galton–Watson trees. ALEA. Latin American Journal of Probability and Mathematical Statistics, vol. 17, pp. 609–642. 2020. arXiv:1906.07913v2 (https://arxiv.org/abs/1906.07913v2)arXivDOI
  3. GPT-6 Astra; Ma, Heng. Monotonicity of the Speed of Biased Random Walks on Galton–Watson Trees: full (GitHub) version. 2026. Companion full manuscript, November 20, 2026, Section 6. Complete proofs and accompanying exact-computation supplement. https://github.com/hengmamath/monotone-speed-biased-RW/blob/main/paper/github.pdflink
  4. GPT-6 Astra; Ma, Heng. Supplementary exact computations and source records for speed monotonicity. 2026. Exact coefficient data, executable verification programs and source records accompanying this article. See the supplementary README for the correspondence with the finite arithmetic lemmas. https://github.com/hengmamath/monotone-speed-biased-RW/tree/main/paper/supplementlink
  5. Lyons, Russell; Pemantle, Robin; Peres, Yuval. Unsolved problems concerning random walks on trees. Classical and Modern Branching Processes, vol. 84, pp. 223–238. 1997. Corrected author version (https://rdlyons.pages.iu.edu/pdf/opentree7.pdf), Question 2.1link
  6. Schwarzfischer, Felix. A proof of the Lyons–Pemantle–Peres monotonicity conjecture for high offspring laws. 2026. Submitted November 19, 2026; Theorem 1.1 and the discussion following it. arXiv:2611.25882v1 (https://arxiv.org/abs/2611.25882v1)link
  7. Song, He; Wang, Longmin; Xiang, Kainan. Monotonicity of speed for biased random walk on Galton–Watson tree. 2016. Theorem 1.2, Lemma 2.1, equation (2.1), and Lemma 2.5. arXiv:1610.08151v1 (https://arxiv.org/abs/1610.08151v1)link

Version history

  1. v1 · 24 pagesSubmitted by Heng MaInitial depositCurrentNov 20, 2026