How Many Vertices Does a Random Walk Miss in a Network with a Moderately Increasing Number of Vertices?

1. Introduction

Networks appearing in the real world, such as the internet, transportation networks, sensor/wireless networks, social networks, and chemical dynamics, change their shape over time. Nevertheless, what is known about the analyses of algorithms on dynamic networks is quite limited, compared with a wealth of knowledge on computations in static networks. In response to it, theoretical analyses of models and algorithms on dynamic networks have received a lot of attention recently, in particular within the context of network science and engineering, concerning such subjects as connectivity, exploration, information spreading, gathering, agreement, sampling, population protocol, random walks, and other stochastic processes; see, for example, Augustine et al. [4], Clementi et al. [10], Cooper [11], Kuhn and Oshman [25], Michail [29], Michail and Spirakis [30], and Sarma et al. [36].

A random walk on a graph is a fundamental stochastic process: a walker on a vertex moves to a randomly picked neighbor at each discrete time step. A random walk is a simple and powerful tool in the wide range of computer science, such as randomized search, page rank, and Markov chain Monte Carlo (MCMC), and also in networking science and engineering (Avin et al. [6], Cooper [11], Sarma et al. [36], Sauerwald and Zanetti [37]). The cover time of a random walk is the time it takes for a walker to visit all vertices of the graph. The cover time is one of the fundamental quantities of a random walk (see, e.g., Aldous [1], Aldous and Fill [2], Aleliunas et al. [3], Doyle and Snell [17], Feige [19], Feige [20], Levin and Peres [27], Matthews [28]), and it is important in applications such as randomized search. Analyses of random walks on dynamic graphs have been actively developed in the context where the cover time is a central issue (Avin et al. [5], Avin et al. [6], Cooper [11], Cooper and Frieze [12], Denysyuk and Rodrigues [15], Lamprou et al. [26], Sauerwald and Zanetti [37], Yu and McCann [39]) (see Section 1.3 for more details).

Those existing works, except for Cooper and Frieze [12], about random walks on dynamic networks are concerned only with networks over a static vertex set. However, the real networks change their vertex sets time by time. For example, graph structures in Social Networking Service (SNS) change their vertex sets by creating or deleting accounts. Motivated by analyzing such networks, this paper investigates random walks on graphs with an increasing number of vertices. A dynamic vertex set causes some technical troubles: it is questionable if the “cover time,” which is a natural quantity for a static vertex set, is also appropriate for a dynamic vertex set, and also it is hopeless, as Cooper and Frieze [12] revealed, to cover vertices beyond a constant ratio when the number of vertices constantly increases. In view of this, we introduce a simple model of growing graphs, and present an analysis of the number of vertices remaining unvisited by a random walk as a counterpart to the cover time of a random walk on a static vertex set.

1.1. Model and Quantities

1.1.1. Example: Collection of Coupons with an Increasing Number of Types.

To introduce our model, let us start with a simple and intuitive example. Suppose you draw a coupon randomly from a finite number of types of coupons every day. A single type of coupon exists on the first day, and a new type of coupon is released at intervals of n days for the number n of existing types of coupons; that is, you draw from two types of coupons for the second and the third days, draw from three for the fourth to the sixth days, and draw from n for the $\left(\left(\begin{array}{c}n\\ 2\end{array}\right)+1\right)$-st to the $\left(\begin{array}{c}n+1\\ 2\end{array}\right)$-th days. It might be difficult to complete all types of coupons because new types are sequentially released. Then, how many types of coupons do you expect to collect? We will prove that you can miss at most two types of coupons in expectation. On the other hand, interestingly, the number of uncollected types of coupons diverges to infinity as the days go by if the release intervals are $\text{o}(n)$, for example, $\lceil \sqrt{n}\rceil$ days (see Theorem 1).

The coupon collector’s problem is often connected to the cover time of a random walk on a complete graph. Generalizing the above example, we investigate a random walk on a network with a moderately increasing number of vertices. In the network model, we introduce a parameter corresponding to the growth rate of the vertex set, which will be represented by the duration. Then, we will be concerned with the number of unvisited vertices, instead of the cover time.

1.1.2. Random Walk on a Growing Graph.

A growing graph is a sequence of graphs $\mathcal{G}={\mathcal{G}}_0,{\mathcal{G}}_1,{\mathcal{G}}_2,\dots$ where each ${\mathcal{G}}_t=({\mathcal{V}}_t,{\mathcal{E}}_t)$ is a connected simple undirected graph such that ${\mathcal{V}}_t\subseteq {\mathcal{V}}_{t+1}$. Here, ${\mathcal{V}}_t$ and ${\mathcal{E}}_t$ are the vertex and edge set of ${\mathcal{G}}_t$, respectively. A random walk on a growing graph (RWoGG) is a stochastic process $Z=Z_0,Z_1,Z_2,\dots$ ($Z_t\in {\mathcal{V}}_t$), where the transition probability from Z_t to $Z_{t+1}$ is provided as a random walk on ${\mathcal{G}}_t$. We remark that $Z_t\in {\mathcal{V}}_{t-1}$ holds for $t=1,2,\dots$.

This paper is particularly concerned with a simple model of growing graphs with moderate changes. We assume that each graph in a growing graph $\mathcal{G}$ belongs to the same graph class. For instance, $G^{(n)}$ is a complete graph, a path graph, an expander graph, etc., of order n, respectively. We do not consider the case that G_i is a path but $G_{i+1}$ is a complete graph. For each n, the graph $G^{(n)}$ is unchanged for some duration of steps, and then changes its topology to $G^{(n+1)}$ by adding a single vertex and connecting it to $G^{(n)}$. Let $\mathfrak{d}:\mathbb{N}\to \mathbb{N}$ be a function, say, $\mathfrak{d}(n)=n$, denoting the duration of keeping the graph unchanged. Then, $\mathcal{G}$ is given as ${\mathcal{G}}_t=G^{(n)}$ for t satisfying ${\sum }_{i=1}^{n-1}\mathfrak{d}(i)\le t<{\sum }_{i=1}^n\mathfrak{d}(i)$ for $n=1,2,\dots$, where $G^{(n)}=(V^{(n)},E^{(n)})$ is a connected graph such that $V^{(n)}=\{v_1,\dots ,v_n\}$ and $E^{(n)}=E^{(n-1)}\cup {\cup }_{u\in S}\{\{v_n,u\}\}$ for some $S\subseteq V^{(n-1)}$ and for $v_n\in V^{(n)}\setminus V^{(n-1)}$.

Notice that ${\mathcal{G}}_0$ is the graph on a single vertex (this is just for convenience of description, but not essential in our later analyses). In other words, $\mathfrak{d}(n)$ denotes the duration of $|{\mathcal{V}}_t|=n$, and hence, $\mathfrak{d}(n)=\min \{t:|{\mathcal{V}}_t|=n+1\}-\min \{t:|{\mathcal{V}}_t|=n\}$ holds. For convenience, let $T_n≔{\sum }_{i=1}^{n-1}\mathfrak{d}(i)=\min \{t:|{\mathcal{V}}_t|=n\}$. Table 1 shows the correspondence between ${\mathcal{G}}_t$ and $G^{(n)}$ in the case of $\mathfrak{d}(n)=n$.

Table 1. Correspondence between ${\mathcal{G}}_t$ and $G^{(n)}$ when $\mathfrak{d}(n)=n$. The transition from Zt to $Z_{t+1}$ is performed on ${\mathcal{G}}_t$, and hence $Z_{t+1}\in {\mathcal{V}}_t$ holds. In this example, $T_1=0,\hspace{0.17em}{T}_2=1,\hspace{0.17em}{T}_3=3$, and $T_4=6$.

This paper is also concerned with a particular model of random walks on growing graphs. For $n\in \mathbb{N}$, let $P^{(n)}$ be the transition matrix of a random walk on $G^{(n)}$, that is, $\mathbf{\text{Pr}}[Z_{t+1}=v|Z_t=u]={(P^{(n)})}_{u,v}$ when ${\mathcal{G}}_t=G^{(n)}$. We define an RWoGG as a triple $R=(\mathfrak{d},{(G^{(n)})}_{n=1}^{\infty },{(P^{(n)})}_{n=1}^{\infty })$.

Then, we are concerned with the number of vertices unvisited by an RWoGG, formally given by

where recall the fact that $Z_t\in {\mathcal{V}}_{t-1}$. Particularly, let U(n) denote ${\mathsf{u}}_{T_{n+1}}$, that is, $U(n)=n-|{\cup }_{t=0}^{T_{n+1}}\{Z_t\}|$, and we will be concerned with it. Remark that ${\mathsf{u}}_t$ is monotone nonincreasing for $t\in (T_n,T_{n+1}]$, and $U(n-1)+1\ge {\mathsf{u}}_t\ge U(n)$ hold for the same period.

1.1.3. Terminology on Time-Homogeneous Markov Chains.

We here briefly introduce other terminology for random walks on static graphs, or time-homogeneous Markov chains (cf. Levin and Peres [27]). Suppose that $X_0,X_1,X_2,\dots$ is a random walk on a static graph $G=(V,E)$ characterized by a time-homogeneous transition matrix $P=(P_{u,v})\in {[0,1]}^{V\times V}$ where $P_{u,v}=\mathbf{\text{Pr}}[X_{t+1}=v|X_t=u]$. A transition matrix P is irreducible if $\forall u,v\in V,\hspace{0.17em}\exists t>0,\hspace{0.17em}{(P^t)}_{u,v}>0$, and is aperiodic if $\forall v\in V,\hspace{0.17em}\text{GCD}\{t>0:{(P^t)}_{v,v}>0\}=1$. An irreducible and aperiodic P is said to be ergodic. A probabilistic distribution π over V is a stationary distribution if it satisfies $\pi P=\pi$. It is well known that an ergodic P has a unique stationary distribution (Levin and Peres [27]). A random walk is lazy if $P_{v,v}\ge 1/2$ for all $v\in V$, and is reversible if $\pi (u)P_{u,v}=\pi (v)P_{v,u}$ for all $u,v\in V$, where $\pi \in {[0,1]}^V$ is the stationary distribution. A simple random walk (resp. simple lazy random walk) on an undirected graph is given by $P_{u,v}=1/d_u$ for $\{u,v\}\in E$ (resp. $P_{u,v}=1/(2d_u)$ for $\{u,v\}\in E$ and $P_{u,u}=1/2$) where d_u is the degree of u. The hitting time $t_{\text{hit}}$ (also denoted by $t_{\text{hit}}(P)$) is given by

The cover time $t_{\text{cov}}$ (or $t_{\text{cov}}(P)$) is given by

The mixing time $t_{\text{mix}}$ is given by

Mixing time is usually parametrized by ϵ, but we call $t_{\text{mix}}=t_{\text{mix}}(P)$ mixing time in this paper (Levin and Peres [27]).

1.2. Our Results

This paper investigates the behavior of $\mathbf{E}[U(n)]$ in relation to $\mathfrak{d}$ for an RWoGG $R=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$, where recall that U is an abbreviation of $U(n)={\mathsf{u}}_{T_{n+1}}$ denoting the number of vertices unvisited by the random walk at the moment just before a new vertex $v_{n+1}$ is attached (see Section 1.1 for details). Our results are summarized as follows. See also Tables 2 and 3.

Table 2. Summary of our results for general growing graphs. The results for short duration in the last line (Theorems 4, 5, and 7) require some assumptions.

Table 3. Concrete examples derived from our results for short duration (Theorems 4, 5, and 7). Here, $0\le \gamma \le 1$ is an arbitrary constant.

1.2.1. Growing Complete Graph.

As an introductory example of our analyses, we are firstly concerned with the simple random walk on a growing complete graph (with self-loops), which corresponds to the example of collecting coupons with new releases in Section 1.1.

Theorem 1.

Consider the simple random walk $R_{\text{c}}=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ on a growing complete graph, where $G^{(i)}$ is a complete graph of order i, and ${(P^{(i)})}_{u,v}=1/i$ for any $u\in V^{(i)}$ and $v\in V^{(i)}$ (including u = v). Then, the following holds:

• (1) If there is a constant C > 0 such that $\mathfrak{d}(i)\ge Ci$ for all $i\in [n]$, then $\mathbf{E}[U(n)]=\text{O}(1)$.

• (2) If $\mathfrak{d}(i)/i$ diverges (i.e., $\mathfrak{d}(i)/i\to \infty$ as $i\to \infty$), then $\mathbf{E}[U(n)]\to 0$ as $n\to \infty$.

• (3) If $\mathfrak{d}(i)/i$ is nonincreasing and converges to zero (i.e., $\frac{\mathfrak{d}(i)}{i}\ge \frac{\mathfrak{d}(i+1)}{i+1}$ for all $i\in \mathbb{N}$ and $\mathfrak{d}(i)/i\to 0$ as $i\to \infty$) and if $\mathfrak{d}$ is nondecreasing and diverges (i.e., $\mathfrak{d}(i)\le \mathfrak{d}(i+1)$ for all $i\in \mathbb{N}$ and $\mathfrak{d}(i)\to \infty$ as $i\to \infty$), then $\mathbf{E}[U(n)]=(1-\text{o}(1))\frac{n}{\mathfrak{d}(n)+1}$.

• (4) If $\mathfrak{d}$ is constant (i.e., for some constant $c\in \mathbb{N},\hspace{0.17em}\mathfrak{d}(i)=c$ for all $i\in \mathbb{N}$), then $\mathbf{E}[U(n)]=(1-\text{O}(n^{-1}))\frac{n}{c+1}$.

Notice that Item (1) implies that the number of missing types of coupons is at most constant in expectation, that is, $\mathbf{E}[{\mathsf{u}}_t]=\text{O}(1)$ at any time t, if $\mathfrak{d}(i)=\mathrm{\Omega }(i)$, whereas Item (2) claims a stronger upper bound with a stronger assumption of $\mathfrak{d}(i)=\omega (i)$ that the expected number of missing types is asymptotic to zero every time just before a new release (recall the relation between U and ${\mathsf{u}}_t$). Item (3) claims in the case of $\mathfrak{d}(i)=\text{o}(i)$ and $\omega (1)$ that $\mathbf{E}[U(n)]\approx \frac{n}{\mathfrak{d}(n)}$ up to the leading coefficient; for instance, $\mathbf{E}[U(n)]\le n^{\gamma }/C$ holds if $\mathfrak{d}(i)\ge C{i}^{1-\gamma }$ as well as $\mathbf{E}[U(n)]\ge n^{\gamma }/C$ holds if $\mathfrak{d}(i)\le C{i}^{1-\gamma }$, where C > 0 and $\gamma \in [0,1]$ are arbitrary constants common in both equations (see also Proposition 1). Item (4) is the counterpart of Item (3) for constant $\mathfrak{d}$. For example, if a new vertex appears at every step ($\mathfrak{d}(i)=1$), a random walk on a growing complete graph misses half of the number of vertices in expectation.

