Fixed/predefined-time generalized synchronization for stochastic complex dynamical networks with delays

1.   Introduction

Consider an infinite, locally finite, and connected graph $G = (V(G), E(G), o)$, where $V(G)$ denotes the vertex set, $E(G)$ the edge set, and $o$ is a designated root. Consider Markov chain. There is a stationary measure $\pi(\cdot)$ such that for any two adjacent vertices $x$ and $y,$ $\pi(x)p(x, y) = \pi(y)p(y, x),$ where $p(x, y)$ is the transition probability. For the edge joining vertices $x$ and $y,$ assign a weight

Now we call the weights of the edges conductance and their reciprocals resistance. In this paper, we study the spectral radius of irreducible Markov chains on weighted graphs. More precisely, we focus on the spectral radius of a biased random walk, which is defined as follows:

Fix a root $o$ in a graph $G.$ Let $\vert x\vert$ be the graph distance between $x$ and $o$ for any vertex $x$ of $G.$ Write $\mathbb{N}$ for the set of natural numbers, and let $\mathbb{Z}_{+} = \mathbb{N}\cup\{0\}.$ For any $n\in\mathbb{Z}_{+},$ we define two subsets of vertices:

The ball of radius $n$ centered at $o$ is denoted by $B_G(n) = \{x\in V(G):\ \vert x\vert\leq n\}.$

The boundary of this ball is $\partial B_G(n) = \{x\in V(G):\ \vert x\vert = n\}.$ Fix any $\lambda\in [0, \infty).$ If edge $e$ is at distance $n$ from $o,$ then let its conductance be $\lambda^{-n}.$ Denote by $RW_\lambda$ the random walk associated the above conductances, and we call $RW_\lambda$ a biased random walk. Recall that a random walk on an infinite connected network is transient iff the effective conductance from any of its vertices to infinity is positive ^[19].

The motivation for introducing $RW_\lambda$ is to design a Monte-Carlo algorithm for self-avoiding walks by Berretti and Sokal ^[5]. See ^[13,20,21] for refinements of this idea. Due to interesting phenomenology and similarities to concrete physical systems (^{[7,9,10,12,23,24,25]}), biased random walks and biased diffusions in disordered media have attracted much attention in the mathematical and physics communities since the 1980s.

In the following, we assume $G$ is transitive. Let $M_n = |\partial B_G(n)|$ be the cardinality of $\partial B_G(n)$ for any $n\in\mathbb{Z}_{+}.$ Define the growth rate of $G$ as

Since the sequence $\{M_n\}_{n = 0}^\infty$ is submultiplicative, the limit $\mathrm{gr}(G) = \lim\limits_{n\rightarrow \infty}\sqrt[n]{M_n}$ exists indeed. R. Lyons ^[15] showed that the critical parameter for $RW_{\lambda}$ on a general tree is exactly the exponent of the Hausdorff dimension of the tree boundary. Moreover, R. Lyons ^[16] proved that for Cayley graphs and degree-bounded transitive graphs, the growth rate is exactly the critical parameter of the $RW_{\lambda}.$

Let $d$ be the vertex degree of $G.$ For any vertex $v$ of $G$ except $o,$ denote by $d_v^-$ the number of edges connecting $v$ to $\partial B_G(|v|-1).$ For the definition of $RW_{\lambda}$ $(X_n)_{n = 0}^{\infty}$ starting at $o$, the transition probability from $v$ to an adjacent vertex $u$ is

Note that $RW_1$ is just a simple random walk on $G.$

We write

The Green function is defined by

Define

the associated generating function

Given any function $g(z)$, let us denote the radius of convergence by $R_g$. By the Cauchy-Hadamard criterion,

Recall [19, Exercise 1.2] that $R_G$ is independent of $x$ and $y$ due to its irreducibility. Define

$\rho$ is called the spectral radius of the biased random walk. The reason for this name we can refer to ^[14,19] for more information on the spectral radius. Moreover,

