2. The model

In this section we provide the definitions, notation, and basic results regarding the general framework where our processes (random walks and graph sequences) will live. At this point, it seems fair to explain the motivations for some of our choices. First, in order to avoid trivialities due to lack of irreducibility of random walks in discrete time, we will assume that the steps of the walker are performed at the jump times of a homogeneous Poisson process. In the same vein, the evolution of the underlying graph will take place at the jump times of a pure birth Markov process (independent of the previous one). Since the main quantity we are interested in is a function of the number of vertices, and since the graph dynamics add vertices one by one, the height of the trajectories of this pure birth process is just the number of vertices modulo a constant. This continuous-time model has a second important advantage over the discrete-time version sketched in the introduction, in that it avoids the rather awkward detention of the walker while the world evolves.

2.1. The construction of the process

We start with some standard definitions and notation. A (simple, undirected) graph is a pair $G=(V,E)$, where V is a finite or countably-infinite set and E is a symmetric, antireflexive relation on $V\times V$ (and so E can be identified with a subset of the unordered pairs of elements of V). The elements of V are referred to as vertices, while those of E are called edges. Given a graph G, the notation V(G) (resp. E(G)) will denote the set of its vertices (resp. the set of its edges). More often than not, we will use uppercase italics, $F, G, H, \ldots$, to identify particular graphs. We say that two vertices $u, v \in V$ are neighbours in the graph $G=(V,E)$ if $\{u,v \} \in E$, and in this case we write $u\sim_{G} v$. Also, for a vertex v, we write $\mathcal{N}^{G}(v)$ to denote the set of neighbours of v in the graph G. We write $\mathcal{G}_{n}$, $\mathcal{G}_{fin}$, and $\mathcal{G}_{\mathbb{N}}$ to denote the families of graphs with n vertices, the finite graphs, and the countably infinite graphs, respectively. Since the nature of the elements used as labels is entirely immaterial, we will assume that the vertices of graphs in $\mathcal{G}_{n}$ are labelled by $[n]=\{1, 2, \ldots, n\}$. With this convention, for a graph $G \in \mathcal{G}_{n}$ and for $m \le n$, we define $G\vert_{[m]}$ to be the subgraph of $\mathcal{G}_{n}$ induced by the first m vertices.

Remark 1. We can get a more vivid image of a random walk in a growing graph sequence from the following alternative construction. Given a graph G and a vertex $v \in G$, write $\mathbb{P}^{G, v}$ to denote the law of the continuous-time simple random walk on the graph G started at v. Given an increasing sequence of graphs $G=\{G_{0}, G_{1}, \ldots\}$ and an increasing sequence of times $T=\{T_{0}=0, T_{1}, T_{2}, \ldots\}$, we build the transition probabilities of the random walk started at vertex x of the graph $G_{0}$ conditioned on (G, T) as follows: if $T_{n-1}\le s \le t < T_{n}$, then

\begin{align*}\mathbb{P}_{G_{0}, x}(X_{t}=v\vert X_{s}=u) = \mathbb{P}^{G_{n-1}, u}(X_{t-s}=v),\end{align*}

whereas if $T_{m-1}\le s \le T_{m} < T_{m+1} < \ldots < T_{n} \le t < T_{n+1}$, then

\begin{align*}\mathbb{P}_{G_{0}, x}(X_{t}=v\vert X_{s}=u) = \sum &\mathbb{P}^{G_{m-1}, u}(X_{T_{m}-s}=v_{m-1}) \mathbb{P}^{G_{m}, v_{m-1}}(X_{T_{m+1}-T_{m}}=v_{m}) \ldots\\&\ldots \mathbb{P}^{G_{n-1}, v_{n-2}}(X_{T_{n}-T_{n-1}}=v_{n-1}) \mathbb{P} ^{G_{n}, v_{n-1}}(X_{t-T_{n}}=v),\end{align*}

where the sum ranges over ${v_{m-1}\in G_{m-1}, \ldots, v_{n-1} \in G_{n-1} }$.

In order to get a Markov process on the pair $(G_{t}, X_{t})$, of course, we need the graph sequence to be a Markov process itself, and we need the inter-arrival times of both the jumps of the walker and the growth epochs of the graph to be exponentially distributed.

Remark 2. In order to keep the notation as simple as possible, in the remaining sections we will abuse it slightly. For example, we will write $K_{t}$ for both the set of vertices visited by time t and the cardinality of this set. The same notational convention will be used for the set of vertices $V_{t}$ and its cardinality. In context, no confusion will be possible.

2.2. An example: increasing finite path sequence

Let $P_{n}$ be the path on n vertices. We label its vertices as $0, 1, \ldots, n-1$. For the construction below, it is worth keeping in mind the usual image of a segment of $\mathbb{R}_{+}$ drawn from left to right. In order to illustrate the usage of the above construction, in this subsection we consider a graph process that starts at $P_{N}$ for some $N \ge 2$ and, at each of the random times $(T_{k})_{k \ge 1}$, gains one vertex at its rightmost end. Thus, $G_{t}=P_{N+k}$ for $t \in [T_{k}, T_{k+1})$. Let $X_{t}$ be a rate $\mu=1$ simple random walk on this increasing sequence of graphs started at vertex 0. With the notation of the previous subsection, the law of the random walk will be denoted by $\mathbb{P}_{P_{N}, 0}$.

Theorem 1.

\begin{align*}\dfrac{K_{t}}{V_{t}} \to 0 \qquad \mathbb{P}_{P_{N}, 0}\textit{- a.s.}\end{align*}

Intuitive as it is, the proof of the above result involves some technicalities. We will need to consider the times when the walker is constrained to perform a deterministic step to the left. Notice that this happens at time $t >0$ if and only if a transition from $V_{t}$ (to the left) is performed. Formally, define $l_{0}=0$, and for $n \ge 1$, let

\begin{align*}l_{n}= \inf \{t \ge l_{n-1}\,:\, X_{t^{-}}=V_{t}, X_{t}=V_{t}-1\}.\end{align*}

It may well be the case that $l_{n}= +\infty$ for some $n \ge 1$, but this is not an issue for the moment.

Now, let $Y_{t}$ be the simple random walk on the one-sided lattice $\mathbb{Z}_{+}$ with reflecting barrier at 0, defined on some arbitrary probability space. Denote by $R_{t}$ the range of $Y_{t}$, i.e.,

\begin{align*}R_{t}= \vert \{Y_{s}\,:\, 0 \le s \le t\} \vert .\end{align*}

In what follows, we will regard $P_{n}$ as an induced subgraph of $\mathbb{Z}_{+}$ (alternatively, $\mathbb{Z}_{+}$ can be seen as the projective limit of $P_{n}$ as $n \to \infty$).

Proof. The demonstration relies on a coupling argument and well-known facts regarding the range of recurrent random walks on the (unrestricted) line.

First, given a sample path $(X_{t}, V_{t})(\omega)$ we build a new walk $(X^{\prime}_{t})_{\{t \ge 0\}}$ on $\mathbb{Z}_{+}$ such that

1. 1. $X_{t}(\omega) \le X^{\prime}_{t}(\omega )$ for all $t \ge 0$;

2. 2. $X^{\prime}_{t} \sim Y_{t}$ for all $t \ge 0$.

To this end, let $(\xi_{n})_{n \ge 1}$ be a sequence of $\{-1, 1\}$-valued independent and identically distributed (i.i.d.) random variables, independent of the process $(X_{t}, V_{t})$ as well, such that for every $n \ge 1$, $(\xi_{n}+1)/2\sim \text{Bernoulli(1/2)}$. Let $X^{\prime}_{0}=0$, and prescribe the following:

1. 1. The jump times of $X^{\prime}$ are exactly the jump times of $X$.

2. 2. If, for some $s \ge 0$, $X^{\prime}_{s}=X_{s}$ holds, then we fix $X^{\prime}_{t}=X_{t}$ for $s \le t < t_{s}\coloneqq \min \{l_{n}\,:\, l_{n} \ge s\}$. If $t_{s}=l_{m}$, fix $X^{\prime}_{l_{m}}=X_{l_{m}^{-}}+\xi_{m}$.

3. 3. If, on the contrary, for some $s \ge 0$, $X^{\prime}_{s} \neq X_{s}$, let $X^{\prime}$ evolve as a simple random walk on the unrestricted line up to the first time after s when both processes meet.

It is easily checked that the construction above works as required. Now, since $X_{t} \le X^{\prime}_{t}$, we have that

\begin{align*}K_{t}= \vert \{X_{s} \,:\, s \le t\} \vert \le R^{\prime}_{t}= \vert \{ X^{\prime}_{s}\,:\, s \le t\}\vert \sim R_{t}.\end{align*}

Since $\frac{V_{t}}{\gamma t} \to 1$$\mathbb{P}_{P_{N}, 0}$-a.s., we have

\begin{align*}\mathbb{P}_{P_{n}, 0} \left \{\limsup_{t} \dfrac{K_{t}} {V_{t}} >0 \right \} &=\mathbb{P}_{P_{n}, 0} \left \{\limsup_{t} \dfrac{K_{t}}{\gamma t} \dfrac{\gamma t} {V_{t}}>0 \right \}\\[3pt]& \le \mathbb{P}_{P_{n}, 0} \left \{ \limsup_{t}\dfrac{R^{\prime}_{t}}{\gamma t}\dfrac{\gamma t}{V_{t}} >0 \right \}=0,\end{align*}

because $R^{\prime} \sim R$ and $\frac{R_{t}}{t} \to 0$ a.s. (see, e.g., [Reference Spitzer16]) implies $\frac{R^{\prime}_{t}}{t} \to 0$ a.s. as well.

2.3. Specialising the model: the sequence of complete graphs

Henceforth we concentrate our efforts on the simple model we will deal with, namely the sequence of growing complete graphs.

For $n \ge 2$, let $C_{n}$ be the complete graph on n vertices. Assume that $G_{0}= C_{N}$ for some natural number $N \ge 2$ and that $P^{\mathcal{G}}(G,\cdot)=\delta_{C_{\vert G\vert +1}}$ is the (trivial) transition kernel of the graph-valued process. By symmetry, it is easily seen that in this case the pair $(\vert G_{t}\vert, \vert K_{t}\vert)$ is a Markov process. Let $b\Delta$ be the space of bounded Borel functions on $\Delta$, and $b\Delta_{0}$ the linear subspace of $b\Delta$ of functions of the form

\begin{align*}h(g,x,k)=h(\vert g \vert, \vert k \vert ).\end{align*}

Introduce the difference operators

\begin{align*}\Delta_{1}f(\vert g \vert ,\vert k \vert )&=f(\vert g \vert +1, \vert k \vert )-f(\vert g \vert, \vert k \vert ),\\[3pt] \Delta_{2} f(\vert g \vert,\vert k\vert )&=f(\vert g \vert,\vert k\vert +1)-f(\vert g \vert ,\vert k\vert ) .\end{align*}