1.2.2. General Bound for Long Duration.

Next, we focus on upper bounds of $\mathbf{E}[U(n)]$ with respect to $\mathfrak{d}$ for RWoGG $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$, in general. For convenience, let $t_{\text{hit}}(i),\hspace{0.17em}{t}_{\text{cov}}(i)$, and $t_{\text{mix}}(i)$ respectively denote the hitting, cover, and mixing times of $P^{(i)}$, in the rest of the paper.

To begin with, we remark that it is easy to prove that $\mathbf{E}[U(n)]=\text{o}(1)$ if $\mathfrak{d}(i)=\mathrm{\Omega }(t_{\text{hit}}(i)\log i)$ for any RWoGG using the known fact that the number of unvisited vertices exponentially decays every unit time of $t_{\text{hit}}$ (see, e.g., sections 2.4.3 and 2.6 of Aldous and Fill [2]; see also Lemma A.3 in the appendix). Thus, our interest is in the case that $\mathfrak{d}(i)=\text{o}(t_{\text{hit}}(i)\log i)$. We establish the following upper bound of $\mathbf{E}[U(n)]$, claiming that $\mathbf{E}[U(n)]=\text{O}(1)$ if $\mathfrak{d}(i)=C{t}_{\text{hit}}(i)$ for C > 1. We remark that the following theorem is an extension of Items (1) and (2) of Theorem 1 for “a specific random walk on growing complete graphs” to general random walks and graphs.

Theorem 2.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an arbitrary RWoGG.

1. If there is a constant C > 1 such that $\mathfrak{d}(i)\ge C{t}_{\text{hit}}(i)$ for all $i\in [n]$, then $\mathbf{E}[U(n)]=\text{O}(1)$.

2. If $\mathfrak{d}(i)/t_{\text{hit}}(i)\to \infty$ as $i\to \infty$, then $\mathbf{E}[U(n)]\to 0$ as $n\to \infty$.

1.2.3. General Bound for Short Duration.

In contrast to the case of $\mathfrak{d}(i)\ge C{t}_{\text{hit}}(i)$ in Theorem 2, the case of $\mathfrak{d}(i)\ll t_{\text{hit}}(i)$ does not seem easy: it contains an issue of “short random walks,” which is a challenging topic in the literature of the cover time of multiple random walks, and so on; see, for example, Kanade et al. [23]. In this paper, we give the upper bounds of $\mathbf{E}[U(n)]$ under $\mathfrak{d}(i)\ll t_{\text{hit}}(i)$ for RWoGG where the stationary distribution changes moderately (Theorems 4 and 7), or the mixing time is sufficiently smaller than the hitting time (Theorem 5). Roughly speaking, for any constant $0\le \gamma \le 1$, we show that $\mathbf{E}[U(n)]=\text{O}(n^{\gamma })$ if $\mathfrak{d}(i)=\mathrm{\Omega }(t_{\text{hit}}(i)/i^{\gamma })$. We put the formal statements of these results in Section 4, the most technical part of this paper. Here, we list some concrete examples derived from our general results.

• (i) A natural example of growing graphs is a path that grows toward one side. We prove that the lazy simple random walk on the growing path with duration $\mathfrak{d}(i)\ge C{i}^{2-\gamma }$ misses $\mathbf{E}[U(n)]=\text{O}(n^{\gamma })$ vertices, and moreover, this bound is tight up to a constant factor. These are direct consequences of Corollary 7.

• (ii) Lollipop graphs gather special attention in random walk theory because they attain asymptotically the worst hitting and cover times of $\mathrm{\Theta }(n^3)$ (Feige [19], Feige [20]). We are concerned with the growing lollipop (see Section 4.2 for details). We show that the lazy simple random walk on the growing lollipop graph misses $\mathbf{E}[U(n)]=\text{O}(n^{\gamma })$ vertices if $\mathfrak{d}(i)\ge C{i}^{3-\gamma }$, which follows immediately from Corollary 3.

• (iii) The preferential attachment model (PA model) is a prominent model of real-world networks. It can be seen as a sequence of growing random graphs ${(G_t)}_{t\ge 0}$ where $G_{t+1}$ is obtained by adding to G_t a new vertex and random edges incident to it. We show that the lazy simple random walk on the PA model misses $\mathbf{E}[U(n)]=\text{O}(n^{\gamma })$ vertices if $\mathfrak{d}(i)\ge C{i}^{1-\gamma }$ (Theorem 6).

• (iv) Expander graphs gather special attention in the context of rapid mixing. This paper concerns a class of expander graphs called degree restricted expanders. Roughly speaking, a graph is a degree restricted expander if it exhibits sufficiently small spectral expansion properties and its degree distribution is “balanced.” We refer the definition to Section 4.3. We show that the lazy simple random walk on a growing degree restricted expander misses $\mathbf{E}[U(n)]=\text{O}(n^{\gamma })$ vertices if $\mathfrak{d}(i)\ge C{i}^{1-\gamma }$ (Corollary 5).

• (v) Consider the Metropolis walk of Nonaka et al. [32] in which the walker on a vertex u moves to a vertex v with probability proportional to $1/\max \{d_u,d_v\}$. We show that the lazy Metropolis walk on any connected growing graph with duration $\mathfrak{d}(i)$ misses $\mathbf{E}[U(n)]=\text{O}(n^{\gamma })$ if $\mathfrak{d}(i)\ge C{t}_{\text{hit}}(i)/i^{\gamma }$ (Corollary 4), where $t_{\text{hit}}(i)$ denotes the hitting time of the walk on the fixed $G^{(i)}$. Note that the Metropolis walk has an $\text{O}(n^2)$ hitting time for any n-vertex connected graphs (Nonaka et al. [32]) as opposed to the worst $\mathrm{\Theta }(n^3)$ bound for simple random walks (Feige [19]).

1.3. Related Works

The cover time is a fundamental topic of analyses of random walks. Here, we review some representative results about the cover times of random walks on static graphs and on dynamic graphs.

1.3.1. Cover Times of Random Walks on Static Graphs.

The cover time of a simple random walk satisfies $t_{\text{cov}}\le 2m(n-1)$ (Aldous [1], Aleliunas et al. [3]). Matthews [28] devised a technique of upper and lower bounding $t_{\text{cov}}$ by $t_{\text{hit}}$, of which a celebrated implication is $t_{\text{cov}}\le t_{\text{hit}}\log n$. The lollipop graph is famous for $t_{\text{hit}}=\mathrm{\Omega }(n^3)$, and hence $t_{\text{cov}}=\mathrm{\Omega }(n^3)$. Feige [20] gave a tight upper bound on the cover times of simple random walks on any graphs of $t_{\text{cov}}\le (4/27)n^3+\text{O}(n^{5/2})$, whereas in [19] he gave a tight lower bound of $t_{\text{cov}}\ge n\ln n+\text{o}(n\ln n)$, using the Matthews method [28]. The connection between the hitting time and electric circuits is well known (see, e.g., Aldous [2], Doyle and Snell [17], Levin and Peres [27]).

Motivated by a faster covering by a random walk, Ikeda et al. [22] (see also Ikeda et al. [21]) proposed a β-random walk, which makes transitions only using local information, and proved that the cover time of a β-random walk is upper bounded by $\text{O}(n^2\log n)$ for any graph. Nonaka et al. [32] proved the same bound holds for a Metropolis walk, which is simpler than a β-random walk. Recently, David and Feige [13] (see also David and Feige [14]) proved that a biased random walk achieves $\text{O}(n^2)$ cover time for any graph, and affirmatively settled the question posed by Ikeda et al. [22].

1.3.2. Cover Time of Random Walks on Dynamic Graphs.

An early work by Cooper and Frieze [12] investigated random walks on “web graphs.” Specifically, they considered a random walk on a growing preferential attachment graph with a constant duration (i.e., the number of vertices increases every constant steps). Note that our framework of RWoGG contains their model as a special case. They proved that $\mathbf{E}[U(n)]/n$ converges to some constant as n tends to infinity.

There are several results about the cover times of random walks on dynamic graphs, sometimes called “evolving graphs,” with static vertex sets. Avin et al. [5] (see also Avin et al. [6]) investigated the hitting time, mixing, and cover times of random walks on evolving graphs with static vertex sets. They gave a prescribed sequence of graphs on which the hitting time of a simple random walk gets $2^{\mathrm{\Omega }(n)}$, and hence, this bound holds for the cover time as well. On the other hand, they proved that the cover time of a max-degree random walk is $\text{O}(d_{\max }{n}^3{(\log n)}^2)$ where $d_{\max }$ is the maximum degree of the evolving graph. Denysyuk and Rodrigues [15] were concerned with the ρ-recurrent family of evolving graphs, where preferable graphs are assumed to appear frequently in the graph sequence. Then, for max-degree random walks on ρ-recurrent families, they gave upper and lower bounds of the cover time in terms of the hitting time, as well as giving an upper bound of the mixing time. Lamprou et al. [26] were concerned with two random walks of “a random walk with delay” (RWD), where, at each step, the walker chooses an edge of the underlying graph and moves when it appears, and “a random walk on what is available” (RWA), where the walker chooses an edge of the current graph and moves immediately. Then, they investigated the cover times of the RWD and RWA for edge-uniform stochastically evolving graphs. Sauerwald and Zanetti [37] extended the argument by Avin et al. [6] in the case that a sequence of graphs has the same stationary distribution, and presented an upper bound $\text{O}(n^2)$ of the cover time on d-regular dynamic graphs.

1.3.3. Other Related Works.

Saloff-Coste and Zúñiga investigated time-inhomogeneous Markov chains, and provided some Nash and log-Sobolev inequalities (Saloff-Coste and Zúñiga [34], Saloff-Coste and Zúñiga [35]). Recently, Cai et al. [9] investigated the relation between the density of edge-Markovian dynamic graphs and the mixing time. They showed for fast-changing dynamic graphs that $t_{\text{mix}}=\infty$ in the sparse case whereas $t_{\text{mix}}=\text{O}(\log n)$ in the dense case. They also showed for slowly changing dynamic graphs that $t_{\text{mix}}=\mathrm{\Omega }(n)$ in the sparse case whereas $t_{\text{mix}}=\text{O}(\log n)$ in the dense case. Random walks on dynamic graphs are also of use in data mining applications. Yu and McCann [39] presented an analysis on “a random walk with restart,” which is used as a measure of proximity between vertices of a graph in the context, over dynamic graphs.

There are many works on other stochastic processes on dynamic graphs, such as exploration, information spreading, rumor spreading, gossiping, and voter model; see, for example, Augustine et al. [4], Berenbrink et al. [8], and Clementi et al. [10]. Theoretical analyses of algorithms on dynamic graphs attract high attention in the context of distributed computing, and there are many works concerning the topics, such as connectivity, exploration, gathering, agreement, flooding, and population protocol, on dynamic networks; see, for example, Kuhn and Oshman [25], Michail [29], and Michail and Spirakis [30].

1.4. Organization

In Section 2, we are concerned with the simple random walk on a growing complete graph (with self-loops). This corresponds to the example of collecting coupons with new releases in Section 1.1. In Section 3, we consider general RWoGGs under the assumption that $\mathfrak{d}(i)>t_{\text{hit}}(i)$. In Section 4, we consider the case of $\mathfrak{d}(i)\ll t_{\text{hit}}(i)$, focusing on lazy and reversible random walks. We prove the general bound that implies several bounds for concrete examples mentioned in Section 1.2. Also, we prove another general bound for rapidly mixing walks without the assumption concerning the stationary distribution above. In Section 5, we focus on the lazy simple random walk on the preferential attachment model. We will combine the structural properties of the preferential attachment model concerning the expansion with our slightly modified general bound to obtain a bound of $\mathbf{E}[U(n)]$ for this setting. This part is the main difference of this paper from the preliminary version (Kijima et al. [24]). In Section 6, we obtain a tight lower bound of $\mathbf{E}[U(n)]$ for random walks on a growing path. We conclude this paper and pose possible future directions in Section 7.

2. Complete Graph

This section is devoted to proving Theorem 1. Throughout this paper, we consider a random walk of length $T_{n+1}$. For convenience, divide the $T_{n+1}$-step random walk into n random walks each of length $\mathfrak{d}(i)$ (for $i=1,\dots ,n$). We call each period a round. For a round $i\in [n]$, let ${(X_s^{(i)})}_{s=0}^{\infty }$ denote a random walk in the i-th round (specifically, it is a random walk according to $P^{(i)}$) with the initial state $X_0^{(i)}=Z_{T_i}=X_{\mathfrak{d}(i-1)}^{(i-1)}$. Note that ${(X_s^{(i)})}_{s=0}^{\infty }$ is a random walk on $G^{(i)}$. Table 4 illustrates the correspondence between Z_t and $X_s^{(i)}$ in the case of $\mathfrak{d}(i)=i$.

Table 4. Correspondence between Zt and $X_s^{(i)}$ when $\mathfrak{d}(i)=i$. For each $i\in \mathbb{N},\hspace{0.17em}{(X_s^{(i)})}_{s=0,1,\dots }$ is a random walk on $G^{(i)}$. Note that $X_0^{(i)}=X_{\mathfrak{d}(i-1)}^{(i-1)}=Z_{T_i}$ holds for $i\ge 2$. In this example, $U(3)=3-|{\cup }_{t=0}^{T_{3+1}}\{Z_t\}|=3-|{\cup }_{i=1}^3{\cup }_{s=0}^i\{X_s^{(i)}\}|$.

For $v\in V^{(n)}$, let $\mathcal{E}(v)$ denote the event that $v\notin {\cup }_{i=1}^n{\cup }_{s=0}^{\mathfrak{d}(i)}\{X_s^{(i)}\}$ ($={\cup }_{t=0}^{T_{n+1}}\{Z_t\}$). In other words, $\mathcal{E}(v)$ means that the random walk $Z_0,Z_1,\dots ,Z_{T_{n+1}}$ does not visit the vertex v. For the vertex v_k attached to $\mathcal{G}$ at time T_k, we see that $\mathbf{\text{Pr}}[\mathcal{E}(v_k)]={\prod }_{i=k}^n{\left(1-\frac{1}{i}\right)}^{\mathfrak{d}(i)}$ holds, and thus

Lemma 1.

For a function $f:\mathbb{N}\to \mathbb{N}$, let $S(n)≔{\sum }_{k=1}^n{\prod }_{i=k}^n{\left(1-\frac{1}{i}\right)}^{f(i)}$.

• (i) If $f(i)\ge Ci$ for every $i\ge L$, then $S(n)\le (L-1){\text{e}}^{-(n-L-1)C}+\frac{{\text{e}}^{-C}}{1-{\text{e}}^{-C}}$.