Define the speed of $RW_{\lambda},$ $(X_n)_{n = 0}^\infty,$ as the limit of $\frac{|X_n|}{n}$ as $n\rightarrow \infty,$ if it exists almost surely (or in probability).

There are many deep and important questions related to how the spectral radius and the speed depend on the bias parameter ${\lambda}$ (see ^[14], Chapter 9). In [17,p.2005 Questions], R. Lyons, R. Pemantle, and Y. Peres raised the Lyons-Pemantle-Peres monotonicity problem. For a Cayley graph $G$ with $\mathrm{gr}(G) > 1,$ does the speed of $RW_{\lambda}$ exist and be positive for all $\lambda\in (1, \mathrm{gr}(G))?$ For more information, readers can refer to ^[1,4].

Moreover, R. Lyons, R. Pemantle and Y. Peres ^[18] conjectured that the speed of $RW_{\lambda}$ on the supercritical Galton-Watson tree without leaves is strictly decreasing. The conjecture has been confirmed for $\lambda$ lying in some regions (see ^[2,4,26]). For Galton-Watson trees without leaves, the Lyons-Pemantle-Peres monotonicity problem was answered positively for $\lambda\leq \frac{m_1}{1160}$ by Ben Arous, Fribergh and Sidoravicius ^[4], where $m_1$ is the minimal degree of the Galton-Watson tree. And Aïdékon ^[1] improved the just-mentioned result to $\lambda\leq \frac{1}{2}$ by a completely different approach. In ^[3], Ben Arous, Hu, Olla, and Zeitouni obtained the Einstein relation for $RW_{\lambda}$ on Galton-Watson trees, which implies the conjecture holds in a neighborhood of $m.$

We are interested in the continuity of the spectral radius of $RW_{\lambda}$. For $\lambda > \mathrm{gr}(G)$, $RW_{\lambda}$ is recurrent, $\rho = 1.$ When $\lambda = 0$ $RW_{\lambda}$ is not irreducible.

Problem 1.1. For a Cayley graph $G$, is the spectral radius of $RW_{\lambda}$ continuous for all $\lambda\in (0, \mathrm{gr}(G)]?$

In this paper, our focus is centered on addressing Problem 1.1 within the realm of a distinctive class of block-free product groups. To ensure a comprehensive understanding, the precise definition and pertinent details regarding free products will be meticulously introduced in Section 2.

Theorem 1.2. Let graph $G$ be a free product of complete graphs. Then the spectral radius $\rho(\lambda)$ of $RW_{\lambda}$ on $G$ is continuous in $\lambda\in (0, \mathrm{gr}(G)]$.

To prove Theorem 1.2, the primary technical obstacle lies in establishing the generating function and subsequently demonstrating that the Cheeger constant is indeed positive.

Theorem 1.2 affirmatively resolves Problem 1.1, specifically for the scenario involving the free product of complete graphs. A key observation here is that the $d$-regular tree $\mathbb{T}_d$, represents a particular instance of such free products of complete graphs. Consequently, it is deduced from the theorem that the spectral radius, $\rho(\lambda)$ of $RW_{\lambda}$ defined on $\mathbb{T}_d$, exhibits a characteristic of continuity over the interval (0, $\mathrm{gr}(\mathbb{T}_d)$], where $\mathrm{gr}(\mathbb{T}_d)$ signifies the growth rate of the $d$-regular tree. This finding underscores the robustness of the spectral property with respect to variations in the parameter ${\lambda}$.

2.   Proof of Theorem 1.2

2.1.   Free product of graphs and growth rate

Intuitively, a "free product" of finite Cayley graphs $G_i$ is a rule to construct a new Cayley graph $\mathcal{G}$ by gluing these $m$ cells at "common vertices" without edge intersection, step by step. Concretely, we construct the Cayley graph $\mathcal{G}$ of $H_1\ast H_2 \ast \cdots \ast H_r$ by the following steps: Here, $\ast$ denotes a free product.

