A Computer-Assisted Proof of Speed Monotonicity for the Biased Random Walk on a Galton-Watson Tree Beyond the Known Range
Listen
Radio episode about this paper
Transcript
Introduction to the show: ident: Mathematics. The day in mathematics: new theorems, new proofs, and what they open.
Ada: We're looking at the paper: "A Computer-Assisted Proof of Speed Monotonicity for the Biased Random Walk on a Galton-Watson Tree Beyond the Known Range".
Emmy: Here's the gist of the paper. 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 <ref:2609.29894#pg2> The paper proves, with computer assistance, that v is strictly decreasing on [0, 1.755: for this law <ref:2609.29894#pg6> The central theorem establishes that for the offspring distribution uniform on the set of values from which the mean is m=2.5, the speed v of the biased walk is strictly decreasing on
0, 1.755: <ref:2609.29894#pg4>.
Ada: This result extends previous known monotonicity ranges and provides a new bound beyond previously established limits like 1.17157 <ref:2609.29894#pg3>.
Emmy: The proof relies on three key reductions, including Aïdékon’s formula relating v to R/λ, a pathwise Lipschitz bound on the conductance, and two-sided bounds on the law of the conductance <ref:2609.29894#pg5>.
Ada: The proof employs a three-part strategy to transform Theorem 1 into finitely many checks <ref:2609.29894#pg6>.
Title and authors: Ada: So we’re looking at the paper "A Computer-Assisted Proof of Speed Monotonicity for the Biased Random Walk on a Galton-Watson Tree Beyond the Known Range." We're seeing them push the known limits for when this speed function is nonincreasing.
Emmy: Exactly, it’s about extending what we already know. They are looking at this speed function v of a biased random walk on a supercritical Galton–Watson tree without leaves, and they are proving that it is strictly decreasing over an interval they previously couldn't reach.
Kolya: What does this mean for the underlying probabilistic structure? The paper focuses on the case where the offspring distribution is uniform on two values, specifically two or three children, which gives them a specific example to work with.
Ada: Right, and they use computer assistance to rigorously check this monotonicity over a range that goes up to one point seven five five <ref:2609.29894#pg1>. This is a significant extension because they've already established bounds for other offspring laws.
Emmy: And their methodology hinges on three main reductions that turn the big theorem into a series of checks, starting with Aïdékon’s formula which relates the speed v to some functional R and lambda, so monotonicity is equivalent to checking if R over lambda decreases.
Kolya: That comparison between two biases directly without needing derivatives of the conductance sounds like a very smart way to handle things probabilistically. But what about how they control that conductance itself?
Ada: They use a pathwise Lipschitz bound on the conductance in lambda, which turns that comparison into an inequality between expectations of explicit functions, and then they have these two-sided bounds on the law of the conductance.
Emmy: And to make those bounds concrete, they set up this uniform grid of points from one minus lambda over two to one minus lambda over three, and they verify each cell using exact rational arithmetic <ref:2609.29894#pg1>.
Kolya: So it seems like the rigorous verification comes from using that exact arithmetic for every cell, which gives them a very high degree of confidence in those checks. But where does this leave us regarding the overall scope?
Ada: Well, they found that their certificate covers the range from one point one seven to one point seven five five, and they even confirmed one last cell with a small margin of error, which is good for robustness <ref:2609.29894#pg1>. They also noted that this result is partial because it doesn't quite reach the mean offspring m equals two point five they are aiming for in the full example <ref:2609.29894#pg1>.
Emmy: And they flag something important too, saying that the crude Lipschitz constant remains an obstacle if they want to push further towards m equals two point five, suggesting that controlling those constants is their next big structural challenge <ref:2609.29894#pg1>.
Kolya: If we only look at this result, it tells us that for this specific uniform law on two or three children, we have a solid piece of evidence showing the speed function isn't just nonincreasing up to a certain point. But what about its application in other contexts?
Ada: That’s the big question. It suggests that computer-assisted proof pipelines using these three reductions are a viable way to rigorously establish monotonicity for walks on Galton–Watson trees when analytical methods hit walls.
Emmy: And the structure they found, with Aïdékon’s formula and the difference-quotient criterion, shows how we can translate properties of expectations of functions into strict inequalities about the underlying random walk speed.
Kolya: I wonder if this technique for bounding the law of the conductance could be adapted to study other types of stochastic processes where we also have a geometric structure like a tree.
Ada: That’s definitely an avenue for future work, exploring those dynamic bounds derived from the recursive structure of the conductance law, as they mentioned in their notes. They’re essentially building a system that can adapt its verification as it checks larger intervals.
Emmy: And you have to remember that this specific result applies to offspring uniform on two or three children; extending it cleanly to arbitrary means might require a different kind of distributional control, which is what they noted as the current limitation.
Kolya: So for now, we’ve got a very controlled region of strict decrease up to one point seven five five for that specific law, backed by exact arithmetic checks on five cells and three hand-proved reductions in the "A Computer-Assisted Proof of Speed Monotonicity for the Biased Random Walk on a Galton–Watson Tree Beyond the Known Range <ref:2609.29894#pg1,A Computer-Assisted Proof of Speed Monotonicity for the Biased Random Walk>."
Ada: Indeed. So to wrap up, this paper gives us a rigorous certificate for strict decrease up to one point seven five five for uniform offspring on two or three children, using exact arithmetic and three key analytic reductions <ref:2609.29894#pg1>.
Emmy: And the limitation is that it doesn't reach the mean offspring of two point five yet, and controlling those Lipschitz constants is what’s next for them if they want to go further into that range <ref:2609.29894#pg1>.
Kolya: For me, it’s a solid piece of evidence demonstrating how to use computational methods to push beyond the known analytical boundaries in this area of branching processes.
Ada: And that's where we are with this paper on the biased random walk on a Galton–Watson tree without leaves. We'll take a quick break and come back after we talk about other papers from arXiv.
The paper's summary: Ada: So, we’re looking at this paper about the speed of a biased random walk on a Galton–Watson tree without leaves, and they’ve used computer assistance to prove that this speed function is strictly decreasing over an interval up to one point seven five five.
Emmy: Exactly. The core idea is that they took the big theorem and broke it down into three specific steps—Aïdékon’s formula, a pathwise Lipschitz bound on the conductance, and bounds on the law of that conductance—and turned those complex math conditions into simple checks they could verify exactly with rational arithmetic.
Kolya: What this means for us is that we can now rigorously confirm strict decrease in speed over a range we couldn't touch before, which is up to one point seven five five, and it’s based on the offspring distribution being uniform on two or three children.
Ada: Right. And they confirmed those checks by setting up a grid of points from one minus lambda over two to one minus lambda over three and verifying each cell using exact rational arithmetic, which gives them a high degree of confidence in the inequality checks.
Emmy: That method, using the map u seven to u minus one divided by u plus one, is what lets them show that the function x of lambda over lambda decreases when they prove it’s decreasing on that interval.
Kolya: The result itself is partial because they haven't reached the mean offspring value of two point five yet, and they noted that the crude Lipschitz constant still poses a challenge if you want to extend this proof further.
Ada: So while this gives us a solid certificate for strict decrease up to one point seven five five, it shows us exactly where we need more distributional control of that conductance law to get closer to the full mean.
Emmy: It highlights how these computer-assisted proofs can establish monotonicity through hand-proved reductions, giving us a clear map of what analytic tools are needed for each step.
Kolya: If we look at this from the perspective of tail behavior, it tells us about the speed function’s sensitivity to small changes in the underlying growth process near those smaller values of lambda.
Ada: And that sensitivity is precisely what we need to understand when designing models where the branching structure has a specific bias.
Emmy: So, this work provides a very concrete, verifiable certificate for strict monotonicity in a specific regime of this random walk speed function.
Kolya: That sets up an interesting question for next time: how do we use those dynamic bounds derived from the recursive structure of the conductance law to adapt this verification process for even larger intervals?
The paper's improvements: Tom: So, we’re looking at how the authors suggest they can take this result on speed monotonicity further than what they actually proved for now, and what those suggestions mean for future work.
Ada: They point out that the current method uses floating-point arithmetic for some of the checks, and they want to build an independent interval-arithmetic implementation so they can re-verify those five critical cells with exact rational arithmetic to get more certainty.
Emmy: That’s about robustness; they realize that relying on standard floating point can introduce errors when checking those inequalities like Proposition six point two.
Kolya: From a probabilistic standpoint, their suggestion is to integrate dynamic bounds that come from the recursive structure of the conductance law, using stochastic order envelopes called U lambda and L lambda.
Ada: They want to show that the expected value of a function h three is bounded by its expectation multiplied by U lambda minus A lambda, which helps control those errors as you move further out.
Emmy: That allows them to adapt the verification process, so they can certify monotonicity over larger intervals than just what they checked in this specific run.
Kolya: If they can manage that adaptation, it means we could potentially push the range where the speed function is strictly decreasing much closer to that mean offspring value of two point five.
Ada: Right. But there’s a caveat too; they admit that reaching the full mean requires better distributional control of the derivative of that conductance law, which is what they flagged as an obstacle before.
Emmy: So the implication is that while their current computer-assisted pipeline gives them a good starting point, the next big challenge is developing sharper tools for controlling those underlying stochastic processes.
Kolya: It shifts the focus from just proving a local bound to finding a way to control the global behavior of these geometric structures in branching processes.
Conclusion: Ada: So, to wrap up this discussion on "A Computer-Assisted Proof of Speed Monotonicity for the Biased Random Walk on a Galton–Watson Tree Beyond the Known Range," we’ve established that they rigorously proved strict decrease in speed up to one point seven five five for uniform offspring distributions.
Emmy: That result uses three specific hand-proved reductions and exact rational arithmetic to check conditions across a grid of points, which gives us a solid certificate for that monotonicity.
Kolya: From my side, the implication is that we can now be more precise about the speed function’s behavior in these branching processes, especially when we are looking at those smaller values of lambda where the growth starts to slow down.
Ada: It means we have a better handle on how much control a probabilistic researcher has over these random walk speeds in these tree structures.
Emmy: The paper shows that using computer assistance to verify these analytic reductions is a viable way to push beyond what pure analytical methods can do alone.
Kolya: And the limitation they noted—that they haven't reached the mean offspring value of two point five yet—is important because it tells us exactly where the next layer of complexity in controlling those stochastic processes lies.
Ada: Right. They’ve shown us a very controlled region, but that boundary is still defined by what we don't fully understand about the conductance law.
Emmy: We need better distributional control of that conductance law to get closer to proving it for the full mean value of two point five.
Kolya: For me, this work demonstrates a powerful technique for using computational rigor to bridge gaps in our understanding of these geometric branching processes.
VaidhyaMegha Private Limited, India
math.PR
Submitted: 2026-09-24
Updated: 2026-11-11
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
Code: https://github.com/samyama-ai/gw-speed-certificate
License: http://creativecommons.org/licenses/by/4.0/
Importance score: 90/100
The gist: The speed v(λ) of the λ-biased random walk on a supercritical Galton–Watson tree without leaves is conjectured to be nonincreasing on [0, m)…
Key concepts
- Speed v(λ)
- This represents how fast a biased random walk moves as a function of λ. The goal is to show that this speed is strictly decreasing over certain values of λ, which relates to the structure and behavior of the tree.
- Aïdékon’s formula
- This formula provides a way to relate the speed v(λ) directly to other quantities, specifically R(λ) and λ. Monotonicity (whether it's increasing or decreasing) is mathematically equivalent to checking if the ratio x(λ) = R(λ)/λ decreases.
- Conductance β
- Conductance measures a property related to the walk's movement within the tree structure. The proof uses bounds on this conductance, showing that for uniform offspring distributions, it stays within specific ranges like [1 - λ/2, 1 - λ/3].
- Computer-Assisted Proof Pipeline
- This refers to a systematic method using computational tools to rigorously check complex mathematical inequalities. It involves building a grid of points and using exact rational arithmetic to verify the conditions required for strict speed decrease across various segments.
Terminology
Summary
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 <ref:2609. p. 0 A Computer-Assisted Proof of Speed Monotonicity for the Biased
Random Walk on a Galton–Watson Tree Beyond the Known Range
Madhulatha Mandarapu∗ Sandeep Kunkunuru†
VaidhyaMegha Private Limited, India
https://samyama. ai/
September 2026
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. 5) the last bound is 2/(1 + p
1/2) ≈ 1. We prove, with computer
assistance, that v is strictly decreasing on [0, 1. We prove, with computer
assistance, that v is strictly decreasing on [0, 1. 755] for this law.Where the paper says it
Where the paper says it
Where the paper says it
Main Result and Context
The central theorem establishes that for the offspring distribution uniform on the set of values from which the mean is m=2.5, the speed v of the biased walk is strictly decreasing on [0, 1. p. 1 Let P(ν = 2) = P(ν = 3) = 1/2. The speed v of the λ-biased walk on the ν-Galton–
Watson tree is strictly decreasing on [0, 351/200], that is, on [0, 1. ai
†
sandeep@samyama. ai
1
arXiv:2609. ai
†
sandeep@samyama. ai
1
arXiv:2609. ai
†
sandeep@samyama. ai
1
arXiv:2609. 755],
beyond the known 1. The certificate rests on three hand-proved reductions (a differencequotient form of the monotonicity criterion, a pathwise Lipschitz bound on the conductance, and
stochastic-order envelopes for its law) and one inequality per λ-cell checked with exact rational
6 ai
†
sandeep@samyama. ai
1
arXiv:2609. 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 verified with exact
rational arithmetic on top of bounded floating-point error; an independent interval-arithmetic
implementation re-certifies five cells, including the one that sets the endpoint.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Methodology for Proof
The proof employs a three-part strategy to transform Theorem 1 into finitely many checks <ref:2609.29894#pg6>.
-
Aïdékon’s formula is used, which gives v = (R − λ)/(R + λ) where R(λ) = E[νf0]/E[f0] <ref:2609. p. 1
29894#pg4>. Monotonicity is equivalent to the condition that x(λ) = R(λ)/λ decreases <ref:2609. p. 0Where the paper says it
Three reductions turn Theorem 1 into finitely many checks. Aïdékon’s formula [Aïdékon, 2014] gives v = (R−λ)/(R+λ) with R(λ) = E[νf0]/E[f0] (Section 3).
29894#pg4>.Where the paper says it
ai † sandeep@samyama. ai 1 arXiv:2609.
-
A pathwise Lipschitz bound on the conductance β in λ, combined with the mean value theorem, bounds the difference quotient by expectations of two explicit functions <ref:2609. p. 1
29894#pg6>.Where the paper says it
A pathwise Lipschitz bound on the conductance β in λ (Lemma 4. 3) and the mean value theorem bound the difference quotient by expectations of two explicit functions (Section 6).
-
Two-sided bounds on the law of β are derived from iterating recursion on discretized laws using rounding in a safe direction <ref:2609. p. 1
29894#pg6>. Each cell is then verified with exact rational arithmetic <ref:2609. p. 0Where the paper says it
3) and the mean value theorem bound the difference quotient by expectations of two explicit functions (Section 6). Two-sided bounds, in the stochastic order, on the law of β come from iterating the recursion for β on discretised laws with rounding in the safe direction (Section 5).
29894#pg6>.Where the paper says it
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 verified with exact rational arithmetic on top of bounded floating-point error; an independent interval-arithmetic implementation re-certifies five cells, including the one that sets the endpoint.
Key Lemmas and Bounds
Several lemmas provide the necessary analytic control for the proof <ref:2609.29894#pg6>.
: Lemma 3.1 states that v is strictly decreasing on an interval if and only if x(λ) = R(λ)/λ is decreasing <ref:2609. p. 2 Let R(λ) = E[νf0]/E[f0]. Then v = (R − λ)/(R + λ), and v is strictly decreasing on
an interval if and only if x(λ) = R(λ)/λ is. The map u 7→ (u−1)/(u+1)
is increasing, and v = (x − 1)/(x + 1) with x = R/λ. Proof of Lemma 3. For λa ≤ λ1 < λ2 ≤ λb, with β0 and T =
Pν
i=1 βi taken at λ1,
(ν − R1)
∆f0
∆λ
≤
(
(3 − R1) h3(β0, T), ν = 3,
(R1 − 2) h2(β0, T), ν = 2,
provided κ > 0 and 3(1 − λb/2) > 2 − λa. The proof applies the mean value theorem to f0 along the segment from (λ1, β(λ1)) to (λ2, β(λ2)),
bounds each partial derivative using its sign and Lemma 4. ai
†
sandeep@samyama. ai
1
arXiv:2609. 4 Bounds on the conductance
From here on ν is uniform on {2, 3}. For λ < 2, almost surely 1 − λ/2 ≤ β ≤ 1 − λ/3. (5)
Lemma 6. For λa ≤ λ1 < λ2 ≤ λb, with β0 and T =
Pν
i=1 βi taken at λ1,
(ν − R1)
∆f0
∆λ
≤
(
(3 − R1) h3(β0, T), ν = 3,
(R1 − 2) h2(β0, T), ν = 2,
provided κ > 0 and 3(1 − λb/2) > 2 − λa. Then R(λ) ∈ [Rlo, Rhi] and
E[f0(λ)] ≥ E[f0]lo for every λ in the cell. Proposition 6. Apply Lemmas 3. 7 Results
We ran the certificate on cells of width 0. • Floating point. The per-cell arithmetic uses floating point with the written error bounds of
Appendix B rather than a formally verified library; the interval-arithmetic re-check covers five
cells, including the last, not every cell. 02328, and at K = 2000 the
last cell, [1. 755], with margin 0. ai
†
sandeep@samyama. ai
1
arXiv:2609. 755], and on each closed cell v is strictly
decreasing (Proposition 6. A function that is strictly decreasing on each of finitely many closed
intervals, each sharing at least a point with the next, is strictly decreasing on their union. [2025]; the new part is (1. The result is
partial: it does not reach m = 2. ai
†
sandeep@samyama. ai
1
arXiv:2609. 5) for a single offspring law. • The crude Lipschitz constant is the obstacle. 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. ai
†
sandeep@samyama. ai
1
arXiv:2609. ai
†
sandeep@samyama. ai
1
arXiv:2609.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
**
How the training signal is built
The method constructs a uniform grid of K + 1 points on [a, b] = [1 − λ/2, 1 − λ/3] to verify the cell conditions <ref:2609.29894#pg6>. The process involves starting from U0 = δb and L0 = δa <ref:2609. p. 3 We use a uniform grid of K + 1 points on [a, b], start from U0 = δb and L0 = δa, and after
each application of Tλ round the image of every lattice value up (for U) or down (for L) to the
grid. Grid points and λ are exact rationals; a rounding decision is taken in floating point only
when the computed position is at least 10−9
from a grid point, and otherwise in exact rational
arithmetic. We use a uniform grid of K + 1 points on [a, b], start from U0 = δb and L0 = δa, and after
each application of Tλ round the image of every lattice value up (for U) or down (for L) to the
grid. Grid points and λ are exact rationals; a rounding decision is taken in floating point only
when the computed position is at least 10−9
from a grid point, and otherwise in exact rational
arithmetic. We use a uniform grid of K + 1 points on [a, b], start from U0 = δb and L0 = δa, and after
each application of Tλ round the image of every lattice value up (for U) or down (for L) to the
grid. Grid points and λ are exact rationals; a rounding decision is taken in floating point only
when the computed position is at least 10−9
from a grid point, and otherwise in exact rational
arithmetic. Grid points and λ are exact rationals; a rounding decision is taken in floating point only
when the computed position is at least 10−9
from a grid point, and otherwise in exact rational
arithmetic. Masses are propagated in floating point by direct convolution; after each step the
cumulative distribution function is moved in the safe direction by a relative 10−10 plus an absolute
10−10, far above the accumulated rounding error (Appendix B).Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the gains come from
The primary source of rigorous verification is the exact arithmetic used for checking each λ-cell <ref:2609.29894#pg6>. The certificate rests on three hand-proved reductions, including a differencequotient form of the monotonicity criterion <ref:2609. p. 5 755],
beyond the known 1. The certificate rests on three hand-proved reductions (a differencequotient form of the monotonicity criterion, a pathwise Lipschitz bound on the conductance, and
stochastic-order envelopes for its law) and one inequality per λ-cell checked with exact rational
6 755],
beyond the known 1. The certificate rests on three hand-proved reductions (a differencequotient form of the monotonicity criterion, a pathwise Lipschitz bound on the conductance, and
stochastic-order envelopes for its law) and one inequality per λ-cell checked with exact rational
6 Each λ-cell is then one
inequality between two numbers, checked in exact rational arithmetic. Everything except the per-cell arithmetic is proved by hand.Where the paper says it
Where the paper says it
Where the paper says it
Limitations
The limitations identified include a partial range covering [0, 1.755] of [0, 2. p. 0 We prove, with computer
assistance, that v is strictly decreasing on [0, 1. 755] for this law. ai
†
sandeep@samyama. ai
1
arXiv:2609. 5) for a single offspring law. • The crude Lipschitz constant is the obstacle. • Floating point. The per-cell arithmetic uses floating point with the written error bounds of
Appendix B rather than a formally verified library; the interval-arithmetic re-check covers five
cells, including the last, not every cell. Replacing the constant
by a bound depending on β, computed by iterating the recursion for the derivative, pushes
an uncertified floating-point version further, but we do not claim it here. Reaching m needs
distributional control of the derivative of β, and for λ ≥ 2 a new lower bound on β, since the
binary support bound vanishes there.Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Where the paper says it
Conclusion
For offspring uniform on uniform on the set of values from which the mean is m=2.5, the speed of the biased walk is strictly decreasing on [0, 1. p. 1 Let P(ν = 2) = P(ν = 3) = 1/2. The speed v of the λ-biased walk on the ν-Galton–
Watson tree is strictly decreasing on [0, 351/200], that is, on [0, 1. 755],
beyond the known 1. The certificate rests on three hand-proved reductions (a differencequotient form of the monotonicity criterion, a pathwise Lipschitz bound on the conductance, and
stochastic-order envelopes for its law) and one inequality per λ-cell checked with exact rational
6Where the paper says it
Where the paper says it
References
<ref:2609.29894#pg4> **
<ref:2609.29894#pg6> B B **
<ref:2609.29894#pg4> B</ref:2609. p. 0 ai
†
sandeep@samyama. ai
1
arXiv:2609.Where the paper says it
Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.
Improvements for AI systems
-
Enhanced speed monotonicity verification for biased random walks on Galton-Watson trees beyond known ranges can be achieved by implementing a computer-assisted proof pipeline that uses three reductions: Aidekon’s formula comparison, a pathwise Lipschitz bound on conductance, and two-sided bounds on the law of the conductance. This allows for rigorous certification of strict decrease in speed over a wider range, such as up to 1.755 for the uniform offspring law on two or three children.
-
Development of an independent interval-arithmetic implementation that re-certifies five cells, including the endpoint cell, ensures robustness against floating-point errors. This system can verify critical inequalities like Proposition 6.2 with high confidence by checking conditions in exact rational arithmetic, providing a rigorous certificate for strict monotonicity on each verified interval.
-
Integration of dynamic bounds derived from the recursive structure of the conductance law allows for adaptive refinement of the verification process. By using stochastic order envelopes U lambda and L lambda, the system can certify monotonicity over larger intervals by showing that E[h3] is bounded by EU lambda a,Ulambda a [h3] and E[h2] is bounded by EU lambda a,Llambda b [h2].
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: λ at most 1/1160, λ at most 1/2, and, when every vertex has at least m 1 at least 2 children, λ at most 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) about1.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.
Sources
- Speed of the biased random walk on a Galton--Watson tree
- Biased random walks on random graphs
- Einstein relation for biased random walk on Galton--Watson trees
- A proof of the Lyons-Pemantle-Peres monotonicity conjecture for high biases
- Differentiability of the speed of biased random walks on Galton-Watson trees
- Rigorous confidence intervals for critical probabilities
- Monotonicity of the speed for biased random walk on Galton-Watson tree
Related papers
- Rank-One HCIZ Integrals and Multiplicative Convolutions
- Repeated averaging on random d-regular graphs
- Precise cover times for branching random walks on Hamming graphs: (iterated) logarithmic corrections
- Markov Chain CLTs: Resolving Open Problems
- Marked stable L'evy processes in Brownian local time
- A Sharp Refinement of Samuels' Inequality via Cap Moves