The voter model on random regular graphs
with random rewiring

The voter model [35] is a classical interacting particle system that can be described as follows. Initially, each vertex of the graph is equipped with a binary opinion. At the arrival times of a Poisson process, a vertex selects one of its neighbours uniformly at random and copies its opinion. Clearly, if the underlying graph is connected and finite, then the system eventually gets absorbed into one of the two consensus configurations where all the vertices share the same opinion.

As pointed out in [6, 2, 27], it is heuristically clear that universal behaviour emerges for the voter model in the scaling limit when the underlying graph is locally transient, i.e., when it converges to a transient graph in the local-weak sense. More precisely, focusing on the density of one of the two opinions and scaling time appropriately, convergence is expected towards the solution of the classical SDE for the Fisher-Wright diffusion $(\mathfrak{B}_{t})_{t\geq 0}$, which is given by

where $(\mathfrak{W}_{t})_{t\geq 0}$ is the standard Brownian motion and $\vartheta$ is a positive real number referred to as the diffusion constant. This idea has been made rigorous for the complete graph [26] (where $\vartheta=1$), and for the $d$-dimensional torus [23] (where $\vartheta$ is related to the Green function of simple random walk on the infinite lattice). More recently, in [20] (see also [43]) sufficient conditions are provided that ensure the above convergence, which is part of a more general program initiated in [24] referred to as the finite-systems scheme. In particular, the approach developed in [20] is capable of predicting that the limiting diffusion constant must be given by a proper rescaling of the expected meeting time of two stationary independent simple random walks evolving on the same underlying random graph. Exploiting this perspective, the limiting diffusion constant has been successfully identified for a number of static random graph models [22, 19, 7, 8, 47].

In the present paper, we consider the two-opinion voter model evolving on a dynamic random regular graph, where the dynamics arises from random rewiring. More precisely, our (autonomous) graph dynamics is initialised with a random regular graph and evolves in a stationary way by randomly rewiring edges at exponential times. More precisely, each stub (half-edge) is equipped with a Poisson process and, at each arrival time, selects another stub uniformly at random and matches with it, i.e., the two half-edges are linked together to form an edge. A parameter $\nu\in(0,\infty)$ controls the rate of the Poisson process, slowing down or speeding up the graph dynamics, with $\nu=0$ corresponding to the static graph. This model of a dynamic random graph has been used in [49, 48] as the underlying geometry for the contact process.

The goal of the present paper is to extend the work in [20] from a static to a dynamic environment, thereby proving pathwise convergence of the opinion densities to a Fisher-Wright diffusion. Moreover, by studying the meeting time of two independent random walks on our dynamic random graph, we identify the diffusion constant, $\vartheta_{d,\nu}$ as a function of the degree $d$ and the rewiring rate $\nu$. In particular, we provide an explicit expression for the diffusion constant in terms of a continued-fraction expansion, from which its finer properties can be deduced. As a byproduct of the analysis of this expansion, we derive relevant takeaways for applications: To what extent does the rewiring dynamics enhance the speed of consensus? What is the interplay between the speed of the dynamics and the degree? Moreover, we recover the mean-field setting in the limit as $\nu\to\infty$ or $d\to\infty$, and the static setting in the limit as $\nu\downarrow 0$.

To the best of our knowledge, the results presented in this paper provide the first instance of a voter model in a dynamic random environment for which the diffusion constant is computed explicitly (in accordance with the program set out in [6, 27, 2]). Our results may also serve as a benchmark for different graph models.

The precise statement of our main result, Theorem 2.5, is postponed to Section 2, following a detailed description of the model. In the same section, we also provide a thorough account of the proof strategy. Section 3 presents additional preliminaries, while the core of the paper is covered in Sections 4–7. A more detailed road map of the paper can be found in Section 2.6.