Theorem 2. Assume that $G_{0}= C_{N}$ for some natural number $N \ge 2$ and that $P^{\mathcal{G}}(G,\cdot)=\delta_{C_{\vert G\vert +1}}$. Then, for $h \in b\Delta_{0}$, the prescription

(2)\begin{align}\mathcal{L}h(\vert g \vert, \vert k \vert )= \gamma \Delta_{1}h(\vert g\vert, \vert k \vert ) + \mu \left( 1-\dfrac{\vert k\vert - 1}{\vert g\vert -1 }\right) \Delta_{2} h (\vert g \vert, \vert k \vert)\end{align}

corresponds to the action of the infinitesimal generator of the process $(\vert G_{t}\vert, \vert K_{t}\vert )$.

Proof. The reader is referred to Theorem 6 in the Appendix. Just observe that, in this case, for any $x \le \vert g \vert $, the second term in (20) equals

\begin{align*}\mu \dfrac{1}{\vert g \vert -1} \left ( \vert \mathcal{N}^{g}(x) \vert - \vert \mathcal{N}^{g}(x) \cap k \vert \right) \Delta_{2}h(\vert g \vert, \vert k \vert )&= \mu \dfrac{(\vert g\vert - 1)- (\vert k \vert -1)}{\vert g \vert -1} \Delta_{2}h(\vert g \vert, \vert k \vert ) \\[2pt]&= \mu \dfrac{\vert g\vert - \vert k \vert }{\vert g \vert -1} \Delta_{2} h(\vert g \vert, \vert k\vert ).\end{align*}

In accordance with Remark 2, in order to simplify the notation, from now on we write v for the size of a graph g, and we put k instead of $\vert k \vert$. With this, the above expression can be written as

\begin{align*}\mathcal{L}h(v,k)= \gamma \Delta_{1}h(v,k ) + \mu \left( 1-\dfrac{k - 1}{v-1 }\right) \Delta_{2} h (v,k).\end{align*}

Remark 3. We turn back for a while to the discrete parameter model informally sketched in the introduction. What does $K_{n}$ look like as the walker wanders in a fixed structure, say the complete N-graph? Since at time 0 the walker has already visited one vertex, and since our walker is not lazy, $K_{0}=1$ and $K_{1}=2$. For $n \ge 0$, let $\mathcal{F}_{n}$ be the $\sigma$-field generated by the random variables $X_{0}, X_{1}, \ldots, X_{n}$. We observe that, for $n \ge 2$, given the past $\mathcal{F}_{n}$, we have $K_{n+1}=K_{n}$ if the $(n+1)$th step takes the walker to an already visited vertex, and this happens with probability

\begin{equation*}\dfrac{K_{n}-1}{N-1}\end{equation*}

(the $-1$ in the numerator takes care of the fact that the random walk is a simple random walk, so that the walker never stays at a given vertex). The complementary event is, of course, $K_{n+1}=K_{n}+1$, and this happens with probability

\begin{equation*}\dfrac{N-K_{n}}{N-1}.\end{equation*}

Rearranging terms, we get

(3)\begin{align}\mathbb{E}(K_{n+1}\vert \mathcal{F}_{n})=K_{n}\bigg( \dfrac{N-2}{N-1} \bigg) + \dfrac{N}{N-1}.\end{align}

Iteration yields

(4)\begin{align}\mathbb{E}(K_{n+1})=N-(N-1)\bigg( 1-\dfrac{1}{N-1}\bigg)^{n+1}.\end{align}

Now, from (3), we see that $(K_{n}\,:\, n \ge 0)$ is a bounded $\mathcal{F}_{n}$-submartingale, and hence has an a.s. limit that is, of course, $\lim_{n\to \infty}\mathbb{E}(K_{n})=N$.

Trivial as it is, the point of this observation is that, to some extent, we can rely on analogous reasoning to understand the knowledge process as the complete graph grows. To grasp this connection, let $[N]=\{1,2, \ldots, N\}$, and consider an [N]-valued pure birth process, say ${(Z_{s}\,:\, s \ge 0)}$, started at $Z_{0}=1$, with absorbing barrier at N, and with transition rates given by

(5)\begin{align}\nu_{i,i+1}=\mu \dfrac{N-i}{N-1}, \qquad 1 \le i < N.\end{align}

We see that in this case, $Z_{s}$ and (the continuous counterpart of) the walker of the first paragraph have the same law. In other words, in the complete graph, the knowledge process is a pure birth Markov process with rates of the type given in (5). Now, by looking at (2), we see clearly what we mentioned before. By identifying a pair $(\vert g\vert ,\vert k \vert )$ with the corresponding point of the lattice $\mathbb{N}^{2}$, we can consider a derived random walk on $\Delta$ that starts at (N, 1) and whose transitions are as follows. At the jump times of a Poisson process of intensity $\gamma$, the derived walker performs a unit step from $(\vert g \vert ,\vert k \vert )$ to $(\vert g \vert +1, \vert k \vert)$. This is a process of constant drift towards the east. Independently of the above drift, when the walker is at $(\vert g \vert ,\cdot)$, a pure birth process of rate

\begin{equation*}\mu \dfrac{\vert g\vert -\vert k\vert }{\vert g\vert -1}\end{equation*}

controls the transition from $(\vert g\vert ,\vert k\vert )$ to $(\vert g\vert, \vert k \vert +1)$. This is a process of decreasing drift towards the north. The overall behaviour is that of a walker travelling northeast. In this setting, if there exists a random variable

\begin{equation*}\lim_{s \to \infty}\dfrac{\vert K_{s}\vert }{\vert G_{s} \vert },\end{equation*}

this corresponds to the asymptotic slope of the walker in the wedge. This is the topic of the next section.

Later, we will use the expression at (2) to derive limit theorems. Meanwhile, as a direct consequence of the above theorem, we provide a semimartingale representation of the knowledge process.

Corollary 1. Let $f \in b\Delta$ be defined by

\begin{align*}f_{0}(v,k)= \dfrac{k-1}{v-1}.\end{align*}

Then

\begin{align*}M_{t}\coloneqq f_{0}(V_{t}, K_{t})+ \gamma \int_{0}^{t} \dfrac{f_{0}(V_{s}, K_{s})}{V_{s}}ds-\mu \int_{0}^{t} \dfrac{1-f_{0}(V_{s}, K_{s})}{V_{s}-1}ds\end{align*}

is an $L^{2}$-bounded $\mathcal{F}_{t}$-martingale.

Proof. A straightforward application of (2) shows that $M_{t}$ is a centred local martingale. An easy computation shows that the carré du champ associated to $f \in b\Delta$ is given by

\begin{align*}\Gamma(\,f,f)&\coloneqq \mathcal{L}(\,f^{2})-2f \mathcal{L}(\,f)\\&=\gamma (\Delta_{1}f)^{2} + \mu(1-f_{0}) (\Delta_{2}f)^{2}.\end{align*}

Hence, the unique predictable process $( \langle M, M\rangle_{t}\,:\, t \ge 0)$ such that $(M_{t}^{2}- \langle M, M\rangle_{t}\,:\, t \ge 0)$ is a centred local martingale is given by

\begin{align*}\langle M,M\rangle _{t}&= \int_{0}^{t} \Gamma(\,f_{0}, f_{0}) (V_{s}, K_{s}) ds\\[2pt] &=\int_{0}^{t} \gamma f_{0}(V_{s}, K_{s})^{2} \left ( \dfrac{1}{V_{s}} \right)^{2}+ \mu (1-f_{0}(V_{s}, K_{s})) \left (\dfrac{1}{V_{s}-1} \right)^{2}ds.\end{align*}

For a fixed time $t \ge 0$, let $T_{t}$ be the first jump time of V after t, and let $N_{t}$ be the number of jumps up to and including time $T_{t}$. Since $f_{0} \in [0,1]$ a.s., for some constant C independent of t, we have the estimate

(6)\begin{align}\langle M,M\rangle_{t} &\le C \int_{0}^{t} \dfrac{1}{(V_{s}-1)^{2}}ds \nonumber\\[2pt] &= C\sum_{k=0}^{N_{t}} \dfrac{1}{(N+k)^{2}} (T_{k+1}-T_{k}) \nonumber \\[2pt] &\le C \sum_{k \ge 0} \dfrac{1}{(N+k)^{2}} (T_{k+1}-T_{k}). \end{align}

Since $(T_{k}-T_{k-1}\,:\, k \ge 1)$ is an i.i.d. sequence of random variables with distribution $\text{Exp}(\gamma)$, we have

\begin{align*}\mathbb{E}(\langle M,M\rangle_{t})\le C \sum_{k \ge 0} \dfrac{1}{\gamma}\dfrac{1}{(N+k)^{2}} \le \tilde{C},\end{align*}

where $\tilde{C}$ is some constant independent of t. Now, let $(U_{n}\,:\, n \ge 0)$ be a localising sequence for the local martingale M, i.e., an increasing sequence of stopping times satisfying $U_{n}\to \infty$ a.s. and such that $(M^{U_{n}}_{t}\coloneqq M_{t\wedge U_{n}}\,:\, t \ge 0)$ is a martingale for each n. We have

\begin{align*}\mathbb{E}\big(\big(M^{U_{n}}_{t}\big)^{2}\big)= \mathbb{E}\big(\langle M^{U_{n}}, M^{U_{n}}\rangle_{t}\big) = \mathbb{E}(\langle M,M\rangle_{t \wedge U_{n}}) \le \tilde{C},\end{align*}

and taking the limit as $n \to \infty$, we obtain

\begin{align*}\mathbb{E}(M^{2}_{t}) \le \tilde{C}.\end{align*}

3. Covering properties on the complete graph sequence

In this section we apply the previous Markov model to the problem of finding asymptotics of $\vert K_{t} \vert $ when the underlying graph sequence is simple enough to yield analytically solvable expressions. As at the end of the previous section, we set $V_{s}= \vert G_{s} \vert $, and we drop the bars in expressions such as $\vert K_{s} \vert $ and simply put $K_{s}$. Recall the notation: $\mathbb{P}^{G, v}$ is the probability measure induced by the continuous-time simple random walk on the fixed graph G started from v, and for a given graph G and vertex $v \in G$, we write $\mathbb{P}_{G_{0}, v}$ for the law of the Markov process $(G_{t}, X_{t})$ started at the vertex v of the graph G. Let $T_0 = 0 < T_1 < \ldots$ be the jump times of the structure, and let $S_0 = 0 < S_1 < \ldots$ be the jump times of the walker.

3.1. Hitting times on the complete graph sequence

We first study the behaviour of the hitting times on the sequence of growing complete graphs. Just for this subsection, we set $\mu=1$, and $G_{N}$ refers to the complete graph on $N> 2$ vertices. Fix arbitrarily a vertex of $G_{N}$, say v, and let $\tau$ be the hitting time of v, i.e.,

