How fast do rumours spread?

Rishideep Roy Kumarjit Saha

Abstract

We study a rumour propagation model along the lines of [21] as a long-range percolation model on $\mathbb{Z}$ . We begin by showing a sharp phase transition-type behaviour in the sense of exponential decay of the survival time of the rumour cluster in the sub-critical phase.

In the super-critical phase, under the assumption that radius of influence r.v. has $2+\epsilon$ moment finite (for some $\epsilon>0$ ), we show that the rightmost vertex in the rumour cluster has a deterministic speed in the sense that after appropriate scaling, the location of the rightmost vertex converges a.s. to a deterministic positive constant. Under the assumption that radius of influence r.v. has $4+\epsilon$ moment finite, we obtain a central limit theorem for appropriately scaled and centered rightmost vertex. Later, we introduce a rumour propagation model with reactivation. For this section, we work with a family of exponentially decaying i.i.d. radius of influence r.v.’s, and we obtain the speed result for the scaled rightmost position of the rumour cluster. Each of these results is novel, in the sense that such properties have never been established before in the context of the rumour propagation model on $\mathbb{Z}$ , to the best of our knowledge.

keywords:

Rumour Percolation , Renewal process , Speed of rightmost vertex , Re-activated Rumour process

\affiliation

[UoE]organization=School of Mathematics, Statistics and Actuarial Science, University of Essex, addressline=Wivenhoe Park, city=Colchester, postcode=CO4 3SQ, state=Essex, country=UK

\affiliation

[AU]organization=Department of Mathematics, Ashoka University, addressline=NH 44, Rajiv Gandhi Education City, city=Sonepat, postcode=131029, state=HR, country=India

1 Introduction

Interacting particle systems have been an area of interest for a long time. There have been numerous works related to varied forms of it. We are particularly interested in the spread of rumours within networks. We work with the rumour propagation model having rumours propagating on an infinite graph, which is within the class of long-range percolation models. We study rumour percolation models and we are interested sharp phase transition (in terms of the survival time of the rumour cluster) and speed of the scaled boundary points of the rumour cluster. We want to highlight here that extinction probabilities and phase transitions results have been studied on rumour models for some time. Still, to our knowledge, there has not been any previous work on the speed of propagation of rumours, which is our novelty. In addition, we also obtain a CLT result for the rightmost particle of the rumour cluster. In our work, we further generalise the rumour model to allow for reactivations, which basically means that a particle who heard the rumour in the past may spread it again at a future reactivation time point. To the best of our knowledge, this model has never been studied before. The concept of reactivation is influenced by the idea of recurring public opinion and its dissemination, considered for example in [27]. It is further motivated by the concept of reinfection in case of disease spread models, which have been studied in works such as [28].

There are close resemblances between rumour propagation and epidemic models as observed in [3]. However, they have their differences also, as stated in [6] that the fraction of the population who ultimately hears a rumour is independent of the population size. Both of them consider a finite population. Daley in [4] discussed stochastic and deterministic versions of the rumour process within a finite population. Dunstan in [7] extended the work on these models. There have been other works too on the spread of rumours in a finite population, for example, in [12]. They consider a complete graph with $n$ nodes, and the main object of interest is the time required for the rumour to spread to the entire network. This model assumes that the ones hearing the rumour will always spread it to other vertices that have never heard it before. Pittel in [22] extends results on this model.

Lebensztayn et al. in [21] consider a long-range percolation model, which they call a disk-percolation model, for the spread of infection. The model can be invariably used for rumour propagation as well. They have random variables termed radii of infection linked to each vertex $v$ in a locally finite and connected graph $\mathcal{G}$ , which follow geometric distributions. Initially, only the root is infected, and with time, the infection grows. They study the question of the indefinite spread of infection with positive probability and critical probability based on the parameter of the geometric distribution for the same. Junior et al. in [17] consider a similar model on $\mathbb{N}$ , which is called the Firework process. There, the propagation of rumours is uni-directional. They also consider a similar process called the reverse firework process, where instead of the propagation of rumours by an active vertex, the rumour is collected by the inactive vertices based on the random variables associated with inactive vertices. Their results consider generalisations over the distributions of the random variables associated with the vertices. Gallo et al. in [13] use the same models and construct a renewal process associated with the rumours to arrive at their results. Alsadat et al. in [2] consider a variant of the firework process, where rumours are spread to a new vertex only if it receives them from at least two sources. Junior et al. in a survey in [16] consider various variants of the rumour model and the major works done on them. Some recent works on the rumour model include [10], [11]. For a long range percolation model the question of eventual coverage of $[0,\infty)^{d}$ for $d\geq 1$ has been studied in [1]. However the question of rumour percolation on $\mathbb{Z}$ (which essentially means complete coverage) is different than the question of eventual coverage.

The shape of percolation clusters has also been studied for a long period. On $\mathbb{Z}$ , the study of the shape of the percolation cluster is equivalent to the study of the speed of propagation of the cluster. In the case of contact processes on $\mathbb{Z}$ , another closely related stochastic growth model, it has been shown in [8] that the rightmost particle grows at a linear rate, starting from one active particle at time zero at the origin. In the case of oriented percolation on $\mathbb{Z}^{2}$ , a similar result has been shown in [9]. For generalised oriented site percolation on $\mathbb{Z}^{2}$ , it has been shown that the rightmost infinite open path has a linear speed in [15]. Co-existence in interacting particle systems is another question of interest in the literature. Kostka et al. in [18] study competing rumours in social networks. Co-existence in another related percolation model, the frog model, is studied in [5], [23].

Below, we describe our initial rumour propagation model. On the infinite graph $\mathbb{Z}$ we consider an i.i.d. family of non-negative random variables such that these random variables are linked to every vertex $z\in\mathbb{Z}$ . We term these variables as radius of influence random variable. A rumour is initiated in one of these vertices, and we are interested in the phenomenon of the indefinite spread of the rumour. In the beginning, we assume that the radius of influence random variable attached to a vertex, does not change over time. As a result, after hearing the rumour, a vertex can spread the rumour only once and that too only at the time of hearing. Under the assumption that the $1+\epsilon$ moment of radius of influence random variable is finite (for some $\epsilon>0$ ), we establish a sharp phase transition behaviour in rumour percolation in terms of sharp decay of the survival time of the subcritical rumour cluster (see 3.2). Our methods can be successfully extended to analyze some rumour propagation models where individuals are randomly placed on $\mathbb{Z}$ (see Remark 3.2 for more details).

The next aspect we study is the speed of growth of the rumour cluster in the supercritical phase. In Theorem 4.1, we show that in the supercritical phase, under the assumption that the $2+\epsilon$ moment of the radius of influence random variable is finite for some $\epsilon>0$ , the appropriately scaled rightmost vertex in the rumour cluster converges to a deterministic positive constant almost surely. This result can be interpreted as the ‘speed’ of the growth of the rumour cluster in the supercritical phase. In Theorem 4.2 under the assumption that the $4+\epsilon$ moment is finite, we obtain the central limit theorem for the appropriately scaled and centred rightmost vertex in the rumour cluster.

Later, we generalise our model and allow vertices that heard the rumour in the past to spread it at multiple re-activation time points using independent copies of radii of influence random variables. Even though re-activation is a phenomenon that has been considered in different interacting particle systems, to the best of our knowledge, it has not been considered in the rumour propagation model so far. This provides a greater flexibility to individual vertices to spread the rumour. As a result, the question of phase transition in terms of rumour percolation becomes trivial. For this re-activation model, we deal with an i.i.d. family of radius of influence random variables with exponentially decaying tails and we show that the appropriately scaled rightmost vertex in the rumour cluster almost surely converges to a deterministic positive constant as well (see Theorem 5.1).

For both models, our proof techniques rely heavily on a renewal construction (see section 4.1). Later, in section 5.1 we modify this renewal construction in a non-trivial manner for the model with re-activation. The differences between the rightmost vertices of rumour clusters between successive renewals, together with the time gaps between successive renewal steps are shown to be i.i.d.

The paper is organised as follows. The model we work with initially, is formally defined in Section 2. We exhibit sharpness of phase transition regarding rumour percolation in Section 3. The result related to the ‘speed’ of growth of the rumour cluster in the supercritical phase is proved in Section 4. In the same section we obtain a central limit theorem for suitably centred and scaled position of the right-most vertex of the rumour cluster. In Section 5 as a generalisation of the usual rumour model, we introduce a rumour propagation model with independent re-activation clocks attached to each vertex and we obtain a deterministic speed for the growth of the rumour cluster in this set-up. The renewal constructions, especially in the case of the re-activated rumour model, are non-trivial.

We shall make use of the following lemma in our proofs. This lemma is a standard result of analysis, and as such, the proof is left to the readers.

Lemma 1.1.

For a sequence of real numbers $q_{n}$ , where $0\leqslant q_{n}<1$ , the infinite product $\prod_{n=1}^{\infty}(1-q_{n})$ converges to a non-zero number iff $\sum_{n=1}^{\infty}q_{n}$ converges.

2 Rumour model

We define our model of rumour percolation following the lines of [21], which is also discussed in [16, Section 3]. We consider the one-dimensional integer lattice $\mathbb{Z}$ as our intended network on which we wish to study the percolation of a rumour. We denote the set $\mathbb{Z}\cap[0,\infty)$ by $\mathbb{Z}^{+}$ and $\mathbb{Z}\cap(-\infty,0]$ by $\mathbb{Z}^{-}$ . We consider $\{I_{z}:z\in\mathbb{Z}\}$ , a collection of independent and identically distributed (i.i.d.) non-negative random variables, where $I_{z}$ represents the radius of influence for rumour propagation at the vertex $z\in\mathbb{Z}$ . Let $p_{1}:=P(I_{z}\in[0,1))$ and we assume that $\mathbb{E}(I_{z}^{1+\epsilon})<\infty$ for some $\epsilon>0$ . Using this collection $\{I_{z}:z\in\mathbb{Z}\}$ , we define the rumour percolation process as follows:

1.

At time $n=0$ , only a vertex $x\in\mathbb{Z}$ hears a rumour, becomes active and spreads the rumour to all vertices within $I_{x}$ distance from it. The rest of the vertices remain inactive (in terms of propagating the rumour). Without loss of generality, we can assume $x$ to be $0$ . Set $\mathcal{A}_{0}=\{0\}$ , which denotes the set of vertices that have heard a rumour at $0$ .

The set of vertices that have heard the rumour by time $n=1$ is given by

\mathcal{A}_{1}:=\{z:|z|\leqslant I_{0}\}.

Vertices in $\mathcal{A}_{1}$ spread the rumour to new vertices which have not heard the rumour till then, according to their respective radii of influences. Precisely, $z\in\mathcal{A}_{1}$ spreads rumour to an inactive vertex $u$ in the set $\mathbb{Z}\setminus\mathcal{A}_{1}$ at time $2$ if and only if $|u-z|\leqslant I_{z}$ .

We note that the vertex $0\in\mathcal{A}_{1}$ , that has heard the rumour in the past, fails to spread the rumour to any new vertex after time $1$ . The set of newly activated vertices at time $1$ , denoted by $\tilde{\mathcal{A}}_{1}:=\mathcal{A}_{1}\setminus\mathcal{A}_{0}$ may spread the rumour to other inactive vertices that have not heard the rumour till then, and make them active for the next time point. Keeping this in mind, the vertex $0$ becomes effectively inactive from time $1$ onward as it cannot spread the rumour to any new vertex after time $1$ and $\tilde{\mathcal{A}}_{1}:=\mathcal{A}_{1}\setminus\mathcal{A}_{0}=\mathcal{A}_{1}\setminus\{0\}$ denotes the set of (effectively) active vertices at time $1$ .

Similarly, the set of active vertices at time $2$ , which have heard the rumour at time $2$ and can propagate the rumour to new inactive vertices at time $3$ , is given by

\tilde{\mathcal{A}}_{2}:=\{z\in\mathbb{Z}\setminus\mathcal{A}_{1}:|z-u|\leqslant I_{u}\text{ for some }u\in\tilde{\mathcal{A}}_{1}\}.

The set of vertices that have heard the rumour by time $2$ is given by

\mathcal{A}_{2}:=\mathcal{A}_{1}\cup\tilde{\mathcal{A}}_{2}.

More generally, at time $n\geqslant 1$ , let $\tilde{\mathcal{A}}_{n}$ denote the set of active vertices at time $n$ and the set of vertices that have heard the rumour by time $n$ , is given by $\mathcal{A}_{n}:=\mathcal{A}_{n-1}\cup\tilde{\mathcal{A}}_{n}$ . An active vertex $u\in\tilde{\mathcal{A}}_{n}$ spreads rumour to all inactive vertices within $I_{u}$ distance that never heard the rumour in the past and makes them active at time $n+1$ . We observe that vertices in the set $\mathcal{A}_{n-1}$ can not spread the rumour to any new inactive vertex at time $n$ or later. Consequently, the set of active vertices at time $n+1$ is given by

\mathcal{\tilde{A}}_{n+1}:=\{z\in\mathbb{Z}\setminus\mathcal{A}_{n}:|z-u|\leqslant I_{u}\text{ for some }u\in\tilde{\mathcal{A}}_{n}\},

and $\mathcal{A}_{n+1}:=\mathcal{A}_{n}\cup\tilde{\mathcal{A}}_{n+1}$ denotes the set of vertices which have heard the rumour by time $n+1$ .

Figure 1: Rumour percolation at time

n=0

, with rumour starting at

x\in\mathbb{Z}

Figure 1 and Figure 2 together give a pictorial representation of the rumour process, starting from $x\in\mathbb{Z}$ . Grey dots denote the inactive vertices which have never heard a rumour. Black dots represent vertices that have heard the rumour so far, and black dots with red boundaries denote vertices that have heard the rumour newly, i.e., the set of currently active vertices. In the figure, we can see that $\tilde{\mathcal{A}}_{0}=\{x\}$ and $I_{x}=3$ . Hence, $\mathcal{A}_{1}=\{x-3,\ldots,x+3\}$ and $\tilde{\mathcal{A}}_{1}=\mathcal{A}_{1}\backslash\{0\}$ , as is shown in Figure 2. Assuming $I_{x+1}=2$ , $I_{x+2}=3$ , $I_{x+3}=1$ , $I_{x-1}=3$ , $I_{x-2}=2$ and $I_{x-3}=4$ , we have $\mathcal{A}_{2}=\{x-7,\ldots,x+5\}$ and $\mathcal{\tilde{A}}_{2}=\{x-7,\ldots,x+5\}\setminus\mathcal{A}_{1}$ . In this way, the rumour process evolves.

Figure 2: Rumour percolation at time

n=1

, with rumour starting at

x\in\mathbb{Z}

at time

n=0

