1. Introduction
In this paper, we investigate the properties of biased random walks denoted as
$\mathit{RW}_{\lambda}$
on Galton–Watson trees
$\mathbb{T}$
. We focus our attention on the following inquiry: Is the speed of
$\mathit{RW}_\lambda$
monotonic non-increasing as a function of its bias
$\lambda$
when the Galton–Watson tree has no leaves?
Let
$\mathbb{T}$
denote a Galton–Watson tree with the root e,
$\nu$
represent the offspring distribution with
$m=\mathbb{E}(\nu)>1$
. Denote the associated probability space as
$(\Omega, \mathbb{P})$
. Note that
$\mathbb{T}$
is super-critical and the extinction probability
$q=\mathbb{P}[\mathbb{T}\ \mbox{is finite}]<1$
. Let
$\nu(x)$
denote the number of children of a vertex
$x\in \mathbb{T}$
. For any
$x\in\mathbb{T}\setminus\{e\}$
, let
$x_{\ast}$
be the parent of x, which refers to the neighbor of x that lies on a geodesic path from x to e. We write xi,
$1\leq i\leq \nu(x)$
, as the children of x.
For any
$\lambda\geq 0$
, a
$\lambda$
-biased random walk
$\mathit{RW}_{\lambda}$
,
$(X_n)_{n=0}^{\infty}$
, on the Galton–Watson tree
$\mathbb{T}$
is defined as follows. The transition probability from x to an adjacent vertex y is
\[ p(x,y) = \left\{ \begin{array}{c@{\quad}l} \dfrac{1}{\nu(x)} \quad & \mathrm{if}\ x=e, \\[3pt] \dfrac{\lambda}{\lambda+\nu(x)} \quad & \mathrm{if}\ y=x_{\ast},\ x\neq e, \\[3pt] \dfrac{1}{\lambda+\nu(x)} \quad & \mathrm{otherwise}. \end{array} \right.\]
$(X_n)_{n=0}^{\infty}$
is a reversible Markov chain for
$\lambda > 0$
. Let
$\mathbf{P}_x$
be the quenched probability of
$\mathit{RW}_{\lambda}$
starting at x and
$\mathbb{P}_x$
the annealed probability obtained by the semi-direct product
$\mathbb{P}_x=\mathbb{P}\times \mathbf{P}_x$
. Denote the respectively associated expectations by
$\mathbf{E}_x$
and
$\mathbb{E}_x$
. A motivation for the introduction of
$\mathit{RW}_\lambda$
on trees is its ability to obtain almost uniform samples from the set of self-avoiding walks of a given length on a lattice [Reference Berretti and Sokal6]. For further insights into the motivations for biased random walks on graphs, see the existing surveys [Reference Ben-Arous and Fribergh3, Reference Lyons, Pemantle and Peres12].
On a general tree, [Reference Lyons8] showed that there exists a critical parameter
$\lambda_{\mathrm{c}}$
for
$\mathit{RW}_{\lambda}$
, where
$\lambda_{\mathrm{c}}$
is equal to the exponential of the Hausdorff dimension of the tree boundary. It was found that
$\mathit{RW}_\lambda$
exhibits transient behavior for
$\lambda < \lambda_{\mathrm{c}}$
and recurrent behavior for
$\lambda > \lambda_{\mathrm{c}}$
. It was also proved that, for almost every Galton–Watson tree conditioned on non-extinction,
$\mathrm{RW}_{\lambda}$
is transient for
$0\leq \lambda < m$
. In [Reference Lyons9], it was shown that, conditional on non-extinction,
$\mathit{RW}_{m}$
is null recurrent, while
$\mathit{RW}_\lambda$
is positive recurrent for
$\lambda > m$
.
Let
$\vert x\vert$
be the graph distance between x and e for any vertex
$x\in \mathbb{T}$
. Note that
$\vert x\vert$
is also the generation of x. Fix
$X_0=e$
. The speed
$\ell_\lambda$
of
$\mathit{RW}_\lambda$
is defined as the almost sure limit, if it exists, of the ratio
${|X_n|}/{n}$
as
$n\rightarrow \infty$
. In this paper, the dependence of
$\ell_\lambda$
with respect to the environment will often be omitted. A transient
$\mathit{RW}_\lambda$
may exhibit zero speed when an excessive amount of time is allocated to the leaves. In [Reference Lyons, Pemantle and Peres11], it was proved that, conditional on non-extinction,
$\ell_\lambda$
exists almost surely and
$\ell_{\lambda}$
is deterministic and positive if and only if
$\lambda\in(\mathbb{E}(\nu q^{\nu-1}),m)$
. From [Reference Lyons, Pemantle and Peres10],
$\ell_1=\mathbb{E}(({\nu-1})/({\nu+1}))$
. An expression for
$\ell_\lambda$
, shown in (1), was specified in [Reference Adékon2], though an artificial parent to e was added there. For related results, see [Reference Gantert, Müller, Popov and Vachkovskaia7].
The following problem was raised in [Reference Lyons, Pemantle and Peres11] (see also [Reference Lyons, Pemantle and Peres12]), and was called the Lyons–Pemantle–Peres monotonicity problem in [Reference Ben-Arous, Fribergh and Sidoravicius4].
Problem 1.
([Reference Lyons, Pemantle and Peres11].) Assume
$\mathbb{P}(\nu=0)=0$
, namely that the Galton–Watson tree
$\mathbb{T}$
has no leaf, meaning that the extinction probability
$q=0$
. Is the speed
$\ell_\lambda$
of
$\mathit{RW}_{\lambda}$
on
$\mathbb{T}$
monotonic non-increasing in
$\lambda\in [0, m)$
?
It was conjectured in [Reference Lyons, Pemantle and Peres11, Reference Lyons, Pemantle and Peres12] that Problem 1 should have a positive answer. If we consider general trees, monotonicity does not hold. Moreover, we should notice that speed might not exist on general trees. For instance, on a binary tree with pipes (a binary tree to every vertex of which is joined a unary tree), which is a multi-type Galton–Watson tree, the speed is
${(2-\lambda)(\lambda-1)}/({\lambda^2+3\lambda-2})$
for
$1\leq \lambda\leq 2$
[Reference Lyons, Pemantle and Peres12]. For any
$0<\lambda_1<\lambda_2$
, by the repeated filtering method we can produce a tree such that the speed of
$\mathit{RW}_{\lambda_1}$
is less than that of
$\mathit{RW}_{\lambda_2}$
[Reference Lyons, Pemantle and Peres12]. Notice that these examples are not Galton–Watson trees and show the complexity of Problem 1. Therefore, the monotonicity of
$\ell_\lambda$
would represent a highly significant and fundamental characteristic of Galton–Watson trees.
The Lyons–Pemantle–Peres monotonicity problem for Galton–Watson trees without leaves was proven to have a positive solution for
$\lambda\leq{m_1}/{1160}$
in [Reference Ben-Arous, Fribergh and Sidoravicius4], where
$m_1=\min\{k\geq 1\,\colon P[\nu=k]>0\}$
is the minimal degree of the Galton–Watson tree. This result was improved in [Reference Adékon1] to
$\lambda\leq \frac{1}{2}$
by a completely different approach. In [Reference Ben-Arous, Hu, Olla and Zeitouni5], the Einstein relation was obtained for
$\mathit{RW}_{\lambda}$
on Galton–Watson trees, which implies that Problem 1 holds in a neighborhood of m. These slow advances indicate that Problem 1 is rather difficult. For more information on
$\mathit{RW}_\lambda$
on
$\mathbb{T}$
, see [Reference Ben-Arous and Fribergh3, Reference Lyons, Pemantle and Peres12] and references therein. For the monotonicity of the speed of biased random walks on groups, see [Reference Song, Wang, Xiang and Zang14, Reference Song and Xiang15].
The main result of our study is presented as follows.
Theorem 1. The speed
$\ell_\lambda$
of
$\mathit{RW}_{\lambda}$
on a Galton–Watson tree
$\mathbb{T}$
without leaves is strictly decreasing in
$\lambda\in[0,{m_1}/({1+\sqrt{1-{1}/{m_1}}})]$
when
$m_1\geq 2$
.
2. Proof of Theorem 1
Inspired by [Reference Adékon1], based on some new observations, we prove Theorem 1. Let
$\mathbb{T}_{\ast}$
be the tree obtained from
$\mathbb{T}$
by adding an artificial parent
$e_{\ast}$
to the root e. For any vertex
$x \in \mathbb{T}_{\ast}$
, let
$\tau_x=\min\{n\geq 0, X_n=x\}$
, where
$\min \emptyset=\infty$
and
$(X_n)_{n=0}^\infty$
is a
$\lambda$
-biased random walk on
$\mathbb{T}_{\ast}$
. For
$x \neq e_{\ast}$
, let
$\beta(x)\,:\!=\,\beta(x,\lambda)=\mathbf{P}_x(\tau_{x_{\ast}}=\infty)$
be the quenched probability of never reaching the parent
$x_{\ast}$
of x when starting from x. Since
$\mathbb{T}$
has no leaf and
$\lambda < m$
, we have
$\beta(x)>0$
due to transience. Let
$(\beta_i)_{i\geq 0}$
be generic independent and identically distributed random variables distributed under
$\mathbb{P}$
as
$\beta(e)$
, and independent of
$\nu$
.
The following expression for
$\ell_{\lambda}$
was given in [Reference Adékon2]:
\begin{align} \ell_{\lambda} = \frac{\mathbb{E}\left( (\nu-\lambda) \beta_{0} / \left( \lambda-1+\sum_{i=0}^{\nu} \beta_{i}\right)\right)} {\mathbb{E}\left( (\nu+\lambda) \beta_{0} / \left( \lambda-1+\sum_{i=0}^{\nu} \beta_{i}\right)\right)}, \quad \lambda < m.\end{align}
Notice that (1) holds trivially when
$\lambda=0$
. In this context, it is important to note that
$\mathit{RW}_{\lambda}$
on
$\mathbb{T}_{\ast}$
and
$\mathit{RW}_\lambda$
on
$\mathbb{T}$
have a slight difference, but due to
$\lambda < m$
and transience these two biased random walks have the same speed when starting at e. Indeed, we have the following result.
Lemma 1. For
$\lambda < m$
,
$\mathit{RW}_{\lambda}$
on
$\mathbb{T}_{\ast}$
and
$\mathit{RW}_\lambda$
on
$\mathbb{T}$
have the same speed when starting at e.
Proof. Since the random walk on
$\mathit{RW}_{\lambda}$
$(X_n)_{n=0}^\infty$
on
$\mathbb{T}_{\ast}$
is transience, the edge
$ee_{\ast}$
(
$ee_{\ast}$
denotes the edge that connects the vertices e and
$e_{\ast}$
) can be visited only a finite number of times. We can define
$K=\sup\{n, X_n\not\in\{e,e_{\ast}\}\}$
, where K is finite. And
$\mathit{RW}_{\lambda}$
$(X_n)_{n=K+1}^\infty$
is a biased random walk on
$\mathbb{T}$
. This implies the lemma.
For the reader’s convenience, we provide a more detailed proof as follows.
For
$\mathit{RW}_\lambda$
$(X_n)_{n=0}^\infty$
on
$\mathbb{T}_{\ast}$
with
$X_0=e$
, define the following regenerative times [Reference Thorisson16]:
-
•
$\tau_0=0$
,
$\sigma_0=\inf\{n\geq\tau_0\,\colon X_n\not\in\{e,e_{\ast}\}\}$
; -
•
$\tau_1=\inf\{n\geq \sigma_0\,\colon X_n=e\}$
,
$\sigma_1=\inf\{n\geq\tau_1\,\colon X_n\not\in\{e,e_{\ast}\}\}$
when
$\tau_1<\infty$
; -
• for any
$i\geq 1$
,
$\tau_{i+1}=\inf\{n\geq \sigma_i\,\colon X_n=e\}$
,
$\sigma_{i+1}=\inf\{n\geq\tau_{i+1}\,\colon X_n\not\in\{e,e_{\ast}\}\}$
when
$\tau_{i+1}<\infty$
.
Since
$\mathit{RW}_\lambda$
$(X_n)_{n=0}^\infty$
is transient, there exists a unique
$\hat{\kern-1.5pt i}$
such that
$\tau_{\hat{\kern-1.5pt i}}<\infty$
and
$\tau_{\hat{\kern-1.5pt i}+1}=\infty$
. Define a random walk
$(Y_n)_{n=0}^{\infty}$
as follows:
\begin{equation*} (Y_n)_{n=0}^{\infty} = \big(X_{\tau_0}, \underbrace{X_{\sigma_0},\ldots,X_{\tau_1}}, \underbrace{X_{\sigma_1},\ldots,X_{\tau_2}}, \ldots, \underbrace{X_{\sigma_{\hat{\kern-1.5pt i}-1}},\ldots,X_{\tau_{\hat{\kern-1.5pt i}}}}, X_{\sigma_{\hat{\kern-1.5pt i}}}, X_{\sigma_{\hat{\kern-1.5pt i}}+1}, \ldots\big). \end{equation*}
It is evident that the sequence
$(Y_n)_{n=0}^{\infty}$
is just an
$\mathit{RW}_\lambda$
on
$\mathbb{T}$
starting at e. It is known that, almost surely, both
$\lim_{n\rightarrow\infty}({\vert Y_n\vert}/{n})$
and
$\lim_{n\rightarrow\infty}({\vert X_n\vert}/{n})$
exist and are deterministic. By construction, there exists a random function
$s({\cdot})$
on non-negative integers such that, almost surely,
$Y_n=X_{s(n)}$
,
$n\geq 1$
, and
$\lim_{k\rightarrow\infty}({s(k)}/{k})=1$
. Therefore, almost surely,
\[\lim_{n\rightarrow\infty}\frac{\vert Y_n\vert}{n}=\lim_{n\rightarrow\infty}\frac{\vert X_{s(n)}\vert}{n} =\lim_{n\rightarrow\infty}\frac{\vert X_{s(n)}\vert}{s(n)}=\lim_{n\rightarrow\infty}\frac{\vert X_{n}\vert}{n}.\]
This implies the lemma.
For any
$n\geq 1$
, let
$\beta_n(x)\,:\!=\,\beta_{n,\lambda}(x)$
denote the probability of hitting level n before
$x_{\ast}$
when
$\vert x\vert\leq n$
. Recall that, for a given vertex x, xi is its ith child and
$\nu(x)$
is the number of its children. Then
$\beta_n(x)=1$
if
$|x|=n$
and, for
$|x|<n$
,
\begin{equation*} \beta_n(x)=\frac{\sum_{i=1}^{v(x)}\beta_n(xi)}{\lambda+\sum_{i=1}^{v(x)}\beta_n(xi)}.\end{equation*}
Fix
$\lambda\in [0, m)$
, and consider the derivative of
$\beta_n(x)$
at
$\lambda$
; we have
\begin{align*} & \lim_{\lambda_1\rightarrow\lambda}\frac{\beta_{n,\lambda_1}(x)-\beta_{n,\lambda}(x)}{\lambda_1-\lambda} \\ & = \left(\frac{\sum_{i=1}^{v(x)}\beta_{n,\lambda_1}(xi)}{\lambda_1+\sum_{i=1}^{v(x)}\beta_{n,\lambda_1}(xi)}-\frac{\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)}{\lambda+\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)}\right)/(\lambda_1-\lambda) \\ & = \lim_{\lambda\rightarrow\lambda_1}\frac{\big(\lambda+\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)\big)\sum_{i=1}^{v(x)}\beta_{n,\lambda_1}(xi)-\big(\lambda_1+\sum_{i=1}^{v(x)}\beta_{n,\lambda_1}(xi)\big)\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)}{\big(\lambda_1+\sum_{i=1}^{v(x)}\beta_{n,\lambda_1}(xi)\big)\big(\lambda+\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)\big)}/(\lambda_1-\lambda) \\ & = \lim_{\lambda\rightarrow\lambda_1}\frac{\lambda\sum_{i=1}^{v(x)}\beta_{n,\lambda_1}(xi)-\lambda_1\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)}{\big(\lambda_1+\sum_{i=1}^{v(x)}\beta_{n,\lambda_1}(xi)\big)\big(\lambda+\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)\big)}/(\lambda_1-\lambda) = -\frac{\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)}{\big(\lambda+\sum_{i=1}^{v(x)}\beta_{n,\lambda}(xi)\big)^2}.\end{align*}
We can deduce that each
$\beta_n(x)$
has a continuous derivative in
$\lambda$
when
$|x|\leq n$
. Also,
$\beta_n(e)\downarrow\beta(e)$
as
$n\uparrow\infty$
, almost surely. To continue, we need Lemmas 2 and 3. For any natural number d, let
$\mathbb{T}_{d+1}$
denote the
$(d+1)$
-regular tree.
Let
$\mathbf{P}_x$
represent the probability measure of
$\mathit{RW}_\lambda$
starting at x on
$\mathbb{T}_{d+1}$
with a fixed root e, and
$\tau_{x_{\ast}}$
denote the hitting time of
${x_{\ast}}$
.
Lemma 2. For any
$\lambda\geq 0$
and any vertex
$x\in \mathbb{T}_{d+1}\setminus\{e\}$
with parent
${x_{\ast}}$
,
\[\mathbf{P}_x(\tau_{x_{\ast}}=\infty) = 1-\frac{\lambda\wedge d}{d}.\]
Proof. We can project the biased random walk on
$\mathbb{Z}$
as the tree is regular.
Let us analyze the meaning of
$\beta(e)$
within the framework of electric networks. Consider any weighted graph (say, an electric network)
$G=(V(G),E(G))$
with a non-negative edge weight function c (here the weights are called conductances). Suppose
$a\in V(G)$
and
$Z\subseteq V(G)$
. Write
$\mathbf{P}^{G,c}_a(a\rightarrow Z) = \mathbf{P}^{G,c}_a(\tau_Z< \tau_a^+)$
, where
$\tau_Z=\inf\{n\geq 0\,\colon X_n\in Z\}$
,
$\tau_a^+=\inf\{n\geq 1\,\colon X_n=a\}$
,
$(X_n)_{n\geq 0}$
is the random walk associated with electric network G, and
$\mathbf{P}^{G,c}_a$
is the law of
$(X_n)_{n\geq 0}$
starting at a. Let
$\pi(x)=\sum_{y\in V(G): y\sim x}c(\{x,y\})$
for all
$x\in V(G)$
, where
$y\sim x$
means y is adjacent to x. Then
$\pi({\cdot})$
is a stationary measure of
$(X_n)_{n\geq 0}$
. Call
$$\mathcal{C}_G(a\leftrightarrow Z)\,:\!=\,\mathcal{C}_{G,c}(a\leftrightarrow Z)=\pi(a)\mathbf{P}^{G,c}_a(a\rightarrow Z)$$
the effective conductance between a and Z. Note that
$\mathbb{P}^{G,c}_{a}(a\rightarrow \infty)=\mathbb{P}_a\{X_i\neq a\ \mathrm{for}\ i\geq 1\}$
. Then call
$$\mathcal{C}_G(a\leftrightarrow \infty)\,:\!=\,\mathcal{C}_{G,c}(a\leftrightarrow \infty)=\pi(a)\mathbf{P}^{G,c}_a(a\rightarrow \infty)$$
the effective conductance from a to
$\infty$
in G.
To emphasize the concentration on
$\mathbb{T}_\ast$
, denote
$\beta(e)=\beta(e,\lambda)$
by
$\beta_{\mathbb{T}_\ast}(e,\lambda)$
. When
$\lambda > 0$
, on
$\mathbb{T}_\ast$
endow any edge
$\{x,y\}$
where
$x,y\not=e_\ast$
with a weight
$\lambda^{-\vert x\vert\wedge\vert y\vert-1}$
, and the edge
$\{e_\ast,e\}$
with weight 1; denote this weight function by
$c_0$
. Then, for
$\lambda > 0$
, the
$\mathit{RW}_\lambda$
on
$\mathbb{T}_\ast$
is the random walk associated with the weighted graph (electric network)
$\mathbb{T}_\ast$
;
$$\beta_{\mathbb{T}_\ast}(e,\lambda)=\mathbf{P}^{\mathbb{T}_\ast,c_0}_{e_\ast}(e_\ast\rightarrow\infty)=\mathcal{C}_{\mathbb{T}_\ast,c_0}(e_\ast\leftrightarrow\infty).$$
Lemma 3. Assume the Galton–Watson tree
$\mathbb{T}$
has no leaf. Then, almost surely,
\[ 1-\frac{\lambda\wedge m_1}{m_1} \leq\beta_{\mathbb{T}_\ast}(e,\lambda)\leq 1-\frac{\lambda}{m_2}, \quad \lambda\in [0,m), \]
where
$m_2=\sup\{k\geq 1\,\colon P[\nu=k]>0\}$
.
Proof. When
$m_2=\infty$
,
$\beta(e)\leq 1-{\lambda}/{m_2}$
holds trivially. Clearly, the lemma holds true when
$\lambda=0$
, so we assume
$m_2<\infty$
(namely
$\nu$
takes finitely many values) and
$0 < \lambda < m$
. In a natural way, we can embed an
$m_1$
-ary tree
$\mathbb{H}^1$
into
$\mathbb{T}$
and also embed
$\mathbb{T}$
into an
$m_2$
-ary tree
$\mathbb{H}^2$
such that the roots of
$\mathbb{H}^1$
and
$\mathbb{H}^2$
are the root e of
$\mathbb{T}$
. Similarly to
$\mathbb{T}_{\ast}$
, let each
$\mathbb{H}^i_{\ast}$
be obtained from
$\mathbb{H}^i$
by adding the artificial parent
$e_{\ast}$
of e to
$\mathbb{H}^i$
.
Like the electric network
$(\mathbb{T}_\ast,c_0)$
, we endow each
$\mathbb{H}^i_\ast$
with a weight function
$c_i$
, and view
$c_0$
and
$c_1$
as functions on the set of edges of
$\mathbb{H}^2_\ast$
by letting
$c_0(\{x,y\})=0$
(
$c_1(\{x,y\})=0$
) when
$\{x,y\}$
is not an edge of
$\mathbb{T}_\ast$
(
$\mathbb{H}^1_\ast$
). Then
$c_1(\{x,y\})\leq c_0(\{x,y\})\leq c_2(\{x,y\})$
for any edge
$\{x,y\}$
of
$\mathbb{H}^2_\ast$
.
Notice that
\begin{align*} \beta_{\mathbb{T}_\ast}(e,\lambda) & = \mathbf{P}^{\mathbb{T}_{\ast},c_0}_{e_\ast}(e_{\ast}\rightarrow\infty) = \mathbf{P}^{\mathbb{H}^2_{\ast},c_0}_{e_\ast}(e_{\ast}\rightarrow \infty) = \mathcal{C}_{\mathbb{H}^2_\ast,c_0}(e_\ast\leftrightarrow\infty), \\ \beta_{\mathbb{H}^i_\ast}(e,\lambda) & = \mathbf{P}^{\mathbb{H}^i_\ast,c_i}_{e_\ast}(e_{\ast}\rightarrow \infty) = \mathbf{P}^{\mathbb{H}^2_{\ast},c_i}_{e_\ast}(e_{\ast}\rightarrow \infty) = \mathcal{C}_{\mathbb{H}^2_\ast,c_i}(e_\ast\leftrightarrow\infty), \quad i=1,2. \end{align*}
Recall Rayleigh’s monotonicity principle from [Reference Lyons and Peres13, Section 2.4]: Let G be an infinite connected graph with two non-negative edge weight functions c and
$c^\prime$
such that
$c\leq c^\prime$
everywhere. Then, for any vertex a of G,
$\mathcal{C}_{G,c}(a\leftrightarrow \infty)\leq \mathcal{C}_{G,c'}(a\leftrightarrow \infty)$
.
Therefore, we have
$\mathcal{C}_{\mathbb{H}^2_\ast,c_1}(e_\ast\leftrightarrow\infty) \leq \mathcal{C}_{\mathbb{H}^2_\ast,c_0}(e_\ast\leftrightarrow\infty) \leq \mathcal{C}_{\mathbb{H}^2_\ast,c_2}(e_\ast\leftrightarrow\infty)$
. In other words,
$\beta_{\mathbb{H}^1_\ast}(e,\lambda)\leq \beta_{\mathbb{T}_\ast}(e,\lambda)\leq \beta_{\mathbb{H}^2_\ast}(e,\lambda)$
. Hence, by Lemma 2, we obtain that
\begin{equation*} 1-\frac{\lambda\wedge m_1}{m_1}\leq\beta_{\mathbb{T}_\ast}(e,\lambda)\leq 1-\frac{\lambda}{m_2}. \end{equation*}
The lemma holds.
Put
\begin{equation*} A_n(x)=\frac{\lambda}{\big(\lambda+\sum_{i=1}^{v(x)}\beta_n(xi)\big)^2}, \qquad B_n(x)=\frac{\sum_{i=1}^{v(x)}\beta_n(xi)}{\big(\lambda+\sum_{i=1}^{v(x)}\beta_n(xi)\big)^2}.\end{equation*}
Now we are in a position to prove the following lemma on the derivative of
$\beta(e,\lambda)$
.
Lemma 4. For a Galton–Watson tree
$\mathbb{T}$
without leaves,
$\beta(e)=\beta(e,\lambda)$
almost surely has a continuous derivative
$\beta^\prime(e)=\beta^\prime(e,\lambda)$
in
$\lambda\in [0,m_1)$
, with
\begin{equation*} 0 < -\beta^{\prime}(e,\lambda) \leq \frac{\beta(e,\lambda)}{m_1-\lambda}, \quad \lambda\in [0,m_1). \end{equation*}
Proof. Differentiating (1) for
$\lambda < m$
yields
$-\beta_{n}^{\prime}(x,\lambda)=A_n(x)\sum_{i=1}^{\nu(x)}-\beta^{\prime}_n(xi,\lambda)+B_n(x)$
, where
$\beta^{\prime}_n(x,\lambda)$
is the derivative in
$\lambda$
. Then
\begin{equation} -\beta_{n}^{\prime}(e,\lambda) = \sum_{k=0}^{n-1}\sum_{|x|=k}B_n(x)\prod_{i=0}^{k-1}A_n(x_i), \quad \lambda < m, \end{equation}
where
$x_i$
is the ancestor at generation i of x. And, for any
$k\in [0,n-1]$
,
\[ \beta_n(e,\lambda) = \sum_{|x|=k}\beta_n(x,\lambda) \prod_{i=0}^{k-1}\frac{1}{\lambda+\sum_{i=1}^{\nu(x_i)}\beta_n(x_ij,\lambda)}, \quad \lambda < m. \]
Here,
$x_ij$
is the jth child of the ancestor
$x_i$
.
Clearly,
$\beta_n(x,\lambda)$
is non-increasing in n. By Lemma 3,
$\lambda+\sum_{i=1}^{\nu(x)}\beta_n(xi,\lambda)\geq m_1$
,
$\lambda < m$
. Hence, for
$\lambda < m$
,
\begin{equation*} A_n(x)\leq\frac{1}{m_1}\frac{\lambda}{\lambda+\sum_{i=1}^{\nu(x)}\beta_n(xi,\lambda)}, \qquad B_n(x)\leq \frac{1}{m_1} \beta_n(x,\lambda). \end{equation*}
For
$\lambda < m$
,
\begin{equation} \sum_{|x|=k}B_n(x)\prod_{i=0}^{k-1}A_n(x_i) \leq \frac{1}{m_1^{k+1}}\sum_{|x|=k}\beta_n(x,\lambda) \prod_{i=0}^{k-1}\frac{\lambda}{\lambda+\sum_{i=1}^{\nu(x_i)}\beta_n(x_ij,\lambda)} = \frac{\lambda^k}{m_1^k}\frac{1}{m_1}\beta_n(e,\lambda). \end{equation}
By (2) and (3), almost surely,
\begin{equation*} 0 \leq -\beta_n^\prime(e,\lambda) \leq \frac{\beta_n(e,\lambda)}{m_1-\lambda} \leq \frac{1}{m_1-\lambda}, \quad \lambda < m_1. \end{equation*}
From this, given any small enough
$\varepsilon>0$
, we see that, almost surely, as a sequence of functions on
$[0,m_1-\varepsilon]$
$\{(\beta_n(e,\lambda)\,:\ \lambda\in [0,m_1-\varepsilon])\}_{n\geq 1}$
is equi-continuous. Combining this with
$\beta_n(e,\lambda)\downarrow\beta(e,\lambda)$
as
$n\uparrow\infty$
for all
$\lambda\in [0,m)$
almost surely, by the Ascoli–Arzelà theorem,
$\{\beta_n(e,\lambda)\,\colon\lambda\in[0,m_1-\varepsilon]\}_{n\geq 1}$
converges uniformly to
$(\beta(e,\lambda)\,\colon\lambda\in[0,m_1-\varepsilon])$
almost surely.
Note that, for any vertex
$x\in\mathbb{T}$
,
$(\{(\beta_n(x,\lambda)\,\colon0\leq\lambda < m)\}_{n\geq 1}, (\beta(x,\lambda)\,\colon0\leq\lambda \lt m))$
has the same distribution as
$(\{(\beta_n(e,\lambda)\,\colon0\leq\lambda \lt m)\}_{n\geq 1},(\beta(e,\lambda)\,\colon0\leq\lambda \lt m))$
. We obtain that, almost surely, for any vertex
$x\in\mathbb{T}$
,
$\{\beta_n(x,\lambda)\,\colon\lambda\in[0,m_1-\varepsilon]\}_{n\geq 1}$
converges uniformly to
$(\beta(x,\lambda)\,\colon\lambda\in[0,m_1-\varepsilon])$
. Hence, by the definitions of
$A_n(x)$
and
$B_n(x)$
, we have that, almost surely, for any vertex x,
$A_n(x)$
and
$B_n(x)$
converge uniformly in
$\lambda\in [0,m_1-\varepsilon]$
to some continuous functions A(x) and B(x) respectively.
Notice (2) and (3). By the dominated convergence theorem, we see that, almost surely,
$\big(\beta^{\prime}_n(x,\lambda)\,\colon\lambda\in[0,m_1-\varepsilon]\big)$
converges uniformly to some continuous function
$(F_{\lambda}\,\colon\lambda\in[0,m_1-\varepsilon])$
. By the dominated convergence theorem again, almost surely,
$\int_0^{\lambda}\beta_{n}^{\prime}(e,s)\,\mathrm{d}s$
converges to
$\int_0^{\lambda}F_s\,\mathrm{d}s$
, which is also
$\beta(e,\lambda)-1$
for all
$\lambda\leq m_1-\varepsilon$
.
Since
$\varepsilon$
is arbitrary,
$\beta(e,\lambda)$
is almost surely differentiable in
$\lambda\in [0,m_1)$
. Further, almost surely,
$$0\leq-\beta^\prime(e,\lambda)\leq\frac{\beta(e)}{m_1-\lambda},\quad \lambda\in [0,m_1).$$
By checking (2) and the definitions of
$A_n(x)$
and
$B_n(x)$
, when taking limits we indeed have, almost surely,
\begin{equation*} 0<-\beta^\prime (e,\lambda)\leq\frac{\beta(e)}{m_1-\lambda},\quad \lambda\in [0,m_1). \end{equation*}
By symmetry, we have
\[ \ell_{\lambda} = \mathbb{E}\bigg(\frac{\nu-\lambda}{\nu+1}\frac{\sum_{i=0}^\nu\beta_i}{\lambda-1+\sum_{i=0}^\nu\beta_i}\bigg)\, \Big/\, \mathbb{E}\bigg(\frac{\nu+\lambda}{\nu+1}\frac{\sum_{i=0}^\nu\beta_i}{\lambda-1+\sum_{i=0}^\nu\beta_i}\bigg).\]
By Lemma 4, each
$\beta_i$
has a derivative in
$\lambda\in[0,m_1)$
, and so does
$\ell_\lambda$
. Write each
$\beta^{\prime}_i$
and
$\ell_{\lambda}^\prime$
for the derivatives in
$\lambda\in [0,m_1)$
of
$\beta_i$
and
$\ell_\lambda$
respectively. Then, by straightforward calculus [Reference Adékon1], for
$\lambda\in [0,m_1)$
,
$\ell_\lambda^{\prime}<0$
is equivalent to
Lemma 5. For a Galton–Watson tree
$\mathbb{T}$
without leaves, when
$m_1\geq 2$
(4) is true for
$\lambda\in[0,{m_1}/({1+\sqrt{1-{1}/{m_1}}})]$
.
Proof. Note that, by Lemma 4,
$$0<-\beta_i^\prime(\lambda)\leq\frac{\beta_i(\lambda)}{m_1-\lambda},\ \lambda \lt m_1,\quad i\geq 0.$$
By Lemma 3,
\begin{eqnarray} \lambda - 1 + \sum_{i=0}^{\nu}\beta_i \geq \lambda - 1 + \bigg(1-\frac{\lambda}{m_1}\bigg)\times(m_1+1) = m_1 - \frac{\lambda}{m_1} > m_1-1,\quad \lambda \lt m_1. \end{eqnarray}
Then, for any
$\lambda < 1$
,
$0\leq\beta_i(\lambda)+(1-\lambda)\beta_i^\prime(\lambda)<\beta_i(\lambda)$
and
\begin{equation*} \mathbb{E}\bigg(\frac{1}{\nu+1}\frac{\sum_{i=0}^\nu\beta_i}{\lambda-1+\sum_{i=0}^\nu\beta_i}\bigg) \mathbb{E}\Bigg(\frac{\nu}{\nu+1}\frac{\sum_{i=0}^\nu(\beta_i+(1-\lambda)\beta_i^{\prime})} {\big(\lambda-1+\sum_{i=0}^\nu\beta_i\big)^2}\Bigg) \geq 0. \end{equation*}
When
$\lambda < 1$
,
Since
$\lambda < 1$
and
$m_1\geq 2$
,
$m_1-{\lambda}/{m_1}>\lambda$
and we obtain that, when
$\lambda < 1$
,
namely, (4) holds.
When
$\lambda=1$
, (4) becomes
\begin{equation*} \mathbb{E}\bigg(\frac{\nu}{\nu+1}\bigg)\mathbb{E}\bigg(\frac{1}{\nu+1}\frac{1}{\sum_{i=0}^\nu\beta_i}\bigg) - \mathbb{E}\bigg(\frac{1}{\nu+1}\bigg)\mathbb{E}\bigg(\frac{\nu}{\nu+1}\frac{1}{\sum_{i=0}^\nu\beta_i}\bigg) < \mathbb{E}\bigg(\frac{\nu}{\nu+1}\bigg)\mathbb{E}\bigg(\frac{1}{\nu+1}\bigg), \end{equation*}
while, by Lemma 3,
$\sum_{i=0}^\nu\beta_i(1)\geq m_1-{1}/{m_1}>1$
, which implies the above inequality.
When
$m_1>\lambda>1$
,
\[\beta_i+(1-\lambda)\beta_i^{\prime}\leq \frac{m_1-1}{m_1-\lambda}\beta_i.\]
Combining this with (5), we obtain, for
$1<\lambda \lt m_1$
,
When
$$\frac{({m_1-1})/({m_1-\lambda})}{m_1-{\lambda}/{m_1}}\leq\frac{1}{\lambda}$$
and
$1<\lambda \lt m_1$
, namely
$\lambda\in(1,{m_1}/({1+\sqrt{1-{1}/{m_1}}})]$
, we have
Note when
$1<\lambda \lt m_1$
,
$\sum_{i=0}^\nu(\beta_i+(1-\lambda)\beta_i^\prime)>\sum_{i=0}^\nu\beta_i>0$
and
\begin{equation*} \mathbb{E}\bigg(\frac{1}{\nu+1}\frac{\sum_{i=0}^\nu\beta_i}{\lambda-1+\sum_{i=0}^\nu\beta_i}\bigg) \mathbb{E}\Bigg(\frac{\nu}{\nu+1} \frac{\sum_{i=0}^\nu(\beta_i+(1-\lambda)\beta_i^{\prime})}{\big(\lambda-1+\sum_{i=0}^\nu\beta_i\big)^2}\Bigg) > 0. \end{equation*}
Therefore, combining with (6), we see that for
$\lambda\in(1,{m_1}/({1+\sqrt{1-{1}/{m_1}}})]$
, (4) holds.
We have thus finished proving Theorem 1.
Acknowledgements
The authors would like to thank the anonymous referees and the editors for their constructive comments that improved the quality of this paper.
Funding information
KX’s research is supported partially by the National Natural Science Foundation of China (No. 12171410) and by Hu Xiang Gao Ceng Ci Ren Cai Ju Jiao Gong Cheng-Chuang Xin Ren Cai (No. 2019RS1057). HS’s research is supported partially by Huai’an City Science and Technology Project (HAB2024052), Jiangsu Province Education Science Research Planning Topics (C/2024/01/45), and by Jiangsu Province University Philosophy and Social Science Research Project (2024SJYB1388).
Competing interests
There were no competing interests to declare which arose during the preparation or publication process of this article.