\begin{align*}\tau=\min\{t \ge 0\,:\, X_{t}=v\}.\end{align*}

For fixed $u \in G_{N}$ different from v, we are interested in the mean hitting time

\begin{align*}\mathbb{E}_{G_{N}, u}(\tau).\end{align*}

It is elementary that, in the case of a fixed graph, $\mathbb{E}_{G_{N}, u}(\tau)=N-1$. In the case of a growing sequence, the situation is much more interesting.

We need the following simple result, whose proof is omitted.

Lemma 1. Let $X\sim \text{ Exp }(\mu_{1}), Y \sim \text{Exp}(\mu_{2})$ be two independent random variables defined on the same probability space $(\Omega, \mathbb{P})$. Then

\begin{align*}\mathbb{E}(X \vert X < Y)= \mathbb{E}(Y \vert Y < X).\end{align*}

We now observe that for $u \neq v$ under $\mathbb{P}^{G_{N+k}, u}$ the random variable $\tau$ is exponentially distributed with rate $\frac{1}{N+k-1}$. Thus, by the previous result,

\begin{align*}\mathbb{E}^{G_{N+k}, u}(\tau \vert \tau < (T_{k+1}-T_{k}))= \mathbb{E}^{G_{N+k}, u}(T_{k+1}-T_{k} \vert \tau > (T_{k+1}-T_{k}))=\dfrac{N+k-1}{(N+k-1)\gamma +1}.\end{align*}

Lemma 2. For $u \neq v$,

\begin{align*}\mathbb{P}^{G_{N+k}, u}(\tau<T_{k+1}-T_{k})=\dfrac{1}{1+\gamma (N+k-1)}.\end{align*}

Proof. Put $n =N+k$, $T=T_{k+1}-T_{k}$, and let $\tilde{S}_{0}, \tilde{S}_{1}, \ldots$ be the jump times of the walker on $G_{n}$. Under $\mathbb{P}^{G_{n}, u}$, $u \neq v$, we have $\tilde{S}_{m} \sim \Gamma(m, 1)$. Plainly,

\begin{align*}\mathbb{P}^{G_{n}, u}(\tau< T)&= \sum_{m \ge 1}\mathbb{P}^{G_{n}, u}(\tau < T \vert v \text{ is reached for the first time in exactly } m \text{ steps}) \\[2pt]& \quad \times\left ( \dfrac{n-2}{n-1} \right) ^{m-1}\dfrac{1}{n-1}\\[2pt]&= \dfrac{1}{n-1}\sum_{m \ge 1} \mathbb{P}^{G_{n}}_{u} (\tilde {S}_{m} < T) \left ( \dfrac{n-2}{n-1} \right) ^{m-1}\displaybreak\\[2pt] &= \dfrac{1}{n-1} \sum_{m \ge 1} \int_{0}^{\infty}\gamma e^{-\gamma t} \int_{0}^{t}\dfrac{s^{m-1}e^{-s}}{(m-1)!} \left ( \dfrac{n-2}{n-1} \right) ^{m-1}ds dt \\[2pt] &= \dfrac{1}{n-1} \int_{0}^{\infty} \gamma e^{-\gamma t} \int_{0}^{t} \sum_{m \ge 1}\dfrac{s^{m-1}e^{-s}}{(m-1)!} \left ( \dfrac{n-2}{n-1} \right) ^{m-1}ds dt \\[2pt] &= \dfrac{1}{n-1}\int_{0}^{\infty} \gamma e^{-\gamma t} \int_{0}^{t} e^{-\frac{s}{n-1}}ds dt \\[2pt] &= \int_{0}^{\infty} \gamma e^{-\gamma t} (1-e^{-\frac{t}{n-1}} )dt\\[2pt] &= \dfrac{1}{1+\gamma (n-1)}.\end{align*}

Lemma 3. For $k \ge 0$,

(7)\begin{align}\mathbb{P}_{G_{N}, u} (\tau \in [ T_{k}, T_{k+1}) )=\dfrac{1}{\gamma } \dfrac{ \Gamma (N+k-1)}{\Gamma (N-1) } \dfrac{\Gamma (N+\gamma^{-1}-1) }{\Gamma (N+\gamma^{-1}+k) }.\end{align}

Proof. Clearly, on the set $\{\tau > T_{j}\}$, we have $X_{T_{j}} \neq v$, and by symmetry,

\begin{align*}\mathbb{P}^{G_{j}, X_{T_{j}}} (\tau > (T_{j+1}-T_{j}))=\mathbb{P}^{G_{j}, u} (\tau > (T_{j+1}-T_{j}))\end{align*}

whenever $u \neq v$. Thus,

(8)\begin{align}\mathbb{P}_{G_{N}, u} &(\tau \in [T_{k}, T_{k+1}))= \mathbb{P}_{G_{N}, u} (\tau < T_{k+1}, \tau > T_{k}, \tau > T_{k-1} \ldots, \tau > T_{1}) \nonumber \\[2pt]&= \mathbb{P}_{G_{N}, u} (\tau < T_{k+1}\vert \tau > T_{k}) \mathbb{P}_{G_{N}, u} (\tau > T_{k} \vert \tau > T_{k-1}) \ldots \nonumber\\[2pt]& \quad \ldots \mathbb{P}_{G_{N}, u} (\tau > T_{2} \vert \tau > T_{1}) \mathbb{P}_{G_{N}, u} ( \tau > T_{1}) \nonumber \\[2pt]&=\mathbb{P}^{G_{N+k},u}(\tau < T_{k+1}-T_{k})\mathbb{P}^{G_{N+k-1},u}(\tau > T_{k}-T_{k-1}) \ldots \nonumber \\[2pt]& \quad \ldots \mathbb{P}^{G_{N+1}, u}(\tau > T_{2}-T_{1}) \mathbb{P}^{G_{N}, u}(\tau > T_{1}) \nonumber \\[2pt]&=\dfrac{1}{1+\gamma (N+k-1)} \prod_{j=0}^{k-1} \dfrac{N-1+j}{N-1+\gamma^{-1}+j},\end{align}

where in the last line we have used the previous lemma. The result follows after rearranging.

Theorem 3. For every $u \neq v$,

(9)\begin{align} \mathbb{E}_{G_{N}, u} (\tau )= \dfrac{1}{\gamma} \sum_{k \ge 0} \left (\sum _{j=0}^{k}\dfrac{N+j-1}{\gamma (N+j-1)+1} \right) \left ( \dfrac{ \Gamma (N+k-1)}{\Gamma (N-1) } \dfrac{\Gamma (N+\gamma^{-1}-1) }{\Gamma (N+\gamma^{-1}+k) } \right).\end{align}

In particular,

\begin{align*}\mathbb{E}_{G_{n}, u} (\tau) < + \infty \textit{ if and only if } \gamma < 1.\end{align*}

Proof. Let $p_{N, k}$ be the expression in the right-hand side of (7). We have

\begin{align*}\mathbb{E}_{G_{n}, u} (\tau) &= \sum_{k \ge 0} \mathbb{E}_{G_{N}, u}(\tau \textbf{1}_{\{\tau \in [T_{k}, T_{k+1})\}})\\[2pt] &= \sum_{k \ge 0} \mathbb{E}_{G_{N}, u}(\tau \vert \tau \in [T_{k}, T_{k+1}) ) p_{k} \\[2pt] &= \sum_{k \ge 0} \mathbb{E}_{G_{N}, u}((\tau-T_{k})+(T_{k}-T_{k-1}+ \ldots (T_{1}-T_{0})) \vert \tau \in [T_{k}, T_{k+1}) ) p_{k}\\[2pt] &= \sum_{k\ge 0} \left ( \sum_ {j=1}^{k} \mathbb{E}_{G_{N}, u} (T_{j}-T_{j-1} \vert \tau \in [T_{k}, T_{k+1})) + \mathbb{E}_{G_{N}, u} (\tau-T_{k} \vert \tau \in [T_{k}, T_{k+1})) \right ) p_{k}.\end{align*}

But for $1 \le j \le k$,

\begin{align*}\mathbb{E}_{G_{N}, u} (T_{j}- T_{j-1} \vert \tau \in [T_{k}, T_{k+1})) &= \mathbb{E}^{G_{N+j-1}, u} (T_{j}- T_{j-1} \vert \tau > (T_{j}-T_{j-1})) \\[2pt] &= \dfrac{N+j-2}{\gamma(N+j-2)+1},\end{align*}

and analogously, using the result in Lemma 2,

\begin{align*}\mathbb{E}_{G_{N}, u} (\tau - T_{k} \vert \tau \in [T_{k}, T_{k+1})) &= \mathbb{E}^{G_{N+k}, u}(\tau \vert \tau < (T_{k+1}-T_{k}))\\[2pt] &=\dfrac{N+k-1}{\gamma (N+k-1)+1}.\end{align*}

The explicit expression for the expectation in (9) follows at once.

Finally, observe that $p_{k} =O(k^{-1-1/\gamma})$, and that the inner sum in (9) is O(k). Thus, the general term of the outer sum is $O(k^{-1/\gamma})$. This proves the last claim of the theorem.

3.2. $L^{1}$ asymptotics for the knowledge process

In this subsection, we set ourselves in the special framework described by (2) and the remark after it, i.e., the random walk on an increasing sequence of complete graphs. Let $\rho=\mu/\gamma$. Figure 3.2 shows a simulation of three sample paths for $K_{t}/V_{t}$ up to horizon $T=50$, with parameters $\rho=1$ (left) and $\rho=0.5$ (right).

Figure 1:

Knowledge process on complete graphs: left, $\rho=1$; right, $\rho=0.5$.

Proposition 1.

\begin{align*}\lim_{k\to \infty} \mathbb{E} \bigg ( \dfrac{ K_{T_{k}} }{V_{T_{k}}} \bigg) =\dfrac{\mu}{\mu+\gamma}\,:\!= \nu.\end{align*}

Proof. We proceed as in the remark after Theorem 2, but now we compute conditional expectations with respect to the stopped filtration $(\mathcal{F}_{T_{k}} \,:\, k \ge 0)$. Let $M_k=\vert \{i\,:\,T_{k-1} < S_{i} < T_{k} \} \vert$ be the number of steps performed by the walker in the time interval $(T_{k-1}, T_{k})$, and let $R_{1}, R_{2}, \ldots, R_{M_{k}}$ be the times when those steps take place. Some observations are in order. First, with probability 1, no step of the walker coincides with a bump of the graph. Second, if there is no step of the walk between $T_{k-1}$ and $T_{k}$, we obviously have $K_{T_{k}}=K_{T_{k-1}}\!$. Otherwise, for $M_{k} \ge 1$, we have that $K_{T_{k}}$ is exactly $K_{R_{M_{k}}}\!$. Third, the random variable $z_{k}\coloneqq T_{k}-T_{k-1}$ is independent of $\mathcal{F}_{T_{k-1}}$ and has an $\text{Exp}(\gamma)$ distribution. Putting together these observations, we get