The set $\mathcal{A}_{n}$ represents the rumour cluster at time $n$ , i.e., the collection of vertices that have heard the rumour by time $n$ . We observe that for our model and for all $n\geqslant 1$ the rumour cluster $\mathcal{A}_{n}$ is a finite set of the form $[a,b]\cap\mathbb{Z}$ for some $a,b\in\mathbb{Z}$ with $a\leqslant 0\leqslant b$ . In what follows, for any set $A$ , the notation $\#A$ denotes the cardinality of the set.

Definition 2.1.

The rumour percolation event is defined as $\#\mathcal{A}_{n}\to\infty$ as $n\to\infty$ .

Clearly, for this rumour propagation model, we have rumour percolation iff $\tilde{\mathcal{A}}_{n}\neq\emptyset\text{ for all }n$ . In other words, rumour percolates if the set of active vertices never becomes an empty set. Otherwise, rumour stops percolating. It is also easy to observe that if $\mathcal{\tilde{A}}_{n_{0}}=\emptyset$ for some $n_{0}\in\mathbb{N}$ , then $\mathcal{\tilde{A}}_{n}=\emptyset$ for all $n\geqslant n_{0}$ . This, however does not necessarily hold for the rumour propagation model with re-activation, introduced in Section 5. In the next section, we present a sharp phase transition result for rumour percolation.

3 Sharp phase transition for Rumour process

In this section, we show that the rumour percolation process exhibits a sharp phase transition. For $n\in\mathbb{N}$ we define the event $B_{n}$ as

B_{n}:=\{\text{either }n\in\mathcal{A}_{m}\text{ or }-n\in\mathcal{A}_{m}\text{ for some }m\geq 1\}.

Starting with the set $\mathcal{A}_{0}=\{0\}$ the rumour percolation event is defined as the event $\cap_{n=1}^{\infty}B_{n}$ . The rumour percolation probability is denoted by $\gamma$ . We observe that for the present model $\gamma$ can be simply expressed as

\gamma=P(\cap_{n=1}^{\infty}\bigl{(}\tilde{\mathcal{A}}_{n}\neq\emptyset)\bigr{)}.

However, for a rumour propagation model with re-activation, the above expression of $\gamma$ does not hold.

Let $\tau$ denote the random time when the rumour stops to percolate, i.e.,

\displaystyle\tau:=\inf\{n\geqslant 1:\tilde{\mathcal{A}}_{m}=\emptyset\text{ for all }m\geq n\},

and for this model we have $\tau=\inf\{n\geqslant 1:\tilde{\mathcal{A}}_{n}=\emptyset\}$ . The rumour percolates if the r.v. $\tau$ takes the value $+\infty$ . The next proposition gives us a necessary and sufficient condition for positive probability of rumour percolation.

Proposition 3.1.

For $n\geq 1$ we define $a_{n}:=\prod_{i=0}^{n}P(I_{0}\leq i)$ . Then

\gamma=0\text{ if and only if }\sum_{n=1}^{\infty}a_{n}=\infty.

Proposition 3.1 is an extension of Theorem 2.1 of [17] where uni-directional rumour percolation process on $\mathbb{N}$ was studied.

Proof.

For $n\geq 1$ we define the events

	$\displaystyle B^{+}_{n}$	$\displaystyle:=\{u+I_{u}<n+1\text{ for all }u\in[0,n]\cap\mathbb{Z}\}\text{ and }$
	$\displaystyle B^{-}_{n}$	$\displaystyle:=\{u-I_{u}>-n-1\text{ for all }u\in[-n,0]\cap\mathbb{Z}\}.$

From the translation invariance nature of our model it follows that $P(B^{+}_{n})=P(B^{-}_{n})=\prod_{i=0}^{n}P(I_{0}\leq i)=a_{n}$ . We define the random variables $J^{+},J^{-}$ respectively as

	$\displaystyle J^{+}$	$\displaystyle:=\sup\{n\geq 1:\text{ the event }B^{+}_{n}\text{ occurs}\}\text{ and }$
	$\displaystyle J^{-}$	$\displaystyle:=\sup\{n\geq 1:\text{ the event }B^{-}_{n}\text{ occurs}\}.$

If $\sum_{n=1}^{\infty}a_{n}<\infty$ , then by Borel-Cantelli lemma we have that $P(J^{+}<\infty)=P(J^{-}<\infty)=1$ which gives us $P(J^{+}\vee J^{-}<\infty)=1$ as well. Choose $M\in\mathbb{N}$ such that $P(J^{+}\vee J^{-}\leq M)>0$ , where ${}^{\prime}\vee^{\prime}$ denotes the maximum of two numbers. We observe that the event $\{J^{+}\vee J^{-}\leq M\}$ depends only on the family $\{I_{u}:u\in\mathbb{Z},u\notin[-M,M]\}$ and on this event this collection $\{I_{u}:u\in\mathbb{Z},u\notin[-M,M]\}$ is such that if the rumour starts propagating from the vertex $M+1$ (- $M+1$ ) towards the right (left) then it never stops. Because if it stops, that would indicate presence of $M^{\prime}>M$ such that the event $B^{+}_{M^{\prime}}\cup B^{-}_{M^{\prime}}$ occurs. This gives a contradiction as such a $M^{\prime}$ should not exist on the event $\{J^{+}\vee J^{-}\leq M\}$ . Now we choose the collection $\{I_{u}:u\in\mathbb{Z},u\in[-M,M]\}$ such that the rumour started from $0$ reaches the vertex $M+1$ and we can always do that with positive probability. This gives us that $\gamma>0$ if $\sum_{n=1}^{\infty}a_{n}<\infty$ .

To complete the proof of Proposition 3.1 we need to show that $\gamma=0$ if $\sum_{n=1}^{\infty}a_{n}=\infty$ . To do that we define an auxiliary construction of the rumour propagation process using i.i.d. collection $\{I^{(n)}_{z}:z\in\mathbb{Z},n\in\mathbb{N}\}$ such that for each $n\geq 1$ , a vertex $u\in\mathcal{\tilde{A}}_{n}$ uses the r.v. $I^{(n+1)}_{u}$ to propagate the rumour. We observe that the process obtained through this auxiliary construction has the same distribution as the original one. Based this auxiliary construction we define the corresponding versions of the events $B_{n}^{+},B_{n}^{-}$ respectively as

	$\displaystyle B^{+}_{n}$	$\displaystyle:=\{u+I^{(n+1)}_{u}<n+1\text{ for all }u\in[0,n]\cap\mathbb{Z}\}\text{ and }$
	$\displaystyle B^{-}_{n}$	$\displaystyle:=\{u-I^{(n+1)}_{u}>-n-1\text{ for all }u\in[-n,0]\cap\mathbb{Z}\}.$

Clearly we have $P(B^{+}_{n})=P(B^{-}_{n})=a_{n}$ and we also have that the events $B^{+}_{n}$ for $n\geq 1$ are mutually independent. Therefore, the converse part of Proposition 3.1 also follows from Borel-Cantelli lemma. This completes the proof. ∎

In addition, if we assume that $\mathbb{E}(I_{0}^{1+\epsilon})<\infty$ for some $\epsilon>0$ then 3.2 shows that there is a sharp phase transition for rumour percolation probability.

Proposition 3.2.

If $\mathbb{E}(I_{0}^{1+\epsilon})<\infty$ for some $\epsilon>0$ then we have

\displaystyle\gamma=\begin{cases}0&\text{ if }p_{1}>0\\ 1&\text{ if }p_{1}=0.\end{cases}

Further, for $p_{1}>0$ there exists $C_{0},C_{1}>0$ depending only on $p_{1}$ such that for all $n\in\mathbb{N}$ we have

\displaystyle P(\tau>n)\leqslant C_{0}e^{(-C_{1}n)}.

(3.1)

We mention here that [21, Remark 5] showed that rumour percolation on $\mathbb{Z}$ doesn’t happen when $p_{1}>0$ . The authors of [21] considered rumour percolation model only for geometrically distributed radii of influence random variables but on more general networks like $\mathbb{Z}^{d}$ for $d\geq 2$ and on regular trees. A proof of this can be found from [20, Theorem 2.1]. It is important to observe that in addition to the phase transition result for rumour percolation, as in [20, Theorem 2.1], 3.2 gives a sharp phase transition result in the sense of exponential decay of the amount of time the sub-critical rumour cluster survives. In Remark 3.2 we will further, apply our method for some other variants of rumour propagation model on $\mathbb{Z}$ where individuals are randomly placed over sites of $\mathbb{Z}$ . These models were earlier proposed in [13, Section 5] as possible extensions to be explored. Later we will show that, under the assumption of exponentially decaying i.i.d. radius of influence random variables, this means that the size of the sub-critical rumour cluster decays exponentially. Before we proceed further, we mention that several qualitative results of this paper involve constants. For more clarity, we will use $C_{0}$ and $C_{1}$ to denote two positive constants whose exact values may change from one line to another. The important thing is that both $C_{0}$ and $C_{1}$ are universal constants whose values depend only on the parameters of the process.

In order to prove 3.2, we define an ‘overshoot’ r.v. based on the collection $\{I_{i}:i\in\mathbb{Z}^{-}\}$ as follows:

\displaystyle O:=\sup\{i+I_{i}:i\in\mathbb{Z}^{-}\}.

(3.2)

Clearly, the overshoot r.v. $O$ is non-negative a.s. and it represents the amount of overshoot on $\mathbb{Z}^{+}$ , the positive part of the integer line, caused due to the family of r.v.’s $\{I_{i}:i\in\mathbb{Z}^{-}\}$ . Simple application of Borel Cantelli lemma shows that under the assumption of $(1+\epsilon)$ finite moment assumption, the overshoot r.v. is finite a.s. Lemma 3.1 analyzes some properties of this overshoot r.v.

Lemma 3.1.

(i)

For any $p_{1}>0$ we have $P(O=0)>p^{\prime}$ , where $p^{\prime}>0$ ;
(ii)

If $P(I_{0}\leqslant 1)>0$ then we have $P(O\leqslant 1)>0$ ;
(iii)
- (a)
  
  If $\mathbb{E}(I_{0})^{2+\epsilon}<\infty$ for some $\epsilon>0$ then we have $\mathbb{E}(O)<\infty$ .
- (b)
  
  If $\mathbb{E}(I_{0})^{4+\epsilon}<\infty$ for some $\epsilon>0$ then we have $\mathbb{E}(O^{2})<\infty$ .
- (c)
  
  If $I_{0}$ has exponentially decaying tails then there exist constants $C_{0},C_{1}>0$ such that
  
  $P(O>n)\leqslant C_{0}e^{-C_{1}n}\text{ for all }n\in\mathbb{N}.$

Proof.

For (i), using Markov inequality we obtain

	$\displaystyle P(O=0)$	$\displaystyle=P(\cap_{i=0}^{\infty}(I_{-i}\leq i))$
		$\displaystyle=p_{1}\prod_{i=1}^{\infty}P(I_{-i}\leq i)$
		$\displaystyle=p_{1}\prod_{i=1}^{\infty}(1-P(I_{-i}>i))$
		$\displaystyle\geq p_{1}\prod_{i=1}^{i_{0}}(1-P(I_{-i}>i))\prod_{i=i_{0}+1}^{\infty}(1-\mathbb{E}(I_{-i}^{1+\epsilon})/i^{1+\epsilon})$
		$\displaystyle=p_{1}\prod_{i=1}^{i_{0}}(1-P(I_{-i}>i))\prod_{i=i_{0}+1}^{\infty}(1-\mathbb{E}(I_{0}^{1+\epsilon})/i^{1+\epsilon})>0,$

where $i_{0}\in\mathbb{N}$ is chosen such that $\mathbb{E}(I_{0}^{1+\epsilon})/i^{1+\epsilon}<1$ for all $i>i_{0}$ .

For (ii), the argument is exactly the same. The only difference is that we no longer require positivity of $p_{1}$ , and instead, we use $P(I_{0}\leq 1)$ , which is positive by assumption.

We now consider part (a) of item (iii). The event $\{O=j\}$ implies $I_{-i}=i+j$ for some $i\geq 0$ . Recall that for this part we have assumed $\mathbb{E}(I_{0}^{2+\epsilon})<\infty$ for some $\epsilon>0$ . As $O$ is a non-negative integer valued r.v., using Markov inequality we obtain

	$\displaystyle\mathbb{E}(O)=$	$\displaystyle\sum_{n=1}^{\infty}P(O\geq n)$
	$\displaystyle=$	$\displaystyle\sum_{n=1}^{\infty}P(\cup_{i\in\mathbb{Z}^{+}}I_{-i}\geq n+i)$
	$\displaystyle\leqslant$	$\displaystyle\sum_{n=1}^{\infty}\sum_{i=0}^{\infty}P(I_{-i}\geq n+i)$
	$\displaystyle\leqslant$	$\displaystyle\sum_{n=1}^{\infty}\sum_{i=0}^{\infty}\mathbb{E}(I_{-i}^{2+\epsilon})/(n+i)^{2+\epsilon}$
	$\displaystyle=$	$\displaystyle\mathbb{E}(I_{0}^{2+\epsilon})\sum_{n=1}^{\infty}\sum_{i=0}^{\infty}1/(n+i)^{2+\epsilon}$
	$\displaystyle=$	$\displaystyle\mathbb{E}(I_{0}^{2+\epsilon})\sum_{m=1}^{\infty}(m+1)/m^{2+\epsilon}<\infty.$

The rearrangement in the last step is justified as we are dealing with non-negative terms only.

Part (b) of item (iii) follows from similar argument. Since $\mathbb{E}(I_{0}^{4+\epsilon})<\infty$ , Markov inequality gives us

	$\displaystyle\mathbb{E}(O^{2})=$	$\displaystyle\sum_{n=1}^{\infty}P(O^{2}\geq n)$
	$\displaystyle=$	$\displaystyle\sum_{n=1}^{\infty}P(\cup_{i\in\mathbb{Z}^{+}}I^{2}_{-i}\geq n+i)$
	$\displaystyle\leqslant$	$\displaystyle\sum_{n=1}^{\infty}\sum_{i=0}^{\infty}P(I_{-i}\geq\sqrt{n+i})$
	$\displaystyle\leqslant$	$\displaystyle\sum_{n=1}^{\infty}\sum_{i=0}^{\infty}\mathbb{E}(I_{-i}^{4+\epsilon})/(n+i)^{(4+\epsilon)/2}$
	$\displaystyle=$	$\displaystyle\mathbb{E}(I_{0}^{4+\epsilon})\sum_{n=1}^{\infty}\sum_{i=0}^{\infty}1/(n+i)^{(4+\epsilon)/2}$
	$\displaystyle=$	$\displaystyle\mathbb{E}(I_{0}^{4+\epsilon})\sum_{m=1}^{\infty}(m+1)/m^{(4+\epsilon)/2}<\infty.$

This completes the proof.

