A Computer-Assisted Proof of Speed Monotonicity for the Biased Random Walk on a Galton-Watson Tree Beyond the Known Range

arXiv:2609.29894 · math.PR · Submitted 2026-09-24 · Read on arXiv

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

Where the paper says it

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.

29894#pg2> The paper proves, with computer assistance, that v is strictly decreasing on [0, 1. p. 0
Where the paper says it

5) the last bound is 2/(1 + p 1/2) ≈ 1. We prove, with computer assistance, that v is strictly decreasing on [0, 1.

755] for this law <ref:2609. p. 0
Where the paper says it

We prove, with computer assistance, that v is strictly decreasing on [0, 1. 755] for this law.

29894#pg6>

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

Where the paper says it

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] <ref:2609. p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

29894#pg4>. This result extends previous known monotonicity ranges and provides a new bound beyond previously established limits like 1. p. 5
Where the paper says it

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

17157 <ref:2609. p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

29894#pg3>. 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. p. 0
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.

29894#pg5>.

Methodology for Proof

The proof employs a three-part strategy to transform Theorem 1 into finitely many checks <ref:2609.29894#pg6>.

  1. Aïdékon’s formula is used, which gives v = (R − λ)/(R + λ) where R(λ) = E[νf0]/E[f0] <ref:2609. p. 1

    Where 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>. Monotonicity is equivalent to the condition that x(λ) = R(λ)/λ decreases <ref:2609. p. 0
    Where the paper says it

    ai † sandeep@samyama. ai 1 arXiv:2609.

    29894#pg4>.

  2. 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

    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).

    29894#pg6>.

  3. 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

    Where 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>. Each cell is then verified with exact rational arithmetic <ref:2609. p. 0
    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.

    29894#pg6>.

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

Where the paper says it

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.

29894#pg4>. The proof of this lemma involves a map u 7→ (u−1)/(u+1) which is increasing <ref:2609. p. 7
Where the paper says it

The map u 7→ (u−1)/(u+1) is increasing, and v = (x − 1)/(x + 1) with x = R/λ. Proof of Lemma 3.

29894#pg6>. The proof of Lemma 3. p. 3
Where the paper says it

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.

2 relates the change in x(λ) to expectations involving ∆f0 <ref:2609. p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

29894#pg6>. 4. Bounds on the conductance establishes that for uniform offspring on a set, almost surely 1 − λ/2 ≤ β ≤ 1 − λ/3 for λ. p. 2
Where the paper says it

4 Bounds on the conductance From here on ν is uniform on {2, 3}. For λ < 2, almost surely 1 − λ/2 ≤ β ≤ 1 − λ/3.

Lemma 4.3 provides a bound on the difference of finite-depth values: 0 ≤ β(λ1) − β(λ2) ≤ (λ2 − λ1)β(λ1)/ (2 − λb) <ref:2609. p. 3
Where the paper says it

(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.

29894#pg6>. The final proposition requires checking a complex inequality involving bounds on R and E[f0] for every cell <ref:2609. p. 3
Where the paper says it

Then R(λ) ∈ [Rlo, Rhi] and E[f0(λ)] ≥ E[f0]lo for every λ in the cell. Proposition 6.

29894#pg6>. 7. Results show that the certificate covers [1. p. 4
Where the paper says it

Apply Lemmas 3. 7 Results We ran the certificate on cells of width 0.

17, 1.755] <ref:2609.29894#pg6>. The independent check confirms the last cell [1. p. 5
Where the paper says it

• 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.

750, 1.755] with a margin of 0. p. 5
Where the paper says it

02328, and at K = 2000 the last cell, [1. 755], with margin 0.

00476 <ref:2609. p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

29894#pg4>. The proof concludes that v is strictly decreasing on the union of these certified intervals <ref:2609. p. 5
Where the paper says it

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.

29894#pg6>. The result is partial, not reaching m = 2. p. 1
Where the paper says it

[2025]; the new part is (1. The result is partial: it does not reach m = 2.

5 <ref:2609. p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

29894#pg4>. The paper notes that the crude Lipschitz constant remains an obstacle to reaching m <ref:2609. p. 5
Where the paper says it

5) for a single offspring law. • The crude Lipschitz constant is the obstacle.

29894#pg4>. The code and certificates are public <ref:2609. p. 0
Where the paper says it

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.

29894#pg6>.> 1, 5, 7, 8, 10">B <ref:2609.29894#pg4> <ref:2609. p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

29894#pg6> <ref:5</ref>
B <ref:7</ref>**

**

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

Where the paper says it

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.

29894#pg6>. After each application of Tλ, the image of every lattice value is rounded up or down to the grid <ref:2609. p. 3
Where the paper says it

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.

29894#pg6>. Rounding decisions are made in floating point only when the computed position is at least 10−9 from a grid point, and otherwise in exact rational arithmetic <ref:2609. p. 3
Where the paper says it

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.

29894#pg6>. The masses are propagated using direct convolution, and the cumulative distribution function is shifted in the safe direction by a relative 10−10 plus an absolute 10−10 to control rounding errors <ref:2609. p. 3
Where the paper says it

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).

29894#pg6>.

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

Where the paper says it

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

29894#pg6>. The method leverages pathwise Lipschitz bounds and stochastic-order envelopes for the law of β <ref:2609. p. 5
Where the paper says it

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

29894#pg6>. The final verification involves checking one inequality per cell using exact rational arithmetic. p. 1
Where the paper says it

Each λ-cell is then one inequality between two numbers, checked in exact rational arithmetic. Everything except the per-cell arithmetic is proved by hand.

Limitations

The limitations identified include a partial range covering [0, 1.755] of [0, 2. p. 0

Where the paper says it

We prove, with computer assistance, that v is strictly decreasing on [0, 1. 755] for this law.

5) <ref:2609. p. 0
Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

29894#pg4>. The crude Lipschitz constant remains an obstacle to reaching m <ref:2609. p. 5
Where the paper says it

5) for a single offspring law. • The crude Lipschitz constant is the obstacle.

29894#pg4>. Floating-point arithmetic is used for per-cell calculations, and the interval-arithmetic re-check only covers five cells, not every cell. p. 5
Where the paper says it

• 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.

Furthermore, reaching m requires distributional control of the derivative of β <ref:2609. p. 5
Where the paper says it

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.

29894#pg4>.

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

Where the paper says it

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] <ref:2609.29894#pg4>. 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 arithmetic. p. 5
Where the paper says it

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

References

<ref:2609.29894#pg4> **

<ref:2609.29894#pg6> B B **

<ref:2609.29894#pg4> B</ref:2609. p. 0

Where the paper says it

ai † sandeep@samyama. ai 1 arXiv:2609.

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

  1. 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.

  2. 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.

  3. 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

Related papers