• (ii) If f satisfies $f(i)\le f(i+1)$ for all $i\in \mathbb{N}$, then $S(n)\ge \frac{n}{f(n)+1}{\left(1-\frac{1}{n}\right)}^{f(n)}$.

• (iii) If f satisfies $\frac{f(i)}{i}\ge \frac{f(i+1)}{i+1}$, then for all $n\in \mathbb{N}$, $S(n)\le \frac{n}{f(n)}$.

• (iv) If there is a constant $c\in \mathbb{N}$ such that f(i) = c for all $i\in \mathbb{N}$, then for all $n\in \mathbb{N}$, $S(n)\le \frac{n}{c+1}$.

Proof of (i).

Because $1+x\le {\text{e}}^x$, we have

$$\begin{array}{l}S(n)\le {\displaystyle \sum _{k=1}^{L-1}\exp }\left(-{\displaystyle \sum _{i=k}^n\frac{f(i)}{i}}\right)+{\displaystyle \sum _{k=L}^n\exp }\left(-{\displaystyle \sum _{i=k}^n\frac{f(i)}{i}}\right)\\ \le (L-1){\text{e}}^{-(n-L-1)C}+{\displaystyle \sum _{k=1}^{\infty }{\text{e}}^{-kC}}\\ \le (L-1){\text{e}}^{-(n-L-1)C}+\frac{{\text{e}}^{-C}}{1-{\text{e}}^{-C}}.\hspace{1em}\square \end{array}$$

Proof of (ii).

Observe that $S(1)=0$ and for all $n\ge 1$,

$$\begin{array}{l}S(n+1)={\displaystyle \sum _{k=1}^{n+1}{\displaystyle \prod _{i=k}^{n+1}{\left(1-\frac{1}{i}\right)}^{f(i)}}}\\ ={\displaystyle \sum _{k=1}^n{\left(1-\frac{1}{n+1}\right)}^{f(n+1)}}{\displaystyle \prod _{i=k}^n{\left(1-\frac{1}{i}\right)}^{f(i)}}+{\left(1-\frac{1}{n+1}\right)}^{f(n+1)}\\ ={\left(1-\frac{1}{n+1}\right)}^{f(n+1)}(S(n)+1).\end{array}$$(1)

We prove (ii) by induction on n. In the base case, $S(1)=0$ and we are done. If $S(n)\ge \frac{n}{f(n)+1}{\left(1-\frac{1}{n}\right)}^{f(n)}$, then

$$\begin{array}{l}S(n)+1\ge \frac{n}{f(n)+1}{\left(1-\frac{1}{n}\right)}^{f(n)}+1\\ \ge \frac{n}{f(n)+1}\left(1-\frac{f(n)}{n}\right)+1\\ =\frac{n-f(n)}{f(n)+1}+1=\frac{n+1}{f(n)+1}\ge \frac{n+1}{f(n+1)+1}.\end{array}$$(2)

Here, we used ${(1+x)}^r\ge 1+rx$ in the second inequality and $f(n)\le f(n+1)$ in the last inequality. Combining (1) and (2), $S(n+1)\ge {\left(1-\frac{1}{n+1}\right)}^{f(n+1)}\frac{n+1}{f(n+1)+1}$ and we are done. □

Proof of (iii).

The proof is obtained by induction on $n\ge 1$. When n = 1, $S(1)=0\le 1/f(1)$. Assume $S(n)\le n/f(n)$. Then,

$$S(n+1)={\left(1-\frac{1}{n+1}\right)}^{f(n+1)}(S(n)+1)\le \frac{\frac{n}{f(n)}+1}{1+\frac{f(n+1)}{n+1}}\le \frac{\frac{n+1}{f(n+1)}+1}{1+\frac{f(n+1)}{n+1}}=\frac{n+1}{f(n+1)}.$$

Note that ${(1-x)}^y\le 1/(1+xy)$ for all $x\in [0,1]$ and $y\ge 0$. The second inequality follows from $\frac{f(n+1)}{n+1}\le \frac{f(n)}{n}$. □

Proof of (iv).

The proof is obtained by induction on n. First, we have $S(1)=0\le 1/(f(1)+1)$. Assume $S(n)\le n/(f(n)+1)$. Then, from (1) and the induction assumption, we have

$$\begin{array}{l}S(n+1)={\left(1-\frac{1}{n+1}\right)}^{f(n+1)}(S(n)+1)\\ \le \frac{\frac{n}{f(n)+1}+1}{1+\frac{f(n+1)}{n+1}}=\frac{\frac{n}{f(n)+1}+1}{1+\frac{f(n)}{n+1}}=\frac{\frac{n+1}{f(n)+1}\left(\frac{n}{n+1}+\frac{f(n)+1}{n+1}\right)}{\frac{n}{n+1}+\frac{f(n)+1}{n+1}}=\frac{n+1}{f(n)+1}=\frac{n+1}{f(n+1)+1}.\end{array}$$

Note that we use ${(1-x)}^y\le 1/(1+xy)$ again and $f(n)=f(n+1)$ in the first and the last equality. □

We are ready to prove Theorem 1.

Proof of Theorem 1.

Recall that $\mathbf{E}[U(n)]=S(n)$. Item (1) follows from Lemma 1(i). Item (3) follows from (ii) and (iii) of Lemma 1. Item (4) follows from (ii) and (iv) of Lemma 1.

We prove Item (2). Formally, we prove that, for any $ϵ>0$, there is $n_0\in \mathbb{N}$ such that for all $n\ge n_0$, $S(n)\le ϵ$ holds. Because $\mathfrak{d}(i)/i\to \infty$, for any C > 0, there exists $i_0\in \mathbb{N}$ such that $\mathfrak{d}(i)\ge Ci$ holds for all $i\ge i_0$. From Lemma 1(i), we have $\mathbf{E}[U(n)]\le i_0{\text{e}}^{-(n-i_0+1)C}+\frac{{\text{e}}^{-C}}{1-{\text{e}}^{-C}}$. For a fixed arbitrary small constant $ϵ>0$, take $C=C(ϵ)>0$ such that $\frac{{\text{e}}^{-C}}{1-{\text{e}}^{-C}}<\frac{ϵ}{2}$ holds. According to this constant C, we can take i₀ such that f(i) > Ci for all $i\ge i_0$ holds. Now C and i₀ are fixed. Hence, for sufficiently large n, we have $i_0\exp (-(n-i_0+1)C)\le ϵ/2$. This implies $S(n)\le ϵ$ and we are done. □

2.1. Remark

We remark on some monotonicity of $\mathbf{E}[U(n)]$ on the sequence of complete graphs with respect to $\mathfrak{d}$. Suppose functions ${\mathfrak{d}}^{*}$ and $\mathfrak{d}$ satisfy ${\mathfrak{d}}^{*}(i)\ge \mathfrak{d}(i)$ for all i. Let $U^{*}(n)$ and U(n) respectively denote the numbers of unvisited vertices at the end of the n-th round for $R_{\text{c}}^{*}=({\mathfrak{d}}^{*},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ and $R_{\text{c}}=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$. Then, $\mathbf{E}[U^{*}(n)]\le \mathbf{E}[U(n)]$ is clear. From this observation, Lemma 1 implies the following proposition, which is a variant of Theorem 1 Items (1), (3), and (4).

Proposition 1.

Consider the simple random walk $R_{\text{c}}=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ on a growing complete graph, where $G^{(i)}$ is a complete graph of order i, and ${(P^{(i)})}_{u,v}=1/i$ for any $u\in V^{(i)}$ and $v\in V^{(i)}$ (including u = v). Let $C>0,\gamma \in [0,1]$ be arbitrary constants. Then, the following holds:

• (1) If $\mathfrak{d}(i)\ge C{i}^{1-\gamma }$ for all i, then $\mathbf{E}[U(n)]\le \frac{n^{\gamma }}{C}$.

• (2) If $\mathfrak{d}(i)\le C{i}^{1-\gamma }$ for all i, then $\mathbf{E}[U(n)]\ge \frac{n^{\gamma }}{C+n^{\gamma -1}}{\left(1-\frac{1}{n}\right)}^{C{n}^{1-\gamma }}\ge \frac{n^{\gamma }}{C}-1$.

Finally, we consider an RWoGG on a growing complete graph which is initially $K_{n_0}$ for some $n_0\in \mathbb{N}$. We prove the following analogous bound of Theorem 1 Item (2) (note that Theorem 1 addresses the case of $n_0=1$).

Theorem 3.

Let $G^{(i)}=K_{n_0+i}$, that is, the complete graph with $n_0+i$ vertices, and let ${(P^{(i)})}_{u,v}=1/(n_0+i)$ for all $u,v\in V^{(i)}$ in $R=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$. Let N be an arbitrary positive number. If $\mathfrak{d}(i)\ge 2i/N$ for all i, then $\mathbf{E}[U(n)]\le 2n_0+N$.

Proof.

If $n\le n_0,|V^{(n)}|=n_0+n\le 2n_0$ and we are done. Suppose that $n>n_0$. Then it is straightforward to see that

$$\begin{array}{l}\mathbf{E}[U(n)]=n_0{\displaystyle \prod _{i=1}^n{\left(1-\frac{1}{n_0+i}\right)}^{\mathfrak{d}(i)}}+{\displaystyle \sum _{k=1}^n{\displaystyle \prod _{i=k}^n{\left(1-\frac{1}{n_0+i}\right)}^{\mathfrak{d}(i)}}}\\ \le n_0+n_0+{\displaystyle \sum _{k=n_0+1}^n{\displaystyle \prod _{i=k}^n{\left(1-\frac{1}{n_0+i}\right)}^{\mathfrak{d}(i)}}}\\ \le 2n_0+{\displaystyle \sum _{k=n_0+1}^n{\displaystyle \prod _{i=k}^n{\left(1-\frac{1}{2i}\right)}^{\mathfrak{d}(i)}}}\\ \le 2n_0+N.\end{array}$$

Note that we use Lemma 6 in the last inequality. □

3. Upper Bound for $\mathfrak{d}$ Larger than $t_{\text{hit}}$

This section is devoted to proving Theorem 2. Let $t_{\text{hit}}(i)$ denote the hitting time of the random walk specified by the fixed $P^{(i)}$. Consider an RWoGG $R=(\mathfrak{d},{(G^{(n)})}_{n=1}^{\infty },{(P^{(n)})}_{n=1}^{\infty })$. Recall that, at each round i, ${(X_t^{(i)})}_{t=0}^{\infty }$ denotes the random walk according to $P^{(i)}$ where $X_0^{(i)}=X_{\mathfrak{d}(i-1)}^{(i-1)}$ holds (see Table 4 for an example). Let ${\pi }^{(i)}$ denote the stationary distribution of $P^{(i)}$. Let ${\tau }_v^{(i)}≔\min \{t\ge 0:X_t^{(i)}=v\}$; that is, ${\tau }_v^{(i)}$ denotes the time taken for a random walk ${(X_t^{(i)})}_{t=0}^{\infty }$ to reach $v\in V^{(i)}$. Note that $t_{\text{hit}}(i)={\max }_{u,v\in V}\mathbf{E}[{\tau }_v^{(i)}|X_0^{(i)}=u]$. Suppose that the initial position is fixed, that is, $X_0^{(1)}=v_1$. For any round $k\le n$, the probability that the walker does not visit the vertex v_k before the end of the round n is equal to $\mathbf{\text{Pr}}[{\wedge }_{i=k}^n\{{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)\}]$. Hence, we have

The rest of this section is devoted to bounding (3) and (4). We show Theorem 2 in this section. To begin with, we show the following useful lemma.

Lemma 2.

For any $R=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$, we have

$$\mathbf{E}[U(n)]\le {\displaystyle \sum _{k=2}^n{\displaystyle \prod _{i=k}^n\underset{v\in V^{(i)}}{\max }}}\mathbf{P}\mathbf{r}\left[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)|X_0^{(i)}=v\right].$$

Proof.

Consider a fixed vertex v_k with k > 1. For a round $i\ge k$ and a vertex $u\in V^{(i)}$, let ${\mathcal{E}}_u^{(i)}={\mathcal{E}}_u^{(i)}(v_k)$ denote the event that the walker is in vertex u at the end of the i-th round without visiting vertex v_k during the round. Formally ${\mathcal{E}}_u^{(i)}(v_k)$ is defined as the event of $\{{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)\}\wedge \{X_{\mathfrak{d}(i)}^{(i)}=u\}$. Then for any $u_{k-1}\in V^{(k-1)}$,

$$\mathbf{\text{Pr}}\left[\underset{i=k}{\overset{n}{\wedge }}\left\{{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)\right\}|X_0^{(k)}=u_{k-1}\right]={\displaystyle \sum _{u_k\in V^{(k)}}\cdots }{\displaystyle \sum _{u_n\in V^{(n)}}\mathbf{\text{Pr}}}\left[\underset{i=k}{\overset{n}{\wedge }}{\mathcal{E}}_{u_i}^{(i)}|X_0^{(k)}=u_{k-1}\right].$$(5)

To bound (5), we first observe that, for any vertices, $u_{k-1}\in V^{(k-1)},\dots ,u_n\in V^{(n)}$,

$$\mathbf{\text{Pr}}\left[\underset{i=k}{\overset{n}{\wedge }}{\mathcal{E}}_{u_i}^{(i)}|X_0^{(k)}=u_{k-1}\right]=\frac{\mathbf{\text{Pr}}\left[X_0^{(k)}=u_{k-1},{\mathcal{E}}_{u_k}^{(k)}\right]}{\mathbf{\text{Pr}}\left[X_0^{(k)}=u_{k-1}\right]} \cdot {\displaystyle \prod _{\mathcal{\ell }=k+1}^n\frac{\mathbf{\text{Pr}}\left[X_0^{(k)}=u_{k-1},{\wedge }_{i=k}^{\mathcal{\ell }}{\mathcal{E}}_{u_i}^{(i)}\right]}{\mathbf{\text{Pr}}\left[X_0^{(k)}=u_{k-1},{\wedge }_{i=k}^{\mathcal{\ell }-1}{\mathcal{E}}_{u_i}^{(i)}\right]}}$$(6)

holds. Then, from the definition of the conditional probability, $\frac{\mathbf{\text{Pr}}\left[X_0^{(k)}=u_{k-1},{\mathcal{E}}_{u_k}^{(k)}\right]}{\mathbf{\text{Pr}}\left[X_0^{(k)}=u_{k-1}\right]}=\mathbf{\text{Pr}}[{\mathcal{E}}_{u_k}^{(k)}|X_0^{(k)}=u_{k-1}]$ and