Finally, for part (c) of item (iii) we have assumed that there exist $C_{0},C_{1}>0$ such that

P(I_{0}>n)\leq C_{0}e^{(-C_{1}n)}\text{ for all }n.

Under this assumption, we obtain

\displaystyle P(O>n)=P(\cup_{i\in\mathbb{Z}^{+}}I_{-i}>n+i)\leqslant\sum_{i=0}^{\infty}P(I_{-i}>n+i)\leqslant\sum_{i=0}^{\infty}C_{0}e^{-C_{1}(n+i)}\leqslant C_{2}e^{-C_{3}n},

(3.3)

for some $C_{2},C_{3}>0$ . ∎

Remark 3.1.

We comment here that item (iii) of Lemma 3.1 does not require the collection $\{I_{i}:i\in\mathbb{Z}^{-}\}$ to be i.i.d. An uniform moment bound or an uniform tail bound is enough to conclude item (iii), e.g., part (a) of item (iii) holds for a collection $\{I_{i}:i\in\mathbb{Z}^{-}\}$ satisfying $\mathbb{E}(I_{i}^{2+\epsilon})\leq M<\infty$ for all $i$ .

For any subset $\mathcal{A}\subset\mathbb{Z}$ we consider the family of r.v.’s $\{I_{i}:i\in\mathcal{A}\cap\mathbb{Z}\}$ and corresponding to this family, we define the ‘right overshoot’ r.v. and ‘left overshoot’ r.v. towards the right side and left side of $\mathcal{A}$ respectively as below:

O^{\mathcal{A},+}:=\max\{(i+I_{i})-\sup(\mathcal{A}):i\in\mathcal{A}\cap\mathbb{Z}\}\text{ and }O^{\mathcal{A},-}:=\max\{\inf(\mathcal{A})-(i-I_{i}):i\in\mathcal{A}\cap\mathbb{Z}\}.

Clearly, the r.v. $O^{\mathcal{A},+}$ ( $O^{\mathcal{A},-}$ ) makes sense only if $\mathcal{A}\subseteq(-\infty,b]$ ( $\mathcal{A}\subseteq[a,+\infty)$ ) for some $b\in\mathbb{Z}$ ( $a\in\mathbb{Z}$ ). On the other hand, for any bounded set $\mathcal{A}\subset\mathbb{Z}$ , both these two r.v.s are a.s. finite. We are now ready to prove 3.2.

Proof of 3.2.

It is immediate that for the choice $p_{1}=0$ , rumour must percolate. Hence, to complete the proof of 3.2, it suffices to show eq. 3.1. Set ${\cal F}_{0}=\{\emptyset,\Omega\}$ and for $n\geq 1$ we define ${\cal F}_{n}:=\sigma(I_{z}:z\in\mathcal{A}_{n-1})$ . It is not difficult to see that the rumour propagation process $\{\mathcal{A}_{n}:n\geq 0\}$ is adapted to the filtration $\{{\cal F}_{n}:n\in\mathbb{N}\}$ .

For $n\in\mathbb{N}$ let $\mathcal{\tilde{A}}^{+}_{n}:=\mathcal{\tilde{A}}_{n}\cap\mathbb{Z}^{+}$ denote the set of active vertices at time point $n$ on the positive side. Similarly, the set $\mathcal{\tilde{A}}^{-}_{n}$ is defined. Both the random sets $\mathcal{\tilde{A}}^{+}_{n}$ and $\mathcal{\tilde{A}}^{-}_{n}$ are ${\cal F}_{n}$ measurable. Given the $\sigma$ -field ${\cal F}_{n}$ , we consider the overshoot r.v.’s $O^{\mathcal{\tilde{A}}^{+}_{n},+}$ and $O^{\mathcal{\tilde{A}}^{-}_{n},-}$ . By construction, for all $n\geqslant 1$ we have $\mathcal{\tilde{A}}^{+}_{n}\cap\mathcal{\tilde{A}}^{-}_{n}=\emptyset$ a.s. Therefore, given the $\sigma$ -field ${\cal F}_{n}$ , the overshoot r.v.’s $O^{\mathcal{\tilde{A}}^{+}_{n},+}$ and $O^{\mathcal{\tilde{A}}^{-}_{n},-}$ are supported on disjoint sets of influence r.v.’s, and for any two Borel sets $B_{1},B_{2}$ we have

\displaystyle P\bigl{(}O^{\mathcal{\tilde{A}}^{+}_{n},+}\in B_{1},O^{\mathcal{\tilde{A}}^{-}_{n},-}\in B_{2}\mid{\cal F}_{n}\bigr{)}=P\bigl{(}O^{\mathcal{\tilde{A}}^{+}_{n},+}\in B_{1}\mid{\cal F}_{n}\bigr{)}P\bigl{(}O^{\mathcal{\tilde{A}}^{-}_{n},-}\in B_{2}\mid{\cal F}_{n}\bigr{)}.

(3.4)

Further, given ${\cal F}_{n}$ the conditional distributions of both the overshoot r.v.’s, $O^{\mathcal{\tilde{A}}^{+}_{n},+}$ and $O^{\mathcal{\tilde{A}}^{-}_{n},-}$ , are stochastically dominated by the overshoot r.v. $O$ as defined in eq. 3.2 in the following sense:

		$\displaystyle P\bigl{(}O^{\mathcal{\tilde{A}}^{+}_{n},+}=0\mid{\cal F}_{n}\bigr{)}\wedge P\bigl{(}O^{\mathcal{\tilde{A}}^{-}_{n},-}=0\mid{\cal F}_{n}\bigr{)}\geqslant P(O=0)\text{ and }$
		$\displaystyle P\bigl{(}O^{\mathcal{\tilde{A}}^{+}_{n},+}>m\mid{\cal F}_{n}\bigr{)}\vee P\bigl{(}O^{\mathcal{\tilde{A}}^{-}_{n},-}>m\mid{\cal F}_{n}\bigr{)}\leqslant P(O>m)\text{ for any }m\in\mathbb{N},$		(3.5)

where ${}^{\prime}\wedge^{\prime}$ and ${}^{\prime}\vee^{\prime}$ denotes the minimum and maximum respectively.

Given $\tau>n$ , the r.v. $\tau$ takes the value $n+1$ if and only if the event $\{O^{\mathcal{\tilde{A}}^{+}_{n},+}=O^{\mathcal{\tilde{A}}^{-}_{n},-}=0\}$ occurs. Therefore, using eq. 3.4 and section 3 we obtain

	$\displaystyle P(\tau=n+1\mid\tau>n,{\cal F}_{n})$	$\displaystyle=P(O^{\mathcal{\tilde{A}}^{+}_{n},+}=0,O^{\mathcal{\tilde{A}}^{-}_{n},-}=0\mid\tau>n,{\cal F}_{n})$
		$\displaystyle=P(O^{\mathcal{\tilde{A}}^{+}_{n},+}=0\mid\tau>n,{\cal F}_{n})P(O^{\mathcal{\tilde{A}}^{-}_{n},-}=0\mid\tau>n,{\cal F}_{n})$
		$\displaystyle\geqslant P(O=0)^{2}>0.$

This gives us

P(\tau>n)\leqslant(1-P(O=0)^{2})^{n},

and completes the proof. ∎

The above result allows us to obtain moment bounds for the size of the sub-critical rumour cluster. Let $M=\#\mathcal{A}_{\tau}$ denote the size of the rumour cluster. Under the assumption that $\mathbb{E}(I_{0}^{1+\epsilon})<\infty$ for some $\epsilon>0$ , we proved that $M$ is finite a.s. if $p_{1}>0$ .

Proposition 3.3.

(i)

If $p_{1}>0$ and $\mathbb{E}(I_{0}^{2+\epsilon})<\infty$ for some $\epsilon>0$ , then $M$ has finite expectation.
(ii)

If $p_{1}>0$ and $\mathbb{E}(I_{0}^{4+\epsilon})<\infty$ for some $\epsilon>0$ , then $\mathbb{E}(M^{2})<\infty$ .
(iii)

If $p_{1}>0$ and there exist $C_{0},C_{1}>0$ such that $P(I_{0}>n)<C_{0}e^{(-C_{1}n)}$ for all $n\in\mathbb{N}$ , then $M$ also has exponentially decaying tail.

Proof.

Set $p_{1}>0$ . Let $\#\mathcal{A}^{+}_{\tau}=M_{+}$ and $\#\mathcal{A}^{-}_{\tau}=M_{-}$ . Clearly $M\leq M_{+}+M_{-}$ . From the translation invariance nature of our model it follows that both these two r.v.’s, $M_{+}$ and $M_{-}$ are identically distributed. Therefore, it is enough to prove 3.3 in terms of $M_{+}$ .

Next, we observe that for any $n\geq 0$ given $\mathcal{F}_{n}$ , the increment $\#\mathcal{\tilde{A}}^{+}_{n+1}$ is stochastically dominated by the overshoot r.v. $O$ . Therefore, the r.v. $M_{+}$ is stochastically dominated by the random sum $\sum_{m=1}^{\tau}O_{m}$ where $\{O_{m}:m\in\mathbb{N}\}$ gives a family of i.i.d. copies of $O$ . With the help of item (iii) of Lemma 3.1, the proof of 3.3 for $M_{+}$ readily follows from the following corollary. ∎

Corollary 3.1.

Consider a collection of i.i.d. r.v.’s $\{X_{i}:i\geq 1\}$ and let $\eta$ be a non-negative integer valued r.v. Consider the random sum $Z:=\sum_{i=1}^{\eta}X_{i}$

(i)

If $X_{1}$ and $\eta$ both have finite expectation then $Z$ has finite expectation.
(ii)

If $\mathbb{E}(X^{2}_{1})<\infty$ and $\eta$ is of finite expectation, then $Z$ has finite second moment.
(iii)

If there exist $C_{0},C_{1}>0$ such that $P(X_{1}>n)\vee P(\eta>n)\leq C_{0}e^{(-C_{1}n)}$ for all $n\geq 1$ , then $Z$ has exponentially decaying tail.

The first and the second parts of the Corollary follow from the Wald’s equation and the Blackwell-Girshick equation. The third part is also a well known result, e.g., we refer the reader to Lemma 2.7 of [24].

Before ending this section below application of our methods for some related models.

Remark 3.2.

(a)

Consider an i.i.d. collection of Bernoulli random variables $\{X_{u}:u\in\mathbb{Z}\}$ and assume that there is an individual at $u$ , who can participate for rumour propagation, if and only it $X_{u}=1$ . This model was introduced in [1] where the question of complete coverage has been studied. This problem was also mentioned in Section 5 of [13] as a possible direction for extension. For this model under the assumption that $\mathbb{E}(I^{1+\epsilon}_{0})$ is finite, our method applies as well and gives us that irrespective of the value of $p_{1}\in[0,1]$ , percolation won’t happen. Further, the survival time of the subcritical rumour cluster decays exponentially too. This follows from the observation that if $P(I_{0}\leq m)>0$ for some $m\in\mathbb{N}$ then the same argument as in Lemma 3.1 gives us $P(O\leq m)>0$ as well. We note that for any $n\geq 1$ , the occurrence of the event

E_{n}:=\{I_{u}<m\text{ for all }m\in\mathcal{\tilde{A}}_{n}\}\cap\{X_{v}=0\text{ for all }v\notin\mathcal{A}_{n}\text{ with }|v-w|\leq m\text{ for some }w\in\mathcal{A}_{n}\}

implies rumour percolation stops, and at each step probability of this event is uniformly bounded below.

(b)

Authors of [1] analysed a more general model compared to the previous one where individuals are placed on $\mathbb{Z}$ as a $\{0,1\}$ -valued time-homogeneous Markov chain. This model was mentioned in Section 5 of [13] as a future question to explore. As long as we have $P(X_{1}=0\mid X_{0}=0)\wedge P(X_{1}=0\mid X_{0}=1)>0$ , our method applies in this set up also (under the assumption $\mathbb{E}(I^{1+\epsilon}_{0})$ is finite) and gives the same set of conclusions.

4 Speed of the rightmost vertex in rumour cluster in the supercritical phase

In what follows, we will continue to work in the supercritical phase, i.e., we assume that $p_{1}=0$ . In addition, for the next result we assume that

\displaystyle\mathbb{E}(I_{0}^{2+\epsilon})<\infty\text{ for some }\epsilon>0.

(4.1)

Let $r_{n}=\max\mathcal{A}_{n}$ and $l_{n}=\min\mathcal{A}_{n}$ respectively denote the rightmost and the leftmost vertex in the set $\mathcal{A}_{n}$ . Clearly, for any $n\geqslant 1$ , both $r_{n}$ and $l_{n}$ are a.s. finite r.v.’s and the rumour cluster is represented by the set $[l_{n},r_{n}]\cap\mathbb{Z}$ . Under the assumption $p_{1}=0$ , we have $[-n,n]\subseteq[l_{n},r_{n}]$ for all $n\geqslant 1$ a.s. The main result of this section is the following:

Theorem 4.1.

Fix any $\epsilon>0$ . Under the assumption that the radius of influence r.v. has $2+\epsilon$ moment finite, there exists a deterministic constant $\mu\geqslant 1$ such that we have

\lim_{n\to\infty}\frac{r_{n}}{n}=\mu\quad\text{ a.s.}

To prove Theorem 4.1 in the following section we introduce a renewal construction for the rumour propagation process.

4.1 A renewal process

In this section, we describe a renewal construction for the rumour propagation process. In [13] the authors observed a renewal process based on the firework process on $\mathbb{N}$ . For rumour propagation on $\mathbb{Z}$ our renewal process construction is along different lines. The main challenge here lies in the fact that the rumour can spread on the positive side as well as on the negative side of the integer line $\mathbb{Z}$ here, making it more complicated than the firework process.

We define a random time $\sigma$ as

\displaystyle\sigma=\inf\{n\geqslant 1:O^{(-\infty,-n],+}\leq n\}.

(4.2)

Firstly, from the model description, it follows that $l_{n}\leq-n$ for all $n\geq 1$ . Next corollary shows that the r.v. $\sigma$ is finite a.s.

Corollary 4.1.

The r.v. $\sigma$ defined as in (4.2) is finite a.s.

Proof.

For $n\geq 1$ we consider the event $A_{n}:=\{I_{-n}\geq 2n\text{ for all }u\in\mathcal{\tilde{A}}^{-}_{m}\}$ and observe the following event inclusion relation

\{\sigma=+\infty\}\subset\limsup_{n\to\infty}A_{n}.

Under the assumption that $\mathbb{E}(I_{0}^{1+\epsilon})<\infty$ for some $\epsilon>0$ , using Markov inequality we obtain

\sum_{n=1}^{\infty}P(A_{n})=\sum_{n=1}^{\infty}P(I_{0}\geq 2n)\leq\mathbb{E}(I_{0}^{1+\epsilon})\sum_{n=1}^{\infty}\frac{1}{(2n)^{1+\epsilon}}<\infty.