\begin{align*}&\mathbb{E}(K_{T_{k}}\vert \mathcal{F}_{T_{k-1}})\\ &\quad =\sum_{n \ge 0} \mathbb{E}(K_{T_{k}} \textbf{1}_{\{M_{k}=n\}}\vert \mathcal{F}_{T_{k-1}})\\ &\quad =K_{T_{k-1}}\mathbb{E}(e^{-\mu (T_{k}-T_{k-1})} \vert \mathcal{F}_{T_{k-1}})+ \sum_{n \ge 1}\mathbb{E}( K_{R_{M_{k}}} \textbf{1}_{\{M_{k}=n\}} \vert \mathcal{F}_{T_{k-1}} )\\ &\quad =K_{T_{k-1}}\mathbb{E}(e^{-\mu z_{k}}) + \sum_{n \ge 1}\mathbb{E}\bigg \{ \left [ K_{R_{M_{k}}-1} \left ( \dfrac{N+k-3}{N+k-2} \right) +\dfrac{N+k-1}{N+k-2} \right ]\textbf{1}_{\{M_{k}=n\}} \vert \mathcal{F}_{T_{k-1}} \bigg\}\\ &\quad =K_{T_{k-1}}\mathbb{E}(e^{-\mu z_{k}}) + \\ &\quad \quad \sum_{n \ge 1}\mathbb{E}\!\left \{ \left [ K_{T_{k-1}} \left ( \dfrac{N+k-3}{N+k-2} \right)^{n} +\dfrac{N+k-1}{N+k-2} \sum_{j=0}^{n-1}\left (\dfrac{N+k-3}{N+k-2} \right )^{j} \right ]\textbf{1}_{\{M_{k}=n\}} \vert \mathcal{F}_{T_{k-1}} \right \}\\ &\quad =K_{T_{k-1}} \mathbb{E}(e^{-\mu z_{k}}) +\\ & \qquad \sum_{n \ge 1} \left [ K_{T_{k-1}} \left ( \dfrac{N+k-3}{N+k-2} \right)^{n} +\dfrac{N+k-1}{N+k-2} \sum_{j=0}^{n-1}\left (\dfrac{N+k-3}{N+k-2} \right )^{j} \right ] \mathbb{E}\Bigg ( e^{-\mu z_{k}} \dfrac{(\mu z_{k})^{n}}{n!} \Bigg),\end{align*}

where in the last line we have used the independence of $z_{k}$ and $\mathcal{F}_{T_{k-1}}$ and the fact that $M_{k}$ has law $\text{Poisson} (\mu z_{k})$. Now, for $n \ge 0$,

\begin{align*}\mathbb{E}(e^{-\mu z_{k}}z_{k}^{n})=({-}1)^{n}\dfrac{d^{n}}{d\mu^{n}}\mathbb{E}(e^{-\mu z_{k}}) = n! \dfrac{\gamma}{(\mu+\gamma)^{n+1}},\end{align*}

but then we can write

\begin{align*}\mathbb{E}(K_{T_{k}}\vert \mathcal{F}_{T_{k-1}})&=K_{T_{k-1}}\dfrac{\gamma}{\mu+\gamma} \sum_{n\ge 0} \left (\dfrac{\mu (N+k-3)}{(\mu+\gamma)(N+k-2)} \right) ^{n} + \\[2pt] & \quad (N+k-1)\dfrac{\gamma}{\mu+\gamma} \sum_{n\ge 1} \left [ \left ( \dfrac{\mu}{\mu+\gamma} \right)^{n} - \left ( \dfrac{\mu (N+k-3)}{(\mu+\gamma)(N+k-2)} \right)^{n}\right].\end{align*}

After some algebra we get

(10)\begin{align} \mathbb{E}(K_{T_{k}}\vert \mathcal{F}_{T_{k-1}})&=K_{T_{k-1}} \dfrac{\gamma(N+k-2)}{\mu+ \gamma(N+k-2)} + \dfrac{\mu (N+k-1)}{\mu+\gamma (N+k.-2)}\nonumber \nonumber \\[3pt]&=K_{T_{k-1}} \dfrac{N+k-2}{N+k-2+\rho}+ \rho \dfrac{N+k-1}{N+k-2+\rho},\end{align}

and hence

(11)\begin{align}M_{k}\coloneqq K_{T_{k}} \dfrac{\Gamma(N+k-1+\rho)}{\Gamma(N+k-1)} - \rho \sum_{j=N}^{N+K-1} j \dfrac{\Gamma(\,j-1+\rho)}{\Gamma(\,j)}\end{align}

is an $\mathcal{F}_{T_{k}}$-martingale. So

(12)\begin{align}\mathbb{E}(K_{T_{k}})=\dfrac{\Gamma(N+k-1)}{\Gamma(N+k-1+\rho)} \bigg( \dfrac{\Gamma(N-1+\rho)}{\Gamma(N-1)} +\rho \sum_{j=N}^{N+K-1} j \dfrac{\Gamma(\,j-1+\rho)}{\Gamma(\,j)} \bigg).\end{align}

Now, the usual approximation procedures (application of Stirling’s formula and comparison of the sum with the corresponding integral) allow us to obtain the asymptotic ratio

\begin{align*}\lim_{k \to \infty} \dfrac{\mathbb{E}(K_{T_{k}})}{N+k}= \dfrac{\rho}{1+\rho}= \dfrac{\mu}{\mu+\gamma}.\end{align*}

3.3. $\textbf{\textit{L}}^{\textbf{1}}$ asymptotics on the complete graph sequence: variable rate of growth

With minor modifications, the growth rate of the underlying world can be made size-dependent. Of course, the important case is when the vertex-addition rate decreases. In this case, the fundamental recurrence equation becomes

\begin{align*}\mathbb{E}(K_{T_{k}})= \mathbb{E}(K_{T_{k-1}}) \dfrac{N+k-2}{N+k-2+\rho_{k}}+ \rho_{k} \dfrac{N+k-1}{N+k-2+\rho_{k}}.\end{align*}

Proposition 2. With the above notation, if $\alpha \in (0,1 )$ and $\rho_{k}= \rho k^{\alpha}$, then

\begin{align*}\mathbb{E}\left ( \dfrac{K_{T_{k}}}{V_{T_{k}}} \right) & \sim \dfrac{e^{-\frac{\rho}{\alpha}k^{\alpha}}}{k}\int_{1}^{k}\rho x^{\alpha} e^{\frac{\rho}{\alpha}x^{\alpha}}dx \\[2pt]& \sim 1- \dfrac{1}{\rho k^{\alpha}} \left [ 1+\dfrac{\alpha-1}{ \rho k^{\alpha}} + \dfrac{(\alpha-1)(2\alpha-1)}{\rho^{2}k^{2\alpha}} + \dfrac{(\alpha-1)(2\alpha-1)(3\alpha-1)}{\rho^{3}k^{3\alpha}}+ \ldots \right],\end{align*}

whereas if $\rho_{k}=\rho \ln(k)$, then

\begin{align*}\mathbb{E}\left ( \dfrac{K_{T_{k}}}{V_{T_{k}}} \right) &\sim \dfrac{e^{-\frac{\rho}{2} \ln^{2}(k)}}{k} \int_{1}^{k} \rho \ln(x) e^{\frac{\rho}{2}\ln^{2}(x)}dx \\[2pt] & \sim 1- \dfrac{1}{(1+\rho \ln(k))} \left [ 1+ \dfrac{1 \cdot \rho}{(1+\rho \ln(k))^{2}} + \dfrac{3\cdot 1 \cdot \rho^{2}}{(1+\rho \ln(k))^{4}}+ \dfrac{5 \cdot 3 \cdot 1 \cdot \rho^3} {(1+\rho \ln(k))^6} + \ldots \right ],\end{align*}

where an expression of the form $a_{k} \sim b_{k}$ stands for $\lim_{k\to \infty } \dfrac{a_{k}}{b_{k}}=1$.

Proof. We prove the asymptotics for the power decay rate, since the logarithmic case is demonstrated along the same lines. Write $e_{k}=\mathbb{E}\left ( K_{T_{k}} \right) $. Observe that

(13)\begin{align}e_{k}=e_{k-1}(1-\rho k^{\alpha-1}) + \rho k^{\alpha} + \delta_{k},\end{align}

where $\delta_{k}=O(k^{3\alpha-2})$. Since $\alpha < 1$, we have $3\alpha-2 < \alpha$, and thus $\delta_{k}=o(k^{\alpha})$. Choose $k_{0} > 1$ such that $\rho k_{0}^{\alpha -1 } < 1$, and for $k \ge k_{0}$ define

\begin{align*}\phi(k)\coloneqq (1-\rho k^{\alpha-1})(1-\rho (k-1)^{\alpha-1})\ldots (1-\rho k_{0}^{\alpha-1})= \prod_{j=k_{0}}^{k} (1-\rho j^{\alpha-1}).\end{align*}

Iterating the relation (13), we can write

(14)\begin{align}e_{k}=\dfrac{\phi(k)}{\phi(k_{0})} e_{k_{0}} + \sum_{j=k_{0}+1}^{k}\rho j^{\alpha} \dfrac{\phi(k)}{\phi(\,j)} + \sum_{j=k_{0}+1}^{k}\delta_{j}\dfrac{\phi(k)}{\phi(\,j)}.\end{align}

On the other hand,

\begin{align*}\ln (\phi(\,j))&= \sum_{i=k_{0}}^{j}\ln(1-\rho i^{\alpha-1})=-\sum_{i=k_{0}}^{j}\rho i^{\alpha-1} + O(\,j^{2\alpha-1}) =-\sum_{i=k_{0}}^{j}\rho i^{\alpha-1} + o(\,j^{\alpha}),\end{align*}

where the last equality follows since $\alpha < 1$. Thus,

\begin{align*}\phi(\,j)&=e^{-\sum_{i=k_{0}}^{j}\rho i^{\alpha-1} + o(\,j^{\alpha})}.\end{align*}

Observe that

\begin{align*}\int_{k_{0}}^{j} x^{\alpha-1} dx \le \sum_{i=k_{0}}^{j}i^{\alpha-1} \le \int_{k_{0}-1}^{j}x^{\alpha-1}dx,\end{align*}

and hence, for some constant $C(k_{0})$ depending only on $k_{0}$,

\begin{align*}\phi(\,j)&=C(k_{0}) (1+o(1)) \exp \left ({-}\int_{k_{0}}^{j}\rho x^{\alpha-1}dx +o (\,j^{\alpha}) \right)\\[2pt]&=C(k_{0}) (1+o(1)) \exp \left ( -\dfrac{\rho}{\alpha} j^{\alpha} + o (\,j^{\alpha})\right).\end{align*}