$$\begin{array}{l}\frac{\mathbf{\text{Pr}}\left[X_0^{(k)}=u_{k-1},{\wedge }_{i=k}^{\mathcal{\ell }}{\mathcal{E}}_{u_i}^{(i)}\right]}{\mathbf{\text{Pr}}\left[X_0^{(k)}=u_{k-1},{\wedge }_{i=k}^{\mathcal{\ell }-1}{\mathcal{E}}_{u_i}^{(i)}\right]}=\mathbf{\text{Pr}}\left[{\mathcal{E}}_{u_{\mathcal{\ell }}}^{(\mathcal{\ell })}|X_0^{(k)}=u_{k-1},\underset{i=k}{\overset{\mathcal{\ell }-1}{\wedge }}{\mathcal{E}}_{u_i}^{(i)}\right]\\ =\mathbf{\text{Pr}}\left[{\mathcal{E}}_{u_{\mathcal{\ell }}}^{(\mathcal{\ell })}|X_{\mathfrak{d}(\mathcal{\ell }-1)}^{(\mathcal{\ell }-1)}=u_{\mathcal{\ell }-1}\right]\\ =\mathbf{\text{Pr}}\left[{\mathcal{E}}_{u_{\mathcal{\ell }}}^{(\mathcal{\ell })}|X_0^{(\mathcal{\ell })}=u_{\mathcal{\ell }-1}\right]\end{array}$$(7)

hold. We use the Markov property in the second equality. The last equality follows from our assumption of $X_{\mathfrak{d}(\mathcal{\ell }-1)}^{(\mathcal{\ell }-1)}=X_0^{(\mathcal{\ell })}$. Hence, combining (5), (6), and (7), we have

$$\begin{array}{l}\mathbf{P}\mathbf{r}\left[\underset{i=k}{\overset{n}{\wedge }}\left\{{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)\right\}|X_0^{(k)}=u_{k-1}\right]\\ ={\displaystyle \sum _{u_k\in V^{(k)}}\cdots }{\displaystyle \sum _{u_n\in V^{(n)}}{\displaystyle \prod _{\mathcal{\ell }=k}^n\mathbf{\text{Pr}}}}\left[{\tau }_{v_k}^{(\mathcal{\ell })}>\mathfrak{d}(\mathcal{\ell }),X_{\mathfrak{d}(\mathcal{\ell })}^{(\mathcal{\ell })}=u_{\mathcal{\ell }}|X_0^{(\mathcal{\ell })}=u_{\mathcal{\ell }-1}\right]\end{array}$$(8)

$$\begin{array}{l}={\displaystyle \sum _{u_k\in V^{(k)}}\mathbf{\text{Pr}}}\left[{\mathcal{E}}_{u_k}^{(k)}|X_0^{(k)}=u_{k-1}\right]{\displaystyle \sum _{u_{k+1}\in V^{(k+1)}}\cdots }{\displaystyle \sum _{u_n\in V^{(n)}}\mathbf{\text{Pr}}}\left[{\mathcal{E}}_{u_n}^{(n)}|X_0^{(n)}=u_{n-1}\right]\\ \le {\displaystyle \prod _{\mathcal{\ell }=k}^n\underset{u\in V^{(\mathcal{\ell })}}{\max }}{\displaystyle \sum _{u_{\mathcal{\ell }}\in V^{(\mathcal{\ell })}}\mathbf{\text{Pr}}}\left[{\mathcal{E}}_{u_{\mathcal{\ell }}}^{(\mathcal{\ell })}|X_0^{(\mathcal{\ell })}=u\right]={\displaystyle \prod _{\mathcal{\ell }=k}^n\underset{u\in V^{(\mathcal{\ell })}}{\max }}\mathbf{P}\mathbf{r}\left[{\tau }_{v_k}^{(\mathcal{\ell })}>\mathfrak{d}(\mathcal{\ell })|X_0^{(\mathcal{\ell })}=u\right].\end{array}$$(9)

We obtain the claim from (4) and (9). □

Proof of Theorem 2 Item (1).

From the Markov inequality, for any $k\le i$ and $v\in V^{(i)}$, we have

$$\mathbf{\text{Pr}}\left[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)|X_0^{(i)}=v\right]\le \frac{\mathbf{E}\left[{\tau }_{v_k}^{(i)}|X_0^{(i)}=v\right]}{\mathfrak{d}(i)}\le \frac{t_{\text{hit}}(i)}{\mathfrak{d}(i)}.$$

Hence, from Lemma 2, we obtain

$$\mathbf{E}[U(n)]\le {\displaystyle \sum _{k=1}^n{\displaystyle \prod _{i=k}^n\frac{t_{\text{hit}}(i)}{\mathfrak{d}(i)}}}\le {\displaystyle \sum _{k=1}^n{C}^{-(n-k+1)}}\le \frac{1}{C-1}.\hspace{1em}\square$$

Proof of Theorem 2 Item (2).

For an arbitrary (small) $ϵ>0$, let $C=C(ϵ)=\frac{2}{ϵ}+1$. From the assumption of Item (2), we can take some $i_0=i_0(ϵ)$ such that $\mathfrak{d}(i)\ge C{t}_{\text{hit}}(i)$ for all $i\ge i_0$. Let $K={\max }_{i\in [i_0]}\frac{t_{\text{hit}}(i)}{\mathfrak{d}(i)}$. From Lemma 2,

$$\begin{array}{l}\mathbf{E}[U(n)]\le {\displaystyle \sum _{i=1}^{i_0}\left({\displaystyle \prod _{k=i}^{i_0}\frac{t_{\text{hit}}(k)}{\mathfrak{d}(k)}}\right)}\left({\displaystyle \prod _{k=i_0+1}^n\frac{t_{\text{hit}}(k)}{\mathfrak{d}(k)}}\right)+{\displaystyle \sum _{i=i_0+1}^n{\displaystyle \prod _{k=i}^n\frac{t_{\text{hit}}(k)}{\mathfrak{d}(k)}}}\\ \le C^{-(n-i_0)}{\displaystyle \sum _{i=1}^{i_0}{K}^{i-i_0+1}}+{\displaystyle \sum _{i=i_0+1}^n{C}^{-(n-i+1)}}\\ =C^{-(n-i_0)}{\displaystyle \sum _{i=1}^{i_0}{K}^i}+{\displaystyle \sum _{i=1}^{n-i_0}{C}^{-i}}\\ \le C^{-(n-i_0)}\frac{K(1-K^{i_0})}{1-K}+\frac{1}{C-1}.\end{array}$$

Then we can take some $n_0=n_0(ϵ)$ satisfying $C^{-(n-i_0)}\frac{K(1-K^{i_0})}{1-K}\le ϵ/2$. Hence, for any $n\ge n_0,\hspace{0.17em}\mathbf{E}[U(n)]\le ϵ$ and we obtain the claim. □

4. Upper Bound for $\mathfrak{d}$ Smaller than $t_{\text{hit}}$

4.1. General Upper Bound

In this subsection, we prove the following technical result that provides general upper bounds on $\mathbf{E}[U(n)]$. Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG. Let

for $1<i\le n$, where ${\pi }^{(i)}$ is the stationary distribution of $P^{(i)}$.

Theorem 4.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. Let N > 0 be an arbitrary number. If $\mathfrak{d}(i)\ge \left(\frac{1}{N}+\frac{i(r_i-1)+1}{2i}\right)t_{\text{hit}}^{(i)}$ for all i, then $\mathbf{E}[U(n)]\le N\sqrt{{\max }_{1<i\le n}i(r_i-1)+1}$, where r_i is defined in (10).

To show Theorem 4, we set the following notations. For two vectors $f,g\in \mathbb{R}$ and a probability vector $\pi \in {(0,1]}^V$, let ${〈f,g〉}_{\pi }≔{\sum }_{v\in V}\pi (v)f(v)g(v)$. Then, the ${\mathcal{\ell }}_2(\pi )$-norm of f is defined by ${\Vert f\Vert }_{2,\pi }≔\sqrt{{〈f,f〉}_{\pi }}=\sqrt{{\sum }_{v\in V}\pi (v)f{(v)}^2}$. For two vectors $f,g\in {\mathbb{R}}^V$ where $g(v)\ne 0$ holds for all $v\in V$, define $\frac{f}{g}\in {\mathbb{R}}^V$ by $\frac{f}{g}(v)=\frac{f(v)}{g(v)}$. Note that from these definitions, for any probability vector $\xi \in {[0,1]}^V,{\Vert \frac{\xi }{\pi }-{\mathbf{1}}^{(|V|)}\Vert }_{2,\pi }^2={\Vert \frac{\xi }{\pi }\Vert }_{2,\pi }^2-1$ holds. Here, ${\mathbf{1}}^{(n)}$ denotes the n-dimensional vector where all elements are equal to one. For a matrix $M\in {\mathbb{R}}^{V\times V}$, let ${\lambda }_j(M)$ denote the j-th largest (in absolute value) eigenvalue of M.

For any round $1<\mathcal{\ell }\le n$ and $0\le t\le \mathfrak{d}(\mathcal{\ell })$, define a probability vector ${\nu }_t^{(\mathcal{\ell })}\in {[0,1]}^{V^{(\mathcal{\ell })}}$ where

for every $v\in V^{(\mathcal{\ell })}$. Furthermore, for any rounds $k,\mathcal{\ell }$ satisfying $k-1\le \mathcal{\ell }\le n-1$ and for any $v\in V^{(\mathcal{\ell })}$, define ${\mu }_{v_k}^{(\mathcal{\ell })}\in {[0,1]}^{V^{(\mathcal{\ell })}}$ byand ${\mu }_{v_k}^{(n)}≔{\mathbf{1}}^{(n)}$. Recall ${\tau }_v^{(i)}≔\min \{t\ge 0:X_t^{(i)}=v\}$. Then, combining the Cauchy-Schwarz inequality, (3), (11), and (12), we have

In the rest of this section, we show the following bounds of ${\Vert \frac{{\nu }_{\mathfrak{d}(k)}^{(k)}}{{\pi }^{(k)}}-{\mathbf{1}}^{(k)}\Vert }_{2,{\pi }^{(k)}}$ and ${\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}$, from which we immediately derive Theorem 4.

Lemma 3.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. If $\mathfrak{d}(i)\ge \frac{i(r_i-1)+1}{2i(1-{\lambda }_2(P^{(i)}))}$, then

$${\Vert \frac{{\nu }_{\mathfrak{d}(k)}^{(k)}}{{\pi }^{(k)}}-{\mathbf{1}}^{(k)}\Vert }_{2,{\pi }^{(k)}}^2<\underset{1<i\le n}{\max }i(r_i-1)$$

for all $1\le k\le n$, where r_i is defined in (10).

Lemma 4.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. Let N be an arbitrary positive number. If $\mathfrak{d}(i)\ge \left(\frac{1}{N}+\frac{r_i-1}{2}\right)t_{\text{hit}}(i)$ for all $1<i\le n$, then ${\sum }_{k=2}^n{\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}\le N,$ where r_i is defined in (10).

Proof of Theorem 4.

Suppose $\mathfrak{d}(i)\ge \frac{t_{\text{hit}}(i)}{N}+\frac{(i(r_i-1)+1)t_{\text{hit}}(i)}{2i}$ for all $1<i\le n$. Then, $\mathfrak{d}(i)\ge \frac{i(r_i-1)+1}{2i(1-{\lambda }_2(P^{(i)}))}$ from Lemma A.7. Furthermore, $\mathfrak{d}(i)\ge \frac{t_{\text{hit}}(i)}{N}+\frac{r_i-1}{2}{t}_{\text{hit}}(i)$. Thus, applying Lemmas 3 and 4 to (13),

$$\mathbf{E}[U(n)]\le {\displaystyle \sum _{k=2}^n\sqrt{\underset{1<i\le n}{\max }i(r_i-1)+1}}{\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}\le N\sqrt{\underset{1<i\le n}{\max }i(r_i-1)+1}$$

and we obtain the claim. □

Proof of Lemma 3.

First, we show the following lemma, which gives a general upper bound of ${\Vert \frac{{\nu }_{\mathfrak{d}(k)}^{(k)}}{{\pi }^{(k)}}-{\mathbf{1}}^{(k)}\Vert }_{2,{\pi }^{(k)}}^2$ in terms of r_i.

Lemma 5.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. Then for any round $1\le k\le n$,

$${\Vert \frac{{\nu }_{\mathfrak{d}(k)}^{(k)}}{{\pi }^{(k)}}-{\mathbf{1}}^{(k)}\Vert }_{2,{\pi }^{(k)}}^2\le {\displaystyle \sum _{i=2}^k\left(1-\frac{1}{r_i}\right)}{\displaystyle \prod _{j=i}^k{r}_j}{\lambda }_2{(P^{(j)})}^{2\mathfrak{d}(j)},$$

where r_i is defined in (10).

Proof.

To obtain the claim, we show the following recurrence inequality:

$${\left|\left|\frac{{\nu }_{\mathfrak{d}(\mathcal{\ell })}^{(\mathcal{\ell })}}{{\pi }^{(\mathcal{\ell })}}-{\mathbf{1}}^{(\mathcal{\ell })}\right|\right|}_{2,{\pi }^{(\mathcal{\ell })}}^2\le r_{\mathcal{\ell }}{\lambda }_2{(P^{(\mathcal{\ell })})}^{2\mathfrak{d}(\mathcal{\ell })}{\Vert \frac{{\nu }_{\mathfrak{d}(\mathcal{\ell }-1)}^{(\mathcal{\ell }-1)}}{{\pi }^{(\mathcal{\ell }-1)}}-{\mathbf{1}}^{(\mathcal{\ell }-1)}\Vert }_{2,{\pi }^{(\mathcal{\ell }-1)}}^2+(r_{\mathcal{\ell }}-1){\lambda }_2{(P^{(\mathcal{\ell })})}^{2\mathfrak{d}(\mathcal{\ell })}.$$(14)

Write $x_{\mathcal{\ell }}={\Vert \frac{{\nu }_{\mathfrak{d}(\mathcal{\ell })}^{(\mathcal{\ell })}}{{\pi }^{(\mathcal{\ell })}}-{\mathbf{1}}^{(\mathcal{\ell })}\Vert }_{2,{\pi }^{(\mathcal{\ell })}}^2,\hspace{0.17em}{c}_{\mathcal{\ell }}=r_{\mathcal{\ell }}{\lambda }_2{(P^{(\mathcal{\ell })})}^{2\mathfrak{d}(\mathcal{\ell })}$, and $d_{\mathcal{\ell }}=(r_{\mathcal{\ell }}-1){\lambda }_2{(P^{(\mathcal{\ell })})}^{2\mathfrak{d}(\mathcal{\ell })}$ for notational convenience. If (14) holds for any $\mathcal{\ell }>1$, applying (14) repeatedly yields