Step 1. Glue each $i$-cell ($1\leq i\leq r$) at a common vertex $o$ such that any two of the $r$ cells only have one common vertex $o.$ View $o$ as the birth root of these $m$ cells. Usually $o$ is chosen to be the identity element $1.$ Denote the obtained graph as $G^{(1)},$ and mark any vertex $x$ in the $j$-cell as $[j].$

Step 2. For any $x\in G^{(1)}\backslash\{o\},$ it must be in some cell, say an $i$-cell, then we glue each $j$-cell ($1\leq j\neq i \leq r$) at $x$ such that any of the $r-1$ cells has only one common vertex $x$ with $G^{(1)}$ and any two of the $r-1$ cells only have one common vertex $x.$ View $x$ as the birth root of just added $r-1$ cells. For any distinctive two vertices $x$ and $y$ of $G^{(1)}\backslash\{o\},$ we require that any cell glued at $x$ is disjoint from any cell glued at $y.$ Let $G^{(2)}$ be the resulting graph. And for any $1\leq j\leq r,$ also mark a vertex $x$ of $G^{(2)}\backslash G^{(1)}$ in the $j$-cell as $[j]$.

Step 3. For all $x\in G^{(2)}\backslash G^{(1)},$ according to $\langle x\rangle,$ we can determine which type of cell $x$ belongs to, and glue other type cells as Step 2. And then mark all new added vertices $y$ and define $\langle y\rangle$ and $[y]$ as Step 2. Denote by $G^{(3)}$ the obtained graph. And so on, we obtain $\mathcal{G}$ with a type function $[\cdot]$ in its vertices, where for convenience we let $[o] = 0$.

2.2.   Spectral radius: Free product of complete graphs

Now let $G$ be the Cayley graph of $H_1\ast H_2\ast \cdots \ast H_r$ with root $o$, where each $H_i$ ($1\leq i \leq r$) is a finite group whose Cayley graph is the complete graph $K_{m_i+1}$ on $m_i+1$ vertices. Let $\sum_{i = 1}^r m_i = m.$ Thus, the transition probability from $v$ to an adjacent vertex $u$ is

Let $f_i^{(n)}(o, o)$ ($i = 1, 2, \cdots, r$) be the probability of the biased random walk on $G$ starting at $o$ and $\tau_o = n$, which does visit a vertex of $K_{m_i+1}.$ Define

Hence,

Note the tree-like structure of $G$. To compute $f_i^{(n)}(o, o)$, a biased random walk must reach an edge in $K_{m_i+1}$ from $o$ and return $o$ by an edge in $K_{m_i+1}$ at last step. Each vertex of $K_{m_i+1}$ glues a copy of $K_{m_j+1}$ ($j\neq i$). By the symmetry of $K_{m_i+1}$, we can regard $K_{m_i+1}$ as an edge with a cycle and glue the same structure as in $G$. Thus

Here $M_j(z)$ denotes the generating function associated with the hitting probability of $K_{m_i+1}$, which starts at a vertex of $K_{m_j+1}$ ($j\neq i$). Note that the probability from $o$ to verteices of $K_{m_j+1}$ is $\frac{m_i}{m}$ and from a vertex of $K_{m_i+1}$ to the vertices of $K_{m_j+1}$ is $\frac{m_i}{m+\lambda-1}.$ And the other steps obey the same law as $U_j(o, o|z)$. Thus

Therefore, in the domain $\{z\in \mathbb{C}|\; |z| < R_U\},$

Hence,

Drawing upon the results established in Eqs 2.1 and 2.2, we are able to deduce that

Let

Define

Lemma 2.1. ^[8]

where $z_S$ is the unique real number with

In the work of E. Candellero, L. A. Gilch, and S. Müller ^[8], they derive an upper bound for the upper box-counting dimension and a complementary lower bound for the Hausdorff dimension of the geometric endpoint boundary of the trace. This analysis is instrumental in establishing Lemma 2.1. Our approach subsequently leverages Lemma 2.1 as a pivotal step to demonstrate that the growth rate of the free product of complete graphs is indeed positive.