Then, from (14) we obtain

(15)\begin{align}\dfrac{e_{k}}{k}&= \dfrac{e^ { -\frac{\rho}{\alpha} k^{\alpha} + o (k^{\alpha}) } }{k} + \dfrac{e^{ -\frac{\rho}{\alpha} k^{\alpha} + o (k^{\alpha})} }{k} \sum_{j=k_{0}+1}^{k} \rho j ^{\alpha} e^{ \frac{\rho}{\alpha} j^{\alpha} + o (\,j^{\alpha}) } \nonumber\\[3pt]&\quad + \dfrac{e^{ -\frac{\rho}{\alpha} k^{\alpha} + o (k^{\alpha}) } }{k} \sum_{j=k_{0}+1}^{k} \delta_{j} e^{ \frac{\rho}{\alpha} j^{\alpha} + o (\,j^{\alpha})}.\end{align}

Since $\delta_{j}=o(\,j^{\alpha})$, we see that the leading term in the above expression is the second of the three summands. Thus,

\begin{align*}\dfrac{e_{k}}{k} \sim \dfrac{e^{-\frac{\rho}{\alpha} k^{\alpha}}}{k} \sum_{j=k_{0}+1}^{k} \rho j^{\alpha} e^{\frac{\rho}{\alpha} j^{\alpha}}.\end{align*}

A new comparison of the sum with the corresponding integral yields

\begin{align*}\dfrac{e_{k}}{k} \sim \dfrac{e^{-\frac{\rho}{\alpha} k^{\alpha}}}{k} \int_{k_{0}}^{k} \rho x^{\alpha} e^{\frac{\rho}{\alpha} x^{\alpha}}dx \sim \dfrac{e^{-\frac{\rho}{\alpha} k^{\alpha}}}{k} \int_{1}^{k} \rho x^{\alpha} e^{\frac{\rho}{\alpha} x^{\alpha}}dx,\end{align*}

since any finite interval of integration is asymptotically immaterial. This proves the first line of our claim. The second line follows easily by integration by parts.

The next result is a direct consequence of the above proposition, L’Hôpital’s rule, and Markov’s inequality.

Corollary 2. For the power and logarithmic decay,

\begin{align*}\dfrac{K_{T_{k}}}{V_{T_{k}}} \to 1 \quad \textit{ in probability.}\end{align*}

Remark 4. As a second extension to the basic model, we can assume that at each time $t\ge 0$ there are L independent walkers investigating the growing structure. Here, $L\ge 1$ is the number of walkers that collaborate to achieve the goal of knowing as much of the network as possible; i.e., the knowledge at time $t\ge 0$ increases if and only if at least one (and, a.s., exactly one) amongst the L walkers jumps at time t into a non-visited vertex. Of course, we can regard these L walkers as a single walker $(\textbf{X}_{\textbf{t}}=(X_{t}^{(i)})_{1\le i \le L}\,:\, t \ge 0)$ such that for each $t \ge 0$, $\textbf{X}_{\textbf{t}} \in V_{t}^{L}$. For $1 \le i \le L$, let $\mu_{i}$ be the transition rate of the ith walker. Thanks to independence, the transitions of $\textbf{X}_{\textbf{t}}$ occur at rate $\mu= \sum_{i=1}^{L}\mu_{i}$. This fact leads to a pleasant additive property of the knowledge process: regardless of which walker is performing a transition at time t, a jump of K occurs at this time if and only if this walker jumps into one of the $V_{t^{-}}-K_{t^{-}}$ non-visited vertices. This said, the next result, whose proof is omitted, should be almost obvious.

Proposition 3. With $\mu$ redefined as above, in the multiple-walker case,

\begin{align*}\lim_{k\to \infty} \mathbb{E} \bigg( \dfrac{ K_{T_{k}} }{V_{T_{k}}} \bigg) =\dfrac{\mu}{\mu+\gamma}\end{align*}

holds as well.

3.4. Almost sure properties for the knowledge process on the complete graph sequence

We turn back to the model of the growing sequence of complete graphs with constant rate of growth. Recall the generator (2). In what follows, $\mathcal{L}^{*}$ denotes the adjoint operator of $\mathcal{L}$.

Lemma 4. Let $h \in b\Delta^{*}$ be defined as

\begin{align*}h(v,k)= \binom{v-1}{k-1}\nu^{k-1}(1-\nu)^{v-k}, \qquad 1 \le k \le v.\end{align*}

Then $\mathcal{L}^{*}h=0$.

Proof. Based on (2), a routine computation shows that $\mathcal{L}^{*}$ is given by

(16)\begin{align}\mathcal{L}^{*}g(v,k)= \gamma \left [g(v-1,k) -g(v,k)\right ] + \mu \bigg[g(v,k-1)\dfrac{v-k+1}{v-1} -g(v,k)\dfrac{v-k}{v-1}\bigg].\end{align}

When this is applied to h, we obtain

\begin{align*}\mathcal{L}^{*}h(v,k)&=\gamma \bigg[ \binom{v-2}{k-1}\nu^{k-1}(1-\nu)^{v-k-1} - \binom{v-1}{k-1}\nu^{k-1}(1-\nu)^{v-k} \bigg] + \\[2pt]&\quad + \mu \left [ \binom{v-1}{k-2}\nu^{k-2}(1-\nu)^{v-k+1}\dfrac{v-k+1}{v-1} - \binom{v-1}{k-1}\nu^{k-1}(1-\nu)^{v-k} \dfrac{v-k}{v-1}\right]\\[2pt] &= \gamma \dfrac{\nu}{1-\nu} \binom{v-2}{k-1}\nu^{k-2}(1-\nu)^{v-k} - \gamma \binom{v-1}{k-1}\nu^{k-1}(1-\nu)^{v-k}\\[2pt] &\quad + \mu \dfrac{1-\nu}{\nu} \nu^{k-1}(1-\nu)^{v-k} \binom{v-1}{k-2}\dfrac{v-k+1}{v-1} - \mu \nu^{k-1}(1-\nu)^{v-k}\binom{v-1}{k-1} \dfrac{v-k}{v-1}\\[2pt] &=\mu \nu^{k-2}(1-\nu)^{v-k}\binom{v-2}{k-1} \\[2pt] &\quad + \nu^{k-1}(1-\nu)^{v-k}\left [ \gamma \binom{v-1}{k-2} \dfrac{v-k+1}{v-1} - \mu \binom{v-1}{k-1}\dfrac{v-k}{v-1}- \gamma \binom{v-1}{k-1}\right].\end{align*}

But the expression inside the square brackets equals

\begin{align*}\gamma \left (\binom{v-2}{k-2}-\binom {v-1}{k-1} \right ) - \mu \binom{v-2}{k-1}= -(\mu+\gamma) \binom{v-2}{k-1},\end{align*}

and thus

\begin{align*}\mathcal{L}^{*}h(v,k)&= \mu \nu^{k-2}(1-\nu)^{v-k}\binom{v-2}{k-1} - (\mu + \gamma) \nu^{k-1}(1-\nu)^{v-k} \binom{v-2}{k-1} \\[2pt]&=0,\end{align*}

as claimed.

For $k \le v$, set $p_{v}(k)=h(v,k)$.

Theorem 4. We have

\begin{align*}\dfrac{K_{t}}{V_{t}} \xrightarrow[t \to \infty]{} \nu \qquad \mathbb{P}_{C_{N}, K_{0}\sim p_{N}} \textit{-a.s.}\end{align*}

Proof. Let $(P_{t}\,:\, t \ge 0)$ be the Markov semigroup associated to the process $(V_{t}, K_{t})_{t \ge 0}$, and $P^{*}_{t}$ its adjoint. Lemma 4 says that $p_{v}$ is harmonic for $P^{*}_{t}$; i.e.,

(17)\begin{align}P^{*}_{t}(p_{v})(\!\cdot\!)= p_{v}(\!\cdot\!).\end{align}

For $n \ge 1$ consider any measurable function $f\,:\, [1, n]\to \mathbb{R}$, and define the function $g \in b\Delta$ by

\begin{align*}g(v,k)=f(k)\textbf{1}_{\{v=n\}}.\end{align*}

If we use integrals instead of the corresponding finite sums, a.s. we have

\begin{align*}\mathbb{E}_{K_{0}\sim p_{V_{0} } } ( g(V_{t}, K_{t}) )&=\int P_{t} (\,f \textbf{1}_{\{\cdot=n\} }) (V_{0}, k) p_{V_{0}}(dk)\\&=\int f(k)\textbf{1}_{\{V_{0}=n\}} (P^{*}_{t} p_{V_{0}})(dk),\end{align*}

and by the harmonic property (16), a.s. the last line equals

\begin{align*}\int f(k)\textbf{1}_{\{V_{0}=n\}} p_{V_{0}}(dk)= \textbf{1}_{\{V_{0}=n\}}\mathbb{E}_{K_{0} \sim p_{V_{0}}}(\,f(K_{0})).\end{align*}

In other words, we have proved that

\begin{align*}\mathbb{E}_{K_{0} \sim p_{V_{0}}}(\,f(K_{t}) \vert V_{t})= \mathbb{E}_{K_{t} \sim p_{V_{t}}} (\,f(K_{t})) \quad \text{a.s.,}\end{align*}

or

\begin{align*}(K_{t}-1)\vert V_{t} \sim \text{Binomial}(V_{t}-1, \nu) \quad \text{a.s.}\end{align*}

The rest of the proof relies on the classical estimate for trials of i.i.d. random variables with finite fourth moment. Indeed, there exists a constant c, depending on $\nu$ but not on t, such that

\begin{align*}\mathbb{E}( \left \vert (K_{t}-1)- \nu (V_{t}-1)\right \vert^{4} \vert V_{t}) \le c (V_{t}-1)^{2},\end{align*}

and thus

\begin{align*}\mathbb{E}\bigg( \left \vert \dfrac{K_{t}-1}{V_{t}-1}- \nu \right \vert^{4} \vert V_{t}\bigg) \le c (V_{t}-1)^{-2},\end{align*}

so that

\begin{align*}\mathbb{E}\bigg( \left \vert \dfrac{K_{t}-1}{V_{t}-1}- \nu \right \vert^{4} \bigg) \le \mathbb{E}(c (V_{t}-1)^{-2}).\end{align*}

An application of the Fubini–Tonelli theorem to the left-hand side of this inequality yields

\begin{align*}\mathbb{E} \bigg( \int_{0}^{\infty} \left \vert \dfrac{K_{t}-1}{V_{t}-1}- \nu \right \vert^{4} dt \bigg) \le \int_{0}^{\infty}\mathbb{E}(c (V_{t}-1)^{-2})dt.\end{align*}

The expression on the right-hand side is easily seen to be convergent. Thus, the integral on the left-hand side converges a.s. In particular, the integrand vanishes a.s. as t goes to infinity, and this implies our claim.