Therefore, the proof follows from Borel Cantelli lemma. ∎

After the $\sigma$ -th step, active vertices on the negative side, i.e., vertices in the set $\mathcal{\tilde{A}}^{-}_{n}$ for any $n>\sigma$ , cannot spread the rumour to inactive vertices on the positive side and vertices in the set $\mathcal{\tilde{A}}^{+}_{n}$ only can spread the rumour to the positive side. We observe that the distribution of $\sigma$ depends only on radii of influences r.v.’s on the negative part of the integer line and hence, for any $z\in\mathbb{N}$ the r.v. $I_{z}$ is independent of $\sigma$ .

We now define the following sequence of random steps:

		$\displaystyle\tau_{0}=\sigma\text{ and for }j\geqslant 1$
		$\displaystyle\tau_{j}=\inf\{n>\tau_{j-1}:\#\mathcal{\tilde{A}}^{+}_{n}=1\}={\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}\inf\{n>\tau_{j-1}:r_{n}-r_{n-1}=1\}}.$		(4.3)

We need to show that for any $j\geqslant 1$ , the r.v. $\tau_{j}$ is a.s. finite. This is done in part (i) of Proposition 4.1. We recall that the notation $r_{n}$ denotes the location of the rightmost vertex of the rumour cluster at time $n$ .

Proposition 4.1.

(i)

There exist $C_{0},C_{1}>0$ such that for all $n\geq 1$ we have

$P(\tau_{j+1}-\tau_{j}>n\mid\tau_{1},\cdots,\tau_{j-1})\leqslant C_{0}e^{(-C_{1}n)};$
(ii)

Under the assumption (4.1) the increment r.v. $(r_{\tau_{j+1}}-r_{\tau_{j}})$ has finite expectation.

Proof.

Note that for the rumour propagation process starting from the origin, the process $\{(\mathcal{\tilde{A}}^{+}_{n},\mathcal{\tilde{A}}^{-}_{n}):n\geq 1\}$ is Markov. By definition of the random step $\sigma$ , for any $n>\sigma$ vertices in $\mathcal{\tilde{A}}^{-}_{n}$ cannot spread the rumour to the positive side. Therefore, for any $n>\sigma=\tau_{0}$ we have

\displaystyle P\bigl{(}\#\mathcal{\tilde{A}}^{+}_{n+1}=1\mid(\mathcal{\tilde{A}}^{-}_{n},\mathcal{\tilde{A}}^{+}_{n}),(\sigma<n)\bigr{)}

\displaystyle\geqslant P(O=1)>0,

(4.4)

where $O$ is defined as in (3.2).

This implies that after the $\sigma$ -th step at every step, there is a fixed positive lower bound for the probability of occurrence of a $\tau$ step. Hence, 4.4 proves part (i) of 4.1.

Regarding (ii), we observe that

r_{\tau_{j+1}}-r_{\tau_{j}}=\sum_{m=\tau_{j}+1}^{\tau_{j+1}}\#\mathcal{\tilde{A}}^{+}_{m}.

(4.5)

Consider a collection of i.i.d. copies of the overshoot r.v. $O$ given as $\{O_{i}:i\geq 1\}$ and let $\overline{\tau}:=\inf\{i\geq 1:O_{i}=1\}$ . It follows that the increment r.v. $r_{\tau_{j+1}}-r_{\tau_{j}}$ is stochastically dominated by the random sum $\sum_{i=1}^{\overline{\tau}}O_{i}$ . Finally, Corollary 3.1 ensures under the assumption (4.1), i.e., $\mathbb{E}(I^{(2+\epsilon)}_{0})<\infty$ for some $\epsilon>0$ , the random sum $\sum_{i=1}^{\overline{\tau}}O_{i}$ has finite expectation and therefore, the increment r.v. $(r_{\tau_{j+1}}-r_{\tau_{j}})$ has finite mean too. ∎

The next result shows that the above sequence of random steps gives a sequence of renewal steps with i.i.d. increments for the rumour propagation process.

Proposition 4.2.

$\{(\tau_{j+1}-\tau_{j},r_{\tau_{j+1}}-r_{\tau_{j}}):j\geqslant 1\}$ gives a collection of i.i.d. random vectors taking values in $\mathbb{N}\times\mathbb{N}$ .

Proof.

Independence of increment vectors between successive renewals follows as they are supported on disjoint sets of radius of influence random variables. We present a brief description of the identical distribution of the increment random vector below.

Consider a rumour propagation process only on $\mathbb{Z}^{+}$ starting with the origin as the only active vertex at time point $0$ . Let $\mathcal{A}^{+}_{n}$ and $\mathcal{\tilde{A}}^{+}_{n}$ denote the corresponding analog of sets $\mathcal{A}_{n}$ and $\mathcal{\tilde{A}}_{n}$ when the sets $\mathcal{A}_{n}$ and $\mathcal{\tilde{A}}_{n}$ are now restricted to $\mathbb{Z}^{+}$ only. We consider the evolution of this process till the random time $\gamma$ such that we have $\#\mathcal{\tilde{A}}^{+}_{\gamma}=1$ . Let $r^{+}_{\gamma}$ denote the position of the rightmost active vertex at time $\gamma$ . The increment random vectors between successive renewals have the same distribution as $(\gamma,r^{+}_{\gamma})$ , i.e., for all $j\geqslant 1$ we have

(\tau_{j+1}-\tau_{j},r_{\tau_{j+1}}-r_{\tau_{j}})\stackrel{{\scriptstyle{\cal L}}}{{=}}(\gamma,r^{+}_{\gamma}),

where the notation $\stackrel{{\scriptstyle{\cal L}}}{{=}}$ denotes equality in distribution. This completes the proof.

∎

4.2 Proof of Theorem 4.1

In this section we complete the proof of Theorem 4.1. In the next corollary, using our renewal construction, we prove Theorem 4.1 and provide a precise understanding of the limit too.

Corollary 4.2.

We have

\displaystyle\lim_{n\to\infty}r_{n}/n=\mu=\frac{\mathbb{E}(r_{\tau_{2}}-r_{\tau_{1}})}{\mathbb{E}({\tau_{2}}-{\tau_{1}})}\text{a.s.}

(4.6)

Proof.

From 4.2, we can write the right hand side of eq. 4.6 as:

\lim_{k\to\infty}\dfrac{\frac{1}{k}\left(\sum_{j=1}^{k}r_{\tau_{j+1}}-r_{\tau_{j}}\right)}{\frac{1}{k}\left(\sum_{j=1}^{k}\tau_{j+1}-\tau_{j}\right)}.

This reduces to give,

\displaystyle\frac{\mathbb{E}(r_{\tau_{2}}-r_{\tau_{1}})}{\mathbb{E}({\tau_{2}}-{\tau_{1}})}=\lim_{k\to\infty}\frac{r_{\tau_{k+1}}-r_{\tau_{1}}}{\tau_{k+1}-\tau_{1}}.

(4.7)

Let $n$ be large enough such that $\tau_{1}<n$ . Let $k(n)\in\mathbb{N}$ be such that $\tau_{k(n)}\leqslant n<\tau_{k(n)+1}$ . From now on we shall just use $k$ to denote $k(n)$ . Then, $r_{\tau_{k}}-r_{\tau_{1}}\leqslant r_{n}-r_{\tau_{1}}<r_{\tau_{k+1}}-r_{\tau_{1}}.$ Since we have

\displaystyle\lim_{k\to\infty}\frac{r_{\tau_{k+1}}-r_{\tau_{1}}}{\tau_{k+1}-\tau_{1}}=\lim_{k\to\infty}\frac{r_{\tau_{k}}-r_{\tau_{1}}}{\tau_{k}-\tau_{1}},

hence,

\displaystyle\lim_{n\to\infty}\frac{r_{n}-r_{\tau_{1}}}{n-\tau_{1}}=\lim_{k\to\infty}\frac{r_{\tau_{k+1}}-r_{\tau_{1}}}{\tau_{k+1}-\tau_{1}}.

(4.8)

So, from eq. 4.7 and eq. 4.8 we get,

\displaystyle\frac{\mathbb{E}(r_{\tau_{2}}-r_{\tau_{1}})}{\mathbb{E}({\tau_{2}}-{\tau_{1}})}=\lim_{n\to\infty}\frac{r_{n}-r_{\tau_{1}}}{n-\tau_{1}}=\lim_{n\to\infty}\frac{r_{n}}{n}.

∎

4.3 A central limit theorem for the position of rightmost vertex

In this section, we prove a central limit theorem for the position of the rightmost vertex in a super-critical rumour percolation cluster, motivated by similar work by [19] on the right edge of super-critical oriented percolation. For this part of the result we assume that $\mathbb{E}(I_{0})^{4+\epsilon}<\infty$ for some $\epsilon>0$ . Under this assumption by item (iii) of Lemma 3.1 we have that the overshoot r.v. $O$ has finite second order moment. Further, Corollary 3.1 and the same argument as in part (ii) of Proposition 4.1 together give us that the increment r.v. $(r_{\tau_{j+1}}-r_{\tau_{j}})$ has finite second order moment as well.

The main result of the section is the following:

Theorem 4.2.

Under the assumption that $\mathbb{E}(I_{0})^{4+\epsilon}<\infty$ for some $\epsilon>0$ and $p_{1}=0$ , we have

\frac{r_{n}-n\mu}{\sqrt{n}}\overset{\mathcal{L}}{\longrightarrow}N(0,\psi^{2}),

(4.9)

where the notation $\overset{\mathcal{L}}{\longrightarrow}$ denotes convergence in distribution.

Proof.

Choose $n$ large enough such that $\tau_{1}<n$ . Let $k(n)\in\mathbb{N}$ be such that $\tau_{k(n)}\leqslant n<\tau_{k(n)+1}$ . From now on we shall just use $k$ to denote $k(n)$ . Then, $r_{\tau_{k}}\leqslant r_{n}<r_{\tau_{k+1}}.$ So we also have,

\frac{r_{\tau_{k}}-n\mu}{\sqrt{n}}\leqslant\frac{r_{n}-n\mu}{\sqrt{n}}<\frac{r_{\tau_{k+1}}-n\mu}{\sqrt{n}}.

From 4.2 we know that $\frac{\tau_{j+1}-\tau_{j}}{\sqrt{n}}$ converges in probability to $0$ as $n\to\infty$ , for all $j\geqslant 1$ , also that $\frac{r_{\tau_{k+1}}-r_{\tau_{k}}}{\sqrt{n}}\overset{P}{\longrightarrow}0$ . Hence, we shall have $\frac{r_{\tau_{k+1}}-r_{n}}{\sqrt{n}}\overset{P}{\longrightarrow}0$ . So, it remains to show that,

\frac{r_{\tau_{k+1}}-n\mu}{\sqrt{n}}\overset{\cal L}{\longrightarrow}N(0,\psi^{2}).

From [26, Lemma 2] as stated in [19, Corollary 1], we know that in our notation

\frac{r_{\tau_{k+1}}-n\mu}{\sqrt{n}}\overset{\cal L}{\longrightarrow}N(0,\psi^{2}).

Here, $\psi$ is a positive real number. On incorporating Corollary 4.2, we have eq. 4.9. ∎

5 A rumour model with a reactivation mechanism

In this section, we will introduce and analyse a rumour model with a reactivation mechanism where, due to reactivation, a vertex which received the rumour at a past time point, may spread it again in future using an independent radius of influence random variable. The motivation is that, on the event of spreading a gossip over a network, an enthusiastic individual may contribute at multiple time points. As we have mentioned before, this concept of reactivation is influenced by the idea of recurring public opinion and its dissemination, considered for example in [27]. It is further motivated by the concept of reinfection in case of disease spread models. Below, we describe our model.

We start with a family of i.i.d. radii of influence r.v.’s. $\{I^{n}_{v}:v\in\mathbb{Z},n\in\mathbb{Z}^{+}\}$ and a family of i.i.d. Bernoulli r.v.’s $\{B^{n}_{v}:v\in\mathbb{Z},n\in\mathbb{Z}^{+}\}$ with parameter ${\color[rgb]{0,0,0}\definecolor[named]{pgfstrokecolor}{rgb}{0,0,0}\pgfsys@color@gray@stroke{0}\pgfsys@color@gray@fill{0}p_{2}}\in(0,1)$ . A vertex $u\in\mathbb{Z}$ , which has newly heard the rumour at time $n$ , uses the r.v. $I^{n}_{u}$ to spread the rumour. In addition to it, a vertex $u^{\prime}\in\mathbb{Z}$ which heard it at some time before $n$ , becomes active again and spreads the rumour using $I^{n}_{u^{\prime}}$ at time $n$ if and only if $B^{n}_{u^{\prime}}=1$ . In other words, for a vertex $u\in\mathbb{Z}$ , which heard the rumour at a previous time point, the Bernoulli r.v. $B^{n}_{u}$ indicates whether $n$ is an activation time or not. For this section, we would assume that the radius of influence r.v. $I^{0}_{0}$ has exponentially decaying tail. Our results, however, would still hold true without assuming this, but with assumptions on higher moments only. We are now ready to define this rumour propagation with the reactivation model formally.

For any interval $I$ with $I\cap\mathbb{Z}\neq\emptyset$ , we denote the rumour percolation process with reactivation starting from an initial active set $I\cap\mathbb{Z}$ as $\{(\mathcal{A}^{\text{R},I}_{n},\mathcal{\tilde{A}}^{\text{R},I}_{n}):n\geqslant 0\}$ where $\mathcal{A}^{\text{R},I}_{n}$ denotes the set of vertices that have heard the rumour by time $n$ and $\mathcal{\tilde{A}}^{\text{R},I}_{n}$ denotes the set of vertices that are ready to spread the rumour at time $n$ . The random set $\mathcal{\tilde{A}}^{\text{R},I}_{n}$ definitely contains vertices that have newly heard the rumour at time $n$ . More importantly, it may contain an additional set of reactivated vertices that heard the rumour in the past. We define this model inductively as follows:

	$\displaystyle\mathcal{A}^{\text{R},I}_{0}$	$\displaystyle:=\mathcal{\tilde{A}}^{\text{R},I}_{0}=I\cap\mathbb{Z}\text{ and }$
	$\displaystyle\mathcal{\tilde{A}}^{\text{R},I}_{1}$	$\displaystyle:=\{u\in\mathbb{Z}\setminus\mathcal{A}^{\text{R},I}_{0}:\|u-w\|\leqslant I^{0}_{w}\text{ for some }w\in\mathcal{\tilde{A}}^{\text{R},I}_{0}\}\cup\{u\in\mathcal{A}^{\text{R},I}_{0}:B^{1}_{u}=1\}.$
	$\displaystyle\mathcal{A}^{\text{R},I}_{1}$	$\displaystyle:=\mathcal{A}^{\text{R},I}_{0}\cup\mathcal{\tilde{A}}^{\text{R},I}_{1}.$

The set $\mathcal{A}^{\text{R},I}_{1}$ represents the rumour cluster at time $1$ , i.e., the set of vertices that have heard the rumour by time $1$ . We recall that for the conventional rumour percolation model, there is no reactivation, and we have $\mathcal{\tilde{A}}_{m}\cap\mathcal{\tilde{A}}_{n}=\emptyset$ for all $m,n\in\mathbb{Z}^{+}$ with $m\neq n$ . This no longer holds for the reactivation model. In fact, a vertex $u\in\mathcal{\tilde{A}}^{\text{R},I}_{0}$ belongs to $\mathcal{\tilde{A}}^{\text{R},I}_{1}$ as well iff we have $B^{1}_{u}=1$ . The set of vertices ready to spread the rumour at time $2$ is given by

	$\displaystyle\mathcal{\tilde{A}}^{\text{R},I}_{2}$	$\displaystyle:=\{u\in\mathbb{Z}\setminus\mathcal{A}^{\text{R},I}_{1}:\|u-w\|\leqslant I^{1}_{w}\text{ for some }w\in\mathcal{\tilde{A}}^{\text{R},I}_{1}\}\cup\{u\in\mathcal{A}^{\text{R},I}_{1}:B^{2}_{u}=1\}.$
	$\displaystyle\mathcal{A}^{\text{R},I}_{2}$	$\displaystyle:=\mathcal{A}^{\text{R},I}_{1}\cup\mathcal{\tilde{A}}^{\text{R},I}_{2}.$

The set $\mathcal{A}^{\text{R},I}_{2}$ represents the rumour cluster at time $2$ , i.e., the set of vertices that have heard the rumour by time $2$ . More generally, for $n\geqslant 2$ given $(\mathcal{A}^{\text{R},I}_{n-1},\mathcal{\tilde{A}}^{\text{R},I}_{n-1})$ , we define the sets $\mathcal{\tilde{A}}^{\text{R},I}_{n}$ and $\mathcal{A}^{\text{R},I}_{n}$ respectively as:

	$\displaystyle\mathcal{\tilde{A}}^{\text{R},I}_{n}$	$\displaystyle:=\{u\in\mathbb{Z}\setminus\mathcal{A}^{\text{R},I}_{n-1}:\|u-w\|\leqslant I^{n-1}_{w}\text{ for some }w\in\mathcal{\tilde{A}}^{\text{R},I}_{n-1}\}\cup\{u\in\mathcal{A}^{\text{R},I}_{n-1}:B^{n}_{u}=1\}.$
	$\displaystyle\mathcal{A}^{\text{R},I}_{n}$	$\displaystyle:=\mathcal{A}^{\text{R},I}_{n-1}\cup\mathcal{\tilde{A}}^{\text{R},I}_{n}.$

$\mathcal{A}^{\text{R}}_{n}$ represents the random set of vertices that have heard the rumour by time $n$ and therefore, it represents the rumour cluster at time $n$ . It follows that for any vertex which heard the rumour in the past, the time gaps between successive reactivations follow i.i.d. geometric distributions with parameter $p_{2}$ , which represents the laziness parameter of the reactivation clock.

With a slight abuse of notations, for an interval $I$ of the form $I\cap\mathbb{Z}=\{u\}$ , we denote the corresponding rumour propagation process simply as $\{(\mathcal{A}^{\text{R},u}_{n},\mathcal{\tilde{A}}^{\text{R},u}_{n}):n\geq 0\}$ . In particular, for simplicity of notation the process $\{(\mathcal{A}^{\text{R},0}_{n},\mathcal{\tilde{A}}^{\text{R},0}_{n}):n\geq 0\}$ is simply denoted as $\{(\mathcal{A}^{\text{R}}_{n},\mathcal{\tilde{A}}^{\text{R}}_{n}):n\geq 0\}$ . It is not difficult to see that, similar to the earlier model, for any $u\in\mathbb{Z}$ and $n\geqslant 1$ , the random set $\mathcal{A}^{\text{R},u}_{n}$ is a.s. finite and of the form $[a,b]\cap\mathbb{Z}$ , for some $-\infty<a<b<\infty$ .

The rumour percolation event for this model is defined as in Definition 2.1. We observe that, unlike the earlier model, the event

\mathcal{A}^{\text{R}}_{n}=\mathcal{A}^{\text{R}}_{n+1}\text{ for some }n\geqslant 1,

no longer implies non-occurrence of percolation. In fact, even if the radius r.v. $I^{0}_{0}$ takes the value zero with positive probability, it is not hard to see that for all $p_{2}>0$ this reactivation model percolates. In this section we will assume that the i.i.d. family of radius of influence r.v.’s is such that the following two conditions are satisfied:

(a)

There exist $C_{0},C_{1}>0$ such that $P(I^{0}_{0}>n)\leq C_{0}e^{(-C_{1}n)}$ for all $n\geq 1$ and
(b)

$P(I^{0}_{0}=0)=p_{1}>0$ .

Let $l^{\text{R}}_{n}$ and $r^{\text{R}}_{n}$ denote the leftmost and rightmost vertex in the set $\mathcal{A}^{\text{R}}_{n}$ respectively. Under the above mentioned assumptions on the i.i.d. family $\{I^{n}_{z}:n\in\mathbb{Z}^{+},z\in\mathbb{Z}\}$ we show that almost surely the random quantity $r_{n}^{R}/n$ has a deterministic limit. We comment that one can proceed along the same line of arguments as in the previous section and under the assumption of existence of sufficient higher order moments of radius of influence r.v. Theorem 5.1 can be proved. However, in this article we chose to work with the exponentially decaying radii of influence r.v.’s.

Theorem 5.1.

There exists some deterministic constant $\mu^{\prime}>0$ such that almost surely we have

\lim_{n\to\infty}r_{n}^{R}/n=\mu^{\prime}.

The next section and the rest of the paper is dedicated to the proof of Theorem 4.1. Though the proof technique is the same, because of the re-activation the renewal construction requires non-trivial modification.

5.1 Renewal process for reactivation rumour process

We need to modify our renewal construction in Section 4.1 in a non-trivial manner such that it takes care of the re-activation mechanism. Recall that we have started with two independent collections $\{I^{n}_{z}:n\in\mathbb{Z}^{+},z\in\mathbb{Z}\}$ and $\{B^{n}_{z}:n\in\mathbb{Z}^{+},z\in\mathbb{Z}\}$ of i.i.d. random variables. Before proceeding further, we define an one-sided version of our rumour propagation model, which we will use in our renewal event construction.

For $u\in\mathbb{Z}$ we define an one-sided version of rumour propagation such that starting from $u$ the rumour propagates towards the right side of $u$ only, i.e., on the set $[u,\infty)\cap\mathbb{Z}$ . Set $\mathcal{A}^{R,+,u}_{0}=\mathcal{\tilde{A}}^{R,+,u}_{0}=\{u\}$ and define

	$\displaystyle\mathcal{\tilde{A}}^{R,+,u}_{1}$	$\displaystyle:=\{v\in\mathbb{Z}:v>u:\|v-u\|\leq I^{0}_{u}\}\cup\{v\in\mathcal{A}^{R,+,u}_{0}:B^{1}_{v}=1\}\text{ and }$
	$\displaystyle\mathcal{A}^{R,+,u}_{1}$	$\displaystyle:=\mathcal{A}^{R,+,u}_{0}\cup\mathcal{\tilde{A}}^{R,+,u}_{1}.$

Given $(\mathcal{A}^{R,+,u}_{n},\mathcal{\tilde{A}}^{R,+,u}_{n})$ we define

	$\displaystyle\mathcal{\tilde{A}}^{R,+,u}_{n+1}$	$\displaystyle:=\{v\in\mathbb{Z}:v>\max(\mathcal{A}^{R,+,u}_{n}):\|v-w\|\leq I^{n}_{w}\text{ for some }w\in\mathcal{\tilde{A}}^{R,+,u}_{n}\}\cup\{v\in\mathcal{A}^{R,+,u}_{n}:B^{n+1}_{v}=1\},$
	$\displaystyle\mathcal{A}^{R,+,u}_{n+1}$	$\displaystyle:=\mathcal{A}^{R,+,u}_{n}\cup\mathcal{\tilde{A}}^{R,+,u}_{n+1}.$

As earlier, the set $\mathcal{A}^{R,+,u}_{n+1}$ represents the set of vertices that have heard the rumour by time $n+1$ of this one-sided rumour propagation with re-activation model. On the other hand, the set $\mathcal{\tilde{A}}^{R,+,u}_{n+1}$ represents the set of vertices that are ready to spread the rumour at time $n+1$ . For any interval $I$ with $I\cap\mathbb{Z}\neq\emptyset$ , we define the processes $\{(\mathcal{A}^{R,+,I}_{n+1},\mathcal{\tilde{A}}^{R,+,I}_{n+1}):n\geq 1\}$ similarly.

We observe that for any two intervals $I_{1}$ and $I_{2}$ , the two independent families $\{I^{n}_{z}:n\in\mathbb{Z}^{+},z\in\mathbb{Z}\}$ and $\{B^{n}_{z}:n\in\mathbb{Z}^{+},z\in\mathbb{Z}\}$ allow us to couple together all the processes mentioned below:

		$\displaystyle\{(\mathcal{A}^{R,I_{1}}_{n},\mathcal{\tilde{A}}^{R,I_{1}}_{n}):n\geq 0\},\{(\mathcal{A}^{R,I_{2}}_{n},\mathcal{\tilde{A}}^{R,I_{2}}_{n}):n\geq 0\}\text{ and }$
		$\displaystyle\{(\mathcal{A}^{R,+,I_{1}}_{n},\mathcal{\tilde{A}}^{R,+,I_{1}}_{n}):n\geq 0\},\{(\mathcal{A}^{R,+,I_{2}}_{n},\mathcal{\tilde{A}}^{R,+,I_{2}}_{n}):n\geq 0\}.$		(5.1)

Next, for $u\in\mathbb{Z}$ we consider the two processes $\{(\mathcal{A}^{R,(-\infty,u)}_{n},\mathcal{\tilde{A}}^{R,(-\infty,u)}_{n}):n\geq 0\}$ and $\{(\mathcal{A}^{R,+,u}_{n},\mathcal{\tilde{A}}^{R,+,u}_{n}):n\geq 0\}$ coupled together. For $u\in\mathbb{Z}$ , the event ‘ $\text{Dom}(u)$ ’ means that propagation of the rumour towards the right side of $u$ starting from an initial set of active vertices $(-\infty,u)\cap\mathbb{Z}=(-\infty,u-1]\cap\mathbb{Z}$ remains dominated throughout by the one-sided rumour propagation process starting from a singleton active set $\{u\}$ . Mathematically, we define this event as

\displaystyle\text{Dom}(u):=\{\max(\mathcal{A}^{R,+,(-\infty,u)}_{n})\leq\max(\mathcal{A}^{R,+,u}_{n})\text{ for all }n\geq 1\}.

(5.2)

It is not difficult to observe that for every $n\geq 1$ we have $\mathcal{A}^{R,+,(-\infty,u)}_{n}=\mathcal{A}^{R,(-\infty,u)}_{n}$ a.s.

We are now ready to define our renewal steps for the process $\{(\mathcal{A}^{R}_{n},\mathcal{\tilde{A}}^{R}_{n}):n\geq 0\}$ . Given $(\mathcal{A}^{R}_{n},\mathcal{\tilde{A}}^{R}_{n})$ we say that the renewal event occurs at the $n$ -th step if the event $\text{Dom}(r^{R}_{n})\equiv\text{Dom}(\max(\mathcal{A}^{R}_{n}))$ occurs. The sequence of successive renewal steps is defined below:

Set $\tau^{R}_{0}=-1$ . For $j\geq 1$ , the $j$ -th renewal step for this rumour propagation with reactivation is defined as

\displaystyle\tau^{R}_{j}

\displaystyle:=\inf\{n\in\mathbb{Z}^{+},n>\tau^{R}_{j-1}:\text{Dom}(r^{R}_{n})\text{ occurs}\}.

(5.3)

We need to show that the above definition makes sense in the sense that for any $j\geqslant 1$ , the r.v. $\tau^{R}_{j}$ is a.s. finite. This is done in Proposition 5.1. We define two filtrations $\{{\cal F}^{R}_{n}:n\geq 0\}$ and $\{{\cal G}^{R}_{n}:n\geq 0\}$ such that ${\cal F}^{R}_{0}={\cal G}^{R}_{0}=\emptyset$ and for $n\geq 1$

	$\displaystyle{\cal F}^{R}_{n}$	$\displaystyle:=\sigma\bigl{(}(I^{m}_{z},B^{m+1}_{z}):z\in(-\infty,r^{R}_{n-1}]\cap\mathbb{Z},0\leq m\leq n-1\bigr{)}\text{ and }$
	$\displaystyle{\cal G}^{R}_{n}$	$\displaystyle:=\sigma\bigl{(}(I^{m}_{z},B^{m+1}_{z},\mathbf{1}_{\text{Dom}(r^{R}_{m})}):z\in(-\infty,r^{R}_{n-1}]\cap\mathbb{Z},0\leq m\leq n-1\bigr{)}.$		(5.4)

We observe that both the processes, $\{(\mathcal{A}^{R,(-\infty,0)}_{n},\mathcal{\tilde{A}}^{R,(-\infty,0)}_{n}):n\geq 0\}$ and $\{(\mathcal{\tilde{A}}^{R}_{n},\mathcal{\tilde{A}}^{R}_{n}):n\geq 0\}$ , are adapted to the filtration $\{{\cal F}^{R}_{n}:n\geq 0\}$ . Further, for any $j\geq 1$ the random step $\tau^{R}_{j}$ is a stopping time w.r.t. the filtration $\{{\cal G}^{R}_{n}:n\geq 0\}$ . This gives us another filtration $\{{\cal S}^{R}_{j}:={\cal G}^{R}_{\tau^{R}_{j}}:j\geq 0\}$ to work with such that the random variable $\tau^{R}_{j}$ is ${\cal S}^{R}_{j}$ measurable for all $j\geq 0$ .

Proposition 5.1.

There exist $C_{0},C_{1}>0$ which do not depend on $j$ such that for any $j\geqslant 0$ we have

P(\tau^{R}_{j+1}-\tau^{R}_{j}>n\mid{\cal S}^{R}_{j})\leqslant C_{0}e^{(-C_{1}n)}\text{ for all }n\in\mathbb{N}.

We first prove Proposition 5.1 for $j=0$ and we will it prove for general $j>0$ later. In order to do that, we need the following lemma which proves that given ${\cal F}^{R}_{n}$ , the probability that the $n$ -th step is a renewal step or a $\tau^{R}$ step has a strictly positive uniform lower bound.

Lemma 5.1.

For any $n\geq 0$ there exists $\tilde{p}>0$ not depending on $n$ such that

P(n-\text{th step is a renewal step}\mid{\cal F}^{R}_{n})=P(\text{Dom}(r^{R}_{n})\mid{\cal F}^{R}_{n})\geq\tilde{p}.

To prove Lemma 5.1 we need the following corollary involving a family of random variables with uniformly bounded $2+\epsilon$ moments for some $\epsilon>0$ .

Corollary 5.1.

Consider a family of i.i.d. random variables $\{Y_{n}:n\in\mathbb{N}\}$ with finite $2+\epsilon$ moment for some $\epsilon>0$ . In addition, we assume that $P(Y_{1}=0)>0$ . Then for any $\gamma>0$ , we have

P(Y_{n}\leq n\gamma\text{ for all }n\geq 1)>0.

Proof.

We have assumed that $\mathbb{E}(Y_{1})^{2+\epsilon}=M<\infty$ . Define the event

A_{n}:=\{Y_{n+j}>(n+j)\gamma\text{ for some }j\geq 1\}

and we obtain

$\displaystyle P(A_{n})=$	$\displaystyle P(\cup_{j=1}^{\infty}(Y_{n+j}>(n+j)\gamma))$
$\displaystyle\leq$	$\displaystyle\sum_{j=1}^{\infty}P(Y_{n+j}>(n+j)\gamma)$
$\displaystyle\leq$	$\displaystyle\sum_{j=1}^{\infty}\mathbb{E}(Y_{n+j})^{2+\epsilon}/((n+j)\gamma)^{2+\epsilon}$
$\displaystyle\leq$	$\displaystyle\sum_{j=1}^{\infty}\mathbb{E}(Y_{n+j})^{2+\epsilon}/((n+j)\gamma)^{2+\epsilon}$
$\displaystyle=$	$\displaystyle M\gamma^{-(2+\epsilon)}\sum_{j=1}^{\infty}1/(n+j)^{(2+\epsilon)}.$	(5.5)

We define $N:=\sup\{n\geq 1:A_{n}\text{ occurs}\}$ , i.e., the last time the event $A_{n}$ has occurred. Equation (5.1) gives us

\sum_{n=1}^{\infty}P(A_{n})\leq M\sum_{n=1}^{\infty}\sum_{j=1}^{\infty}1/((n+j)\gamma)^{2+\epsilon}=M\sum_{m=1}^{\infty}(m-1)/(m\gamma)^{2+\epsilon}<\infty,

implying that the r.v. $N$ is finite a.s. Choose $K\in\mathbb{N}$ such that $P(N\leq K)\geq 1/2$ . On the other hand, we obtain

P(\cap_{n=1}^{K}(Y_{n}\leq n\gamma))\geq P(\cap_{n=1}^{K}(Y_{n}=0))=P(Y_{1}=0)^{K}>0,

by our assumption. Further, the event $\{N\leq K\}$ depends only on the collection $\{Y_{K+1},Y_{K+2},\cdots\}$ and therefore, independent of the event $\cap_{n=1}^{K}(Y_{n}\leq n\gamma)$ . Finally, our proof follows from the event inclusion relation given below:

\{Y_{n}\leq n\gamma\text{ for all }n\}\supseteq(\cap_{n=1}^{K}(Y_{n}=0))\cap(N\leq K).

This completes the proof. ∎

It is important to observe that in Corollary 5.1 we don’t require $\{Y_{n}:n\in\mathbb{N}\}$ to be an i.i.d. collection. We are ready to prove Lemma 5.1 now.

Proof of Lemma 5.1:.

We prove Lemma 5.1 for $n=0$ . For general $n\geq 0$ the argument is exactly the same. We couple a positive drift random walk with the evolution of the rightmost vertex of the rumour cluster as follows. Set $X_{0}=0$ and for $n\geq 1$ let

\displaystyle X_{n}:=\begin{cases}X_{n-1}+1&\text{ if }B^{n}_{r^{R}_{n-1}}=1,I^{n}_{r^{R}_{n-1}}\geq 1\\ X_{n-1}&\text{ otherwise}.\end{cases}

By construction $\{X_{n}:n\geq 0\}$ is a positive drift random walk with i.i.d. increments such that we have $\lim_{n\to\infty}X_{n}/n=\theta$ almost surely where

\displaystyle\theta=P(B^{0}_{0}=1,I^{0}_{0}\geq 1)>0.

(5.6)

Therefore, there exists $\eta_{1}>0$ such that

P(X_{n}\geq\frac{3}{4}n\theta\text{ for all }n\in\mathbb{Z}^{+})=\eta_{1}.

Our construction ensures that $X_{n}\leq r_{n}^{R}$ for all $n\geq 0$ a.s.

Next, we consider the sequence of ‘right’ overshoot random variables given by $\{O^{(-\infty,-1],+}_{n}:n\in\mathbb{Z}^{+}\}$ , where $O^{(-\infty,-1],+}_{n}$ represents the amount of overshoot towards on $\mathbb{Z}^{+}$ due to the family $\{I_{z}^{n}:z\in(-\infty,-1]\cap\mathbb{Z}\}$ . The translation invariance nature of our model ensures that the collection $\{O^{(-\infty,-1],+}_{n}:n\in\mathbb{Z}^{+}\}$ gives a sequence of i.i.d. copies of the overshoot r.v. $O$ , where $O$ is defined as in eq. 3.2. Define the event $E$ as

E:=\{O_{n}^{(-\infty,-1],+}\leq\frac{1}{4}n\theta\text{ for all }n\in\mathbb{Z}^{+}\}.

Lemma 3.1 together with Corollary 5.1 ensure that $P(E)\geq\eta_{2}$ for some $\eta_{2}>0$ .

The occurrence of the event $\{X_{n}\geq\frac{3}{4}n\theta\text{ for all }n\in\mathbb{Z}^{+}\}\cap E$ implies the occurrence of the renewal step at the very first step. Further, these two events are supported on disjoint sets of random variables and they are therefore independent. This gives us

P(0-\text{th step is a renewal step }\mid{\cal F}^{R}_{0})\geq\eta_{1}\eta_{2}>0,

and completes the proof. ∎

Additionally to prove 5.1 we need [25, Corollary 2.7], which is a general result giving a sufficient condition for exponential tail decay of a random sum of random variables which need not be i.i.d. We will use this condition repeatedly in this section. For completeness, we mentioned the details below. We start with a notion of ‘uniform exponential decay’ and ‘strong exponential decay’ for a family of r.v.’s.

Definition 5.1.

We say that a family of r.v.’s $\{X_{i}:i\geqslant 1\}$ has uniform exponential tail decay if uniformly for all $i\geqslant 1$ there exist constants $C_{0},C_{1}>0$ such that

\displaystyle P\bigl{(}|X_{i}|>n)\bigr{)}\leqslant C_{0}e^{(-C_{1}n)}\text{ for all }n\in\mathbb{N},

(5.7)

where $C_{0},C_{1}$ do not depend on $i$ .

We say that a family of r.v.’s $\{X_{i}:i\geqslant 1\}$ has strong exponential tail decay if uniformly for all $i\geqslant 1$ there exist constants $C_{0},C_{1}>0$ such that

\displaystyle P\bigl{(}X_{i}>n\mid(X_{i-1},\cdots,X_{1})\bigr{)}\leqslant C_{0}e^{(-C_{1}n)}\text{ for all }n\in\mathbb{N}.

(5.8)

Lemma 5.2.

Consider a family of r.v.’s $\{X_{i}:i\geqslant 1\}$ with strong exponential tail decay and a positive integer-valued r.v. $Y$ with an exponentially decaying tail. Then there exist $C_{0},C_{1}>0$ such that for all $n\in\mathbb{N}$ we have

P(\sum_{i=1}^{Y}|X_{i}|>n)\leqslant C_{0}e^{-C_{1}n}.

For a proof of Lemma 5.2 we refer the reader to Corollary 2.7 of [25]. It is important to observe that Lemma 5.2 does not assume independence between the r.v. $\sigma$ and the family $\{X_{n}:n\in\mathbb{N}\}$ too. Now we use Lemma 5.1, Lemma 5.2 and proceed to prove 5.1 for $j=0$ .

Proof of Proposition 5.1 for $j=0$ :.

It is important to observe that the occurrence of a renewal event affects the distribution of radius of influence r.v.’s and Bernoulli activation r.v.’s till the infinite future. Therefore, the argument is much more involved here than that of Proposition 4.1. We first check for the occurrence of the renewal event at the very first step and Lemma 5.1 ensures that we have a strictly positive uniform lower bound for probability of the occurrence of the renewal event. But given the renewal step has not occurred at the first step gives us certain information about the future evolution of the process and prohibits us to apply the same bound (for probability of occurrence of renewal event) at the next step. We need to wait for some random amount of time to take care of this information.

For $u\in\mathbb{Z}$ we define the random variable $\beta^{R}(u)$ as

\displaystyle\beta^{R}(u):=\inf\{n\geq 1:\max(\mathcal{A}^{R,(-\infty,u)}_{n})>\max(\mathcal{A}^{R,+,u}_{n})\}.

(5.9)

We observe that $\max\left(\mathcal{A}^{R,(-\infty,u)}_{n}\right)=\max\left(\mathcal{A}^{R,(-\infty,u-1]}_{n}\right)$ for all $n$ a.s. and the r.v. $\beta^{R}(u)$ can take the value infinity with positive probability. For the rumour propagation process $\{(\mathcal{A}^{R}_{n},\mathcal{\tilde{A}}^{R}_{n}):n\geq 0\}$ starting from the origin, we consider the r.v. $\beta^{R}_{1}=\beta^{R}(0)$ and observe that the event $\{\beta^{R}_{1}=\infty\}$ is exactly same as the event that the $0$ -th step is a renewal step. Given the event that renewal has not occurred at the $0$ -th step, which is same as the event $\{\beta^{R}_{1}<\infty\}$ , we have some information till the next $\beta^{R}_{1}$ many steps and we can again test for the occurrence of the renewal event post that. On the event $\{\beta^{R}_{1}<\infty\}$ we run the rumour propagation process for the next $\beta^{R}_{1}+1$ many steps and thereafter we consider the r.v. $\beta^{R}_{2}:=\beta^{R}(r^{R}_{\beta^{R}_{1}+1})$ and so on. It suffices to show that the family $\{\beta^{R}_{k}:k\geq 1\}$ exhibits a strong exponential tail decay type behaviour as defined in Definition 5.1. We prove it for $k=1$ and for general $k\geq 1$ the argument is the same.

For showing the exponential tail for $P(n<\beta^{R}_{1}<\infty)$ , we write it as,

\displaystyle P(n<\beta^{R}_{1}<\infty)\leq\sum_{l=1}^{\infty}P(\beta^{R}_{1}=n+l,r_{n+l}^{R}\geq\frac{3}{4}(n+l)\theta)+\sum_{l=1}^{\infty}P(r_{n+l}^{R}<\frac{3}{4}(n+l)\theta),

(5.10)

where $\theta$ is as in eq. 5.6. The second term in eq. 5.10 will be dealt with later using a concentration bound. We now consider the first term in eq. 5.10. We observe that on the event

\{r_{n+l}^{R}\geq\frac{3}{4}(n+l)\theta,\beta^{R}_{1}=n+l\}

we must have

	$\displaystyle\max(\mathcal{A}^{R,(-\infty,-1]}_{m})\leq\max(\mathcal{A}^{R,+,0}_{m})\text{ for all }0\leq m\leq n+l-1\text{ as well as }$
	$\displaystyle\max(\mathcal{A}^{R,(-\infty,-1]}_{n+l})>\max(\mathcal{A}^{R,+,0}_{n+l})\geq\frac{3}{4}(n+l)\theta.$

In order to have $\max(\mathcal{A}^{R,(-\infty,-1]}_{n+l})>\frac{3}{4}(n+l)\theta$ , there must exist a random variable $I^{n+l}_{z}$ for some $z\in(-\infty,-1]\cap\mathbb{Z}$ with

I^{n+l}_{z}+z>\frac{3}{4}(n+l)\theta.

This implies that the first term inside the sum in the r.h.s of (5.10), viz., $P(\beta^{R}_{1}=n+l,r_{n+l}^{R}\geq\frac{3}{4}(n+l)\theta)$ for every $l\geq 1$ is bounded by $P(O^{(-\infty,-1],+}_{n+l}>\frac{3}{4}(n+l)\theta)$ . Hence, we have

\displaystyle\sum_{l=1}^{\infty}P(\beta^{R}_{1}=n+l,r_{n+l}^{R}\geq\frac{3}{4}(n+l)\theta)\leqslant\sum_{l=1}^{\infty}P(O^{(-\infty,-1],+}_{n+l}>\frac{3}{4}(n+l)\theta)\leqslant\tilde{C}^{\prime}_{0}e^{-\tilde{C}^{\prime}_{1}n},

(5.11)

for some $\tilde{C}^{\prime}_{0},\tilde{C}^{\prime}_{1}>0$ . The last inequality eq. 5.11 follows from Lemma 3.1.

We now consider the second term in eq. 5.10. Recall that $\lim_{n\to\infty}X_{n}/n=\theta$ almost surely. From [14, eq. (7)], and the fact that $X_{n}\leq r^{R}_{n}$ almost surely for all $n\geq 0$ , we have

\displaystyle P(r_{n+l}^{R}<\frac{3}{4}(n+l)\theta)\leqslant P(X_{n+l}<\frac{3}{4}(n+l)\theta)\leqslant B^{\prime}_{0}e^{-B^{\prime}_{1}(n+l)},

(5.12)

for some $B^{\prime}_{0},B^{\prime}_{1}>0$ . Plugging eq. 5.11 and eq. 5.12 into eq. 5.10 and taking the sum in the second term, we get

\displaystyle P(n<\beta^{R}_{1}<\infty)\leq C^{\prime}_{0}e^{-C^{\prime}_{1}n},

for some $C^{\prime}_{0},C^{\prime}_{1}>0$ . A similar argument shows that the probability $P(n<\beta^{R}_{j}<\infty\mid\beta^{R}_{j-1},\cdots,\beta^{R}_{1})$ decays exponentially with uniform decay constants. This ensures that the family $\{\beta_{k}:k\geq 1\}$ exhibits a strong exponential tail decay. The total number of steps required for the occurrence of the first renewal event is dominated by geometric sum of $\beta^{R}_{j}$ ’s with success probability $\tilde{p}$ where $\tilde{p}$ is as in Lemma 5.1. Therefore, Corollary 3.1 completes the proof for $j=0$ . ∎

We will prove 5.1 for general $j\geq 1$ through a sequence of lemmas. We need to be more careful as given that a renewal step has occurred affects distribution of radius of influence r.v.’s and Bernoulli activation r.v.s till the infinite future. To deal with that for $u\in\mathbb{Z}$ and $n\geq 1$ we define a truncated version of the domination event as follows:

\displaystyle\text{Dom}^{(n)}(u)

\displaystyle:=\{\max(\mathcal{A}^{R,(-\infty,u)}_{m})\leq\max(\mathcal{A}^{R^{+},u}_{m})\text{ for all }1\leq m\leq n\},

(5.13)

which means that domination of the rumour propagation continues till the next $n$ steps only. Next lemma allows us to decouple a renewal event as joint occurrence of two independent events.

Lemma 5.3.

For any $w\in\mathbb{N}$ we have the following equality of events:

\displaystyle\{\tau^{R}_{1}=l,r^{R}_{l}=w\}

\displaystyle=\Bigl{[}\{r^{R}_{l}=w\}\cap\bigl{[}\cap_{j=0}^{l-1}\bigl{(}\{\beta^{R}(r^{R}_{j})\leq l-j\}\bigr{)}\bigr{]}\Bigr{]}\bigcap(\text{Dom}(w)),

(5.14)

where the two events on the r.h.s. are independent of each other.

Proof.

By definition of the step $\tau_{1}$ , we have

	$\displaystyle\{\tau^{R}_{1}=l,r^{R}_{l}=w\}=$	$\displaystyle\{r^{R}_{l}=w,\text{Dom}(w)\}\bigcap\bigl{[}\cap_{j=0}^{l-1}(\text{renewal does not occur at }r^{R}_{j})\bigr{]}$
	$\displaystyle=$	$\displaystyle\{r^{R}_{l}=w,\text{Dom}(w)\}\bigcap\bigl{[}\cap_{j=0}^{l-1}(\beta^{R}(r^{R}_{j})<\infty)\bigr{]}.$

In order to complete the proof, for any $0\leq j\leq l-1$ we need to show that

\displaystyle\{r^{R}_{l}=w,\text{Dom}(w),\beta^{R}(r^{R}_{j})<\infty\}=\{r^{R}_{l}=w,\text{Dom}(w),\beta^{R}(r^{R}_{j})\leq l-j\}.

(5.15)

We prove it for $j=0$ and the argument is exactly the same for general $j\geq 1$ . On the event

\{r^{R}_{l}=w,\text{Dom}(w),\beta^{R}(r^{R}_{0})=\beta(0)>l\},

the truncated event $\text{Dom}^{l}(0)$ must have occurred. Otherwise, $\beta^{R}(0)$ must be smaller than $l$ . Further, the event $\text{Dom}(r^{R}_{l})\cap\text{Dom}^{l}(0)$ implies the occurrence of the event $\text{Dom}(0)$ . Hence, on the event $\{r^{R}_{l}=w,\text{Dom}(w),\beta^{R}(0)>l\}$ , the r.v. $\beta^{R}(0)$ must take the value $+\infty$ . This implies that $\{r^{R}_{l}=w,\text{Dom}(w),l<\beta^{R}(0)<+\infty\}=\emptyset$ and completes the proof of eq. 5.15 for $j=0$ . Finally, we observe that the two events in the r.h.s. of eq. 5.14 depend on disjoint sets of r.v.s as the event

\{r^{R}_{l}=w\}\cap\bigl{[}\cap_{j=0}^{l-1}\bigl{(}\{\beta^{R}(r^{R}_{j})\leq l-j\}\bigr{)}\bigr{]}

is ${\cal F}^{R}_{l}$ measurable where ${\cal F}^{R}_{l}$ is defined as in section 5.1. Therefore, they are independent and this completes the proof. ∎

We would like to have a similar result for the $\tau_{j}$ -th step for $j\geq 2$ . For $m_{1},m_{2}\in\mathbb{N}$ with $m_{1}<m_{2}$ we consider the event

\{\tau^{R}_{1}=m_{1},r^{R}_{m_{1}}=w_{1},\tau^{R}_{2}=m_{2},r^{R}_{m_{2}}=w_{2}\}.

The main difficulty is that, both the events $\text{Dom}(w_{1})$ and $\text{Dom}(w_{2})$ depend on the infinite future. To deal with this, we observe the following equality of events

\displaystyle\{r^{R}_{m_{1}}=w_{1},\text{Dom}(w_{1}),r^{R}_{m_{2}}=w_{2},\text{Dom}(w_{2})\}

\displaystyle=\{r^{R}_{m_{1}}=w_{1},\text{Dom}^{(m_{2}-m_{1})}(w_{1}),r^{R}_{m_{2}}=w_{2},\text{Dom}(w_{2})\}.

Using the above decomposition, the same argument as in Lemma 5.3 allows us to express the event $\{\tau^{R}_{1}=m_{1},\tau^{R}_{2}=j_{2},r^{R}_{m_{1}}=w_{1},r^{R}_{m_{2}}=w_{2}\}$ as

		$\displaystyle\Bigl{[}\{r^{R}_{j}\text{ is not a }\tau^{R}\text{ step for all }1\leq j<m_{1},r_{m_{1}}=w_{1},\text{Dom}^{(m_{2}-m_{1})}(w_{1})\}\cap$
		$\displaystyle\qquad\{r^{R}_{j}\text{ is not a }\tau^{R}\text{ step for any }m_{1}<j<m_{2},r^{R}_{m_{2}}=w_{2}\}\Bigr{]}\bigcap\text{Dom}(w_{2}).$		(5.16)

As observed earlier, other than the event $\text{Dom}(w_{2})$ in section 5.1, rest of the events are ${\cal F}^{R}_{m_{2}}$ measurable. In fact, section 5.1 can be further strengthened for any $j\geq 1$ as described in the following corollary.

Corollary 5.2.

For any $j\geq 1$ we obtain the following equality of events

		$\displaystyle\bigcap_{l=1}^{j}\{\tau^{R}_{l}=m_{l},r^{R}_{m_{l}}=w_{l}\}=$
		$\displaystyle\qquad\Bigl{[}\bigcap_{l=1}^{j}\{r^{R}_{m_{l}}=w_{l}\}\cap\bigl{\{}\cap_{n=m_{l-1}+1}^{m_{l}-1}(\beta^{R}(r^{R}_{n})\leq m_{l}-n)\bigr{\}}\bigcap(\cap_{l=1}^{j-1}\text{Dom}^{(m_{(l+1)}-m_{l})}(w_{l}))\Bigr{]}\bigcap\text{Dom}(w_{j}),$		(5.17)

and other than the event $\text{Dom}(w_{j})$ , rest of the other events in the r.h.s. of corollary 5.2 are ${\cal F}^{R}_{m_{l}}$ measurable.

The argument is same as that of Lemma 5.3 and therefore, we skip the details. For simplicity of notation, we denote the ${\cal F}^{R}_{m_{l}}$ measurable part of the event in the r.h.s. of corollary 5.2 as

E(w_{1},m_{1},\cdots,w_{j},m_{j}):=\Bigl{[}\bigcap_{l=1}^{j}\{r^{R}_{m_{l}}=w_{l}\}\cap\bigl{\{}\cap_{n=m_{l-1}+1}^{m_{l}-1}(\beta^{R}(r_{n})\leq m_{l}-n)\bigr{\}}\bigcap(\cap_{l=1}^{j-1}\text{Dom}^{(m_{l+1}-m_{l})}(w_{l}))\Bigr{]}.

It is also important to observe that the event $\text{Dom}(w_{j})$ is actually independent of the event $E(w_{1},m_{1},\cdots,w_{j},m_{j})$ . We need one more lemma before we proceed to prove 5.1 for $j\geq 1$ .

Lemma 5.4.

Fix any $j\geq 1$ . Given $(r^{R}_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau^{R}_{j}},\tau_{j}^{R})=(w_{1},m_{1},\cdots,w_{j},m_{j})$ , for any $l\geq 1$ and $z\in\mathbb{Z}$ there exist $C_{0},C_{1}>0$ , which do not depend on $j,l,z$ such that