Since the Cayley graph of $H_i$ ($1\leq i\leq r$) is a complete graph on $m_i+1$ vertices,

Recall Lemma 2.1,

where $z_S$ is the unique real positive number with

Let $\Gamma_i = (V_i, \; E_i)$ generated by the vertex set

Clearly, for any $n\in \mathbb{Z}_+$, $1\leq i\leq r,$

Hence, for $n$ large enough and $1\leq i\neq j\leq r,$

To continue, we introduce some preliminaries about the Cheeger constant. For a weighted graph $H$ (with weight $c(x, y)$ for the edge joining vertices $x$ and $y$), we say that $H$ satisfies the isoperimetric inequality, briefly $IP_\infty$, if there exists a $\kappa > 0$ such that $C(\partial _E(S))\geq \kappa C(S)$ for any finite connected subset $S.$ Here $C(S) = \sum_{x\in S}C_x$ and $C(\partial _E(S)) = \sum_{x\in S, \; y\not\in S}c(x, y),$ where $C_x = \sum_{y\sim x}c(x, y).$ The largest possible $\kappa$ is the: Kesten-Cheeger-Dodziuk-Mohar theorem, see ^[14] Chapter 7, Theorem 7.3. A weighted graph can also be regarded as a network. Readers can refer to ^[19] for details.

Theorem 2.2. For any connected infinite network $H$, the following are equivalent:

(1) $H$ satisfies $IP_\infty$ with $\kappa > 0.$

(2) $0 < \rho < 1.$

In fact, $\kappa^2/2\leq 1-\rho \leq \kappa.$

In the subsequent discussion, we will undertake the task of proving that the Cheeger constant of $G$ is indeed positive. This assertion is facilitated by invoking the Kesten-Cheeger-Dodziuk-Mohar theorem (Theorem 2.2), which leads us directly to the derivation of the following lemma.

Lemma 2.3. For any $\lambda\in (0, \mathrm{gr}(G)),$ $0 < \rho(\lambda) < 1.$

Proof. To return $o$, a path can hit a vertex $x$ of type $[i]$ with probability $\frac{1}{m}$, then move to another neighbour of $x$ with type $[j]$ with probability $\frac{m_j-1}{m+\lambda-1}$. Until the $n-th$ step, the random walk runs away from $o$. From the $(n+1)-th$ until the $2n-th$ the random walk returns $o$ with probability $\frac{\lambda}{m+\lambda-1}$ for every step. Hence, for any $n\geq 2$

Thus

Let $S$ be any connected, finite subgraph of $G$. Assume that $S$ is between $\partial B_G(n)$ and $\partial B_G(n+m)$. Note that

where $S_j$ denotes $S\cap \partial B_G(j)$ and $S^o$ denotes the interior points of $S$.

For any $x \in S_n,$ denote the subgraph of $x$ as $S_x = (V(S_x), E(G)).$ Here