$$x_k\le c_k{x}_{k-1}+d_k\le c_k{c}_{k-1}{x}_{k-2}+c_k{d}_{k-1}+d_k\le \cdots \le \left({\displaystyle \prod _{i=2}^k{c}_i}\right)x_1+{\displaystyle \sum _{i=2}^k\left({\displaystyle \prod _{j=i+1}^k{c}_j}\right)}{d}_i.$$

Because $x_1={\Vert \frac{{\nu }_{\mathfrak{d}(1)}^{(1)}}{{\pi }^{(1)}}-{\mathbf{1}}^{(1)}\Vert }_{2,{\pi }^{(1)}}^2=0$ from definition, we obtain the claim.

Now we show (14). From the reversibility of $P^{(\mathcal{\ell })}$, it is easy to see that, for all $v\in V^{(\mathcal{\ell })}$,

$$\begin{array}{l}\left(\frac{{\nu }_t^{(\mathcal{\ell })}}{{\pi }^{(\mathcal{\ell })}}\right)(v)=\frac{{\sum }_{u\in V^{(\mathcal{\ell })}}{\nu }_0^{(\mathcal{\ell })}(u){({(P^{(\mathcal{\ell })})}^t)}_{u,v}}{{\pi }^{(\mathcal{\ell })}(v)}\\ ={\displaystyle \sum _{u\in V^{(\mathcal{\ell })}}\frac{{\nu }_0^{(\mathcal{\ell })}(u){({(P^{(\mathcal{\ell })})}^t)}_{v,u}}{{\pi }^{(\mathcal{\ell })}(u)}}=\left({(P^{(\mathcal{\ell })})}^t\frac{{\nu }_0^{(\mathcal{\ell })}}{{\pi }^{(\mathcal{\ell })}}\right)(v).\end{array}$$(15)

From (15) and Lemma A.6, it holds that

$${\Vert \frac{{\nu }_{\mathfrak{d}(\mathcal{\ell })}^{(\mathcal{\ell })}}{{\pi }^{(\mathcal{\ell })}}-{\mathbf{1}}^{(\mathcal{\ell })}\Vert }_{2,{\pi }^{(\mathcal{\ell })}}^2\le {\lambda }_2{(P^{(\mathcal{\ell })})}^{2\mathfrak{d}(\mathcal{\ell })}{\Vert \frac{{\nu }_0^{(\mathcal{\ell })}}{{\pi }^{(\mathcal{\ell })}}-{\mathbf{1}}^{(\mathcal{\ell })}\Vert }_{2,{\pi }^{(\mathcal{\ell })}}^2$$(16)

$$={\lambda }_2{(P^{(\mathcal{\ell })})}^{2\mathfrak{d}(\mathcal{\ell })}\left({\Vert \frac{{\nu }_0^{(\mathcal{\ell })}}{{\pi }^{(\mathcal{\ell })}}\Vert }_{2,{\pi }^{(\mathcal{\ell })}}^2-1\right).$$(17)

Furthermore, for a vertex $v_{\mathcal{\ell }}$ which appears at the round $\mathcal{\ell }$, because ${\nu }_0^{(\mathcal{\ell })}(v_{\mathcal{\ell }})=\mathbf{\text{Pr}}[X_0^{(\mathcal{\ell })}=v_{\mathcal{\ell }}]=0$ holds, we have

$$\begin{array}{l}{\Vert \frac{{\nu }_0^{(\mathcal{\ell })}}{{\pi }^{(\mathcal{\ell })}}\Vert }_{2,{\pi }^{(\mathcal{\ell })}}^2={\displaystyle \sum _{v\in V^{(\mathcal{\ell }-1)}}{\pi }^{(\mathcal{\ell })}}(v)\frac{{\nu }_0^{(\mathcal{\ell })}{(v)}^2}{{\pi }^{(\mathcal{\ell })}{(v)}^2}={\displaystyle \sum _{v\in V^{(\mathcal{\ell }-1)}}\frac{{\pi }^{(\mathcal{\ell }-1)}(v)}{{\pi }^{(\mathcal{\ell })}(v)}}{\pi }^{(\mathcal{\ell }-1)}(v)\frac{{\nu }_{\mathfrak{d}(\mathcal{\ell }-1)}^{(\mathcal{\ell }-1)}{(v)}^2}{{\pi }^{(\mathcal{\ell }-1)}{(v)}^2}\\ \le r_{\mathcal{\ell }}{\displaystyle \sum _{v\in V^{(\mathcal{\ell }-1)}}{\pi }^{(\mathcal{\ell }-1)}}(v)\frac{{\nu }_{\mathfrak{d}(\mathcal{\ell }-1)}^{(\mathcal{\ell }-1)}{(v)}^2}{{\pi }^{(\mathcal{\ell }-1)}{(v)}^2}=r_{\mathcal{\ell }}{\Vert \frac{{\nu }_{\mathfrak{d}(\mathcal{\ell }-1)}^{(\mathcal{\ell }-1)}}{{\pi }^{(\mathcal{\ell }-1)}}\Vert }_{2,{\pi }^{(\mathcal{\ell }-1)}}^2.\end{array}$$(18)

Combining (17) and (18), we obtain (14). □

Proof of Lemma 3.

First, we observe that $\log \left(r_j\left(\frac{j+1}{j}\right)\right)=\log (1+(r_j-1))+\log (1+\frac{1}{j})\le (r_j-1)+\frac{1}{j}$. Hence, it holds that

$${\lambda }_2{(P^{(j)})}^{2\mathfrak{d}(j)}\le {(1-(1-{\lambda }_2(P^{(j)})))}^{\frac{\log (r_j(\frac{j+1}{j}))}{1-{\lambda }_2(P^{(j)})}}\le \frac{1}{r_j}·\frac{j}{j+1}.$$

Applying Lemma 5, we obtain

$$\begin{array}{l}{\Vert \frac{{\nu }_{\mathfrak{d}(k)}^{(k)}}{{\pi }^{(k)}}-{\mathbf{1}}^{(k)}\Vert }_{2,{\pi }^{(k)}}^2\le {\displaystyle \sum _{i=2}^k\left(1-\frac{1}{r_i}\right)}\left({\displaystyle \prod _{j=i}^k{r}_j}{\lambda }_2{(P^{(j)})}^{2\mathfrak{d}(j)}\right)\\ \le {\displaystyle \sum _{i=2}^k\left({\displaystyle \prod _{j=i}^k\frac{j}{j+1}}\right)}\frac{r_i-1}{r_i}\le {\displaystyle \sum _{i=2}^k\frac{i}{k+1}}(r_i-1)\\ \le \underset{1<i\le n}{\max }i(r_i-1)\frac{k-1}{k+1}<\underset{1<i\le n}{\max }i(r_i-1).\hspace{1em}\square \end{array}$$

Proof of Lemma 4.

We begin by presenting two auxiliary results.

Lemma 6.

For $f,h:\mathbb{N}\to \mathbb{N}$ and $n\in \mathbb{N}$, let

$$S_{*}(n)≔{\displaystyle \sum _{k=1}^n{\displaystyle \prod _{i=k}^n{\left(1-\frac{1}{h(i)}\right)}^{f(i)}}}.$$

Let n > 0 be an arbitrary number. If $f(i)\ge \frac{h(i)}{N}$ for all $i\in [n]$, then $S(n)\le N$.

Proof.

It is easy to check that

$$\begin{array}{l}{S}_{*}(n)\le {\displaystyle \sum _{k=1}^n{\displaystyle \prod _{i=k}^n\exp }}\left(-\frac{f(i)}{h(i)}\right)={\displaystyle \sum _{k=1}^n\exp }\left(-{\displaystyle \sum _{i=k}^n\frac{f(i)}{h(i)}}\right)\\ \le {\displaystyle \sum _{k=1}^n\exp }\left(-\frac{n+k-1}{N}\right)={\displaystyle \sum _{k=1}^n\exp }\left(-\frac{k}{N}\right)\\ \le \frac{{\text{e}}^{-1/N}}{1-{\text{e}}^{-1/N}}=\frac{1}{{\text{e}}^{1/N}-1}\le N.\end{array}$$

Note that we use $1+x\le {\text{e}}^x$ in the first and last inequalities. □

Lemma 7.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. Then, for any round k satisfying $1<k\le n$,

$${\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}\le {\displaystyle \prod _{i=k}^n\sqrt{r_i}}{\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)},$$

where r_i is defined in (10).

Proof.

For a transition matrix $P\in {[0,1]}^{V\times V}$ and a vertex $w\in V$, define $P_{\overline{w}}\in {[0,1]}^{V\times V}$ by

$${(P_{\overline{w}})}_{u,v}=\{\begin{array}{ll}{P}_{u,v}\hfill & (\text{if} u\ne w \text{and} v\ne w)\hfill \\ 0\hfill & (\text{otherwise}).\hfill \end{array}$$

In other words, ${(P_{\overline{w}})}_{u,v}=P_{u,v}{\mathbf{1}}_{u\ne w}{\mathbf{1}}_{v\ne w}$ for $u,v\in V$. Note that $P_{\overline{w}}$ is a substochastic matrix (see, e.g., section 3.6.5 of Aldous and Fill [2]); that is, ${\sum }_{v\in V}{(P_{\overline{w}})}_{u,v}\le 1$ holds for any $u\in V$. Observe that, for any $u,v\in V$ and T > 0,

$${(P_{\overline{w}}^T)}_{u,v}=\mathbf{\text{Pr}}\left[{\tau }_w>T,X_T=v|X_0=u\right].$$(19)

Here, ${(X_t)}_{t=0}^{\infty }$ denotes a sequence of a random walk according to P and τ_w denotes the hitting time to w. Note that ${(P_{\overline{w}}^T)}_{u,v}=0$ if u = w or v = w.

Consider a fixed k > 1. Write ${\mu }^{(\mathcal{\ell })}={\mu }_{v_k}^{(\mathcal{\ell })}$ and $Q^{(\mathcal{\ell })}={(P_{{\overline{v}}_k}^{(\mathcal{\ell })})}^{\mathfrak{d}(\mathcal{\ell })}$ for notational convenience. The key property for the proof is the following recurrence equation: for all $k-1\le \mathcal{\ell }\le n-1$ and $v\in V^{(\mathcal{\ell })}$, it holds that

$${\mu }^{(\mathcal{\ell })}(v)=(Q^{(\mathcal{\ell }+1)}{\mu }^{(\mathcal{\ell }+1)})(v).$$(20)

This equation holds because for any $u_{\mathcal{\ell }}\in V^{(\mathcal{\ell })}$, combining (8), (12), and (19) yields

$$\begin{array}{l}{\mu }^{(\mathcal{\ell })}(u_{\mathcal{\ell }})=\mathbf{\text{Pr}}\left[\underset{i=\mathcal{\ell }+1}{\overset{n}{{\displaystyle \wedge }}}\left\{{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)\right\}|X_{\mathfrak{d}(\mathcal{\ell })}^{(\mathcal{\ell })}=u_{\mathcal{\ell }}\right]\\ ={\displaystyle \sum _{u_{\mathcal{\ell }+1}\in V^{(\mathcal{\ell }+1)}}\cdots }{\displaystyle \sum _{u_n\in V^{(n)}}{\displaystyle \prod _{i=\mathcal{\ell }+1}^n{({(P_{\overline{v_k}}^{(i)})}^{\mathfrak{d}(i)})}_{u_{i-1},u_i}}}\\ ={\displaystyle \sum _{u_{\mathcal{\ell }+1}\in V^{(\mathcal{\ell }+1)}}{Q}_{u_{\mathcal{\ell }},u_{\mathcal{\ell }+1}}^{(\mathcal{\ell }+1)}}{\displaystyle \sum _{u_{\mathcal{\ell }+2}\in V^{(\mathcal{\ell }+2)}}{Q}_{u_{\mathcal{\ell }+1},u_{\mathcal{\ell }+2}}^{(\mathcal{\ell }+2)}}\cdots {\displaystyle \sum _{u_n\in V^{(n)}}{Q}_{u_{n-1},u_n}^{(n)}}\\ ={\displaystyle \sum _{u_{\mathcal{\ell }+1}\in V^{(\mathcal{\ell }+1)}}{Q}_{u_{\mathcal{\ell }},u_{\mathcal{\ell }+1}}^{(\mathcal{\ell }+1)}}{\mu }^{(\mathcal{\ell }+1)}(u_{\mathcal{\ell }+1}).\end{array}$$

Using (20) and Corollary A.2, we obtain

$$\begin{array}{l}{\Vert {\mu }^{(\mathcal{\ell })}\Vert }_{2,{\pi }^{(\mathcal{\ell })}}^2={\displaystyle \sum _{v\in V^{(\mathcal{\ell })}}{\pi }^{(\mathcal{\ell })}}(v){\mu }^{(\mathcal{\ell })}{(v)}^2\\ ={\displaystyle \sum _{v\in V^{(\mathcal{\ell })}}\frac{{\pi }^{(\mathcal{\ell })}(v)}{{\pi }^{(\mathcal{\ell }+1)}(v)}}{\pi }^{(\mathcal{\ell }+1)}(v)(Q^{(\mathcal{\ell }+1)}{\mu }^{(\mathcal{\ell }+1)}){(v)}^2\\ \le r_{\mathcal{\ell }+1}{\displaystyle \sum _{v\in V^{(\mathcal{\ell }+1)}}{\pi }^{(\mathcal{\ell }+1)}}(v)(Q^{(\mathcal{\ell }+1)}{\mu }^{(\mathcal{\ell }+1)}){(v)}^2\\ =r_{\mathcal{\ell }+1}{\Vert Q^{(\mathcal{\ell }+1)}{\mu }^{(\mathcal{\ell }+1)}\Vert }_{2,{\pi }^{(\mathcal{\ell }+1)}}^2\\ \le r_{\mathcal{\ell }+1}{\lambda }_1{(Q^{(\mathcal{\ell }+1)})}^2{\Vert {\mu }^{(\mathcal{\ell }+1)}\Vert }_{2,{\pi }^{(\mathcal{\ell }+1)}}^2.\end{array}$$(21)

Hence, applying (21) repeatedly, it holds that

$${\Vert {\mu }^{(\mathcal{\ell })}\Vert }_{2,{\pi }^{(\mathcal{\ell })}}^2\le {\displaystyle \prod _{i=\mathcal{\ell }+1}^n{r}_i}{\lambda }_1{(Q^{(i)})}^2.$$(22)

From the definition of $Q^{(i)}$ and $P_{{\overline{v}}_k}^{(i)}$, Lemma A.5 implies

$${\lambda }_1(Q^{(i)})={\lambda }_1{(P_{{\overline{v}}_k}^{(i)})}^{\mathfrak{d}(i)}\le {\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)}.$$(23)

Thus, we obtain the claim from (22) and (23). □

Proof of Lemma 4.