\displaystyle P\bigl{(}I^{\tau_{j}+l}_{z}>n\mid(r^{R}_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau^{R}_{j}},\tau^{R}_{j})=(w_{1},m_{1},\cdots,w_{j},m_{j})\bigr{)}\leq C_{0}e^{(-C_{1}n)}.

Proof.

Using the event equality in (5.2), and from conditional probability we obtain

		$\displaystyle P\bigl{(}I^{\tau^{R}_{j}+l}_{z}>n\mid(r_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau^{R}_{j}},\tau^{R}_{j})=(w_{1},m_{1},\cdots,w_{j},m_{j})\bigr{)}$
		$\displaystyle=P\bigl{(}I^{\tau^{R}_{j}+l}_{z}>n\cap E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}(w_{j})\bigr{)}/P(E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}(w_{j})).$		(5.18)

The event $(I^{\tau^{R}_{j}+l}_{z}>n)\cap\text{Dom}(w_{j})$ is independent of the event $E(w_{1},m_{1},\cdots,w_{j},m_{j})$ . Earlier we observed that the event $\text{Dom}(w_{j})$ is independent of the event $E(w_{1},m_{1},\cdots,w_{j},m_{j})$ as well. Hence, section 5.1 reduces to

		$\displaystyle P\bigl{(}I^{\tau_{j}+l}_{z}>n\mid(r^{R}_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau^{R}_{j}},\tau^{R}_{j})=(w_{1},m_{1},\cdots,w_{j},m_{j})\bigr{)}$
	$\displaystyle=$	$\displaystyle P\bigl{(}(I^{\tau^{R}_{j}+l}_{z}>n)\cap\text{Dom}(w_{j})\bigr{)}/P(\text{Dom}(w_{j}))$
	$\displaystyle\leqslant$	$\displaystyle P\bigl{(}I^{\tau^{R}_{j}+l}_{z}>n\bigr{)}P(\text{Dom}(0))^{-1}$
	$\displaystyle\leq$	$\displaystyle C_{0}e^{(-C_{1}n)},$