Fix $n\in\mathbb{N}$ and $d\geq 3$ such that $dn$ is even. Let $[n]$ represent the set of (labeled) vertices of our graph. Attach $d$ stubs (or half-edges) to each $x\in[n]$, which will be labeled as $\sigma_{x,1},\dots,\sigma_{x,d}$. In this language, a graph $G$ is a matching on the set of stubs $\cup_{1\leq i\leq d}\cup_{x\in[n]}\{\sigma_{x,i}\}$, and we call $\mathcal{G}_{n}(d)$ the set of all possible graphs. We call an edge of $G$ a matched pair of stubs and write $x\sim_{G}y$ to mean that there exists an edge (possibly more) between $x$ and $y$. More precisely, it will be convenient to write $\sigma_{x,i}\leftrightarrow_{G}\sigma_{y,j}$ to mean that $\sigma_{x,i}$ and $\sigma_{y,j}$ are matched in $G$, and ${\rm v}_{G}(x,i)\in[n]$ to denote the vertex to which the stub matched in $G$ to $\sigma_{x,i}$ belongs. We use the expression “$G$ is sampled according to the Configuration Model” to mean that $G$ is obtained by taking a matching uniformly at random on the set of stubs, i.e., $G$ is uniformly distributed on $\mathcal{G}_{n}(d)$, and we formally write it as $G=^{(\rm d)}\mu_{d}^{(n)}$.

We will also consider the simple random walk evolving on $G\in\mathcal{G}_{n}(d)$, namely, the continuous-time Markov process on $[n]$ with generator

It is worth pointing out that the uniform distribution on $[n]$, which will be denoted by $\pi^{(n)}$, is stationary for the process $L_{G}^{\rm RW}$ regardless of the choice of $G\in\mathcal{G}_{n}(d)$.

The voter model on a given $G\in\mathcal{G}_{n}(d)$ is the continuous-time Markov process $(\eta_{t})_{t\geq 0}$ on $\{0,1\}^{n}$ with generator

where $\eta^{x,y}$ is the configuration obtained from $\eta$ by setting

We will write “$x$ has opinion 0 (respectively, 1) at time $t$” when $\eta_{t}(x)=0$ (respectively, $\eta_{t}(x)=1$). Define $\mathbf{0}$ (respectively, $\mathbf{1}$) as the opinion configuration in which every vertex has opinion 0 (respectively, 1), and

to be the consensus time, i.e., the first time when all the vertices agree on the same opinion. Note that, as soon as $G$ is connected and regardless of the initial configuration, $\tau_{\rm cons}<\infty$ with probability one.

Often, to lighten notation, we suppress the dependence on $n$ and write $\mathcal{G}(d)$ in place of $\mathcal{G}_{n}(d)$, $\mu_{d}$ in place of $\mu_{d}^{(n)}$, and $\pi$ in place of $\pi^{(n)}$.

Next consider a dynamic graph, i.e., a continuous-time Markov process $(G_{t})_{t\geq 0}$ on $\mathcal{G}_{n}(d)$. Starting at an initial graph $G_{0}\in\mathcal{G}_{n}(d)$, we consider a rewiring dynamics in which pairs of edges are rewired, i.e., broken into four stubs that are subsequently reconnected. More precisely, each stub decides to rewire at rate $\frac{\nu}{4}$ in order to get matched to another stub uniformly at random, and the two stubs that are left alone by this procedure will then be matched among themselves. With this choice of parametrisation, a given edge of the graph has a survival time which is exponential of rate $\nu\frac{dn-2}{dn-1}\sim\nu$. Indeed, an edge will be rewired as soon as one of the two stubs which form the edge decides to rewire with another stub, or when another stub in the graph decides to rewire with one of the stubs forming the edge.

We will use the shortcuts $x\sim_{t}y$, $\sigma_{x,i}\leftrightarrow_{t}\sigma_{y,j}$ and ${\rm v}_{t}(x,i)$ to intend $x\sim_{G_{t}}y$, $\sigma_{x,i}\leftrightarrow_{G_{t}}\sigma_{y,j}$ and ${\rm v}_{G_{t}}(x,i)$, respectively. Formally, $(G_{t})_{t\geq 0}$ is the Markov process with generator $L^{\rm dyn}_{d,\nu}$ acting on functions $f:\mathcal{G}_{n}(d)\to\mathbb{R}$ as