4. Complete bipartite graph sequence

As a final application, in this section we consider a simple rule for the growth of a bipartite graph. Let $p^{(\,j)}$, for $j =0, 1$, be positive parameters such that $p^{(0)}+p^{(1)}=1$. We start the graph sequence with $G_{0}$ equal to the complete graph on two vertices. Call the initial vertices 0 and 1. For $t \ge 0$, the set $V_{t}$ is split into two components, $V_{t}= V^{(0)}_{t} \cup V^{(1)}_{t}$, and initially each component contains one vertex. Just as before, at each time of renewal of a Poisson process of parameter $\gamma$ a new vertex arrives. Suppose the new vertex, say v, arrives at time $t > 0$. Then with probability $p^{(\,j)}$ it is assigned to the jth component (i.e. we set $V_{t}^{(\,j)}=V_{t^{-}}^{(\,j)} \cup \{v\}$), and, at the same time, we declare the edges of v to be exactly those of the old vertices in the component it was assigned to.

Just as in the previous section, let $(X_{t}\,:\, t \ge 0)$ be the simple random walk on the growing graph $(G_{t}\,:\, t \ge 0)$. Let $Y_{t}= \textbf{1}_{\{X_{t} \in V^{(1)}_{t}\}}$; i.e., $Y_{t}$ is the component $X_{t}$ belongs to. Let $\pi$ be the invariant distribution of a simple random walk on $G_{0}$. Obviously, $\pi$ is $Y_{t}$-invariant too.

We introduce some new notation related to the splitting of the growing graph into two components. Fix $j \in \{0,1\}$. For $t \ge 0$, let $K^{(\,j)}_{t}=K_{t}\cap V^{(\,j)}_{t}$; i.e., $K^{(\,j)}_{t}$ is the set of vertices in $V^{(\,j)}_{t}$ visited by time t. Let $Z^{(\,j)}_{0}=0$, and for $k \ge 1$, let

\begin{align*}Z^{(\,j)}_{k}\coloneqq \min \big\{t \ge Z^{(\,j)}_{k-1} \,:\, V^{(\,j)}_{t^{-}} \neq V^{(\,j)}_{t}\big\};\end{align*}

write $I_{k}^{(\,j)}=[Z^{(\,j)}_{k-1}, Z^{j}_{k})$ and $l^{(\,j)}_{k}= \vert I^{(\,j)}_{k}\vert $. Finally, let $J^{(\,j)}_{k}$ be the number of transitions to some vertex in the component j performed by the walker in the interval $I^{(\,j)}_{k}$.

Some observations are in order. First, the processes $N^{(\,j)}_{t}\coloneqq \vert \{ k \,:\, Z^{j}_{k} \le t\}\vert $ are (up to a constant shift) Poisson processes of intensity $\gamma p^{(\,j)}$. In particular, $l^{(\,j)}_{k}$ has distribution $\text{Exp}(\gamma p^{(\,j)})$ for every $k \ge 1$. Second, under the assumption that $X_{0} \sim \pi$, we have that for fixed j, the random variables $(J^{(\,j)}_{k}\,:\, k \ge 1)$ are identically distributed. So, for $j=0, 1$, let $J^{(\,j)}$ be a random variable distributed according to this common law, defined on an otherwise arbitrary probability space $(\Omega_{j}, \mathbb{P}_{j})$.

Proposition 4. For $k \ge 1$, let $r_{k}=\left ( 1-\dfrac{1}{k}\right)$, and for $j=0, 1$, let $C_{k}^{(\,j)}\coloneqq \mathbb{E}(r_{k}^{J^{(\,j)}})$. Then, for every $k \ge 1$,

(18)\begin{align} \mathbb{E}_{\pi}\bigg(K^{(\,j)}_{Z_{k}^{(\,j)}}\bigg)=\mathbb{E}_{\pi}\bigg(K^{(\,j)}_{Z_{k-1}^{(\,j)}}\bigg) C_{k}^{(\,j)} + k (1-C_{k}^{(\,j)}).\end{align}

Proof. Let $\mathbb{P}^{Z^{(\,j)}}(J^{(\,j)}_{k}=\cdot)$ be the law of $J^{(\,j)}_{k}$ given the sequence $Z^{(\,j)}\coloneqq (Z_{k}^{(\,j)}\,:\, k \ge 1)$. For $n \ge 0$, define

\begin{align*}P^{(\,j)}_{n}= \mathbb{E}_{\pi} \bigg(\mathbb{P}^{Z^{(\,j)}}(J^{(\,j)}_{k}=n) \vert \mathcal{F}_{Z^{(\,j)}_{k-1}}\bigg).\end{align*}

The definition is consistent. Indeed, $J^{(\,j)}_{k}$ depends only on the length $l_{k}$, and conditional on $\mathcal{F}_{Z_{k-1}}$, this length is distributed as $\text{Exp}(\gamma p^{(\,j)})$ independently of the $\sigma$-field $\mathcal{F}_{Z^{(\,j)}_{k-1}}$. So $P^{(\,j)}_{n}$ is a constant a.s., and furthermore,

\begin{align*}P^{(\,j)}_{n}= \mathbb{P}_{j} (J^{(\,j)}=n),\end{align*}

where $\mathbb{P}_{j}$ refers to the probabilty measure in the space $\Omega_{j}$ where $J^{(\,j)}$ has been defined.

Now, and in the same vein as in the proof of our result for the complete graph sequence, we compute conditional expectations, but this time we condition on $\mathcal{F}_{Z^{(\,j)}_{k-1}}$ for $k \ge 1$. In order to simplify the notation, just for the next computation, we drop the (j) superindices. On the set $J_{k}=n$, let $R_{1}, R_{2}, \ldots, R_{n}$ be the times in the interval $I_{k}$ where a transition to the state in the component j takes place. Then

\begin{align*}\mathbb{E}(K_{Z_{k}} \vert \mathcal{F}_{Z_{k-1}}) &= \mathbb{E}(K_{Z_{k}} \textbf{1}_{\{J_{k}=0\}} \vert \mathcal{F}_{Z_{k-1}}) + \sum_{n \ge 1} \mathbb{E}(K_{Z_{k}} \textbf{1}_{\{J_{k}=n\}} \vert \mathcal{F}_{Z_{k-1}}) \\&= K_{Z_{k-1}} P_{0} + \sum_{n \ge 1} \mathbb{E}(K_{R_{n}} \textbf{1}_{\{J_{k}=n\}} \vert \mathcal{F}_{Z_{k-1}}) \\ &= K_{Z_{k-1}} P_{0} + \sum_{n \ge 1} \mathbb{E}\bigg \{\!\left ( K_{R_{n-1}} \dfrac{K_{R_{n-1}}}{k} + (K_{R_{n-1}}+1) \dfrac{k-K_{R_{n-1}}}{k} \right) \textbf{1}_{\{J_{k}=n\}} \vert \mathcal{F}_{Z_{k-1}} \bigg \} \displaybreak\\ &= K_{Z_{k-1}} P_{0} + \sum_{n \ge 1} \mathbb{E} \bigg \{\!\left ( K_{R_{n-1}} \dfrac{k-1}{k} + 1 \right) \textbf{1}_{\{J_{k}=n\}} \vert \mathcal{F}_{Z_{k-1}} \bigg \} \\ &= K_{Z_{k-1}} p_{0} + \sum_{n \ge 1} \mathbb{E} \Bigg\{ \Bigg( K_{Z_{k-1}} \Big( \dfrac{k-1}{k} \Big)^{n} + \sum_{i=0}^{n-1}\Big( \dfrac{k-1}{k}\Big)^{i} \Bigg) \textbf{1}_{\{J_{k}=n\}} \vert \mathcal{F}_{Z_{k-1}} \Bigg \},\end{align*}

and this line equals

\begin{align*}K_{Z_{k-1}} \Bigg ( \sum_{n \ge 0} \Big( 1-\dfrac{1}{k} \Big)^{n}P_{n} \Bigg )+ k \Bigg(1- \sum_{n \ge 0} \Big ( 1-\dfrac{1}{k} \Big)^{n}P_{n} \Bigg).\end{align*}

After restoring the (j) superindices and taking expectations, we obtain (18).

The constants $C^{(\,j)}_{k}$ can be computed exactly. As an example, when $p^{(0)}=p^{(1)}=1/2$ (and hence, the growth of the structure can be defined as a sequence of uniformly growing complete bipartite graphs), we obtain that

\begin{align*}C^{(0)}_{k}=C^{(1)}_{k}= \dfrac{3\rho+1}{(2\rho+1)^{2}}+ \rho \left ( \dfrac{4\rho+1}{2\rho+1} \right )^{2} \dfrac{k-1}{k (4\rho +1) +4 \rho^{2}} = 1- \dfrac{\rho}{k} + O \left ( \dfrac{1}{k^{2}}\right).\end{align*}

It turns out that we do not need the exact value of these constants.

Theorem 5. For the model of the growing bipartite graph with parameters $p^{(0)},p^{(1)}$,

\begin{align*}\mathbb{E}\!\left( \dfrac{K^{(\,j)}_{Z_{k}^{(\,j)}}}{V^{(\,j)}_{Z_{k}^{(\,j)}}} \right) \to \dfrac{\rho^{(\,j)}}{1+\rho^{(\,j)}},\end{align*}

where $\rho^{(\,j)}= \dfrac{\rho}{2 p^{(\,j)}}$.

Proof. For fixed j and k, consider first the random variable $J^{(\,j)}_{k}$, and let $\tau= \tau_{k}^{(\,j)}$ be the number of steps of the process $Y_{t}$ during the time interval $I_{k}^{(\,j)}$. Then $\mathbb{E}_{\pi}(\tau)= \dfrac{\mu}{\gamma p^{(\,j)}}$. If we write $\tilde Y_{1}, \tilde Y_{2}, \ldots$ for the steps of the discrete parameter chain associated to the process Y during the same time interval $I_{k}^{(\,j)}$, we have

\begin{align*}\mathbb{E}_{\pi}(J^{(\,j)}_{k})&= \mathbb{E}_{\pi}\!\left ( \sum_{i=1}^{\tau} \textbf{1}_{\{\tilde Y_{i}=j\}} \right ) \\[2pt] &= \sum_{m\ge 0} \mathbb{E}_{\pi}\!\left ( \sum_{i=1}^{\tau} \textbf{1}_{\{\tilde Y_{i}=j\}} \vert \tau=m \right ) \mathbb{P}_{\pi}(\tau=m) \\[2pt]&= \sum_{m \ge 0} \pi_{j} m \mathbb{P}_{\pi}(\tau=m)\\[2pt] &=\pi_{j} \mathbb{E}_{\pi}(\tau)\\[2pt] &= \dfrac{\rho}{2 p^{(\,j)}}\\[2pt] &=\rho^{(\,j)}.\end{align*}

Hence