Because $\log \sqrt{r_i}=\frac{1}{2}\log r_i=\frac{1}{2}\log (1+(r_i-1))\le \frac{r_i-1}{2}$, we have

$$\begin{array}{l}\sqrt{r_i}{\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)}=\sqrt{r_i}{\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{t_{\text{hit}}(i)\log \sqrt{r_i}}{\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)-t_{\text{hit}}(i)\log \sqrt{r_i}}\\ \le \sqrt{r_i}·\exp \left(-\log \sqrt{r_i}\right)·{\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)-t_{\text{hit}}(i)\log \sqrt{r_i}}\\ ={\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)-t_{\text{hit}}(i)\log \sqrt{r_i}}\\ \le {\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)-\frac{r_i-1}{2}{t}_{\text{hit}}(i)}.\end{array}$$(24)

Thus, combining Lemma 7 and (24),

$${\displaystyle \sum _{k=2}^n}{\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}\le {\displaystyle \sum _{k=2}^n{\displaystyle \prod _{i=k}^n{\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)-\frac{r_i-1}{2}{t}_{\text{hit}}(i)}}}\le N.$$

We invoked Lemma 6 in the last inequality. □

4.2. Example: Lollipop Graphs and Metropolis Walks

Corollary 1.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG such that $P^{(i)}$ is lazy and simple, and that for all i ($2<i\le n$), $\frac{|E^{(i)}|}{|E^{(i-1)}|}\le 1+\frac{L}{i}$ hold for some positive constant L. Let C > 0 and $\gamma \in [0,1]$ be arbitrary constants. If $\mathfrak{d}(i)\ge \left(\frac{C}{i^{\gamma }}+\frac{L+1}{2i}\right)t_{\text{hit}}(i)$ holds for any $1<i\le n$, then $\mathbf{E}[U(n)]\le \sqrt{L+1}\frac{n^{\gamma }}{C}$.

Proof.

Let $d_v^{(i)}$ denote the degree of a vertex $v\in V^{(i)}$ at round i. Then, for all $v\in V^{(i)}$,

$$\frac{{\pi }^{(i-1)}(v)}{{\pi }^{(i)}(v)}=\frac{d_v^{(i-1)}}{2|E^{(i-1)}|}\frac{2|E^{(i)}|}{d_v^{(i)}}\le \frac{|E^{(i)}|}{|E^{(i-1)}|}.$$

Note that $d_v^{(i-1)}\le d_v^{(i)}$ holds from our assumption. Combining the assumptions on $\mathfrak{d}(i)$ and $E^{(i)}$, we have $\mathfrak{d}(i)\ge \frac{t_{\text{hit}}(i)}{i^{\gamma }/C}+\frac{L+1}{2i}{t}_{\text{hit}}(i)\ge \frac{t_{\text{hit}}(i)}{n^{\gamma }/C}+\frac{L+1}{2i}{t}_{\text{hit}}(i)$. Thus, we obtain the claim by taking $N=n^{\gamma }/C$ in Theorem 4. □

Corollary 2.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG such that $P^{(i)}$ is lazy and symmetric (i.e., $P_{u,v}^{(i)}=P_{v,u}^{(i)}$ for all $u,v\in V^{(i)}$). Let C > 0 and $\gamma \in [0,1]$ be arbitrary constants. If $\mathfrak{d}(i)\ge \left(\frac{C}{i^{\gamma }}+\frac{2}{i}\right)t_{\text{hit}}(i)$ for all $1<i\le n$, then $\mathbf{E}[U(n)]\le \frac{\sqrt{3}{n}^{\gamma }}{C}$.

Proof.

Because $P^{(i)}$ is symmetric, $r_i=\frac{i}{i-1}\le 1+\frac{2}{i}$ for all i > 1. From the assumption of Corollary 2, $\mathfrak{d}(i)\ge \frac{t_{\text{hit}}(i)}{i^{\gamma }/C}+\frac{2t_{\text{hit}}(i)}{i}\ge \frac{t_{\text{hit}}(i)}{n^{\gamma }/C}+\frac{t_{\text{hit}}(i)(2+1)}{2i}$ for all $1<i\le n$. Thus, we obtain the claim by taking $N=n^{\gamma }/C$ in Theorem 4. □

4.2.1. Example: Lollipop Graph.

Consider a growing lollipop graph: We consider $G^{(i)}$ consisting of the complete graph $K_{\lceil i/2\rceil }$ and the path graph $P_{\lfloor i/2\rfloor }$. Formally, at each round $i\in [n]$, the set of odd vertices $V_o^{(i)}≔\{v_{2i-1}:1\le i\le \lceil i/2\rceil \}$ forms the complete graph $K_{\lceil i/2\rceil }$, the set of even vertices $V_e^{(i)}≔\{v_{2i}:1\le i\le \lfloor i/2\rfloor \}$ forms a path graph, and these two components are connected by $\{v_1,v_2\}$. Let $P^{(i)}$ be the transition matrix of the simple lazy random walk on $G^{(i)}$. For such $P^{(i)}$, it is well known that $t_{\text{hit}}(i)=\text{O}(i^3)$ (see, e.g., Feige [20]).

Corollary 3.

Let $R=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $G^{(i)}$ is the lollipop graph defined above and ${(P^{(i)})}_{i\in [n]}$ is the transition matrix of the lazy simple random walk on $G^{(i)}$. Let $\gamma \in [0,1]$ be an arbitrary constant. If $\mathfrak{d}(i)\ge C_1{i}^{3-\gamma }$ for all i, then $\mathbf{E}[U(n)]\le C_2{n}^{\gamma }$. Here, C₁, C₂ are some positive constants.

Proof.

By definition, $|E^{(2i)}|=1+\frac{i(i-1)}{2}+i-1=\frac{i(i+1)}{2}$ and $|E^{(2i+1)}|=1+\frac{(i+1)i}{2}+i-1=\frac{i(i+3)}{2}$. Thus, for any i, $\frac{|E^{(i)|}}{|E^{(i-1)|}}\le 1+\frac{K_1}{i}$ for some constant K₁. Furthermore, $t_{\text{hit}}^{(i)}\le K_2{i}^3$ holds for some constant K₂. Applying Corollary 1, we obtain the claim. □

4.2.2. Example: Metropolis Walk.

For a given $G=(V,E)$, the transition matrix of the lazy Metropolis walk on G is defined by

Because of the work of Nonaka et al. [32], we have $t_{\text{hit}}(P)=\text{O}(|V{|}^2)$ for any connected graphs. Because P is a symmetric matrix, we can apply Corollary 2.

Corollary 4.

Suppose that $P^{(i)}$ is the lazy Metropolis walk on a connected graph $G^{(i)}$ in $R=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$. Let $\gamma \in [0,1]$ and C > 0 be arbitrary constants. If $\mathfrak{d}(i)\ge \left(\frac{C}{i^{\gamma }}+\frac{2}{i}\right)t_{\text{hit}}(i)$ for all $1<i\le n$, then $\mathbf{E}[U(n)]\le \sqrt{3}\frac{n^{\gamma }}{C}$.

4.3. Upper Bound for Random Walks with Small Mixing Times

In this section, we show the following general result that concerns an RWoGG with a small mixing time.

Theorem 5.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. Let N > 0 be an arbitrary positive number. If $\mathfrak{d}(i)\ge \frac{t_{\text{hit}}(i)}{N}+2t_{\text{mix}}(i)$ for all $i\in [n]$, then $\mathbf{E}[U(n)]\le 8N+32$.

To show Theorem 5, we introduce the following lemma that is a useful variant of Lemma 2.

Lemma 8.

Let $R=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG. For any function $s:\mathbb{N}\to \mathbb{N}$ such that $s(i)<\mathfrak{d}(i)$ holds for all i, we have

$$\mathbf{E}[U(n)]\le {\displaystyle \sum _{k=2}^n{\displaystyle \prod _{i=k}^n\underset{u\in V^{(i)}}{\max }}}{\displaystyle \sum _{v\in V^{(i)}}{({(P^{(i)})}^{s(i)})}_{u,v}}\mathbf{P}\mathbf{r}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)-s(i)|X_0^{(i)}=v].$$

Proof.

Fix $k\ge 2$ and i satisfying $k\le i\le n$. First, for any $u,v\in V^{(i)}$, from the definition of the conditional probability, we observe that

$$\begin{array}{l}\mathbf{P}\mathbf{r}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i),X_{s(i)}^{(i)}=v|X_0^{(i)}=u]\\ =\mathbf{\text{Pr}}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)|X_{s(i)}^{(i)}=v,X_0^{(i)}=u,{\tau }_{v_k}^{(i)}>s(i)]\\ \cdot \mathbf{\text{Pr}}[X_{s(i)}^{(i)}=v,{\tau }_{v_k}^{(i)}>s(i)|X_0^{(i)}=u]\\ =\mathbf{\text{Pr}}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)-s(i)|X_0^{(i)}=v] \cdot \mathbf{\text{Pr}}[X_{s(i)}^{(i)}=v,{\tau }_{v_k}^{(i)}>s(i)|X_0^{(i)}=u]\end{array}$$

holds, where we use the Markov property in the third equality. Because

$$\mathbf{\text{Pr}}[X_{s(i)}^{(i)}=v,{\tau }_{v_k}^{(i)}>s(i)|X_0^{(i)}=u]\le \mathbf{\text{Pr}}[X_{s(i)}^{(i)}=v|X_0^{(i)}=u]={({(P^{(i)})}^{s(i)})}_{u,v},$$

we have

$$\begin{array}{l}\mathbf{P}\mathbf{r}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)|X_0^{(i)}=u]={\displaystyle \sum _{v\in V^{(i)}}\mathbf{\text{Pr}}}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i),X_{s(i)}^{(i)}=v|X_0^{(i)}=u]\\ \le {\displaystyle \sum _{v\in V^{(i)}}{({(P^{(i)})}^{s(i)})}_{u,v}}\mathbf{P}\mathbf{r}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)-s(i)|X_0^{(i)}=v]\end{array}$$(26)

for any $u\in V^{(i)}$. Combining Lemma 2 and (26), we obtain the claim. □

Proof of Theorem 5.

If $P^{(i)}$ is reversible, for any $i\in [n]$ and $u,v\in V^{(i)}$, some transition matrix ${\widehat{P}}^{(i)}\in {[0,1]}^{V^{(i)}\times V^{(i)}}$ exists such that

$${({(P^{(i)})}^{2t_{\text{mix}}(i)})}_{u,v}=\frac{1}{4}{\pi }^{(i)}(v)+\frac{3}{4}{({\widehat{P}}^{(i)})}_{u,v}$$(27)

holds (see, e.g., Levin and Peres [27, p. 338]). Hence, it holds for any $u\in V^{(i)}$ that

$$\begin{array}{l}{\displaystyle \sum _{v\in V^{(i)}}{({(P^{(i)})}^{2t_{\text{mix}}(i)})}_{u,v}}\cdot \mathbf{\text{Pr}}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)-2t_{\text{mix}}(i)|X_0^{(i)}=v]\\ =\frac{1}{4}{\displaystyle \sum _{v\in V^{(i)}}{\pi }^{(i)}}(v)\mathbf{\text{Pr}}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)-2t_{\text{mix}}(i)|X_0^{(i)}=v]\\ +\frac{3}{4}{\displaystyle \sum _{v\in V^{(i)}}{({\widehat{P}}^{(i)})}_{u,v}}\mathbf{P}\mathbf{r}[{\tau }_{v_k}^{(i)}>\mathfrak{d}(i)-2t_{\text{mix}}(i)|X_0^{(i)}=v]\\ \le \frac{1}{4}\exp \left(-\frac{\mathfrak{d}(i)-2t_{\text{mix}}(i)}{t_{\text{hit}}(i)}\right)+\frac{3}{4}\le \frac{1}{4}\exp \left(-\frac{1}{N}\right)+\frac{3}{4}.\end{array}$$(28)

We use Corollary A.1 in the first inequality. Now, for a positive integer L, consider a random variable $X\sim \text{Bin}(L,1/4)$. Here, $\text{Bin}(L,1/4)$ is the binomial distribution with parameters L and 1/4. Then, it is straightforward to see that

$$\begin{array}{l}{\left(\frac{1}{4}\exp \left(-\frac{1}{N}\right)+\frac{3}{4}\right)}^L={\displaystyle \sum _{i=0}^L\left(\begin{array}{c}L\\ i\end{array}\right)}{\left(\frac{1}{4}\exp \left(-\frac{1}{N}\right)\right)}^i{\left(\frac{3}{4}\right)}^{L-i}\\ ={\displaystyle \sum _{i=0}^L\exp }\left(-\frac{i}{N}\right)\mathbf{P}\mathbf{r}\left[X=i\right]\\ \le {\displaystyle \sum _{i=0}^{\lfloor L/8\rfloor }\exp }\left(-\frac{i}{N}\right)\mathbf{P}\mathbf{r}\left[X=i\right]+{\displaystyle \sum _{i=\lceil L/8\rceil }^L\exp }\left(-\frac{i}{N}\right)\mathbf{P}\mathbf{r}\left[X=i\right]\\ \le \mathbf{\text{Pr}}\left[X\le \frac{L}{8}\right]+\exp \left(-\frac{L}{8N}\right)\\ \le \exp \left(-\frac{L}{32}\right)+\exp \left(-\frac{L}{8N}\right).\end{array}$$(29)

The last inequality follows because

$$\mathbf{\text{Pr}}\left[X\le \frac{L}{8}\right]=\mathbf{\text{Pr}}\left[X\le \frac{\mathbf{E}[X]}{2}\right]\le \exp \left(-\frac{\mathbf{E}[X]}{8}\right)=\exp \left(-\frac{L}{32}\right)$$

holds from the Chernoff inequality Lemma A.2. Combining Lemma 8 and (28) and (29), we obtain

$$\begin{array}{l}\mathbf{E}[U(n)]\le {\displaystyle \sum _{k=1}^n{\left(\frac{1}{4}\exp \left(-\frac{1}{N}\right)+\frac{3}{4}\right)}^{n-k+1}}\\ \le {\displaystyle \sum _{k=1}^n\left(\exp \left(-\frac{n-k+1}{32}\right)+\exp \left(-\frac{n-k+1}{8N}\right)\right)}\\ ={\displaystyle \sum _{k=1}^n\exp }\left(-\frac{k}{32}\right)+{\displaystyle \sum _{k=1}^n\exp }\left(-\frac{k}{8N}\right)\le 32+8N.\hspace{1em}\square \end{array}$$

4.3.1. Example: Degree Restricted Expander Graph.