where, for any $G\in\mathcal{G}_{n}(d)$, $x,y\in[n]$ and $1\leq i,j\leq d$ such that $\sigma_{x,i}\neq\sigma_{y,j}$ and $\sigma_{x,i}{\not\leftrightarrow}_{G}\sigma_{y,j}$, $\sigma_{z,k}$ and $\sigma_{v,\ell}$ are the stubs matched to $\sigma_{x,i}$ and $\sigma_{y,j}$ in $G$, and $\bar{G}^{x,y}_{i,j}$ is the graph obtained from $G$ by replacing the matchings $\sigma_{x,i}\leftrightarrow\sigma_{z,k}$ and $\sigma_{y,j}\leftrightarrow\sigma_{v,\ell}$ with $\sigma_{x,i}\leftrightarrow\sigma_{y,j}$ and $\sigma_{v,\ell}\leftrightarrow\sigma_{z,k}$. An explicit graphical construction of the process $(G_{t})_{t\geq 0}$ will be given in Section 3.

It is worth noting that the measure $\mu_{d}$ is stationary (actually, reversible) for the rewiring dynamics, in the sense that $G_{t}=^{(\rm d)}\mu_{d}$ for all $t\geq 0$ as soon as $G_{0}=^{(\rm d)}\mu_{d}$.

In analogy with the static case, we now give a formal description of the simple random walk and of the voter model on our dynamic graph set-up. By (simple) random walk on the dynamic graph we mean the continuous-time Markov process $(G_{t},X_{t})_{t\geq 0}$ on $\mathcal{G}_{n}(d)\times[n]$ with generator $L^{\rm dRW}_{d,\nu}$ acting on functions $f\colon\mathcal{G}_{n}(d)\times[n]\to\mathbb{R}$ as

Note that the process above is reversible with respect to the product measure $\mu_{d}\otimes\pi$. We will often consider two independent random walks on the same underlying dynamic graph, i.e., the Markov process $(G_{t},X_{t},Y_{t})_{t\geq 0}$ on $\mathcal{G}_{n}(d)\times[n]^{2}$ with generator $L^{\rm dRW(2)}_{d,\nu}$ acting on functions $g\colon\mathcal{G}_{n}(d)\times[n]^{2}\to\mathbb{R}$ as

Once again, this process is reversible with respect to $\mu_{d}\otimes\pi\otimes\pi$.

The main object in the present paper is the voter model on the dynamic graph $(G_{t})_{t\geq 0}$, namely, the continuous-time Markov process $(G_{t},\eta_{t})_{t\geq 0}$ on $\mathcal{G}_{n}(d)\times\{0,1\}^{n}$ with generator $L_{d,\nu}^{\rm voter}$ acting on functions $h\colon\mathcal{G}_{n}(d)\times\{0,1\}^{n}\to\mathbb{R}$ as

For any $G\in\mathcal{G}_{n}(d)$ and $\xi\in\{0,1\}^{n}$, denote by ${\mathbb{P}}_{G,\xi}={\mathbb{P}}^{(n)}_{G,\xi}$ the law of $(G_{t},\eta_{t})_{t\geq 0}$ starting from $(G,\xi)$. When the initial distribution is of product form with $G_{0}=^{(\rm d)}\mu_{d}$ and $\eta_{0}=^{(\rm d)}\otimes_{x\in[n]}{\rm Bernoulli}(u)$ for some $u\in[0,1]$, we use the shortcut ${\mathbb{P}}_{\mu_{d},u}$ to refer to the law of the joint process with such an initial condition. Also in the dynamic set-up we define the consensus time as in (2.4). Clearly, $(G_{t},\eta_{t})_{t\geq 0}$ has two absorbing sets, $\mathcal{G}_{n}(d)\times\{\mathbf{0}\}$ and $\mathcal{G}_{n}(d)\times\{\mathbf{1}\}$, and the process will be absorbed in one of them in finite time, i.e., ${\mathbb{P}}_{\mu_{d},u}(\tau_{\rm cons}<\infty)=1$ for all $u\in[0,1]$.