for some $C_{0},C_{1}>0$ . The penultimate inequality uses the translation invariant nature of our model. ∎

Now we are ready to prove 5.1 for $j\geq 1$ .

Proof of 5.1 for $j\geq 1$ .

We begin our proof by first fixing $j\geq 1$ . Then, given the value of

(r^{R}_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau^{R}_{j}},\tau^{R}_{j})=(w_{1},m_{1},\cdots,w_{j},m_{j}),

for any $l\geq 1$ we can write the conditional probability as:

		$\displaystyle P\bigl{(}\text{Dom}(r^{R}_{\tau^{R}_{j}+l})\mid(r^{R}_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau^{R}_{j}},\tau^{R}_{j})=(w_{1},m_{1},\cdots,w_{j},m_{j})\bigr{)}$
	$\displaystyle=$	$\displaystyle P\bigl{(}\text{Dom}(r^{R}_{m_{j}+l})\cap(E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}(w_{j}))\bigr{)}/P(E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}(w_{j})).$		(5.19)

From Corollary 5.2, the RHS of section 5.1 is equal to:

\displaystyle P\bigl{(}\text{Dom}(r^{R}_{m_{j}+l})\cap(E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}^{(l)}(w_{j}))\bigr{)}/P(E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}(w_{j})).

(5.20)