Given any fixed $\epsilon > 0,$ from the definition of $\mathrm{gr}(G)$, {there exists $n_0$ such that, for any $k > n_0,$

Define

which means that at $\partial S_x(k-n)$, we can find at least one vertex belonging to $\partial S.$ Hence,

If $n_1-n\leq n_0,$ then

Now assume that, $n_1-n > n_0.$ Notice that every vertex $x\neq o$ has $m-m_i$ neighbors in $B_G(|x|+1)$ and only one neighbour in $B_G(|x|-1)$ if $x\in [i].$ Let $V_j^i$ be the set of all vertices of type $[i]$ in $S^o\cap S_j.$ It is easy to see that

Notice that $\sum_{i = 1}^r(m-m_i)|V_j^i|$ denotes the growth way of $S^o\cap S_j.$ Since $n_1-n > n_0,$ for $n_0\leq j \leq n_1-n,$

Write $c = \mathrm{gr}(G)-\epsilon.$ Hence, for any $n_0\leq j\leq n_1-n$,

In the case when $|\partial S\cap \partial S_x(n_1-n)|\geq \epsilon |\partial S_x(n_1-n)|,$

Therefore, for any $n_0\leq j\leq n_1-n,$

Notice that every vertex in $S^o\cap S_x(j)$ has weight $\lambda^{-j}(m+\lambda-1).$ Therefore,

Combining with that

we have that

Since $\lambda < \mathrm{gr}(G)-\epsilon,$

Hence, we obtain that,

Notice that

Thus,

Notice that the left case is $|\partial S\cap \partial S_x(n_1-n)| < \epsilon |\partial S_x(n_1-n)|.$ However, we will discuss the case in the following ways. If $n_1-n\leq n_0$, for $x_1\in \partial S_x(n_1),$ define

Then, similar to the proof of $S_x(n_1-n)$, we can discuss the case of $S_{x_1}(n_2-n_1).$ If $n_1-n > n_0$, define

Moreover, if $|\partial S\cap \partial S_x(n_2-n)|\geq \epsilon |\partial S_x(n_2-n)|,$ then for $n_1\leq j \leq n_2$,

Similarly, as above, we have

Here $c_1 = \mathrm{gr}(G)-2\epsilon$. The left case is $|\partial S\cap \partial S_x(n_1-n)| < \epsilon |\partial S_x(n_1-n)|$ and $|\partial S\cap \partial S_x(n_2-n_1)| < \epsilon |\partial S_x(n_2-n_1)|.$ Notice that $S$ is a finite graph; then there exists $K > 0$ such that $n_K = n+m.$ And

Hence,

Whatever, from the above discussion, we can divide $S_x$ into several parts. $S_x^1, \; S_x^2, \; \cdots$ such that every part satisfies $\frac{C(\partial S \cap S_x^i)}{C(S_x^i)} > 0$ ($i \in \mathbb{N}$). Therefore,

Here $c_{K-1} = \mathrm{gr}(G)-K\epsilon.$ Hence, for $\lambda\in (0, \mathrm{gr}(G)-K\epsilon),$

Note that $K$ is decreasing as $\epsilon \downarrow 0.$ Thus, we prove that $G$ is a positive Cheeger constant for $\lambda\in (0, \mathrm{gr}(G))$, which completes the proof by Theorem 2.2.

Lemma 2.4. $G(o, o|R_G) < \infty,$ $U(o, o|R_G) < 1,$ and $R_G = R_U.$

Proof. Note that for any $z > 0$

It is easy to see that $R_G\leq R_U,$ and in $|z| < R_G.$

So $U(o, o|R_G)\leq1.$

Recall the following: Pringsheim's Theorem: If $f(z) = \sum_{n = 0}^\infty a_n z^n$ with $a_n\geq 0,$ then the radius of the convergence is the smallest positive singularity of $f(z).$

Hence, the smallest positive singularity $R_G$ of $G(o, o|z)$ is either one of the radius of convergence $R_U$ of $U(o, o|z)$ or the smallest positive number $z_1$ with $U(o, o|z_1) = 1.$ Whatever, notice that $U(o, o|z)$ is strictly increasing for $z.$ Therefore, $z_1$ is the unique positive number satisfying $U(o, o|z) = 1$. Thus, to prove the theorem, we only need to prove $U(o, o|R_G) < 1.$

Assume that $U(o, o|R_G) = 1.$ We exclude the trivial case where $m_i = 1$ for $1\leq i\leq r$. Notice that $R_G\geq1$. If $R_G = 1$, then $U(o, o|1) < 1$ by transience. So the left-case is $R_G > 1.$ Firstly, let us consider the case of $0 < \lambda \leq1.$ Recall that

Thus

Notice $(1-\lambda)+(m_i-1)R_G\geq (1-\lambda)+(m_i-1).$ Since there is at least one $m_i > 1$, which implies $(1-\lambda)+(m_i-1)R_G > (1-\lambda)+(m_i-1)$, we have

It is a contradiction. That is for $0 < \lambda\leq1,$ $U(o, o|R_G) < 1.$

Consider the case when $\lambda > 1.$ Notice that

For $\lambda > 1$,

Since $R_G > 1,$ we have

Thus, we get the following contradiction:

Hence, for $\lambda\geq1,$ $U(o, o|R_G) < 1.$

Suppose that $R_G < R_U.$ There exists $\widetilde{z}$ with $R_G < \widetilde{z} < R_U$ such that $U(o, o|\widetilde{z}) < 1$ since $U(o, o|R_G) < 1.$ Therefore, $G(o, o|\widetilde{z}) < \infty.$ It is in contradiction with $R_G$, which is the convergence radius of $G(o, o|z).$

Therefore, we complete the proof.

Lemma 2.5. For any $\lambda_0\in (0, \mathrm{gr}(G))$, $\lim_{\lambda \rightarrow \lambda_0} R_G(\lambda) = R_G(\lambda_0)$.

Proof. We will employ proof by contradiction to establish the aforementioned theorem.

Fix a sequence $\{\lambda_k\}_{k\geq 1}$ with $\lambda_k \uparrow \lambda_0.$ Suppose $\limsup\limits_{\lambda \rightarrow \lambda_0} R_G(\lambda) > R_G(\lambda_0) = z_*.$ Then we can find a subsequence $n_k$ with $\lim\limits_{k\rightarrow \infty}R_G(\lambda_{n_k}) > z_*.$ Without loss of generality, we can assume $z' = \lim\limits_{k\rightarrow \infty}R_G(\lambda_k) > z_*.$ For a large enough $k,$

Applying Fatou's lemma,

It is a contradiction. Hence, $\limsup\limits_{\lambda \rightarrow \lambda_0} R_G(\lambda) \leq R_G(\lambda_0)$, and especially $\liminf\limits_{\lambda \rightarrow \lambda_0} \rho(\lambda) \leq \rho(\lambda_0)$.

Specially $\limsup\limits_{\lambda \rightarrow gr(G)} R_G(\lambda) \leq R_G(gr(G)) = 1.$ Notice that for any $\lambda$, $R_G(\lambda)\geq 1$. So $\lim\limits_{\lambda \rightarrow gr(G)} R_G(\lambda) = R_G(gr(G)) = 1.$

Here we use $f^{(n)}(\lambda)$ to denote $f^{(n)}(o, o)$ and $U(o, o, \lambda)$ to $U(o, o|z)$. Let

Thus

Here $\mathbb{P}(\gamma, \lambda) = \prod_{i = 0}^n p(w_i, w_{i+1})$ for $\gamma = w_0w_1\cdots w_n.$ Note that

Given $\lambda_0\in (0, \mathrm{gr}(G))$ and $z_0.$ For any $\epsilon > 0$, $R_G(\lambda), R_G(\lambda_0)$, $z < z_0$ with $|z-z_0|^2+|\lambda-\lambda_0|^2 < \epsilon,$ there exists a $0 < \delta < \sqrt{\epsilon}$ such that $\mathbb{P}(\gamma, \lambda)\leq (1+\delta)^n \mathbb{P}(\gamma, \lambda_0)$. Hence, $f^{(n)}(\lambda)\leq (1+\delta)^n f^{(n)}(\lambda_0)$. And there exists a $\delta_1 > 0$ such that

Therefore,

If $\limsup\limits_{\lambda \rightarrow \lambda_0} R_G(\lambda) < R_G(\lambda_0).$ We can find a subsequence $n_k$ such that $\lim\limits_{\lambda_{n_k} \rightarrow \lambda_0} R_G(\lambda) < R_G(\lambda_0).$ Thus for any $\epsilon > 0,$ let $z = R_{\lambda_0}-\frac{\epsilon}{2}.$ Since $\lim\limits_{\lambda \rightarrow \lambda_0} R_G(\lambda) < R_G(\lambda_0),$

It is impossible. It means that $\lim\limits_{\lambda \rightarrow \lambda_0} R_G(\lambda) = R_G(\lambda_0).$

3.   Concluding of some open problems

For any vertex set $A$ and $Z,$ let $\tau_A = \inf\{n\geq 0|\; X_n \in A\}.$ If $RW_{\lambda}$ starts at a vertex in $A$, then $\tau_A = 0$. Write $\tau_A^+ = \inf\{n > 0|\; X_n \in A\}.$ $\tau_A^+$ is different from $\tau_A$ only when $RW_{\lambda}$ starts in $A.$ Consider the probability of a $RW_{\lambda}$ starting at a vertex $x$ that visits $A$ before its visit $Z:$

For $\lambda \in [0, \lambda_c],$ define $\theta(\lambda) = \mathbb{P}_o(\tau_o^+(\lambda) < \infty).$ Clearly, $\theta(\lambda) = U(o, o|1) = \sum_{n = 1}^\infty f^{(n)}(o, o, \lambda),$ and $\theta(0) = 0.$ Suppose $A = \{o\}$ and $(G_n)_{n\geq 1}$ be any sequence of finite subgraphs of $G$ that exhaust $G$. That is $G_n\subseteq G_{n+1}$ and $G = \bigcup G_n$. And let $Z_n$ be the set of vertices in $G\setminus G_n$. So $\lim\limits_{n\rightarrow \infty}\mathbb{P}_o(o\rightarrow Z_n, \lambda)$ is the probability of never returning to $o.$ And $\lim\limits_{n\rightarrow \infty}\mathbb{P}_o(o\rightarrow Z_n, \lambda)$ is independent of $(Z_n)_{n\geq 1}$ see ^[19] Exercise 2.4. We may regard the entire circuit between $o$ and $Z_n$ as a single conductor of effective conductance $\mathscr{C}_c(o\leftrightarrow Z_n).$ Recall ^[19] Chapter 2.2, $\mathscr{C}_c(o\leftrightarrow Z_n) = \pi (o)\mathbb{P}_o(o\rightarrow Z_n, \lambda).$ Hence,

Recall the following: Rayleigh's monotonicity principle.

Theorem 3.1. Let $H$ be a finite graph and $A$ and $Z$ be two disjoint subsets of its vertices. If $c$ and $c'$ are two assignments of conductances on $H$ with $c\leq c'$, then $\mathscr{C}_c(A\leftrightarrow Z)\leq \mathscr{C}_{c'}(A\leftrightarrow Z).$

Notice that $c(x, y) = c(x, y, \lambda)$ is the edge weight of edge $xy.$ And recall the definition of $RW_{\lambda}$, $c(x, y)$ is decreasing of $\lambda.$ By Theorem 3.1, for $\lambda_1\leq \lambda_2$,

Whatever, for $o$, $\pi (o)$ can be any positive constant that is independent of $\lambda.$ In fact, for any vertex $x\in G,$ we can choose $\pi(x) = \sum_{y\sim x}c(x, y).$ Therefore, for $\lambda_1\leq \lambda_2$,

And

The number of visits to vertex $o$ prior to escape is modeled by a geometric random variable, which has an expected value or mean $(1-\theta(\lambda))^{-1}.$ Note that the mean of $\tau_o^+(\lambda),$

Recall the Varopoulos-Carne bound (^[19] Chapter 13.2, Theorem 13.4) of $n$-step transition probability. For any $x,$ $y,$

Clearly, if $\rho < 1,$ then

Hence, for large enough $n$, by the Strong Law of Large Numbers,

Problem 3.2. Is $\mathbb{E}_o(\tau_o^+(\lambda))$ increasing for $\lambda\in [0, \mathrm{gr}(G)]$?

If both problems have a positive answer, then the spectral radius $\rho$ is increasing with $\lambda.$ And for $\lambda\in [0, \mathrm{gr}(G)),$ if $\mathbb{E}_o(\tau_o^+(\lambda)) < \infty$, then $\rho < 1.$

Moreover,

Problem 3.3. For $RW_{\lambda}$ on the free product of complete graphs with $\lambda \in [0, \lambda_c],$ is $\theta(\lambda)$ continuous and strictly increasing?

Recall the following result: ^[19] Chapter 6, Proposition 6.6.

Proposition 3.4. Consider a graph $H$ with an upper exponent growth rate $b > 1$. For a reversible Markov chain $(X_n)_{n\geq 0}$ starting at $o$ on its vertex set with reversible measure $\pi(\cdot)$ is bounded and $\pi(o) > 0$ and $\rho < 1.$ Then, in the graph metric,

Hence, for $RW_{\lambda}$ on $G$ with $\rho < 1,$ $\liminf_{n\rightarrow \infty}\frac{|X_n|}{n} > 0$. So the key, to answer Lyons-Pemantle-Peres monotonicity problem, is to prove the existence of the speed. Furthermore, R. Lyons, R. Pemantle, and Y. Peres ^[17] proved that on the lamplighter group $\mathbb{Z}\ltimes\sum\limits_{x\in\mathbb{Z}}\mathbb{Z}_2,$ which has a growth rate of $(1+\sqrt{5})/2,$ the speed of $RW_\lambda$ is $0$ at $\lambda = 1,$ and is strictly positive when $1 < \lambda < (1+\sqrt{5})/2.$ We wonder whether the spectral radius $\rho$ has a similar property or not. That is

Problem 3.5. For $\lambda\in (0, 1],$ $\rho(\lambda) = 1$? And for $1 < \lambda < (1+\sqrt{5})/2,$ $\rho(\lambda) < 1$?

Moreover, does a similar result hold for amenable groups with exponential growth?

Citing Chapter 9 of ^[14], it is demonstrated that the $n$-step transition probability is governed by the spectral radius $\rho(\lambda)$, with the following upper bound holding:

This inequality underscores the influence of the spectral radius; as the spectral radius decreases, the probability of transition between any two states $x$ and $y$ after $n$ steps becomes more restricted. Given that the speed, a measure of how rapidly the random walk explores the graph, is inherently tied to the transition probabilities, a positive speed necessitates that $p^{(n)}(x, y)$ decreases over time, implicating a requirement for $\rho(\lambda)$ to be sufficiently small. Based on these considerations, we posit that the existence of a positive speed aligns with the premise that the spectral radius $\rho(\lambda)$ must be adequately restrained.

4.   Conclusions

In the paper, we establish the continuity of the spectral radius $\rho(\lambda)$ of $RW_{\lambda}$ on the free product of complete graphs, as a function of the parameter $\lambda$ within the interval $(0, \mathrm{gr}(G)]$.

Author contributions

He Song, Longmin Wang, Kainan Xiang contributed to the conception of the study; He Song, Longmin Wang, Kainan Xiang, Qingpei Zang contributed significantly to analysis and manuscript preparation; He Song, Longmin Wang, Kainan Xiang, Qingpei Zang contributed to the writing of the manuscript. He Song, Longmin Wang, Kainan Xiang, Qingpei Zang helped perform the analysis with constructive discussions. All authors have read and approved the final version of the manuscript for publication.

Use of AI tools declaration

The authors declare they have not used Artificial Intelligence (AI) tools in the creation of this article.

Acknowledgments

The authors would like to thank the anonymous referees, the editors for their constructive comments that improved the quality of this paper.

KX's research is supported partially by National Natural Science Foundation of China (Nos. 11671216, 11871032) 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 the Natural Science Foundation of Jiangsu Higher Education Institutions of China (No. 21KJB110003), Huai'an City Science and Technology Project (HAB202357) and by Xiang Yu, Ying Cai (No. 31SH002).

QZ's research is supported partially by National Natural Science Foundation of China (Nos. 11971197).