Monotonicity of transport speed on Galton–Watson trees
Let $T$ be a Galton–Watson tree whose offspring distribution $(p_k)_{k \ge 1}$ has finite support and mean $m > 1$, so that $T$ has no leaves. For $0 < \lambda < m$, the $\lambda$-biased random walk $(X_n)_{n \ge 0}$ on $T$ starts at the root; from a vertex other than the root with $k$ children it moves to its parent with probability $\lambda/(\lambda + k)$ and to each child with probability $1/(\lambda + k)$, and from the root it moves to a uniformly chosen child. Let $$v(\lambda) = \lim_{n \to \infty} \frac{d_T(X_n, \mathrm{root})}{n}$$ be its speed, which is almost surely a deterministic constant. Lyons, Pemantle and Peres proved that the speed is positive whenever the walk is transient. Ben Arous, Fribergh and Sidoravicius proved that $v$ is decreasing for all sufficiently small $\lambda$, and Song, Wang and Xiang proved that $v$ is strictly decreasing for $0 < \lambda \le m_1/\bigl(1 + \sqrt{1 - 1/m_1}\bigr)$ when $m_1 \ge 2$, where $m_1$ is the least $k$ with $p_k > 0$.
Problem. Is $v(\lambda_1) \ge v(\lambda_2)$ whenever $0 < \lambda_1 < \lambda_2 < m$, for every such offspring distribution?
Source: Lyons, Pemantle and Peres (1996), Question 1, for every offspring law with p₀ = 0; see Lyons and Peres (2016), Question 17.33. Stated by AIM — Open Applied Problems for offspring laws of finite support.
Imported from github.com/MColbrook/AIM.
Classification
- Primary
- PR — Probability
- Secondary
- MP
- Keywords
- AIM Open Applied Problems, biased random walks, Galton–Watson trees
References
@article{lyons1996,
author = {Lyons, Russell and Pemantle, Robin and Peres, Yuval},
title = {Biased random walks on {G}alton--{W}atson trees},
journal = {Probab. Theory Related Fields},
volume = {106},
number = {2},
year = {1996},
pages = {249--264},
doi = {10.1007/s004400050064},
}
@incollection{lyons1997,
author = {Lyons, Russell and Pemantle, Robin and Peres, Yuval},
title = {Unsolved problems concerning random walks on trees},
booktitle = {Classical and Modern Branching Processes},
editor = {Athreya, Krishna B. and Jagers, Peter},
series = {IMA Vol. Math. Appl.},
volume = {84},
publisher = {Springer},
address = {New York},
year = {1997},
pages = {223--237},
doi = {10.1007/978-1-4612-1862-3_18},
}
@book{lyons2016,
author = {Lyons, Russell and Peres, Yuval},
title = {Probability on Trees and Networks},
series = {Cambridge Series in Statistical and Probabilistic Mathematics},
publisher = {Cambridge University Press},
address = {New York},
year = {2016},
doi = {10.1017/9781316672815},
}
@article{benarous2014,
author = {Ben Arous, G{\'e}rard and Fribergh, Alexander and Sidoravicius, Vladas},
title = {{L}yons--{P}emantle--{P}eres monotonicity problem for high biases},
journal = {Comm. Pure Appl. Math.},
volume = {67},
number = {4},
year = {2014},
pages = {519--530},
doi = {10.1002/cpa.21505},
eprint = {1111.5865},
archivePrefix = {arXiv},
}
@article{song2025,
author = {Song, He and Wang, Longmin and Xiang, Kainan},
title = {The speed of a biased walk on a {G}alton--{W}atson tree without leaves is monotonic for low values of bias},
journal = {J. Appl. Probab.},
volume = {62},
number = {3},
year = {2025},
pages = {1044--1052},
doi = {10.1017/jpr.2024.113},
eprint = {1610.08151},
archivePrefix = {arXiv},
}
@misc{aim-galton-watson-speed-monotonicity,
author = {Brunton, Steve and Colbrook, Matthew J. and de Hoop, Maarten V. and Stepaniants, George and Townsend, Alex and Ward, Rachel},
title = {{Monotonicity of transport speed on Galton–Watson trees}},
howpublished = {AIM --- Open Applied Problems, GitHub repository},
year = {2026},
url = {https://github.com/MColbrook/AIM/blob/a153f469ee0ea64e876b2ad97c79d252c19a3e22/problems/173-galton-watson-speed-monotonicity.md},
note = {Entry 173 at commit a153f46, 2026-10-13},
}
Citing this problem
This identifier is permanent. It will not change if the problem is solved, reclassified or withdrawn.
OP-00434, "Monotonicity of transport speed on Galton–Watson trees", clopen.solutions.