Further, as commented earlier, occurrence of the event $\text{Dom}(r^{R}_{m_{j}+l})$ depends on the collection $\{(I^{n}_{w},B^{n}_{w}):w\in\mathbb{Z},n\geq m_{j}+l\}$ and it is independent of every ${\cal F}^{R}_{m_{j}+l}$ measurable event. Therefore, we can simplify the expression in (5.20) as,

\displaystyle P(\text{Dom}(r^{R}_{m_{j}+l}))\Bigl{(}P\bigl{(}E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}^{(l)}(w_{j})\bigr{)}/P(E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}(w_{j}))\Bigr{)}.

(5.21)

From the definition of a renewal step it follows that rumour propagation through vertices in the set $(-\infty,r^{R}_{\tau^{R}_{j}})\cap\mathbb{Z}$ has to be dominated and therefore, the translation invariance nature of our model ensures that $P(\text{Dom}(r^{R}_{m_{j}+l}))$ in (5.21) is at least as large as $P(\text{Dom}(0))$ . On using the fact that

\bigl{(}E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}(w_{j})\bigr{)}\subset\bigl{(}E(w_{1},m_{1},\cdots,w_{j},m_{j})\cap\text{Dom}^{(l)}(w_{j})\bigr{)},

the expression in (5.21) is lower bounded by $P(\text{Dom}(0))$ .

This shows that given $(r^{R}_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau^{R}_{j}},\tau^{R}_{j})=(w_{1},m_{1},\cdots,w_{j},m_{j})$ , for any $l\geq 1$ the probability of the event $\text{Dom}(r^{R}_{\tau^{R}_{j}+l})$ has a strictly positive uniform lower bound.

The same argument of 5.1 for $j=0$ together with Corollary 5.1 give us that, given $(r^{R}_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau^{R}_{j}},\tau^{R}_{j})=(w_{1},m_{1},\cdots,w_{j},m_{j})$ , it suffices to show that the collection $\{O^{(-\infty,r^{R}_{\tau^{R}_{j}+l}-1],+}_{\tau^{R}_{j}+l+n}:l\geq 1\}$ forms an uniform exponentially decaying family in the sense of Definition 5.1.

We recall that for each $n\geq 1$ part (iii) of Lemma 3.1 holds as long as the collection $\{I_{z}^{n}:z\in\mathbb{Z}\}$ forms an uniform exponentially decaying family. In the present set up, Lemma 5.4 ensures that given $(r^{R}_{\tau^{R}_{1}},\tau^{R}_{1},\cdots,r^{R}_{\tau_{j}},\tau^{R}_{j})=(w_{1},m_{1},\cdots,w_{j},m_{j})$ for any $n\in\mathbb{N}$ , the family $\{I^{\tau^{R}_{j}+n}_{z}:z\in\mathbb{Z}\}$ forms an uniform exponentially decaying family. As a result, for each $l\geq 1$ the overshoot r.v. $O^{(-\infty,r^{R}_{\tau^{R}_{j}+l}),+}_{\tau^{R}_{j}+l+n}$ has exponentially decaying tail such that decay constants do not depend on $l$ . This completes the proof. ∎

Next, we show that increments of the rightmost process observed between successive renewals form a strong uniform exponentially decaying family. Together with the translation invariance nature of our model, Corollary 5.1 and Lemma 5.4 give us the following remark.

Remark 5.1.

(i)

For any $z\in\mathbb{Z}$ and for any $m\in\mathbb{N}$ we consider the conditional overshoot r.v. $O^{(-\infty,z],+}_{m}\mid\text{Dom}(0)$ and it is not difficult to see that there exist positive constants $C_{0},C_{1}$ not depending on $z,m$ such that we have