\begin{align*} C_{k}^{(\,j)}=\mathbb{E}\! \left \{ \left ( 1-\dfrac{1}{k} \right) ^{J^{(\,j)}}\right \}&= \mathbb{E}\!\left \{\exp \left(\ln \left(1-\dfrac{1}{k}\right)J^{(\,j)}\right) \right \}\\[2pt] &=1+ \ln \left ( 1-\dfrac{1}{k}\right)\mathbb{E}(J^{(\,j)}) + O \left ( \dfrac{1}{k^{2}}\right)\\[2pt] &= 1- \dfrac{\mathbb{E}(J^{(\,j)})}{k} + O \left ( \dfrac{1}{k^{2}}\right)\\[2pt] &= 1-\dfrac{\rho^{(\,j)}}{k} + O \left ( \dfrac{1}{k^{2}}\right). \end{align*}

Thus, (18) becomes

(19)\begin{align}\mathbb{E}_{\pi}\!\left(K^{(\,j)}_{Z_{k}^{(\,j)}}\right)=\mathbb{E}_{\pi}\!\left(K^{(\,j)}_{Z_{k-1}^{(\,j)}}\right) \left (1-\dfrac{\rho^{(\,j)}}{k} \right) + \rho^{(\,j)} + d_{k},\end{align}

where $d_{k}= O \bigg(\dfrac{1}{k}\bigg) $. Now, fix $k_{0} \ge 1$ such that $\frac{\rho^{(\,j)}}{k_{0}}< 1$. Iterating the relation (19), after a bit of algebra we get for $k \ge k_{0}$ that

\begin{align*}\mathbb{E}_{\pi}\!\left(K^{(\,j)}_{Z_{k}^{(\,j)}}\right)&=\mathbb{E}_{\pi}\!\left(K^{(\,j)}_{Z_{k_{0}}^{(\,j)}}\right) \dfrac{\Gamma (k+1-\rho^{(\,j)})\Gamma(k_{0}+2)}{\Gamma (k_{0}+2-\rho^{(\,j)}) \Gamma (k+1)} + \rho^{(\,j)} \sum_{i=k_{0}+1}^{k} \dfrac{\Gamma (k+1-\rho^{(\,j)}) \Gamma (i+1)}{\Gamma (k+1)\Gamma (i+1-\rho^{(\,j)})} \\[2pt]& \quad + \sum_{i=k_{0}+1}^{k} d_{i} \dfrac{\Gamma (k+1-\rho^{(\,j)}) \Gamma (i+1)}{\Gamma (k+1)\Gamma (i+1-\rho^{(\,j)} )},\end{align*}

and once again, the usual approximations and the fact that $d_{k} \to 0$ as $k \to \infty$ yield

\begin{align*}\mathbb{E}\!\left( \dfrac{K^{(\,j)}_{Z_{k}^{(\,j)}}}{V^{(\,j)}_{Z_{k}^{(\,j)}}} \right) \to \dfrac{\rho^{(\,j)}}{1+\rho^{(\,j)}}.\end{align*}

5. Final remarks

We have conducted a preliminary study of the behaviour of the asymptotic proportion of vertices visited by a random walker embedded in growing structures. We can think of this limit ratio as an index of the fitness of a dynamic structure aimed at supporting a randomised algorithm capable of taking advantage of new processing units as they become available. In fact, questions regarding the efficiency of autonomous, non-centralised crawling of a growing graph, as described in [Reference Cooper and Frieze7], largely served as inspiration for the present work. It must be stressed that any quantification of this efficiency is not likely to be based on other well-known indices (e.g. functionals of hitting times) as we have shown in the case of the complete graphs (Section 3, Subsection 2.1): in a fast-growing regime, $\tau$ turns out to be non-integrable.

The model we have proposed in Section 2 is motivated by the need to answer the question posed in the introduction. Thus, it necessarily differs from the much simpler model presented in [Reference Amir, Benjamini, Gurel-Gurevich and Kozma3], where the question about recurrence/transience of random walks in changing landscapes of conductances is qualitative in nature. The cost to be paid is that, at this stage, our research can only give an account of very simple (equivalently, highly symmetrical) growing strucures.

We have found that when the underlying world is the growing finite path (Subsection 2.2) or the complete graph sequence (Section 3), the asymptotic proportion is a.s. a constant, 0 in the first case and a.s. positive in the second case. In other words, we have found two simple classes of graph evolution that give an answer in the positive sense to Question 1 of the introduction. In the case of a naïve random structure (the complete bipartite graph sequence of Section 4) we were able to exhibit $L^{1}$ asymptotics for the aforementioned proportion in each of the two components of the graph. The question of whether this limit is an a.s. limit remains open, and the same holds for the other questions we posed in the introduction.

In our opinion, there are at least two lines of further research that are worth pursuing. The first one is to prove or disprove the conjecture below (or a related one) regarding the asymptotic order of the cover times of the structures and its relation with the asymptotic expected value of the knowledge process, as described in the last question of the introduction.

Conjecture 1. Let $P^{\mathcal{G}}$ be a Markov kernel on $\mathcal{G}_{fin}$, and $(G_{n}\,:\, n \ge 0)$ a graph process, as in Section 2. Set $c_{n}\coloneqq \dfrac{\mathbb{E}( \text{Cov}(G_{n}) ) }{n \ln n}$. Then

\begin{align*}\lim_{t \to \infty}\mathbb{E}\!\left ( \dfrac{K_{t}}{V_{t}} \right) = \dfrac{\mu}{\mu+ \gamma \lim_{n \to \infty} c_{n} }.\end{align*}

Some support for this still-to be-proved proposition can be found not only in the cases we have analysed in this work, but also in a simple comparison of the main results in [Reference Cooper and Frieze7] and [Reference Cooper and Frieze8].

The second line of further research is related to the regularity of the limits. More precisely, assume that for a given transition kernel $P^{\mathcal{G}}$ and for some choice of $\mu $ and $\gamma$, there exists a constant $\nu(\mu, \gamma)$ such that $\lim_{t \to \infty}K_{t}/V_{t}=\nu (\mu, \gamma)$ a.s. In the interpretation of this limit as an efficiency index for the growing structure intended to support a crawler, it would be desirable to have at our disposal some kind of fine-tuning theorem that gives conditions on $P^{\mathcal{G}}$ such that this limit is a smooth function of the natural parameters of the model. For example, it is far from trivial that the existence of an a.s. positive constant limit for a given choice of $(\mu, \gamma)$ guarantees the existence of an a.s. positive constant limit for some open range of the parameters.

We are currently working on both of these lines of research.

Appendix

In this short appendix, we rigorously construct the Markov process $\Xi_{t}$ of Section 2 and compute its generator. We adopt the notation introduced therein.

First, we observe that the set $\mathcal{G}_{fin}$ can be turned into a metric space. For two graphs $F, G \in \mathcal{G}_{fin}$ we define $N_{0}(F,G)=\inf \{k \,:\, F\vert _{[k]} \neq G\vert _{[k]}\}$, with the convention $\inf \emptyset = +\infty$, and set

\begin{align*}d_{\mathcal{G}_{fin}}(F,G)\coloneqq 2^{-N_{0}(F,G)}.\end{align*}

It is easy to verify that this metric induces the cylinder topology on $\mathcal{G}_{fin}$, and that under $d_{\mathcal{G}_{fin}}$, $\mathcal{G}_{fin}$ is a Polish space.

We give a topology to the set of finite subsets of $\mathbb{N}$, denoted $\mathcal{P}_{fin}(\mathbb{N})$, in such a way that the cardinal application

\begin{align*}\vert \cdot \vert \,:\, \mathcal{P}_{fin}(\mathbb{N}) &\to \mathbb{R}_{+}\\[2pt] A &\mapsto \vert A \vert\end{align*}

and set-union operation

\begin{align*}\cup\,:\, \mathcal{P}_{fin}(\mathbb{N}) \times \mathcal{P}_{fin}(\mathbb{N}) &\to \mathcal{P}_{fin}(\mathbb{N})\\[2pt] (A,B) &\mapsto A \cup B\end{align*}

become continuous functions in this topology. The simplest way to do this is to metrise $\mathcal{P}_{fin}(\mathbb{N})$ with the discrete metric $d_{\mathcal{P}_{fin}(\mathbb{N})}=\textbf{1}_{\{A \neq B\}}$. Observe that under the assumption of the Axiom of Countable Choice, this space becomes trivially a separable space that is complete for the discrete metric.

Finally, we endow $\mathbb{N}$ with the discrete topology as well.

For each of the spaces $\mathcal{G}_{fin}, \mathbb{N}$, and $ \mathcal{P}_{fin}(\mathbb{N})$ endowed with their respective metrics, we consider their Borel $\sigma$-fields, $\mathfrak{B}(\mathcal{G}_{fin})$, $\mathfrak{B}(\mathbb{N})$, and $\mathfrak{B}(\mathcal{P}_{fin}(\mathbb{N}))$, and set $\mathfrak{B}\coloneqq \mathfrak{B}(\mathcal{G}_{fin}) \otimes \mathfrak{B}(\mathbb{N}) \otimes \mathfrak{B}(\mathcal{P}_{fin}(\mathbb{N}))$.

Having established the elementary topological and measure-theoretic ingredients described above, we are now ready to build a Markov process taking values on a subspace of $\mathcal{S}\coloneqq \mathcal{G}_{fin} \times \mathbb{N} \times \mathcal{P}_{fin}(\mathbb{N})$, namely on the wedge

\begin{align*}\Delta \coloneqq \{(g,w, k) \in \mathcal{S}\,:\, w \le \vert g \vert, k \in 2^{\vert g \vert}, w \in k \}.\end{align*}

Every point of $\Delta$ will represent a state of the Markov process, and we give the following interpretation to the coordinates: the first coordinate represents the current world, the second coordinate represents the position of the walker in the current world, and the third coordinate keeps track of the vertices already visited by the walker.

The construction of the process proceeds as follows.

1. 1. Let a kernel $P^{\mathcal{G}}\,:\, \mathcal{G}_{fin}\times \mathfrak{B}(\mathcal{G}_{fin}) \to [0,1]$ be given, and assume that it satisfies the following:

   1. • $P^{\mathcal{G}}(\cdot, A)$ is a measurable application for every $A \in \mathfrak{B}(\mathcal{G}_{fin})$.

   2. • $P^{\mathcal{G}}(G, \cdot)$ is a probability measure for every $G \in \mathcal{G}_{fin}$.

   3. • For every $G \in \mathcal{G}_{n}$, the measure $P^{\mathcal{G}}(G, \cdot)$ is concentrated in $\mathcal{G}_{n+1}\cap \{H\,:\, H\vert _{[n]}=G\}$.

