We prove the Lyons-Pemantle-Peres conjecture for high enough offspring laws, that is we show that the speed satisfies ℓ′(λ)<0 for the entire transient regime of the bias λ∈(0,m) in the special case that the number of children Z in the Galton-Watson tree satisfies Z≥4 almost surely.
Introduction
Let Z be a N={1,2,…} valued random variable and denote by T the corresponding (leafless) Galton-Watson tree having Z as the offspring law at each vertex v and call the resulting law of T as P. On this random environment, we then introduce a random walk (ξkλ)k∈N0 starting at the root ϱ of T, and which follows the following transition probabilities for each vertex v of T which is not the root ϱ:
Here λ∈R≥0 is called the bias parameter, indicating the bias to return to the parent nodes during the random walk. Going from the quenched law Pλ,T, we write for the annealed probability measure
(P∘(T,ξλ)−1)(dτ,dx)=P(dτ)Pλ,τ(dx).
Here we model everything on one probability space (Ω,F,P) furnishing T,ξλ and any additional random variables as needed on the fly. One can prove that for λ∈(0,m) with m:=EZ, the asymptotic speed
ℓ(λ):=k→∞limk∣ξkλ∣
exists and is deterministic P-a.s. [5 Theorem 3.1 + Section 4]. Given this context, we are going to prove the following.
Theorem 1.1 Let Z be such that Z≥4 almost surely and m=EZ<∞. Then ℓ:(0,m)→R≥0 is differentiable and
∀λ∈(0,m):ℓ′(λ)<0.
In recent years variants of Theorem 1.1 have been treated, providing partial resolutions to the Lyons-Pemantle-Peres monotonicity conjecture [6]. We mention for example [AFS11] and [SWX25], where ℓ′(λ)<0 was shown for λ≤1160m1 and λ≤1+1−m11m1 respectively, with m1=min{k≥1:P(Z=k)>0}. Our advance is the extension to the entire transient regime λ∈(0,m), albeit at the cost of requiring high offspring laws Z≥4. With similar techniques as presented in this note, it is possible to prove Theorem 1.1 for the less restrictive case Z≥2. In the interest of clarity we refrain from doing so here, as this requires just lengthier arguments that are merely technical in nature which nonetheless don’t appear to be sufficient yet to resolve the Z≥1 case.
To comment on the main technical concept appearing in the proof, recall the tree-dependent escape probability
Xλ(T)=P(ξλ never returns to ϱ∗∣T)=Pλ,T(ξ never returns to ϱ∗).
Here, ϱ∗ is an artificial parent of the root ϱ, and the random walk (ξkλ) starting at ϱ on the extended tree T∗ is similarly defined as the ordinary random walk on T, resulting though in the same speed ℓ(λ) as in the original random walk [SWX25, Lemma 1] for λ∈(0,m). Calling the law of Xλ under P as μλ, we recall the nonlinear fixed point equation satisfied by the law μλ expressed via Xλ and Z as
Xλ=dλ+∑i=1ZXλ,i∑i=1ZXλ,i,(1)
where Xλ,i are i.i.d. with law μλ, and equality is in distribution under P. This equation (1) is explicitly mentioned for example in [2 Section 13.3.3], but can essentially be traced back to [4, 5]. Whereas [SWX25] now differentiates in a pathwise sense the random variable Xλ in (1)1, we differentiate the law μλ, and thus derive the linearized equation around a given λ for a measure Γλ, resulting in an instance of the Dyson equation
Γλ=σλ+TλΓλ.(2)
Let us elaborate more in an informal manner how to arrive at (2). For every test function f, we can write (1) as an explicit fixed point equation for μλ:
∫f(x)dμλ(x)=n∑pn∫f(λ+∥x∥1∥x∥1)dμλ⊗n(x)(3)
where pn=P(Z=n) and ∥x∥1=x1+⋯+xn. We want to study now the first order change to μλ when λ↦λ+ε, that is, we linearize μλ+ε≈μλ+εμ˙λ. Plugging into (3), to order ε, we get easily the equation satisfied by μ˙λ:
where Fλ(x)=μλ((−∞,x]). This terminology is chosen, as it resembles the continuity equation from fluid dynamics ∂tϱ+∇vϱ=0, with Γλ representing the ‘velocity field’ in this context. This is to say, that it is more natural to formulate (4) in terms of Γλ than with μ˙. Hence, with formal integration by parts
∫f(x)μ˙(dx)=∫f(x)∂xΓλ(dx)=−∫f′(x)Γλ(dx),
we arrive at, by calling the measure arising in the first term of (4) as σλ,
As this holds for every f nice enough, we can read off the operator Tλ and arrive at (2).
This entire preprocessing step lets us eventually express the derivative ℓ′(λ) in a way where its sign can be easily read off from evaluations of some bilinear form on explicit measures related to μλ and Γλ.
Notation: We will frequently use Xλ(T) as the escape probability of the random walk on a given tree T starting at the root. We will drop T though from the notation. Furthermore, many of the appearing objects Xλ,μλ,Qλ,Tλ will be dependent on λ, however for legibility’s sake, inside the proofs we will often drop the subscript λ.
A formula for the speed ℓ′(λ)
We first recall from Aidekon [Aïd14] and Rousselin [8] the formula for the speed
ℓ(λ)=BλAλ,(5)
with
Aλ:=EDλ(X,Y)XY,Bλ:=EDλ(X,Y)X+Y−XY,
where Dλ(x,y)=λ−(1−x)(1−y). Here X,Y are i.i.d and X∼μλ=LawP(Xλ). It turns out that for the technical details appearing later on, it is very convenient to have knowledge of where μλ is supported, since this gives control on the kernel Dλ.
Lemma 2.1 For any offspring law such that Z≥4, it holds that
Xλ≥(1−4λ)+,P-a.s.
and hence suppμλ⊂[(1−4λ)+,1]. As a consequence, we get two-sided bound on the kernel Dλ when sampling from the distribution μλ:
∀x,y∈suppμλ:43λ≤Dλ(x,y)≤λ(6)
Proof. This is a special case of [SWX25, Lemma 3], applied to m1:=inf{n≥1:P(Z=n)>0}≥4, with (6) an immediate computation.
It will be useful to introduce short-hand notations for the following sets of measures
M:={ν∣ν is signed measure on ([0,1],B([0,1]))}
Mλ:={ν∈M∣suppν⊂[(1−λ/4)+,1]}
M+:={ν∈M∣ν≥0}
Mλ+:=Mλ∩M+.
The introduction of signed measures in this context is natural, as we recall from the introduction that we study a family of probability measures {μλ}λ and their linearization μλ+ε≈μλ+εμ˙, from which it follows that μ˙([0,1])=0, hence μ˙ is in general signed.
Definition 2.2 Fix λ∈(0,m). We let T=Tλ be a linear operator mapping
where Sk=∑i=1kXλ,i with Xλ,i are i.i.d. with law μλ. We record two immediate properties about T.
Lemma 2.3
Tλ is a positive linear operator, that is η≥0⇒Tλη≥0. Furthermore, η∈Mλ⇒Tλη∈Mλ.
Tλ is bounded in the total variation norm, that is ∥Tλη∥TV≤λm∥η∥TV for any signed measure η∈M.
Proof. The first part follow from straightforward inspection of the definition of T; boundedness of the total variation norm follows by the characterization ∥ν∥TV=supf:∣f∣≤1∫fdν.
Eventually we want to differentiate Aλ and Bλ with respect to λ. As Xλ is dependent on λ, the prototypical quantity which we need to differentiate is Ef(Xλ)=∫f(x)dμλ(x). We establish first, that in a suitable way the law μλ is differentiable with ‘derivative’ Γλ. More precisely:
Proposition 2.4 Let λ∈(0,m).
There exists a unique positive measure Γλ∈Mλ+ satisfying the fixed point equation
Γλ=σλ+TλΓλ,(7)
where σλ(dx)=x(1−x)μλ(dx).
The measure Γλ is the derivative of μλ in the sense that for all f∈C1[0,1], the map λ↦∫fdμλ is differentiable and
dλd∫f(x)dμλ(x)=λ1∫f′(x)dΓλ(x).(8)
In order to prove Proposition 2.4 the following bilinear operator will prove useful.
Definition 2.5 For fixed λ∈(0,m) we define the mapping
Qλ:Mλ×Mλ→R
(η,ζ)↦∫Dλ(x,y)2λη(dx)ζ(dy).
Because of the kernel bounds (6) on Dλ, Qλ is well-defined and it immediately follows that for positive measures η,ζ∈Mλ+:
λ1∥η∥TV∥ζ∥TV≤Qλ(η,ζ)≤9λ16∥η∥TV∥ζ∥TV.(9)
We will also need a simple technical lemma about the interplay of Q and T and some explicit evaluations of the latter.
Lemma 2.6 It holds
The linear operator Tλ is symmetric with respect to Qλ, that is for any signed measures η,ζ∈Mλ
Qλ(Tλη,ζ)=Qλ(η,Tλζ).(10)
Introducing the measures αλ,σλ≪μλ as
αλ(dx)=xμλ(dx),σλ(dx)=x(1−x)μλ(dx),
they satisfy
Tα=σ,(11)
Proof. Symmetry of T with respect to Q, that is (10), follows directly by plugging in the definitions in each other:
where in the penultimate equality we used the fixed point of the law of X from (1).
This suffices to proof the first part of Proposition 2.4.
Proof of 1. of Proposition 2.4. As usual we split the existence and uniqueness part of the proof.
Existence: We let ΓN:=∑i=0NTiσ and aim to show convergence for N→∞. To this end, first note that as σ≥0, by positivity of T and induction ΓN≥0. The trick now is to observer that α−σ is a positive measure due to α−σ=x2μ(dx)≥0 and compute
It follows that the sequence of positive measures (ΓN)N∈N on [0,1] is Cauchy in (M,∥⋅∥TV) and we denote the limit by Γ:=limN→∞ΓN. It is immediately seen that Γ∈Mλ+, and by continuity of T by Lemma 2.3 we get
TΓ=N→∞limTΓN=N→∞lim(ΓN+1−σ)=Γ−σ.
Uniqueness: Let Γ∈Mλ+ another positive measure satisfying the fixed point equation. Then for any N≥1 we get
Γ==ΓN(σ+…TNσ)+≥0TN+1Γ≥ΓN.
Hence taking limits we get Γ≥Γ. So we apply (9) to Γ−Γ, α−σ≥0 and use again symmetry of T with respect to Q and Tα=σ:
where the penultimate equality is by the fact that T(Γ−Γ)=Γ−Γ. Thus we get ∥Γ−Γ∥TV=0.
Remark 2.7
Intuitively any Γ satisfying (7) should be of the form Γ=σ+Tσ+T2σ+…, so one would be tempted to construct Γ via some Neumann series ∑kTk. Unfortunately, the operator norm of T is only guaranteed to be bounded by λm≥1, which is the reason for the above proof.
One can attach a probabilistic meaning to Γλ in the following way. We formally differentiate (1) to get
where vi is the i-th child of v. It turns out that (13) can be given a meaning in terms of a stopping time τ(v) of an auxiliary random walk on the given Galton Watson tree T. This auxiliary random walk is defined via transition probabilities at vertex v as
(a) with probability Xλ(v) it becomes extinct.
(b) with probability 1−Xλ(v) it moves to one of the children of vi, each with probability SλXλ(vi).
With respect to this construction, let τ(v) be the stopping time until extinction of a random walk started at the vertex v. We can immediately see by a first step analysis that
Thus we have rederived the Dyson series Γ=σ+Tσ+⋯ in a purely probabilistic manner. It is also worthwhile to note that the analytic convergence question of ΓN can be answered (with a bit more work to make the previous steps fully rigorous) by the probabilistic statement of (the weighted) integrability of the existence time τ of the auxiliary process:
∥Γλ∥TV=E[Xλ(ϱ)τ(ϱ)]<∞.
To prove the second part, we will need a technical lemma showing a certain Lipschitz continuity in law:
Lemma 2.8 For any u,v≥0 such that [u,v]⊂(0,m) there exists a constant Cu,v>0 such that
E[Xa−Xb]≤Cu,v(b−a)
uniformly in a,b with u≤a<b≤v.
Proof. See Lemma A.1.
Proof of 2. of Proposition 2.4. Let f∈C1([0,1]). For a,b∈(0,m) with a<b one gets using Xa≥Xb (pathwise for every fixed tree by an application of Rayleigh’s monotonicity principle [7 Section 2.4]), that
f(Xb)−f(Xa)=−∫[0,1]1[Xb,Xa](y)f′(y)dy,
and hence by taking the expectation we get the finite difference equation:
by Lemma 2.8. Hence, by Rademacher’s theorem, for Lebesgue almost every λ∈(0,m) the map λ↦Ef(Xλ) is differentiable. By the usual arguments, for Lebesgue almost every a∈(0,m), for every rational coefficient polynomial f the following exists
dλdEf(Xλ)λ=a∈R.
For further readability, call PQ⊂C([0,1]) the countable set of rational coefficient polynomials and N⊂(0,m) the exceptional set of Lebesgue measure zero.
Take any a∈(0,m)\N and choose a sequence bn↓a. Looking at the positive measure Ra,b, we get immediately by Lemma 2.8
Moving on to show the fixed point equation, we again note that Xλ=λ+∑i=1ZXλ,i∑i=1ZXλ,i in distribution, that is, for any λ∈(0,m) and f∈PQ we have
where pn=P(Z=n) and φλ,n:y↦f(λ+∥y∥1∥y∥1). Here we can write again ∥y∥1=y1+⋯+yn since y∈[0,1]n. We can differentiate this fixed point equation at λ∈(0,m)\N to get
and hence summing over n yields directly ∫f′(x)dσλ(x). The second term is already in the form of the operator T and so we are done. Hence we arrive at
∫f′dΓλ=∫f′dσλ+∫f′d(TΓλ),
and as f∈PQ and the polynomials are dense in C([0,1]), we get Γλ=σλ+TΓλ. By uniqueness of the fixed point equation (7), we get Γa=Γa for any a∈(0,m)\N.
Finally we want to upgrade the convergence result. So fix f′∈PQ. From the previous steps we know that λ↦Ef(Xλ) is locally Lipschitz continuous and so on every compact interval [a,b]⊂(0,m) it is absolutely continuous. As such, by Lebesgue’s fundamental theorem of calculus, for any a,b∈(0,m):
where the last equality comes from the almost everywhere equivalence. Using the fact that λ↦Γλ is weakly continuous by Lemma A.3, we know that λ↦−λ1∫f′(y)Γλ(dy) is continuous, and hence the right-hand-side is equivalent to the Riemann integral. Hence, by the fundamental theorem of calculus
∀λ∈(0,m):dλdEf(Xλ)=−λ1∫f′(y)Γλ(dy).
Now it is straightforward to extend the argument to f∈C1([0,1])⊂PQ∥⋅∥∞.
Having established the derivative formula (8), we record in passing that it is not difficult to show (using weak continuity of λ↦μλ from Lemma A.3) that for f:(0,m)×[0,1]n→R continuously differentiable, we have the formula2
even though Hλ/Dλ is not C1 on (0,m)×[0,1]2, we can easily remedy this fact by noting that μλ has restricted support on which 1/Dλ is C1, so the usual argument with smooth bump functions does the job. we arrive at
Having established (17), we can now quite straightforwardly prove Theorem 1.1. We start with a technical bound on ℓ(λ) which is independent of the assumption on the offspring law of Z≥4.
Lemma 3.1 For λ∈(0,m) it holds that
ℓ(λ)≤2−EXλEXλ.(18)
Proof. The observation we use is that
Aλ=E[Dλ(X,Y)XY]≤E[Y]E[Dλ(X,Y)X].(19)
Indeed, the function r:y↦EDλ(X,y)X=Eλ−(1−X)(1−y)X is monotonically decreasing, hence we have for any random variables Y,Z that
(Y−Z)(r(Y)−r(Z))≤0.
Hence taking in particular Y,Z i.i.d. and distributed according to μλ, we get by taking expectation values the desired inequality (19). Finally, by definition we have
Having established now this bound on the speed ℓ we come now to the proof of Theorem 1.1. The point is that we can lower-bound very crudely each of the appearing terms inside of (17):
Proof of Theorem 1.1. We start by inspecting the formula (17) and note that as Qλ(σλ,σλ)≥0 we are done the moment we can show that the sign of Qλ(Ωλ,wλ) is (strictly) positive as well. Explicitly we can write
Here in the second inequality we used (18) and in the last inequality the elementary inequality 2−x1−x≥21. Since Ωλ is a positive measure by Lemma A.4, we obtain that Qλ(Ωλ,wλ)>0 and hence that −λ2Bλℓ′(λ)>0 and so the theorem follows, as λ2Bλ>0.
Some technical lemmas
We collect some lemmas that were used, which are technical in nature and use often just a slight (but tedious) variant of arguments already presented in the main text.
Lemma A.1 For any u,v≥0 such that [u,v]⊂(0,m) there exists a constant Cu,v>0 such that
E[Xa−Xb]≤Cu,v(b−a)
uniformly in a,b with u≤a<b≤v.
Proof. We fix such u,v as in the assumption and choose some a,b with u≤a<b≤v. We will now define depending on a,b analogous objects to Q, T and α, σ as follows. First we set
Da(x,x′)=a−(1−x)(1−x′),Db(y,y′)=b−(1−y)(1−y′).
The symmetric bilinear form Qa,b we set as
Qa,b:Ma,2×Mb,2→R
(η,ζ)↦∫Da(x,x′)Db(y,y′)abη(dx,dx′)ζ(dy,dy′).
Here, Mλ,2={ν∣suppν⊂[(1−λ/4)+,1]2}. We get similar to (9), that for positive measures η∈Ma,2+, ζ∈Mb,2+:
v1∥η∥TV∥ζ∥TV≤Qa,b(η,ζ)≤9u16∥η∥TV∥ζ∥TV.(20)
as well as an operator Ta,b:M→M defined via actions on test functions f∈C([0,1]2) as
This map Ta,b has analogous properties as in Lemmas 2.3 and 2.6, in particular it is a positive linear operator symmetric with respect to Qa,b, that is for η∈Ma,2, ζ∈Mb,2
Qa,b(Ta,bη,ζ)=Qa,b(η,Ta,bζ).
We introduce furthermore
μa,b=LawP(Xa,Xb),
as well as
αa,b(dx,dy)=(ax+by)μa,b(dx,dy),
σa,b(dx,dy)=(bx(1−y)+ay(1−x))μa,b(dx,dy).
We can check by similar arguments as before that
Ta,bαa,b=σa,b.
Finally we define
Γa,b(dx,dy)=b−ax−yμa,b(dx,dy).
We can now by straightforward algebraic manipulations check that in fact
Γa,b=σa,b+Ta,bΓa,b.
Now we have done enough preprocessing to obtain a bound on ∥Γa,b∥TV. In fact, the procedure will be mimicking again the main text. That is, we note that αa,b−σa,b is positive:
Proof. We evaluate the derivative by taking the limit of the finite difference quotient along a specific sequence λk↓λ for which we know that Rλ,λk⇀Γλ. Without loss of generality this sequence will be contained in some compact interval (λk)k⊂[u,v]⊂(0,m). That is we form
Here we used Lemma 2.8 to obtain the very last inequality. Hence we see that the map n↦In is pointwise bounded by a function which is integrable:
n∑pn(1+nCu,v)u∥f′∥∞=(1+Cu,vEZ)u∥f′∥∞<∞
Thus by dominated convergence theorem we have
k→∞limn∑pnIn(λ,λk)=n∑pnk→∞limIn(λ,λk),
granted that the pointwise limit limkIn(λ,λk) exists. This we will show now. For In(1) this is quite straightforward, since μλk⇀μλ and λk−λφλk,n−φλ,n→∂λφλ,n uniformly as f∈C1([0,1]). Hence
k→∞limIn(1)(λ,λk)=∫∂λφλ,ndμλ⊗n.
For In(2) we extract from the telescoping sum with the fundamental theorem of calculus and the independence of Xλk,1,…,Xλ,n:
The last equality follows from the fact that φλ,n factors through y↦∥y∥1 which is permutation invariant. This concludes the proof.
Lemma A.3.We have
λ↦μλ,(0,m)→M+ is weakly continuous.
λ↦Γλ,(0,m)→M+ is weakly continuous.
Proof. 1. It easy to see that by the Lipschitz continuity of Lemma 2.8, and the fact that Lipschitz continuous functions are dense in C([0,1]), that we have λ↦μλ is weakly continuous.
Let λn→λ. To prove Γλn⇀Γλ we use the usual subsequence argument. So let (λn)n be any subsequence of the original sequence3. First, note that by (12) and Jensen’s inequality, we get a uniform in λ bound
Hence, by tightness, we can extract a subsequence such that (Γλnk)k converges weakly in M+, and denote its limit by Γλ=w−limk→∞Γλnk. Now for every k it holds
Γλnk=σλnk+TλnkΓλnk.
As clearly λ↦σλ is weakly continuous, all that remains is to compute the weak limit of TλnkΓλnk. To this end, let f∈C([0,1]) and compute ∫fdTλnkΓλnk. We denote by Φλ=Φλ(m,f)∈C([0,1]m;R) the function such that
∫fdTλΓλ=m=4∑∞mpm∫Φλd(Γλ⊗μλ⊗(m−1)).
Explicitly, Φλ(x,y1,…,ym−1)=λ+x+∑iyiλf(λ+x+∑iyix+∑iyi). Since ∥Φλnk−Φλ∥∞→0 and Γλnk⊗μλnk⊗(m−1)⇀Γλ⊗μλ⊗(m−1) it is easy to see that for every fixed m∈N:
where u>0 is some lower bound such that for all n∈N: λn>u which we can assume without loss of generality. This, combined with the bound on ∥Γλ∥TV, yields the following uniform in λnk bound
The right-hand-side tends to 0 for N→∞ as EZ=m<∞, and hence we can interchange limit taking over λnk→λ and summing over m∈N. Therefore TλnkΓλnk⇀TλΓλ, and thus
Γλ=σλ+TλΓλ,
from which, by Γλ∈M+ and uniqueness follows Γλ=Γλ. So by the subsequence argument, we have proven that Γλn⇀Γλ.
Lemma A.4.The measureΩλis positive.Proof. Since Ωλ=σλ−(1−λ)Γλ, and σλ,Γλ≥0, positivity is clear when λ∈[1,m). So let λ∈(0,1). Then observe that
Now for λ<1 one sees that with (λα−σ)(dx)=x(λ−(1−x))μ(dx), that as suppμλ⊂[(1−λ/4)+,1], the elementary inequality
x+(λ−1)≥1−λ/4+(λ−1)=43λ>0
yields λα−σ≥0. As T is a positive operator, positivity of Ωλ follows.
Acknowledgements
Acknowledgements. FS is funded by the European Research Council (ERC) under the European Union’s Horizon 2020 research and innovation programme (Grant agreement No. 101045082), funded also by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s Excellence Strategy EXC 2044/2 –390685587, Mathematics Münster: Dynamics–Geometry–Structure, and has been supported by the Research Training Group “Rigorous Analysis of Complex Random Systems” (RTG 3027) funded by the DFG (Project Number 524444762). The author is grateful to Jan Nagel for helpful discussions and for first bringing this theorem to their attention.
Tool usage statement. OpenAI’s ChatGPT 6 Astra was used during the initial stages of this work. The proof in its final form was developed by the author, who takes full responsibility for all claims and arguments made in the paper.
References
[2]D. Aldous and J. Fill. Reversible markov chains and random walks on graphs. 2002.
[4]R. Lyons, R. Pemantle, and Y. Peres. Ergodic theory on galton–watson trees: speed of random walk and dimension of harmonic measure. Ergodic Theory and Dynamical Systems, 15(3):593–619, 1995.DOI
[5]R. Lyons, R. Pemantle, and Y. Peres. Biased random walks on galton–watson trees. Probability theory and related fields, 106(2):249–264, 1996.DOI
[6]R. Lyons, R. Pemantle, and Y. Peres. Unsolved problems concerning random walks on trees. In Classical and Modern Branching Processes, pages 223–237. Springer New York, 1997.DOI
[7]R. Lyons, Y. Peres, and Y. Peres. Probability on trees and networks, volume 42. Cambridge University Press, Cambridge, 2016.DOI
[8]P. Rousselin. Invariant measures, hausdorff dimension and dimension drop of some harmonic measures on galton–watson trees. Electronic Journal of Probability, 23(46):1–31, 2018.arxiv.org/abs/1708.06965