Throughout the sequel we assume $d\geq 3$ and $\nu\in(0,\infty)$ are fixed, and we are interested in deriving asymptotic results in the regime $n\to\infty$. Before presenting our results it is worth defining the following object, which plays a major role in our work.

The key object to deduce the convergence in Theorem 2.5 is an analysis of the time evolution of the density of discordances, defined as

Indeed, in the static set-up the density of opinions $(\mathcal{O}_{t})_{t\geq 0}$ in (2.15) is well-known to be a martingale with predictable quadratic variation given by $(\frac{2}{n}\int_{0}^{t}\mathcal{D}_{s}{\rm d}s)_{t\geq 0}$. As the next result shows, this is still true in our dynamic set-up.

For the simplest case of mean-field interaction, i.e., when the underlying static graph is the complete graph, we have

Because the solution to the SDE in (2.17) with $1$ in place of $\vartheta_{d,\nu}$ can be characterised as the unique continuous martingale having predictable quadratic variation

it is not hard to deduce the classical convergence of the mean-field voter model to the standard Fisher-Wright diffusion when time is rescaled linearly in the volume of the graph.

In [20] it is shown that, beyond the complete graph, the latter condition continues to hold under certain assumptions on the random walk on the underlying graph, which can be essentially summarised by a fast-mixing condition and an anti-concentration property of the stationary distribution (see [20, Theorem 2.2]). For obvious reasons the latter are referred to as mean-field conditions. In particular, convergence to the standard Fisher-Wright diffusion emerges when time is rescaled by the expected meeting time of two independent random walks evolving on the same graph and initialised at stationarity.

In view of this situation, our approach in proving Theorem 2.5 is based on a two-step argument. First. we identify the first-order approximation of the expected meeting time, leading to Theorem 2.4. Second, we generalise the results in [20] to our dynamic set-up. The first step is a major novelty in the present paper, and requires delicate coupling arguments as well as an analysis of certain recursive equations. We provide the proof of and the underlying heuristics behind Theorem 2.4 in Section 4. As to the second step, we follow the strategy developed in [20]. The following convergence criterion, which is stated in [20, Theorem 2.1] for the static case, is based on the analogue of Lemma 2.9 and standard tightness criteria. The reader may check that the proof presented in [20, Section 5] extends to our set-up without any change.

In light of the above discussion, our main task for the second step, spelled out in detail in Section 6, amounts to proving the following homogenisation property for the density of discordant edges of the voter model under the edge-rewiring dynamics.

Theorem 2.5 is a straightforward consequence of Theorem 2.11.

The remainder of this paper is organised as follows. In Section 3 we formally introduce the probability space under investigation, presenting the graphical construction of the joint process and a number of basic tools, including duality of the voter model with a system of coalescing random walks. In Section 4 we consider two idealized models, in which two random walks evolve on certain coalescing and fragmenting trees, which turn out to be the key approximation tools. In Section 5 we couple the idealised models with the actual random walks evolving on the finite dynamic graph, leading to the proof of the exponential law of their meeting time in Theorem 2.4. Section 6 is devoted to the proof of Theorem 2.11, which shows the convergence criterion for the Fisher-Wright approximation is fulfilled in the case of random regular graphs with rewiring. The results presented in this section have been developed in a static set-up in [20], so our main technical contribution in here is to show how to lift the recipe of [20] to our edge-dynamic setting. Finally, in Section 7 we provide a complete analysis of the diffusion constant, thereby settling Propositions 2.7–2.8.

It will be convenient to consider the following construction of the probability space we are interested in, which is usually referred to as the graphical construction:

• (1)

  Attach to each stub $\sigma_{x,i}$, $1\leq i\leq d$, of each vertex $x\in[n]$ a Poisson process of rate $1/d$, and call $(\mathfrak{T}^{\rm rw}_{x,i})_{x\in[n],1\leq i\leq d}$ the collection of these processes.

• (2)

  Attach to each stub $\sigma_{x,i}$, $1\leq i\leq d$, of each vertex $x\in[n]$ a Poisson process of rate $\frac{\nu}{4}$, and mark each arrival of such a process with a uniformly chosen independent stub $\sigma_{y,j}$, $y\in[n]$, $1\leq j\leq d$, with $(x,i)\neq(y,j)$. Call $(\mathfrak{T}^{\rm dyn}_{x,i})_{x\in[n],1\leq i\leq d}$ the collection of these marked processes.

We further assume that all the Poisson processes above are independent. With this source of randomness the graph dynamics, starting from an initial graph $G=G_{0}$, can be obtained as follows:

• •

  Let $t>0$ be the first arrival among the Poisson processes in (2). Assume that this time arrives on the process associated to $\sigma_{x,i}$ and is marked by $\sigma_{y,j}$ (with $(x,i)\neq(y,j)$).

  • –

    If $\sigma_{x,i}$ and $\sigma_{y,j}$ are matched in $G_{0}$, then nothing changes: set $G_{s}=G_{0}$ for all $s\in[0,t]$.

  • –

    If $\sigma_{x,i}$ and $\sigma_{y,j}$ are not matched in $G_{0}$, then call $\sigma_{z,k}$ and $\sigma_{v,\ell}$ the stubs matched to $\sigma_{x,i}$ and $\sigma_{y,j}$, respectively, and:

    • *

      let $G_{s}=G_{0}$ for all $0<s<t$;

    • *

      let $G_{t}$ be obtained from $G_{0}$ by erasing the edges $\sigma_{x,i}\leftrightarrow\sigma_{z,k}$ and $\sigma_{y,j}\leftrightarrow\sigma_{v,\ell}$ and creating the edges $\sigma_{x,i}\leftrightarrow\sigma_{y,j}$ and $\sigma_{z,k}\leftrightarrow\sigma_{v,\ell}$.

For any initial configuration, the voter dynamics on the underlying dynamic graph, i.e., $(G_{t},\eta_{t})_{t\geq 0}$, can be obtained by means of the same source of randomness as follows:

• •

  Consider the rewiring dynamics $(G_{t})_{t\geq 0}$ constructed above starting at some initial graph $G_{0}$, and let $\eta_{0}=\xi$ for some $\xi\in\{0,1\}^{n}$.

• •

  Let $t>0$ be the first arrival among the Poisson processes in (1). Assume that this time arrives on the process associated to $\sigma_{x,i}$, let $\eta_{s}=\eta_{0}$ for all $0<s<t$, and define $\eta_{t}=\eta_{0}^{x,{{\rm v}_{t}(x,i)}}$ (recall (2.3)).

Now, fix an initial graph $G_{0}=G$ and a time horizon $t>0$. We will consider two coalescing random walks evolving on $(G_{s})_{0\leq s\leq t}$ backward in time. More precisely, let $x,y$ be two vertices and consider a process $(\hat{X}^{x}_{s,t},\hat{X}_{s,t}^{y})_{s\in[0,t]}$ on $[n]^{2}$ constructed as follows:

• (a)

  Set $\hat{X}^{x}_{0,t}=x$ and $\hat{X}^{y}_{0,t}=y$.