The choices regarding the metric on $\mathcal{G}_{fin}$ guarantee that $\mathcal{G}_{n}$ is a Borel set of $\mathcal{G}_{fin}$ for each $n \in \mathbb{N}$, and so the above conditions are consistent. Given any initial graph G on $\mathcal{G}_{fin}$, Kolmogorov’s consistency theorem guarantees the existence of a probability measure $P^{\mathcal{G}}_{G}$ on $(\Omega^{\mathcal{G}}\coloneqq \mathcal{G}_{fin}^{\mathbb{N}}, \mathfrak{B}(\mathcal{G}_{fin})^{\otimes \mathbb{N}})$ and a process $(G_{n}\,:\, n \ge 0)$ defined on it with $G_{0}=G$ whose one-step transitions are given by the kernel $P^{\mathcal{G}}$.

1. 2. On an arbitrary space $(\Omega^{0}, \mathcal{F}^{0}, P^{0})$ let there be given two independent, time-homogeneous Poisson processes, $(N^{walk}_{s}\,:\, s \ge 0)$ and $(N^{grow}_{s}\,:\, s \ge 0)$. The first one (which dictates the pace of the walker) is a Poisson process of intensity $\mu$, and the second one (which controls the inflation of the graph) is a Poisson process of intensity $\gamma$. Endow $\Omega^{0}$ with the natural filtration $(\mathcal{F}^{0}_{t})$ induced by the pair $(N^{walk}_{s}, N^{grow}_{s})$. Let $S_{0}= T_{0}=0$, and for $n \ge 1$ let $S_{n}$ (resp. $T_{n}$) be the nth jump time of $N^{walk}$ (resp. $N^{grow}$).

2. 3. Let $G_{0} \in \mathcal{G}_{fin}$ be a fixed initial graph. Given $(\omega, \omega^{\prime})$ drawn from $\Omega^{\mathcal{G}}\times \Omega^{0}$ according to $P^{\mathcal{G}} \otimes P^{0}$, for $s\ge 0$ we define

   \begin{align*}G_{s}(\omega, \omega^{\prime})\coloneqq G_{k}(\omega) \quad \text{ on } \{T_{k}(\omega^{\prime}) \le s < T_{k+1}(\omega^{\prime})\}.\end{align*}

3. 4. We build an $\mathbb{N}$-valued Markov process conditioned on $G=(G_{s}=G_{s}(\omega, \omega^{\prime})\,:\, s \ge 0)$ and on $(N^{walk}, N^{grow})=((N^{walk}_{s}(\omega), N^{grow}_{s}(\omega))\,:\, s \ge 0)$. For each fnite graph $G=(V,E) \in \mathcal{G}_{fin}$, let $P^{G}$ be its one-step transition kernel associated to the simple random walk taking values on the set V. Given an initial vertex $X_{0} \in [\vert G_{0} \vert]$, for $n \ge 1$ we draw $X_{n} \sim P^{G_{S_{n}}}(X_{n-1}, \cdot)$. Again, Kolmogorov’s consistency theorem guarantees the existence of a probability measure $P^{\mathcal{X}}= P^{\mathcal{X}}(\omega, \omega^{\prime})$ on $(\Omega^{\mathcal{X}}\coloneqq \mathbb{N}^{\mathbb{N}}, \mathfrak{B}(\mathbb{N})^{\otimes \mathbb{N}})$ such that $(X_{n}\,:\, n \ge 0)$ is a (non-time-homogeneous) Markov chain with the prescribed probability transition. Let $\omega^{\prime\prime}=\omega^{\prime\prime}(\omega, \omega^{\prime})$ denote a typical sequence on this space, i.e., $X_{n}(\omega^{\prime\prime})= \omega^{\prime\prime}_{n}$. Set $X_{t}= X_{0} $ on $0 \le t \le S_{1}$ and

   \begin{align*}X_{s}(\omega, \omega^{\prime\prime})=X_{n}(\omega^{\prime\prime}) \quad \text { on } \{S_{n}(\omega) \le s < S_{n+1}(\omega)\}.\end{align*}

4. 5. Finally, given a set $K_{0} \subset [\vert G_{0}\vert ]$ such that $K_{0}$ contains $X_{0}$, define

   \begin{equation*}K_{t} \coloneqq K_{0} \cup \{v \in \mathbb{N}\,:\, \exists s \le t \text { such that } X_{s}=v\} .\end{equation*}

Let $\Xi\coloneqq (\Xi_{t}= (G_{t}, X_{t}, K_{t})\,:\, t \ge 0)$, and consider the filtrations

\begin{align*}(\mathcal{F}^{\mathcal{G}}_{t}&\coloneqq \sigma(G_{s}\,:\, 0 \le s \le t) \,:\, t \ge 0), \\[2pt] (\mathcal{F}^{\mathcal{W}}_{t}&\coloneqq \sigma(X_{s}\,:\, 0 \le s \le t)\,:\, t \ge 0), \\[2pt] (\mathcal{F}^{\mathcal{K}}_{t}&\coloneqq \sigma(K_{s}\,:\, 0 \le s \le t)\,:\, t \ge 0), \\[2pt] \mathcal{F}_{t}&= \mathcal{F}_{t}^{\mathcal{G}} \vee \mathcal{F}_{t}^{\mathcal{W}} \vee \mathcal{F}_{t}^{\mathcal{K}}.\end{align*}

The following properties are direct consequences of our definitions:

1. • $\mathcal{F}^{0}_{t} \subset \mathcal{F}_{t}$.

2. • $((G_{s}, X_{s})\,:\, s \ge 0)$ is a $(\mathcal{G}_{fin} \times \mathbb{N})$-valued $\mathcal{F}_{t}$-Markov process defined on the probability space $\Omega\coloneqq \Omega^{0} \times \Omega^{\mathcal{G}} \times \Omega^{\mathcal{X}} $; the law $\mathbb{P}_{g, x}$ of the process started at vertex x in the graph g is computed by the formula

   \begin{align*}\mathbb{P}_{g,x} ((G,X) \in A\times B)= P^{\mathcal{X}}( X^{-1}(B) \vert G^{-1}(A)) (P^{0} \otimes P^{\mathcal{G}})(G^{-1}(A))\end{align*}
   for all Borel sets $A \in \mathfrak{B}(\mathcal{G}_{fin})^{\otimes \mathbb{N}}$, $B \in \mathfrak{B} (\mathbb{N})^{\otimes\mathbb{N}}$.

Let $b\Delta$ be the Banach space of bounded measurable real-valued functions on $\Delta$, and let $\mathbb{E}$ be the expectation operator associated to the probability $\mathbb{P}_{G_{0}, v}$. For a function $f \in b\Delta$, we use the notation

\begin{align*}P^{\mathcal{G}}f (g,x,k)= \sum_{H \in \mathcal{G}_{\vert g \vert +1}} P^{\mathcal{G}}(g, H) f(H, x, k),\end{align*}

and if $g \in \mathcal{G}_{fin}$, we write

\begin{align*}P^{g}f(g,x,k)= \sum_{y \sim_{g} x} P^{g}(x,y)\,f(g,y,k).\end{align*}

Theorem 6. The process $(\Xi_{t}\,:\, t \ge 0 )$ is a $\Delta$-valued Markov process whose infinitesimal generator acts on $f \in b\Delta$ as

(20)\begin{align} \mathcal{L}f (g,x, k)= \gamma \big[P^{\mathcal{G}}f(g,x,k)-f(g,x,k) \big] + \mu \sum_{y \sim_{g}x} P^{g}(x,y) \left [ f(g,y,k\cup \{y\}) -f(g,x,k)\right].\end{align}

Proof. For $0 \le s \le t$, let $w_{s,t}$ be the number of walking steps between s and t, and let $g_{s,t}$ be the number of growing steps (i.e. added vertices) between s and t. Using Landau’s little-o notation, for f as in our claim we compute as follows:

\begin{align*}\mathbb{E}(\,f(G_{t}, X_{t}, K_{t}) \vert \mathcal{F}_{s} ) &= \mathbb{E}(\,f(G_{t}, X_{t}, K_{t}) \vert (G_{s}, X_{s}, K_{s}) ) \\[2pt]&= \sum_{m\ge 0}\sum_{n \ge 0 }\mathbb{E}(\,f(G_{t}, X_{t}, K_{t}) \textbf{1}_{\{g_{s,t}=m\}} \textbf{1}_{\{w_{s,t}=n\}}\vert (G_{s}, X_{s}, K_{s}))\\[2pt]&=e^{-(\mu+ \gamma)(t-s)} f(G_{s}, X_{s}, K_{s}) \\[2pt] &\quad + e^{-\mu (t-s)}\gamma (t-s) e^{-\gamma (t-s)} \sum_{H \in \mathcal{G}_{fin}} P^{\mathcal{G}}(G_{s}, H)\,f(H,X_{s}, K_{s}) \\[2pt] &\quad + e^{-\gamma (t-s)} \mu (t-s)e^{-\mu(t-s)} \\ &\quad \times \sum _{y \sim_{G_{s}X_{s}}}P^{G_{s}}(X_{s}, y) ( f (G_{s}, y , K_{s})\textbf{1}_{\{y \in K_{s} \}} + f(G_{s}, y, K_{s}\cup \{y\}) \textbf{1}_{\{y \notin K_{s}\}} ) \\[2pt] &\quad + o (t-s)\\[2pt] &= e^{-(\mu+ \gamma)(t-s)} f(G_{s}, X_{s}, K_{s}) \\[2pt] &\quad + e^{-\mu (t-s)}\gamma (t-s) e^{-\gamma (t-s)} \sum_{H \in \mathcal{G}_{fin}} P^{\mathcal{G}}(G_{s}, H)\,f(H,X_{s}, K_{s}) \\[2pt] & \quad + e^{-\gamma (t-s)} \mu (t-s)e^{-\mu(t-s)} \sum _{y \sim_{G_{s}X_{s}}}P^{G_{s}}(X_{s}, y) f (G_{s}, y , K_{s} \cup\{y\}) \\[2pt] &\quad + o (t-s),\end{align*}

where the last equality follows from the fact that $K_{s}= K_{s}\cup \{y\}$ on $y \in K_{s}$. Then we have

\begin{align*}\lim_{t\to s} \dfrac{\mathbb{E}(\,f(G_{t}, X_{t}, K_{t}) \vert (G_{s}, X_{s}, K_{s}) )- f(G_{s}, X_{s}, K_{s})}{t-s} = -(\mu + \gamma) f(G_{s},X_{s}, K_{s} ) \\[2pt] \qquad \qquad + \gamma P^{\mathcal{G}}f(G_{s}, X_{s}, K_{s}) + \mu \sum _{y \sim_{G_{s}X_{s}}}P^{G_{s}}(X_{s}, y) f(G_{s}, y, K_{s}\cup \{y\}),\end{align*}

and our claim follows after rearranging terms and observing that

\begin{equation*} \sum _{y \sim_{G_{s}X_{s}}}P^{G_{s}}(X_{s}, y)=1.\end{equation*}