For a graph $G=(V,E)$, let $d_{\text{ave}}(G)$ and $d_{\text{min}}(G)$ denote the average and the minimum degree of G, respectively. Suppose that P is the transition matrix of the lazy simple random walk on G and let ${\lambda }_2(P)$ denote the second-largest eigenvalue of P. We call a graph G degree restricted expander graph if both $\frac{d_{\text{ave}}(G)}{d_{\min }(G)}$ and $\frac{1}{1-{\lambda }_2(P)}$ are upper bounded by some positive constant. For any degree restricted expander graph, we have $t_{\text{hit}}(P)=\text{O}(|V|)$ and $t_{\text{mix}}(P)=\text{O}(\log |V|)$ (see Lemma A.7 in the appendix and theorem 12.4 in Levin and Peres [27]). Thus, Theorem 5 implies the following.

Corollary 5.

Let $R=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $G^{(i)}$ is a degree restricted expander graph and $P^{(i)}$ is the transition matrix of the lazy simple random walk on $G^{(i)}$. Let $\gamma \in [0,1]$ and C > 0 be arbitrary constants. Then there exist two positive constants K₁, K₂ such that $\mathbf{E}[U(n)]\le 8\frac{n^{\gamma }}{C}+32$ if $\mathfrak{d}(i)\ge C{K}_1{i}^{1-\gamma }+K_2\log i$ for all $i\in [n]$.

Proof.

Because there exist some positive constants K₁, K₂ satisfying $t_{\text{hit}}(i)\le K_{1}i$ and $t_{\text{mix}}\le K_2\log i$, we obtain the claim from Theorem 5. □

5. Random Walk on a Growing Preferential Attachment Model

The structure of large-scale real-world networks such as social networks, citation networks, and protein-interaction networks has gathered considerable attention in network analysis. These networks typically have several structural features including the small-world property (Watts and Strogatz [38]) and scale-free degree distribution (Barabási and Albert [7]). Because real-world networks expand day by day, it is natural to model them with a growing sequence of random graphs. A prominent example of such a model is the PA model (Barabási and Albert [7]).

The PA model is a sequence of random graphs ${\mathcal{G}}_d={(G_d^{(i)})}_{i\in \mathbb{N}}$ with a constant parameter $d\in \mathbb{N}$ generated in the following way: We first generate the following random graph T_nd on nd vertices. Initially, T₁ consists of a single vertex u₁ with a self-loop. The graph $T_{k+1}$ can be obtained by adding a vertex $u_{k+1}$ and an edge $\{u_{k+1},u_i\}$ to T_k, where the index i is chosen from $[k]$ with probability proportional to the degree of u_i. Finally, we obtain the graph $G_d^{(n)}$ by contracting d consecutive vertices $u_{id+1},u_{id+2},\dots ,u_{id+d}$ of T_nd for each $i=0,\dots ,n-1$. Note that $G_d^{(n)}$ may contain self-loops and multiedges. We obtain the following result concerning the lazy simple random walk on ${\mathcal{G}}_d$.

Theorem 6.

For any $\gamma >0$, there exist constants $d=d(\gamma )$ and $C=C(\gamma )$ such that the RWoGG $R=(\mathfrak{d},{\mathcal{G}}_d,{(P^{(i)})}_{i=1}^{\infty })$ for the lazy simple random walk on ${\mathcal{G}}_d$ with duration $\mathfrak{d}(i)\ge C{i}^{1-\gamma }$ satisfies $\mathbf{E}[U(n)]\le 4n^{\gamma }$ with probability $1-\text{O}(n^{-1})$ over the construction of ${\mathcal{G}}_d$.

The proof of Theorem 6 is the main difference of this paper from the preliminary version (Kijima et al. [24]). To prove Theorem 6, we exploit the structural properties of ${\mathcal{G}}_d$, namely the conductance. The conductance ${\mathrm{\Phi }}_G$ of a graph $G=(V,E)$ is

where $\text{vol}(S)={\sum }_{s\in S}\mathrm{deg}(s)$ and $e(S,V\setminus S)$ is the number of edges lying between S and $V\setminus S$. By the Cheeger inequality, a graph with high conductance has a rapid mixing as follows.

Lemma 9

(Cheeger Inequality; See, e.g., Theorem 13.10 of Levin and Peres [27]). Let P be the transition matrix of the lazy simple random walk on a graph G and let λ₂ be its second-largest eigenvalue. Then,

$$\frac{{\mathrm{\Phi }}_G^2}{2}\le 1-{\lambda }_2\le 2{\mathrm{\Phi }}_G.$$

Mihail et al. [31] proved that $G_d^{(n)}$ has a constant conductance.

Lemma 10

(Theorem 1 of Mihail et al. [31]). For every $d\ge 2$ and $c<2(d-1)-1$, let $\alpha =\alpha (d,c)≔\min \{\frac{d-1}{2}-\frac{c+1}{4},\frac{1}{5},\frac{(d-1)\ln 2-0.4\ln 5}{2(\ln d+\ln 2+1)}\}$. Then,

$$\mathbf{\text{Pr}}[{\mathrm{\Phi }}_{G_d^{(n)}}\ge \alpha ]\ge 1-\text{o}(n^{-c}).$$

Corollary 6.

For any $ϵ>0$, there exist positive constants $d=d(ϵ),\hspace{0.17em}\alpha =\alpha (ϵ)$, and $C=C(ϵ)$ such that the RWoGG $R=(\mathfrak{d},{\mathcal{G}}_d,{(P^{(i)})}_{i=1}^{\infty })$ for the lazy simple random walk on ${\mathcal{G}}_d$ satisfies the following with probability $1-\text{O}(n^{-1})$ (here, the probability is taken over the construction of ${\mathcal{G}}_d$): For every $i=\lceil n^{ϵ}\rceil ,\dots ,n$, $t_{\text{hit}}(i)\le Ci$.

Proof.

Let $c=c(ϵ)$ be a sufficiently large constant (say, $c=\lceil 100/ϵ\rceil$). From Lemma 10 and the union bound over $i=\lceil n^{ϵ}\rceil ,\dots ,n$, with probability $1-\text{O}(n^{-1})$, all ${(G_d^{(i)})}_{i=\lceil n^{ϵ}\rceil }^n$ have conductance at least $\alpha (c,d)$. Conditioned on this event, the Cheeger inequality (Lemma 9) implies ${\lambda }_2(P^{(i)})\ge \frac{h{(i)}^2}{2}\ge \frac{{\alpha }^2}{2}=\mathrm{\Omega }(1)$ for $h(i)≔{\mathrm{\Phi }}_{G_d^{(i)}}$. This implies $t_{\text{hit}}(i)=\text{O}(i)$ (see Lemma A.7). Note that ${\pi }_{\min }\ge {(2i)}^{-1}$ because $G_d^{(i)}$ has minimum degree at least d and id edges. □

Note that Corollary 6 establishes the rapid hitting for every sufficiently large graph (i.e., graphs on $n^{\mathrm{\Omega }(1)}$ vertices). Our strategy is to apply Theorem 4 that bounds $\mathbf{E}[U(n)]$ in terms of the hitting time. However, Theorem 4 requires the condition that the duration $\mathfrak{d}(i)$ is large for all $i\in \mathbb{N}$. We will show that this condition can be relaxed as follows.

Theorem 7.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. Let $C≔\max \{1,{\max }_{i<i\le n}\{i(r_i-1)\}\}$, where r_i is defined in (10). Let N > 0 be an arbitrary number. If $\mathfrak{d}(i)\ge \left(\frac{1}{N}+\frac{i(r_i-1)+1}{2i}\right)t_{\text{hit}}^{(i)}$ for any $i\ge L$, then $\mathbf{E}[U(n)]\le 2C{L}^C(L+1)+(L+N)\sqrt{C+2}-1$.

Note that the upper bound of Theorem 7 could be worse than that of Theorem 4 if $\sqrt{C}\gg N$: Taking L = 1, $\mathbf{E}[U(n)]=\text{O}(N\sqrt{C})$ for Theorem 4 and $\mathbf{E}[U(n)]=\text{O}(C+N\sqrt{C})$ for Theorem 7.

Proof of Theorem 6.

Assume that $t_{\text{hit}}(i)\le C\prime i$ holds for every $i=\lceil n^{ϵ}\rceil ,\dots ,n$ with an appropriate constant $C\prime =C\prime (\gamma )$, which occurs with probability $1-\text{O}(n^{-1})$ by Corollary 6. Under the condition, we apply Theorem 7 with $L={(N-1)}^{1/(C+1)}$ and C = 1 (note that $r_i\le 1+\frac{1}{i}$). Then, for a sufficiently large n, we have

$$\mathbf{E}[U(n)]\le (2+\sqrt{3}+\text{o}(1))n^{\gamma }\le 4n^{\gamma }.\hspace{1em}\square$$

5.1. Relax the Condition on $\mathfrak{d}(i)$

Assumptions of our results so far are of the form $\mathfrak{d}(i)\ge f(i)$ for all $i\in \mathbb{N}$. We relax this condition to the form $\mathfrak{d}(i)\ge f(i)$ for any $i\ge L$ and obtain upper bounds of $\mathbf{E}[U(n)]$ in terms of L. Note that, by the same argument as (13), for any M, we have

We will determine M later.

Lemma 11.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. Let $C≔\max \{1,{\max }_{i<i\le n}\{i(r_i-1)\}\}$, where r_i is defined in (10). If $\mathfrak{d}(i)\ge \frac{i(r_i-1)+1}{2i(1-{\lambda }_2(P^{(i)}))}$ for any $i\ge L$, then, for all k satisfying $L\le k\le n$, ${\Vert \frac{{\nu }_{\mathfrak{d}(k)}^{(k)}}{{\pi }^{(k)}}-{\mathbf{1}}^{(k)}\Vert }_{2,{\pi }^{(k)}}^2\le 2C{L}^C(L+1)/(k+1)+C$.

Proof.

From the definition of C, we have $r_i\le 1+\frac{C}{i}$ and $C\ge 1$. Fix $k\ge L$. From Lemma 5, we have

$$\begin{array}{l}{\Vert \frac{{\nu }_{\mathfrak{d}(k)}^{(k)}}{{\pi }^{(k)}}-{\mathbf{1}}^{(k)}\Vert }_{2,{\pi }^{(k)}}^2\le {\displaystyle \sum _{i=2}^k\left(1-\frac{1}{r_i}\right)}{\displaystyle \prod _{j=i}^k{r}_j}{\lambda }_2{(P^{(j)})}^{2\mathfrak{d}(j)}\\ ={\displaystyle \sum _{2\le i<L}\left(1-\frac{1}{r_i}\right)}{\displaystyle \prod _{j=i}^k{r}_j}{\lambda }_2{(P^{(j)})}^{2\mathfrak{d}(j)}+{\displaystyle \sum _{L\le i\le k}\left(1-\frac{1}{r_i}\right)}{\displaystyle \prod _{j=i}^k{r}_j}{\lambda }_2{(P^{(j)})}^{2\mathfrak{d}(j)}.\end{array}$$

Let S₁ and S₂ be the former and latter summation, respectively.

From the condition on $\mathfrak{d}(i)$, we have

$$\begin{array}{l}{S}_1={\displaystyle \sum _{2\le i<L}\left(1-\frac{1}{r_i}\right)}{\displaystyle \prod _{j=i}^k{r}_j}{\lambda }_2{(P^{(j)})}^{2\mathfrak{d}(j)}\\ \le {\displaystyle \sum _{2\le i<L}\frac{C}{i+C}}{\displaystyle \prod _{j=i}^L{r}_j}{\displaystyle \prod _{j=L+1}^k\frac{j}{j+1}}\\ \le {\displaystyle \sum _{2\le i<L}\frac{C}{i+C}}{\displaystyle \prod _{j=i}^L\left(1+\frac{C}{j}\right)}\frac{L+1}{k+1}\\ \le \frac{C(L+1)}{k+1}{\displaystyle \sum _{2\le i<L}\frac{1}{i+C}}\exp \left(C{\displaystyle \sum _{j=i}^L\frac{1}{j}}\right)\\ \le \frac{C(L+1)}{k+1}{\displaystyle \sum _{2\le i<L}\frac{1}{i+C}}\frac{L^C}{{(i-1)}^C}\\ \le \frac{{\pi }^2}{6}\frac{C{L}^C(L+1)}{k+1}.\end{array}$$

We used ${\sum }_{i=a}^b\frac{1}{i}\le \ln (b)-\ln (a-1)$ and the condition that $C\ge 1$. From the proof of Lemma 3, we have $S_2<{\max }_{i<i\le n}i(r_i-1)\le C$. □

Lemma 12.

Let $(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be an RWoGG, where $P^{(i)}$ is reversible and lazy. Let N be an arbitrary positive number. If $\mathfrak{d}(i)\ge \left(\frac{1}{N}+\frac{r_i-1}{2}\right)t_{\text{hit}}(i)$ for all $i\ge L$, then ${\sum }_{k=L}^n{\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}\le L+N,$ where r_i is defined in (10).

Proof.

We divide ${\sum }_{k=L}^n{\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}=T_1+T_2$, where

$$\begin{array}{l}{T}_1={\displaystyle \sum _{2\le k<L}}{\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}},\\ T_2={\displaystyle \sum _{L\le k\le n}}{\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}.\end{array}$$

Note that $T_1\le L$ because ${\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}^2={\sum }_{u\in V^{(k-1)}}{\pi }^{(k-1)}(u){\mu }_{v_k}^{(k-1)}{(u)}^2\le 1$. To bound T₂, we use Lemma 7 and (24), which implies

$$\begin{array}{l}{T}_2\le {\displaystyle \sum _{L\le k\le n}{\displaystyle \prod _{i=k}^n{\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\mathfrak{d}(i)-\frac{r_i-1}{2}{t}_{\text{hit}}(i)}}}\\ \le {\displaystyle \sum _{L\le k\le n}{\displaystyle \prod _{i=k}^n{\left(1-\frac{1}{t_{\text{hit}}(i)}\right)}^{\frac{t_{\text{hit}}(i)}{N}}}}\\ \le N.\end{array}$$

In the last equality, we used Lemma 6. □

Proof of Theorem 7.

Set $M=2CL{(L+1)}^C-1\ge L$ in (30) (note that $C\ge 1$ and $L\ge 1$). From Lemma 11, for each $k\ge M\ge L$, we have

$$\begin{array}{l}\sqrt{1+{\Vert \frac{{\nu }_{\mathfrak{d}(k-1)}^{(k-1)}}{{\pi }^{(k-1)}}-{\mathbf{1}}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}^2}\le \sqrt{\frac{2C{L}^C(L+1)}{k+1}+C+1}\\ \le \sqrt{\frac{2C{L}^C(L+1)}{M+1}+C+1}.\end{array}$$

Then