• (b)

  Look at the last arrival time $r$ in the interval $[0,t]$ among the processes defined in (1). Say that this corresponds to an arrival for the process associated to $\sigma_{z,i}$ for some $z\in[n]$ and $1\leq i\leq d$. Set $(\hat{X}_{s,t}^{x},\hat{X}_{s,t}^{y})=(x,y)$ for all $s\in[t-r,t)$. Moreover,

  • –

    if $z\notin\{x,y\}$, then set $\hat{X}^{x}_{t-r,t}=x$ and $\hat{X}^{y}_{t-r,t}=y$;

  • –

    if $z\in\{x,y\}$, then set $\hat{X}^{z}_{t-r,t}$ to be the vertex connected to $x$ (respectively, $y$) through $\sigma_{z,i}$ in $G_{r}$, i.e., $\hat{X}_{t-r,t}^{x}={\rm v}_{r}(\sigma_{z,i})$.

The above construction can be extended to $n$ coalescing random walks $(\hat{X}^{x}_{s,t})_{s\in[0,t],x\in[n]}$ running backwards in time, each starting from a different vertex. Moreover, for any $t>0$ we can also consider the forward-in-time coalescing random walks $(X_{s}^{x})_{s\in[0,t],x\in[n]}$, which are defined in the same fashion as $(\hat{X}_{s,t}^{x})_{s\in[0,t],x\in[n]}$, with the only difference that in (b) the word last is replaced by the word first. Note that when we are looking at first arrivals such a forward-in-time process does not need to be defined on finite time intervals only, so that we can also consider $(X_{s}^{x})_{s\geq 0,x\in[n]}$.

In what follows we employ the symbol ${\mathbb{P}}$ to refer to the probability space associated to the Poisson processes in (1) and (2), and write ${\mathbb{P}}_{G,\xi}$ to intend that the initial state of the process is $(G_{0},\eta_{0})=(G,\xi)$. Similarly, we will write ${\mathbb{P}}_{\mu_{d},u}$ to intend the same probability space enriched with the (independent) randomness needed to construct the initial state $(G_{0},\eta_{0})=^{(\rm d)}\mu_{d}\otimes_{x\in[n]}{\rm Bernoulli}(u)$.

The graphical construction above reveals the following duality relation, which generalises the classical duality between the voter model and coalescent random walks on static graphs: for any initial configuration $(G,\xi)\in\mathcal{G}_{n}(d)\times\{0,1\}^{n}$, any sets of vertices $A,A^{\prime}\subset[n]$ and any time $t>0$,

For $x,y\in[n]$ and $t>0$, consider

and observe that (3.1) gives the relation

which, when the system starts from i.i.d. Bernoulli opinions of parameter $u\in[0,1]$, reduces to

for any $x,y\in[n]$, $G\in\mathcal{G}_{n}(d)$ and $u\in[0,1]$, where the dependence on $u$ in the probability on the right-hand side can be dropped due to the independence of the backward random walks and the initial configuration of the voter model. In particular, letting $G=^{(\rm d)}\mu_{d}$, we obtain

At this point it is worth noting that, since the graph dynamics is reversible with respect to $\mu_{d}$ and the Poisson processes in (1) are i.i.d., we have, for any $t>0$ and $x,y\in[n]$,

where, similarly to (3.2), the meeting time $\tau_{\rm meet}^{x,y}$ is defined as

Combining (3.5) and (3.6), we get

The identity in (3.8) unveils the relation between discordances of opinions for the voter model and meeting times of associated random walks. We next show more explicitly how the expectation of the observables we are interested in (i.e., those in (2.15) and (2.23)) are linked to the meeting time. To do so, it is useful to generalise the definition of meeting time in (3.7) to allow for the two initial positions $x$ and $y$ to be random, possibly depending on the initial graph $G_{0}$. In particular, we will consider the product case $(X_{0},Y_{0})=^{(\rm d)}\pi\otimes\pi$, and the case in which the two random walks start at the extremes of an edge of $G_{0}$ sampled uniformly at random. In order to indicate the meeting time of the two random walks in the latter two scenarios, we will write $\tau_{\rm meet}^{\pi\otimes\pi}$ and $\tau_{\rm meet}^{\rm edge}$, respectively.

With this notation at hand, and with the duality in (3.1), it is not hard to prove the following lemma.