P\bigl{(}O^{(-\infty,z],+}_{m}>n\mid\text{Dom}(0)\bigr{)}\leq C_{0}e^{(-C_{1}n)}\text{ for all }n.

This follows from the observation that

\displaystyle P\bigl{(}O^{(-\infty,z],+}_{m}>n\mid\text{Dom}(0)\bigr{)}\leq P(O^{(-\infty,z],+}_{m}>n)/P(\text{Dom}(0))=P(O^{(-\infty,0],+}>n)/P(\text{Dom}(0)),

where the last equality follows from the translation invariance nature of our model.

(ii)

Repeated applications of the above argument gives us that, given that the event $\text{Dom}(0)$ has occurred, for any $\mathbb{Z}$ -valued sequence $\{z_{n}:n\in\mathbb{N}\}$ the collection $\{O^{(-\infty,z_{n}],+}_{n}\mid:n\geq 1\}$ forms an uniform exponentially decaying family. In fact, the same argument actually gives us that $\{O^{(-\infty,z_{n}],+}_{n}:n\geq 1\}$ forms a strong exponentially decaying family.

Lemma 5.5.

There exist $C_{0},C_{1}>0$ which do not depend on $j\geq 0$ such that for any $j\geqslant 0$ we have

P(r^{R}_{\tau^{R}_{j+1}}-r^{R}_{\tau^{R}_{j}}>n\mid{\cal S}^{R}_{j})\leqslant C_{0}e^{(-C_{1}n)}\text{ for all }n\in\mathbb{N}.

Proof.

We have used similar arguments in this paper. Therefore, we only provide a sketch here. We observe that

\displaystyle(r^{R}_{\tau^{R}_{j+1}}-r^{R}_{\tau^{R}_{j}})=\sum_{m=1}^{\tau^{R}_{j+1}-\tau^{R}_{j}}(r^{R}_{\tau^{R}_{j}+m}-r^{R}_{\tau^{R}_{j}+m-1}).

(5.22)

Note that given ${\cal S}^{R}_{j}$ , the increment r.v. $(r^{R}_{\tau^{R}_{j}+m}-r^{R}_{\tau^{R}_{j}+m-1})$ is stochastically dominated by the overshoot r.v. $O^{(-\infty,r^{R}_{\tau^{R}_{j}+m-1}],+}_{\tau^{R}_{j}+m}$ . Because of Remark 5.1, 5.1 together with Corollary 3.1 give us that the random sum in (5.22) decays exponentially and this completes the proof. ∎

Proposition 5.2.

$\{(r^{R}_{\tau^{R}_{j+1}}-r^{R}_{\tau^{R}_{j}},\tau^{R}_{j+1}-\tau^{R}_{j}):j\geqslant 1\}$ gives a collection of i.i.d. random vectors taking values in $\mathbb{N}\times\mathbb{N}$ whose distribution does not depend on the starting point of the rumour propagation process.

Proof.

Unlike the proof of 4.2, we need to be careful to argue about the independence of increment vectors between successive renewals as given that the renewal event has occurred affects the distribution of the rumour propagation process till infinite time. We first argue that the increment random vectors are identically distributed and present a brief description of the identical distribution.

The one-sided rumour propagation process on $\mathbb{Z}^{+}$ starting from the origin is denoted by

\{(\mathcal{A}^{R,+,0}_{n},\mathcal{\tilde{A}}^{R,+,0}_{n}):n\geq 0\}.

Given that the event $\text{Dom}(0)$ has occurred, we consider the evolution of the conditional process

\{(\mathcal{A}^{R,+,0}_{n},\mathcal{\tilde{A}}^{R,+,0}_{n}):n\geq 0\}\mid\text{Dom}(0)

till the time that the event $\text{Dom}(r^{R,+,0}_{n})$ occurs. Let $\nu$ denote the first time that the event $\text{Dom}(r^{R,+,0}_{n})$ has occurred. The definition of our renewal event ensures that

(\tau^{R}_{j+1}-\tau^{R}_{j},r^{R}_{\tau^{R}_{j+1}}-r^{R}_{\tau^{R}_{j}})\stackrel{{\scriptstyle d}}{{=}}(\nu,\max(\mathcal{A}^{R,+,0}_{\nu}))\text{ for all }j\geqslant 1.

Next, we use the fact that the increment random vectors between successive renewals are identically distributed to show that the increments are independently distributed as well. Recall that the random vector $(\tau^{R}_{j},r^{R}_{\tau^{R}_{j}})$ is ${\cal S}^{R}_{j}$ measurable where ${\cal S}^{R}_{j}$ is defined as in section 5.1. Fix $m\geq 1$ and Borel subsets $B_{2},\dotsc,B_{m+1}$ of $\mathbb{N}\times\mathbb{N}$ . Let $I_{j+1}(B_{j+1})$ be the indicator random variable of the event

(\tau^{R}_{j+1}-\tau^{R}_{j},r^{R}_{\tau^{R}_{j+1}}-r^{R}_{\tau^{R}_{j}})\in B_{j+1}.

Then, we have

	$\displaystyle P\bigl{(}(\tau^{R}_{j+1}-\tau^{R}_{j},r^{R}_{\tau^{R}_{j+1}}-r^{R}_{\tau^{R}_{j}})\in B_{j+1}\text{ for }j=1,\dotsc,m\bigr{)}=\mathbb{E}(\prod_{j=1}^{m}I_{j+1}(B_{j+1}))$
	$\displaystyle=\mathbb{E}\Bigl{(}\mathbb{E}\bigl{(}\prod_{j=1}^{m}I_{j+1}(B_{j+1})\mid{\cal S}^{R}_{m}\bigl{)}\Bigr{)}=\mathbb{E}\Bigl{(}\prod_{j=1}^{m-1}I_{j+1}(B_{j+1})\mathbb{E}\bigl{(}I_{m+1}(B_{m+1})\mid{\cal S}^{R}_{m}\bigl{)}\Bigr{)}$

as the random variables $I_{j+1}(B_{j+1})$ are measurable w.r.t. ${\cal S}^{R}_{m}$ for $j=1,\dotsc,m-1$ .

By the earlier discussion, we have that the conditional distribution of $(\tau^{R}_{m+1}-\tau^{R}_{m},r^{R}_{\tau^{R}_{m+1}}-r^{R}_{\tau^{R}_{m}})$ given ${\cal S}^{R}_{m}$ is given by $(\nu,\max(\mathcal{A}^{R,+,0}_{\nu}))$ . Therefore, we have

	$\displaystyle P((\tau^{R}_{j+1}-\tau^{R}_{j},r^{R}_{\tau^{R}_{j+1}}-r^{R}_{\tau^{R}_{j}})\in B_{j+1}\text{ for }j=1,\dotsc,m)$
	$\displaystyle=\mathbb{E}\Bigl{(}\prod_{j=1}^{m-1}I_{j+1}(B_{j+1})\mathbb{E}\bigl{(}I_{m+1}(B_{m+1})\mid{\cal S}^{R}_{m}\bigl{)}\Bigr{)}$
	$\displaystyle=P\bigl{(}(\nu,\max(\mathcal{A}^{R,+,0}_{\nu}))\in B_{m+1}\bigr{)}\mathbb{E}\Bigl{(}\prod_{j=1}^{m-1}I_{j+1}(B_{j+1})\Bigr{)}.$

Now, induction on $m$ completes the proof. ∎

5.2 Proof of theorem 5.1

The same argument as in Theorem 4.1 gives us that

\displaystyle\lim_{n\to\infty}r^{R}_{n}/n=\lim_{j\to\infty}r^{R}_{\tau^{R}_{j}}/\tau^{R}_{j}=\mu^{\prime}\text{ almost surely}.

Compliance with Ethical Standards

We would like to declare that there are no conflicts of interest, either financial or non-financial, in the preparation of the manuscript. No funding was received to assist with the preparation of the manuscript. The authors are solely responsible for the correctness of the statements provided in the manuscript.

We have not used any data, materials, or codes in our work. We have not conducted any experiments or dealt with subjects for which ethics approvals or consents are required. Both of the authors have contributed equally to the work, and we don’t require the consent of any other individual or authority for the publication of this manuscript.

Acknowledgement

The authors would like to thank the referees and the editors for their valuable comments, which has helped the authors in significantly improving their results.

References

ARS [04] Siva Athreya, Rahul Roy, and Anish Sarkar. On the coverage of space by random sets. Advances in Applied Probability, 36(1):1–18, 2004.
ASR [19] Farkhondeh Alsadat Sajadi and Rahul Roy. On rumour propagation among sceptics. Journal of Statistical Physics, 174(4), 2019.
Ber [83] Sven Berg. Random contact processes, snowball sampling and factorial series distributions. Journal of applied probability, 20(1):31–46, 1983.
Dal [67] Daryl J Daley. Some aspects of Markov chains in queueing theory and epidemiology. PhD thesis, University of Cambridge, 1967.
DHL [19] Maria Deijfen, Timo Hirscher, and Fabio Lopes. Competing frogs on $\mathbb{Z}^{d}$ . Electronic Journal of Probability, 24:1–17, 2019.
DK [65] Daryl J Daley and David G Kendall. Stochastic rumours. IMA Journal of Applied Mathematics, 1(1):42–55, 1965.
Dun [82] Ross Dunstan. The rumour process. Journal of Applied Probability, 19(4):759–766, 1982.
Dur [80] Richard Durrett. On the growth of one dimensional contact processes. The Annals of Probability, 8(5):890–907, 1980.
Dur [84] Richard Durrett. Oriented Percolation in Two Dimensions. The Annals of Probability, 12(4):999 – 1040, 1984.
ES [20] Neda Esmaeeli and Farkhondeh Alsadat Sajadi. Rumour propagation among sceptics: the markovian case. Indian Journal of Pure and Applied Mathematics, 51:1661–1671, 2020.
ES [23] Neda Esmaeeli and Farkhondeh Alsadat Sajadi. On the probability of rumour survival among sceptics. Journal of Applied Probability, pages 1–16, 2023.
FG [85] Alan M Frieze and Geoffrey R Grimmett. The shortest-path problem for graphs with random arc-lengths. Discrete Applied Mathematics, 10(1):57–77, 1985.
GGJR [14] Sandro Gallo, Nancy L. Garcia, Valdivino Vargas Junior, and Pablo M. Rodríguez. Rumor processes on $\mathbb{N}$ and discrete renewal processes. Journal of Statistical Physics, 155(3):591–602, 2014.
HR [90] Torben Hagerup and Christine Rüb. A guided tour of chernoff bounds. Information processing letters, 33(6):305–308, 1990.
HS [21] Ivailo Hartarsky and Réka Szabó. Generalised oriented site percolation. arXiv preprint arXiv:2103.15621, 2021.
JMR [19] Valdivino V Junior, Fábio P Machado, and Krishnamurthi Ravishankar. The rumor percolation model and its variations. In Sojourns in Probability Theory and Statistical Physics-II, pages 208–227. Springer, 2019.
JMZ [11] Valdivino V Junior, Fabio P Machado, and Mauricio Zuluaga. Rumor processes on $\mathbb{N}$ . Journal of applied probability, 48(3):624 – 636, 2011.
KOW [08] Jan Kostka, Yvonne Anne Oswald, and Roger Wattenhofer. Word of mouth: Rumor dissemination in social networks. In International colloquium on structural information and communication complexity, pages 185–196. Springer, 2008.
Kuc [89] Thomas Kuczek. The central limit theorem for the right edge of supercritical oriented percolation. The Annals of Probability, pages 1322–1332, 1989.
LMM [08] Elcio Lebensztayn, Fábio Prates Machado, and Mauricio Zuluaga Martinez. Random walks systems with killing on $\mathbb{Z}$ . Stochastics, 80(5):451–457, 2008.
LR [08] Elcio Lebensztayn and Pablo M Rodriguez. The disk-percolation model on graphs. Statistics & probability letters, 78(14):2130–2136, 2008.
Pit [87] Boris Pittel. On spreading a rumor. SIAM Journal on Applied Mathematics, 47(1):213–223, 1987.
RS [21] Rishideep Roy and Kumarjit Saha. Coexistence in discrete time multi-type competing frog models. Electronic Communications in Probability, 26:1–9, 2021.
RSS [16] Rahul Roy, Kumarjit Saha, and Anish Sarkar. Random directed forest and the brownian web. Annales de l’Institut Henri Poincaré-Probabilités et Statistiques, 52(3):1106–1143, 2016.
RSS [23] Rahul Roy, Kumarjit Saha, and Anish Sarkar. Scaling limit of a drainage network model on perturbed lattice. arXiv preprint arXiv:2302.09489, 2023.
Sie [75] D Siegmund. The time until ruin in collective risk theory. Mitt. Verein. Schweiz. Versicherungsmath, 75(2):157–166, 1975.
XTZW [20] Jiuping Xu, Weiyao Tang, Yi Zhang, and Fengjuan Wang. A dynamic dissemination model for recurring online public opinion. Nonlinear Dynamics, 99:1269–1293, 2020.
YC [23] Yannis C Yortsos and Jincai Chang. A model for reinfections and the transition of epidemics. Viruses, 15(6):1340, 2023.

How fast do rumours spread?

Abstract

keywords:

1 Introduction

Lemma 1.1.

2 Rumour model

Definition 2.1.

3 Sharp phase transition for Rumour process

Proposition 3.1.

Proof.

Proposition 3.2.

Lemma 3.1.

Proof.

Remark 3.1.

Proof of 3.2.

Proposition 3.3.

Proof.

Corollary 3.1.

Remark 3.2.

4 Speed of the rightmost vertex in rumour cluster in the supercritical phase

Theorem 4.1.

4.1 A renewal process

Corollary 4.1.

Proof.

Proposition 4.1.

Proof.

Proposition 4.2.

Proof.

4.2 Proof of Theorem 4.1

Corollary 4.2.

Proof.

4.3 A central limit theorem for the position of rightmost vertex

Theorem 4.2.

Proof.

5 A rumour model with a reactivation mechanism

Theorem 5.1.

5.1 Renewal process for reactivation rumour process

Proposition 5.1.

Lemma 5.1.

Corollary 5.1.

Proof.

Proof of Lemma 5.1:.

Definition 5.1.

Lemma 5.2.

Proof of Proposition 5.1 for j=0j=0:.

Lemma 5.3.

Proof.

Corollary 5.2.

Lemma 5.4.

Proof.

Proof of 5.1 for j≥1j\geq 1.

Remark 5.1.

Lemma 5.5.

Proof.

Proposition 5.2.

Proof.

5.2 Proof of theorem 5.1

Compliance with Ethical Standards

Acknowledgement

References

Proof of Proposition 5.1 for $j=0$ :.

Proof of 5.1 for $j\geq 1$ .