$$\begin{array}{l}\mathbf{E}[U(n)]\le M+\sqrt{\frac{2C{L}^C(L+1)}{M+1}+C+1}{\displaystyle \sum _{M\le k\le n}}{\Vert {\mu }_{v_k}^{(k-1)}\Vert }_{2,{\pi }^{(k-1)}}\\ \le M+(L+N)\sqrt{\frac{2C{L}^C(L+1)}{M+1}+C+1}\\ \le 2C{L}^C(L+1)+(L+N)\sqrt{C+2}-1.\hspace{1em}\square \end{array}$$

6. A Lower Bound for a Growing Path

In contrast to upper bounds, obtaining lower bounds seems to require more technically complicated arguments. We establish a lower bound of $\mathbf{E}[U(n)]$ for a random walk on a growing path graph, which implies that the upper bound by Corollary 2 is tight in the case. Let $R_{\text{p}}=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$ be a random walk on a growing path graph, where $G^{(i)}=(V^{(i)},E^{(i)})$ is given by $V^{(i)}=\{v_1,\dots ,v_i\}$, and $E^{(i)}=\{\{v_1,v_2\},\hspace{0.17em}\dots ,\hspace{0.17em}\{v_{i-1},v_i\}\}$, and $P^{(i)}$ is given by

for two parameters $p,q\in [0,1]$ satisfying $p\ge q$ and $q\le 1/2$ (see Figure 1). For example, if $(p,q)=(\frac{1}{2},\frac{1}{4})$, the corresponding walk is a lazy simple random walk. If $(p,q)=(\frac{3}{4},\frac{1}{4})$, the corresponding one is the lazy Metropolis random walk (see (25) for the definition of Metropolis random walk).

Theorem 8.

Let $R_{\text{p}}=(\mathfrak{d},{\{G^{(i)}\}}_{i=1,2,\dots },{\{P^{(i)}\}}_{n=1,2,\dots })$ be the RWoGG on a growing path, where $P^{(i)}$ is given in (31) such that $p\ge q$ and $q\le 1/2$. If $\mathfrak{d}(i)\le C{i}^{2-\gamma }$ in $R_{\text{p}}$ for some constants C > 0 and $\gamma \in [0,1]$, then $\mathbf{E}[U(n)]=\mathrm{\Omega }(n^{\gamma }/C)$.

Corollaries 1 and 2 and Theorem 8 imply the following tight bounds of $\mathbf{E}[U(n)]$.

Corollary 7.

For $R_{\text{p}}=(\mathfrak{d},{(G^{(i)})}_{i=1}^{\infty },{(P^{(i)})}_{i=1}^{\infty })$, where $P^{(i)}$ is the transition matrix of either the lazy simple random walk or the lazy Metropolis random walk. Then

• (i) If $\mathfrak{d}(i)\ge C{i}^{2-\gamma }$ for some constants C > 0 and $\gamma \in [0,1]$, then $\mathbf{E}[U(n)]=\text{O}(n^{\gamma }/C)$.

• (ii) If $\mathfrak{d}(i)\le C{i}^{2-\gamma }$ for some constants C > 0 and $\gamma \in [0,1]$, then $\mathbf{E}[U(n)]=\mathrm{\Omega }(n^{\gamma }/C)$.

We prove Theorem 8. Let $L,R\in [n]$ be parameters satisfying L < R. For a vertex $v\in V^{(n)}$, let $\mathcal{E}(v)$ be the event that $v\notin {\cup }_{i=1}^n{\cup }_{t=0}^{\mathfrak{d}(i)}\{X_t^{(i)}\}$. In other words, $\mathcal{E}(v)$ means that the walker does not visit the vertex v during the walk. For two vertices $v_i,v_j\in V^{(n)}$, we write $v_i⪯v_j$ if $i\le j$. Note that, for any two vertices $u⪯v$ and any round $k\in [n]$, it holds that $\mathbf{\text{Pr}}[\mathcal{E}(v)|X_0^{(k)}⪯u]\ge \mathbf{\text{Pr}}[\mathcal{E}(v)|X_0^{(k)}=u]$. Then, we have

We will determine the parameters R and L such that, for all $R\le k\le n$, $n-R=\mathrm{\Omega }(n^{\gamma })$, $\mathbf{\text{Pr}}[\mathcal{E}(v_R)|X_0^{(R)}=v_L]=\mathrm{\Omega }(1/C)$ and $\mathbf{\text{Pr}}[X_0^{(k)}\le L]=\mathrm{\Omega }(1)$. This yields the lower bound $\mathbf{E}[U(n)]=\mathrm{\Omega }(n^{\gamma }/C)$. For a fixed parameter R, let $T≔{\sum }_{i=R}^n\mathfrak{d}(i)$ denote the number of steps of the walk during the last $n-R+1$ rounds.

Lemma 13.

Let $L,R\in \mathbb{N}$ be parameters satisfying L < R and let $T≔{\sum }_{i=R}^n\mathfrak{d}(i)$. Then, the following holds.

• (i) $\mathbf{\text{Pr}}[\mathcal{E}(v_R)|X_0^{(R)}=v_L]\ge 1-\frac{T}{4{(R-L)}^2}$, and

• (ii) $\mathbf{\text{Pr}}[X_0^{(k)}⪯v_L]\ge \frac{L}{n}$ for all $k\in [n]$.

Proof of (i).

We recall the notion of stochastic dominance: For two random variables X and Y, we say X dominates Y if, for any $r\in \mathbb{R}$, we have $\mathbf{\text{Pr}}[X\ge r]\ge \mathbf{\text{Pr}}[Y\ge r]$. Let ${(Z_t)}_{t=1}^{\infty }$ be i.i.d. random variables sampled from the uniform distribution over $\{-1,+1\}$ and $S_c≔{\sum }_{j=0}^c{Z}_j$ denote the sum. For a vertex $v_i\in V^{(n)}$, let $\text{pos}(v_i)=i$ denote the position of v_i. Then the complementary event $\overline{\mathcal{E}(v_R)}$ conditioned on $X_0^{(R)}=v_L$ is identical to the event ${\max }_{R\le i\le n,0\le j\le \mathfrak{d}(i)}\{\text{pos}(X_j^{(i)})-\text{pos}(X_0^{(R)})\}\ge R-L$. Moreover, the random variable ${\max }_{R\le i\le n,0\le j\le \mathfrak{d}(i)}|\text{pos}(X_j^{(i)})-\text{pos}(X_0^{(R)})|$ is dominated by ${\max }_{1\le c\le T}|S_c|$ (recall $T={\sum }_{i=R}^n\mathfrak{d}(i)$). This is because the distribution of $\text{pos}(X_j^{(i)})-\text{pos}(X_{j-1}^{(i)})$ conditioned on $\text{pos}(X_j^{(i)})-\text{pos}(X_{j-1}^{(i)})\ne 0$ is uniform on $\{-1,+1\}$. Thus, letting $Z≔{\max }_{R\le i\le n,0\le j\le \mathfrak{d}(i)}|\text{pos}(X_j^{(i)})-\text{pos}(X_0^{(R)})|$, we obtain

$$\begin{array}{l}\mathbf{P}\mathbf{r}\left[\overline{\mathcal{E}(v_R)}|X_0^{(R)}=v_L\right]\le \mathbf{\text{Pr}}\left[Z\ge R-L|X_0^{(R)}=L\right]\\ \le \mathbf{\text{Pr}}[\underset{1\le c\le T}{\max }|S_c|\ge R-L]\\ \le \frac{\mathbf{\text{Var}}[S_T]}{{(R-L)}^2}=\frac{T}{4{(R-L)}^2}.\end{array}$$

In the last inequality, we used the Kolmogorov inequality (Lemma A.1). □

Proof of (ii).

It suffices to show that

$$\mathbf{\text{Pr}}[X_0^{(k)}=v_i]\ge \mathbf{\text{Pr}}[X_0^{(k)}=v_{i+1}]$$(33)

holds for any $1\le i\le k-1$. To see this, assuming (33), we obtain

$$\frac{\mathbf{\text{Pr}}[X_0^{(k)}⪯v_L]}{L}\ge \mathbf{\text{Pr}}[X_0^{(k)}=v_L]\ge \frac{1-\mathbf{\text{Pr}}[X_0^{(k)}⪯v_L]}{n-L}.$$

By solving this inequality for $\mathbf{\text{Pr}}[X_0^{(k)}⪯v_L]$, we obtain Item (ii). Here, in the second inequality, note that $\mathbf{\text{Pr}}[X_0^{(k)}=v_L]\ge \mathbf{\text{Pr}}[X_0^{(k)}=v_j]$ for all j > L and, thus, the average $\frac{1}{n-L}{\sum }_{j>L}\mathbf{\text{Pr}}[X_0^{(k)}=v_j]=\frac{1-\mathbf{\text{Pr}}[X_0^{(k)}⪯v_L]}{n-L}$ is at most the maximum ${\max }_{j>L}\{\mathbf{\text{Pr}}[X_0^{(k)}=v_j]\}\le \mathbf{\text{Pr}}[X_0^{(k)}=v_L]$.

Now we prove the inequality (33). Let $x_j^{(i)}\in {[0,1]}^{V_i}$ denote the distribution of $X_j^{(i)}$. To simplify the notations, for a vector $y\in {[0,1]}^{V^{(i)}}$, we write $y[u]$ for the u-th element of y. We call the distribution $y\in {[0,1]}^{V^{(i)}}$ monotone if $y[v_k]\ge y[v_{k+1}]$ holds for any $1\le k\le i-1$. Our aim here is to prove that $x_0^{(k)}$ is monotone, which is equivalent to (33).

Indeed, we will prove a stronger statement: $x_j^{(i)}$ is monotone for any i and j. We prove this statement inductively. As the base case, observe that the vector $x_j^{(1)}=(1)$ is monotone. Suppose that $x_{\mathfrak{d}(i)}^{(i)}$ is monotone. We claim $x_0^{(i+1)}$ is also monotone. To see this, note that $x_0^{(i+1)}$ is obtained by concatenating $x_{\mathfrak{d}(i)}^{(i)}$ with zero. More precisely, $x_0^{(i+1)}\in {[0,1]}^{i+1}$ satisfies

$$x_0^{(i+1)}[j]=\{\begin{array}{ll}{x}_{\mathfrak{d}(i)}^{(i)}[j]\hfill & \text{if} 1\le j\le i,\hfill \\ 0\hfill & \text{if} j=i+1.\hfill \end{array}$$

Finally, we check that $x_{j+1}^{(i)}$ is monotone if $x_j^{(i)}$ is monotone. Let $S_1=p{x}_j^{(i)}[v_1]+(1-p)x_j^{(i)}[v_2]$, $S_2=q{x}_j^{(i)}[v_{k-1}]+(1-2q)x_j^{(i)}[v_k]+q{x}_j^{(i)}[v_{k+1}]$ (for $1<k<i$), and $S_3=(1-p)x_j^{(i)}[v_{i-1}]+p{x}_j^{(i)}[v_i]$. From (31), we have

$$x_{j+1}^{(i)}[v_k]=\{\begin{array}{ll}{S}_1\hfill & \text{if} k=1,\hfill \\ S_2\hfill & \text{if} 1<k<i,\hfill \\ S_3\hfill & \text{if} k=i.\hfill \end{array}$$

By the induction assumption, $x_j^{(i)}$ is monotone. Now we check that $x_j^{(i)}$ is monotone. For k = 1, because $p\ge q$, we have

$$x_{j+1}^{(i)}[v_1]-x_{j+1}^{(i)}[v_2]=(p-q)(x_j^{(i)}[v_1]-x_j^{(i)}[v_2])+q(x_j^{(i)}[v_2]-x_j^{(i)}[v_3])\ge 0.$$

For $1<k<i-1$, because $q\le \frac{1}{2}$, we have

$$\begin{array}{l}{x}_{j+1}^{(i)}[v_i]-x_{j+1}^{(i)}[v_{i+1}]=q{x}_j^{(i)}[v_{k-1}]+(1-3q)x_j^{(i)}[v_k]-(1-3q)x_j^{(i)}[v_{k+1}]-q{x}_j^{(i)}[v_{k+2}]\\ \ge (1-2q)(x_j^{(i)}[v_k]-x_j^{(i)}[v_{k+1}])\ge 0.\end{array}$$

Finally, for k = i, because $p\ge q$, we have

$$x_{j+1}^{(i)}[v_{i-1}]-x_{j+1}^{(i)}[v_i]=q(x_j^{(i)}[v_{i-2}]-x_j^{(i)}[v_{i-1}])+(p-q)(x_j^{(i)}[v_{i-1}]-x_j^{(i)}[v_i])\ge 0.$$

Therefore $x_{j+1}^{(i)}$ is monotone. □

Now we are ready to prove Theorem 8. Recall $\mathfrak{d}(i)\le C{i}^{2-\gamma }$. Fix a small positive constant ϵ such that $ϵ<\min \{1/C,0.1\}$. Set $R≔n-ϵn^{\gamma }$ and $L≔R-0.6n\in [0.3n,0.4n]$. Then we have $T\le (n-R)\mathfrak{d}(n)\le Cϵn^2\le n^2$ and thus $1-\frac{T}{4{(R-L)}^2}\ge 1-\frac{1}{4\times 0.36}>0.3$ and $\frac{L}{n}\ge 0.3$. Then, from (32) and Lemma 13, we have

which completes the proof of Theorem 8 (here, we take $ϵ>0$ such that $ϵ=\mathrm{\Omega }(1/C)$).

7. Concluding Remarks

This paper has investigated the expected numbers of vertices remaining unvisited by random walks on growing graphs parametrized by $\mathfrak{d}$. We have presented some upper bounds of $\mathbf{E}[U(n)]$ with respect to $\mathfrak{d}$, where we revealed that $\mathbf{E}[U(n)]=\text{O}(1)$ if $\mathfrak{d}(i)\ge C{t}_{\text{hit}}(i)$ for C > 1 in general (Theorem 2), and that $\mathbf{E}[U(n)]=\text{O}(1)$ if $\mathfrak{d}(i)=\mathrm{\Omega }(t_{\text{hit}}(i))$ on some natural assumptions (Theorem 5 and Corollaries 1 and 2). We have also presented lower bounds of $\mathbf{E}[U(n)]$ for random walks on growing complete graphs and on growing path graphs, which imply the upper bounds by Theorem 5 and Corollaries 1 and 2 are tight in those cases. A general lower bound of $\mathbf{E}[U(n)]$ is a challenge: a natural question remains unsettled whether $\mathbf{E}[U(n)]=\text{O}(1)$ requires $\mathfrak{d}(i)=\mathrm{\Omega }(t_{\text{hit}}(i))$. A concentration result should be another future work (Cooper and Frieze [12]).

In this paper, we have been concerned with a simple model of graphs with the increasing number of vertices, to develop a new technique for analyses of random walks on dynamic graphs. Clearly, it is an interesting and important future work to analyze algorithms on dynamic graphs whose vertex set and edge set are both dynamic.