1. Introduction
Directed random networks, where edges have a preferred direction of propagation, have long been an important class of models for understanding the large-scale behaviour of systems in a wide array of applications. These include, but are not limited to, transport networks, power grids, various kinds of social networks, different types of communication networks, including wireless sensor networks, multicast communication networks, and peer-to-peer networks, and drainage networks.
It has been empirically observed that river networks satisfy various scaling laws, and studying drainage networks is a statistical approach to understand the unifying behaviour of river basins. Scheidegger [Reference Scheidegger28] was the first to propose a directed network model for a drainage network by imposing a preferential flow condition where each source empties into one of its two neighbours in a preferred direction. Howard [Reference Howard18] removed the restriction of drainage to neighbouring sites only. Rodriguez-Iturbe and Rinaldo [Reference Rodriguez-Iturbe and Rinaldo24] provided an excellent survey of development in this field.
We first describe the modification of the Scheiddegger model proposed by Howard [Reference Howard18]. Each vertex in
$\mathbb{Z}^d$
is labelled open or closed independently with probability p or
$1-p$
, respectively. In what follows, for
$\mathbf{x} \in \mathbb{R}^d$
and for
$1 \leq i \leq d$
, we denote the ith coordinate of
$\mathbf{x}$
by
$\mathbf{x}(i)$
. An open vertex
$\mathbf{u} \in \mathbb{Z}^d$
is connected by an edge to the nearest open vertex at the next level
$\{ \mathbf{w} \in \mathbb{Z}^d\;:\; \mathbf{w}(d) = \mathbf{u}(d) + 1 \}$
. If there are two or more such vertices, then one of them is chosen uniformly at random. Note that for the Howard network and also for other drainage network models, the dth axis plays the role of time, whereas the
$(d-1)$
-dimensional space is represented by the first
$d-1$
coordinates. For the Howard network, Gangopadhyay et al. [Reference Gangopadhyay, Roy and Sarkar15] showed that it is a (connected) tree almost surely (a.s.) for
$d = 2, 3$
and it is a forest with infinitely many disjoint components for
$d \geq 4$
. Many other models (see [Reference Coupier and Tran9], [Reference Ferrari, Landim and Thorisson13], [Reference Ghosh and Saha16], and [Reference Roy, Saha and Sarkar25]) exhibit such tree–forest dichotomy depending on the dimensions.
Most of these models exhibit a commonality with Howard’s model: the random distributions of the open vertices are generally taken to be uniform over space and independent over disjoint regions, such as the Poisson point process and its discrete variants. Such distribution of vertices is comparatively amenable to rigorous mathematical analysis. In this work we venture beyond this standard paradigm and study a network constructed on a correlated point process generated from perturbed lattice points. The generated set of perturbed open vertices belongs to the general class of correlated point processes. In the rest of this section, we spell out the formal details of the two-dimensional model we work with and give an account of our principal results.
We start with an independent and identically distributed (i.i.d.) family of random vectors
\begin{align} \big\{ \Gamma_{\mathbf{u}} \;:\!=\; (B_{\mathbf{u}}, R_{\mathbf{u}}, \Lambda_{\mathbf{u}}) :\; \mathbf{u} \in \mathbb{Z}^2 \big\}\end{align}
such that the i.i.d. collections
$\{B_{\mathbf{u}} \;:\; {\mathbf{u}} \in \mathbb{Z}^2\}$
,
$\{R_{\mathbf{u}} \;:\; {\mathbf{u}} \in \mathbb{Z}^2\}$
, and
$\{\Lambda_{\mathbf{u}} \;:\; {\mathbf{u}} \in \mathbb{Z}^2\}$
are mutually independent of each other and satisfy the following.
-
(i) We use
$B_{\mathbf{u}}$
to denote a Bernoulli random variable with success probability
$p \in (0,1)$
which indicates whether
${\mathbf{u}}$
is an open vertex or not. -
(ii) We use
$R_{\mathbf{u}}$
to denote a Rademacher random variable associated with
${\mathbf{u}}$
which helps to resolve a tie (if there is one) for deciding among two equally nearer closest open vertices. -
(iii) We use
$\Lambda_{\mathbf{u}} \;:\!=\; (X_{\mathbf{u}}, Y_{\mathbf{u}})$
to denote the random vector associated with
${\mathbf{u}}$
, where
$X_{\mathbf{u}}$
and
$Y_{\mathbf{u}}$
denote the random variables of coordinate perturbations x and y, respectively. We assume that both perturbation random variables are integer-valued random variables satisfying the following assumptions: -
(a)
$\mathbb{P}(X_{\mathbf{u}} = Y_{\mathbf{u}} = 0) \gt 0$
and
$\mathbb{P}(Y_{\mathbf{u}} \lt 0) = 0$
; -
(b) there exist constants
$D_0, D_1 \gt 0$
such that (2)
\begin{align}\max\{ \mathbb{P}( |X_{\mathbf{u}}| \gt n), \; \mathbb{P}( Y_{\mathbf{u}} \gt n)\} \leq D_0 \exp{(\!-\!D_1 n)} \text{ for all }n \geq 1;\end{align}
-
(c)
$\mathbb{P}( X_{\mathbf{u}} = j) = \mathbb{P}( X_{\mathbf{u}} = -j)$
for all
$j \geq 1$
, i.e. the random variable
$X_{\mathbf{u}}$
is symmetrically distributed around 0.
-
Let
$\{ \mathbf{u} \in \mathbb{Z}^2 \;:\; B_{\mathbf{u}} = 1\}$
denote the collection of open vertices. If we use the random perturbation vector
$\Lambda_{\mathbf{w}} = (X_{\mathbf{w}}, Y_{\mathbf{w}})$
, a vertex
$\mathbf{w} \in \mathbb{Z}^2$
is perturbed to a new location
$\mathbf{w} + \Lambda_{\mathbf{w}} $
in
$\mathbb{Z}^2$
which is denoted by
$\tilde{\mathbf{w}}$
. Note that two vertices
$\mathbf{u}$
and
$\mathbf{w}$
may be perturbed to the same location, i.e. we may have
$\tilde{\mathbf{u}} = \tilde{\mathbf{w}} $
, in which case in the random graph we place only a single open vertex at location
$\tilde{\mathbf{u} }$
. We consider the set of perturbed open vertices V, given by
\begin{align}V \;:\!=\; \big\{ \tilde{\mathbf{u}} = \mathbf{u} + \Lambda_{\mathbf{u}} \;:\; \mathbf{u} \in \mathbb{Z}^2, B_{\mathbf{u}} = 1 \big\}.\end{align}
Since
$\Lambda_{\mathbf{u}} \in \mathbb{Z} \times \mathbb{Z}_+$
(where
$\mathbb{Z}_+ \;:\!=\; \mathbb{N} \cup \{ 0 \}$
), we have
$V \subset \mathbb{Z}^2$
a.s. Using the point process V, we construct the random graph as follows. For
$\mathbf{u} \in \mathbb{Z}^2$
we define the non-negative integer-valued random variable
$J(\mathbf{u})$
as
\begin{align*}J(\mathbf{u}) \;:\!=\; \min \{ |\mathbf{w}(1) - \mathbf{u}(1)| \;:\; \mathbf{w} \in V, \mathbf{w}(2) = \mathbf{u}(2) + 1\}.\end{align*}
In other words,
$J(\mathbf{u})$
denotes the distance of the nearest open vertex in V from
$\mathbf{u}$
having y coordinate
$\mathbf{u}(2) + 1$
. We recall that the x coordinate represents space, whereas the y coordinate stands for time. For
$\mathbf{u} \in \mathbb{Z}^2$
let
$h(\mathbf{u})=h(\mathbf{u}, V)$
be the (almost sure) unique point in V with
$h(\mathbf{u})(2) = \mathbf{u}(2) + 1$
such that
\begin{align} h(\mathbf{u}) \;:\!=\;\begin{cases}\mathbf{u} + (J(\mathbf{u}), 1) & \text{ if }\mathbf{u} + (J(\mathbf{u}), 1) \in V \text{ and } \mathbf{u} + (\!-\!J(\mathbf{u}), 1) \notin V, \\[5pt] \mathbf{u} + (\!-\!J(\mathbf{u}), 1) & \text{ if }\mathbf{u} + (\!-\!J(\mathbf{u}), 1) \in V \text{ and } \mathbf{u} + (J(\mathbf{u}), 1) \notin V, \\[5pt] \mathbf{u} + (R_{\mathbf{u}} J(\mathbf{u}), 1) & \text{ otherwise}.\end{cases}\end{align}
We drop V from the notation
$h(\mathbf{u}, V)$
when it is clear from the context and denote it simply as
$h(\mathbf{u})$
. Henceforth, we study the perturbed Howard (PH) random graph
$G \;:\!=\; (V, E)$
with vertex set V, as given in (3), and edge set
$E \;:\!=\; \{\langle \mathbf{u} , h(\mathbf{u}) \rangle \;:\; \mathbf{u} \in V\}$
. We observe that each
$\mathbf{u} \in V$
has exactly one outgoing edge, and therefore G does not have any cycle or loop a.s. Our first result shows that the random graph G is connected a.s.
Theorem 1. We have that
$G = (V, E)$
is connected and consists of a single tree a.s.
Recently, there has been some interest in studying networks constructed on perturbed vertices and, more generally, on correlated point processes; for example, Ghosh and Saha [Reference Ghosh and Saha16] studied a drainage network model where vertices from a d-dimensional integer lattice undergo i.i.d. perturbations with perturbation random vectors restricted to compact domains. The question of tree–forest dichotomy depending on dimensions is explored in [Reference Ghosh and Saha16]. To the best of the authors’ knowledge, this is the only other work which analyses the connectivity property of an infinite directed network constructed on perturbed vertices. In the present work, we remove the limitation of working with compactly supported perturbation random vectors, although we are working with a two-dimensional network only. It is important to observe that the perturbed point process studied in [Reference Ghosh and Saha16] was not a subset of
$\mathbb{Z}^d$
. For technical reasons, for our model we have
$V \subset \mathbb{Z}^2$
a.s.
Our next result shows that the graph G observed as a collection of paths converges in distribution to the Brownian web under a suitable diffusive scaling. The standard Brownian web originated in the work of Arratia [Reference Arratia1] as the scaling limit of the voter model on
$\mathbb{Z}$
. Intuitively, the Brownian web can be thought of as a collection of one-dimensional coalescing Brownian motions starting from every point in the space–time plane
$\mathbb{R}^2$
, where the y axis plays the role of time and the x axis represents space. Later, Fontes et al. [Reference Fontes, Isopi, Newman and Ravishankar14] provided a framework in which the Brownian web is realized as a random variable taking values in a Polish space. In Subsection 7.1, we present a brief introduction of the Brownian web and present the relevant topological details for convergence from [Reference Fontes, Isopi, Newman and Ravishankar14].
Set
$h^0(\mathbf{u}) = \mathbf{u} \in \mathbb{Z}^2 $
and
$h^k(\mathbf{u}) = h(h^{k-1}(\mathbf{u})) \in V$
for
$k \geq 1$
. We define the path
$\pi^{\mathbf{u}}$
starting from
$ \mathbf{u} $
as
$\pi^{\mathbf{u}} \;:\!=\; ( h^{0}(\mathbf{u}), h^1(\mathbf{u}), h^2(\mathbf{u}) , \dotsc \!)$
with edges joining consecutive vertices.
Let
$\mathcal{X} \;:\!=\; \{ \pi^{\mathbf{u}}\;:\; \mathbf{u} \in V \}$
. For
$ \mathbf{u} \in \mathbb{Z}^2$
and
$n \in \mathbb{N} $
, let
$ \mathbf{u}_n = ( \mathbf{u}(1)/\sqrt{n} , \mathbf{u}(2)/n ) $
. For
$ \pi^{\mathbf{u}} \in \mathcal{X} $
,
$ \gamma, \sigma \gt 0$
, and
$ t \geq \mathbf{u}(2) / (n \gamma) $
, let
\begin{align} \pi_n^{\mathbf{u}}(\gamma,\sigma)(t) \;:\!=\; \pi^{\mathbf{u}}(n \gamma t)/(\sqrt{n} \sigma)\quad \text{and}\quad \mathcal{X}_n(\gamma,\sigma) \;:\!=\; \big\{ \pi_n^{\mathbf{u}}(\gamma,\sigma) \;:\; \mathbf{u} \in V \big\} .\end{align}
Let
$\overline{\mathcal{X}}_n(\gamma,\sigma)$
denote the closure of the collection of the scaled paths
$\mathcal{X}_n(\gamma,\sigma)$
with respect to a certain metric, which is explained in detail in Subsection 7.1. Our second theorem gives that the diffusively scaled network converges to the Brownian web in a suitable topology (see Subsection 7.1).
Theorem 2. There exist
$\sigma \gt 0$
and
$\gamma \gt 0$
such that
$\overline{\mathcal{X}}_n(\gamma,\sigma)$
converges in distribution to the Brownian web
$\mathcal{W}$
as
$n \to \infty$
.
Fontes et al. [Reference Fontes, Isopi, Newman and Ravishankar14] established conditions for a random network to converge to the Brownian web and showed that the collection of coalescing simple symmetric random walks, also known as the Scheidegger drainage network [Reference Scheidegger28], converges to the Brownian web. Since then, the Brownian web has appeared as the universal scaling limit for various directed networks (see [Reference Coletti, Fontes and Dias7], [Reference Coupier, Saha, Sarkar and Tran8], [Reference Ferrari, Fontes and Wu12], [Reference Roy, Saha and Sarkar25], and [Reference Sarkar and Sun27]). In particular, Coletti et al. [Reference Coletti, Fontes and Dias7] showed that the diffusively scaled two-dimensional Howard network converges to the Brownian web. Apart from drainage network models, the Brownian web appears as the universal scaling limit for a large number of seemingly unrelated systems of coalescing paths. We mention here the work of Tóth and Werner [Reference Tóth and Werner31] in the context of true self-repelling motion, and the work of Norris and Turner [Reference Norris and Turner22] in connection with Hastings–Levitov planar aggregation models. The Brownian web and its branching variant, the Brownian net, have found connections in population genetic models as well [Reference Athreya and Sun2, Reference Etheridge, Freeman and Straulino11, Reference Greven, Sun and Winter17]. In the context of networks constructed on perturbed vertices, [Reference Ghosh and Saha16] establishes convergence to the Brownian web for
$d = 2$
. There are examples of various networks with crossing paths also in the basin of attraction of the Brownian web (see [Reference Belhaouari, Mountford, Sun and Valle3], [Reference Berestycki, Garban and Sen4], [Reference Coletti and Valle10], [Reference Newman, Ravishankar and Sun21], and [Reference Parvaneh and Roy23]).
The main idea of our argument is based on a construction of suitable renewal steps which decomposes the path process into blocks of i.i.d. increments. For an intuitive description of these renewal steps, we refer the reader to Figure 3, which ensures that at a renewal step, the future evolution of the path uses perturbed versions of open vertices from the upper half-plane only and their distribution is independent of the past steps. The detailed description of the renewal steps can be found in Section 3. In the literature, there are several examples of the use of renewal constructions to recover Markovian structures for drainage networks with complex dependencies (see [Reference Coupier, Saha, Sarkar and Tran8], [Reference Ghosh and Saha16], [Reference Roy, Saha and Sarkar25], and [Reference Valle and Zuaznabar32]); however, all renewal constructions in the cited papers are based on configurations within compact regions only. Our renewal construction depends on the configuration over an unbounded region. In that sense, our renewal construction is similar to the renewal construction for a supercritical oriented percolation model, which is based on percolating points or ‘break’ points (see [Reference Birkner, Cerny, Depperschmidt and Gantert5], [Reference Birkner, Gantert and Steiber6], [Reference Kuczek19], and [Reference Sarkar and Sun27]). As our renewal construction depends on the infinite future, we need to work considerably harder to study these renewal steps. Before ending this section, we remark on our results below.
Remark 1. It is important to observe that in the present work, y coordinate perturbation random variables are allowed to take non-negative values only. Without this restriction, our choice of filtration as in (6) would not work. We believe that with the help of the techniques introduced in this paper and with some additional work it should be possible to deal with y coordinate perturbation random variables satisfying
$\mathbb{P}(Y_{\mathbf{u}} \geq - m) = 1$
for some
$m \in \mathbb{N}$
.
2. The joint exploration process and a sequence of ‘In’ steps
Fix
$k \geq 1$
. In this section we start from k many lattice points
$\mathbf{x}_1, \ldots, \mathbf{x}_k \in \mathbb{Z}^2$
such that
$\mathbf{x}_1(2) = \cdots = \mathbf{x}_k(2) $
, and we consider the joint exploration process of successive steps
$\{h^n(\mathbf{x}_1), \ldots,h^n(\mathbf{x}_k) \;:\; n \geq 0\}$
. Note that the starting points
$\mathbf{x}_1,\ldots, \mathbf{x}_k$
are not necessarily in V. Without loss of generality, we consider
$\mathbf{x}_1(2) = \cdots = \mathbf{x}_k(2) = 0$
. Recall that the y coordinate represents the time, and for
$n \in \mathbb{Z}$
, let
$\mathcal{F}_n$
denote the
$\sigma$
-field:
\begin{align}\mathcal{F}_n \;:\!=\; \sigma \bigl( \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{Z}^2 \text{ with }\mathbf{w}(2) \leq n \bigl).\end{align}
We observe that the joint exploration process
$\{h^n(\mathbf{x}_1), \ldots, h^n(\mathbf{x}_k) \;:\; n \geq 0\}$
is measurable with respect to the filtration
$\{\mathcal{F}_n \;:\; n \geq 0\}$
. We note that the filtration
$\{\mathcal{F}_n \;:\; n \geq 0\}$
is not the natural or minimal filtration for the joint exploration process. Nevertheless, we continue to work with this filtration.
We introduce some notation. For
$n \in \mathbb{Z}$
, consider the half-planes
\begin{align*}\mathbb{H}^+( n ) \;:\!=\; \big\{\mathbf{w} \in \mathbb{Z}^2 \;:\; \mathbf{w}(2) \gt n \big\}\quad\text{ and }\quad \mathbb{H}^-(n) \;:\!=\; \big\{\mathbf{w} \in \mathbb{Z}^2 \;:\; \mathbf{w}(2) \leq n \big\}.\end{align*}
For
$n \geq 0$
, we observe that the set
$\{ \tilde{\mathbf{w}} \in V \cap \mathbb{H}^+(n) \;:\; \mathbf{w} \in \mathbb{H}^-(n), B_{\mathbf{w}} = 1\}$
is measurable with respect to the
$\sigma$
-field
$\mathcal{F}_n$
. Note that
$\tilde{\mathbf{w}} \in V$
with
$\tilde{\mathbf{w}}(2) \gt n$
may have arisen as a perturbation of a vertex in
$\mathbb{H}^-(n-1)$
, and as such the Markov property does not hold.
2.1. Markov property of the joint exploration process
For
$\ell \in \mathbb{Z}$
we partition the set V as
\begin{align}V^+_\ell & \;:\!=\; \{ \tilde{\mathbf{w}} = \mathbf{w} + \Lambda_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\ell), B_{\mathbf{w}} = 1\}, \nonumber\\[5pt] V^-_\ell & \;:\!=\; \{ \tilde{\mathbf{w}} = \mathbf{w} + \Lambda_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^-(\ell), B_{\mathbf{w}} = 1\};\end{align}
note that
$V^+_\ell \cap V^-_\ell$
need not be empty because a point
$\tilde{\mathbf{w}} \in V$
may have arisen as a perturbed vertex of many different vertices.
We observe that the random point set
$V^+_\ell$
is contained in
$\mathbb{H}^+(\ell)$
and is independent of the
$\sigma$
-field
$\mathcal{F}_\ell$
. On the other hand, the set
$V^-_\ell$
is
$\mathcal{F}_\ell$
measurable. In particular, for
$\mathbf{w} \in \mathbb{H}^-(\ell)$
, the event
$\{ \tilde{\mathbf{w}} \in V^-_\ell \}$
is
$\mathcal{F}_\ell$
measurable, while for
$\mathbf{w} \in \mathbb{H}^+(\ell)$
, it is independent of
$\mathcal{F}_\ell$
. We note that the set
$V^-_\ell$
may have some overlap with
$\mathbb{H}^+(\ell)$
. Let
$I_\ell$
denote the
$\mathcal{F}_\ell$
measurable set defined as
\begin{align}I_\ell \;:\!=\; V^-_\ell \cap \mathbb{H}^+(\ell) = \{ \tilde{\mathbf{w}} = \mathbf{w} + \Lambda_{\mathbf{w}} \in \mathbb{H}^+(\ell) \;:\; \mathbf{w} \in \mathbb{H}^-(\ell), B_{\mathbf{w}} = 1\}.\end{align}
The following proposition shows that, together with this ‘information set’
$I_\ell$
, the joint exploration process is Markov.
Proposition 1. Let
$\mathbf{x}_1, \ldots, \mathbf{x}_k \in \mathbb{Z}^2$
be such that
$\mathbf{x}_1(2)= \cdots = \mathbf{x}_k(2) $
. The
$\{\mathcal{F}_n \;:\; n \geq 0 \}$
adapted process
\begin{align*}\{ (h^{n}(\mathbf{x}_1), \ldots, h^{n}(\mathbf{x}_k), I_n) \;:\; n \geq 0\}\end{align*}
is a Markov chain with state space
$\mathbb{Z}^{2k} \times \mathcal{P}$
, where
$\mathcal{P}$
denotes the collection of all subsets of
$\mathbb{Z}^2$
.
Proof. Without loss of generality we assume
$\mathbf{x}_1(2)= \cdots = \mathbf{x}_k(2) = 0$
, so that we have
$h^{n}(\mathbf{x}_i)(2) = n$
for all
$1 \leq i \leq k$
. Let
$\bigl \{ \Gamma^{\text{ind}}_{\mathbf{w}} \;:\!=\; \bigl ( B^{\text{ind}}_{\mathbf{w}}, R^{\text{ind}}_{\mathbf{w}}, \Lambda^{\text{ind}}_{\mathbf{w}}\bigr ) \;:\; \mathbf{w} \in \mathbb{Z}^2 \bigr \}$
be an independent copy of the collection
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{Z}^2\}$
as defined in (1). Given that
$\{(h^n(\mathbf{x}_1), \ldots, h^n(\mathbf{x}_k), I_n) =(\mathbf{w}_1, \ldots, \mathbf{w}_k, \Delta)\}$
with
$\Delta \in \mathcal{P}$
, we consider the set
\begin{align*}\Psi_n(\Delta) \;:\!=\; \big\{ \mathbf{w} + \Lambda^{\text{ind}}_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(n), B^{\text{ind}}_{\mathbf{w}} = 1\big\} \cup \Delta\end{align*}
in the upper half-plane
$\mathbb{H}^+(n)$
.
Parabolic curve
$\{( \pm y^2, y) \;:\; y \geq 0\}$
.
$\nabla(\mathbf{0})$
is the grey region inside this curve. Observe that for any
$\mathbf{v} \in \nabla(\mathbf{0}) $
we have
$\nabla(\mathbf{v}) \subseteq \nabla(\mathbf{0})$
. Further, for
$\mathbf{v} \in \mathbb{Z}^2$
the ‘In’ event occurs at
$\mathbf{v}$
as the path
$\{ h^j(\mathbf{v}) \;:\; j \geq 1\}$
stays inside the region
$\nabla(\mathbf{v})$
throughout.
We observe that the set
$\Delta$
gives us the information about vertices in
$\Delta \cap \mathbb{H}^+(n)$
which arose as perturbations of some open vertices in
$\mathbb{H}^-(n)$
. The set
$V^+_{n}$
is independent of
$\mathcal{F}_n$
and has the same distribution as
$\{ \mathbf{w} + \Lambda^{\text{ind}}_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(n), B^{\text{ind}}_{\mathbf{w}} = 1\}$
. Therefore, the
$(n+1)$
th step taken by the joint exploration process has the same distribution as starting from
$(\mathbf{w}_1, \ldots, \mathbf{w}_k)$
and taking the next step using
$\Psi_n(\Delta)$
. In other words, we have
\begin{align*}\big(h^{n+1}(\mathbf{x}_1), \ldots, h^{n+1}(\mathbf{x}_k), I_{n+1}\big) \mid & \bigl((h^{n}(\mathbf{x}_1), \ldots, h^{n}(\mathbf{x}_k), I_n) = (\mathbf{w}_1, \ldots, \mathbf{w}_k, \Delta), \mathcal{F}_n \bigr )\\[5pt] & \stackrel{\mathrm{d}}{=} f \bigl( (\mathbf{w}_1, \ldots, \mathbf{w}_k, \Delta),\big\{ \Gamma^{\text{ind}}_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{Z}^2\big\} \bigr )\end{align*}
for some measurable function f. Hence, by the random mapping theorem (see [Reference Levin, Peres and Wilmer20]), Proposition 1 follows.
2.2. Sequence of ‘In’ steps
Now we define a sequence of stopping times, which allows us to obtain a renewal structure in our model. Towards this, we define a region of our interest in the upper half-plane. We consider the parabolic curve
$\Upsilon \;:\!=\; \{( \pm y^2, y) \;:\; y \geq 0\}$
. The region ‘inside’ this parabolic curve is denoted as
\begin{align*}\nabla = \nabla(\mathbf{0}) \;:\!=\; \big\{( x , y) \in \mathbb{R}^2 \;:\; y \geq 0, x \in \big[\!-\!y^2, y^2\big] \big\} .\end{align*}
For
$\mathbf{x} \in \mathbb{R}^2$
and
$B \subset \mathbb{R}^2$
, let
$\mathbf{x} \oplus B \;:\!=\; \{\mathbf{x} + \mathbf{y} \;:\; \mathbf{y} \in B \}$
. For
$\mathbf{u} \in \mathbb{R}^2$
, let
$\nabla(\mathbf{u}) \;:\!=\; \mathbf{u} \oplus \nabla$
denote the translated version of
$\nabla$
translated by
$\mathbf{u}$
. Observe that for any
$\mathbf{u}, \mathbf{v} \in \mathbb{R}^2$
with
$\mathbf{v} \in \nabla(\mathbf{u}) $
, the regions
$\nabla(\mathbf{u})$
and
$\nabla(\mathbf{v})$
are nested in the sense that
\begin{align}\nabla(\mathbf{v}) \subseteq \nabla(\mathbf{u}) .\end{align}
This nesting property (see Figure 1) will be used later. For
$\mathbf{v} \in \mathbb{Z}^2$
, we define the event
$\text{In}(\mathbf{v})$
as
\begin{align*}\text{In}(\mathbf{v}) \;:\!=\; \{ h^n(\mathbf{v}) = h^n(\mathbf{v}, V) \in \nabla(\mathbf{v}) \text{ for all }n \geq 1 \}.\end{align*}
For the joint exploration process of k paths starting from
$\mathbf{x}_1, \ldots , \mathbf{x}_k$
, we say that the ‘In’ event occurs at the nth step if
$\bigcap_{i=1}^{k} \text{In}(h^n(\mathbf{x}_i))$
occurs. In other words, occurrence of the ‘In’ event at the nth step ensures that for each
$1 \leq i \leq k$
the path starting from
$h^n(\mathbf{x}_i)$
stays inside the region
$\nabla(h^n(\mathbf{x}_i))$
.
Next we define our sequence of ‘In’ steps. Set
$\tau_0 = \tau_0(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k) = 0$
, and for
$j \geq 1$
we define the random step
$\tau_j$
as
\begin{align*}\tau_j = \tau_j(\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k) &\;:\!=\; \inf\Bigg\{ n \gt \tau_{j -1 } \;:\; \text{the event } \bigcap_{i=1}^{k} \text{In}\big(h^n(\mathbf{x}_i)\big) \text{ occurs}\Bigg\}.\end{align*}
Proposition 2 tells us that for all
$j \geq 1$
$\tau_j$
is finite a.s. We observe that
$\tau_j$
is not a stopping time with respect to filtration
$\{\mathcal{F}_n \;:\; n \geq 0\}$
. We need to extend the filtration to make it a stopping time. For
$n \geq 1$
, we define the
$\sigma$
-field
\begin{align*}\overline{\mathcal{F}}_n \;:\!=\; \sigma \bigl ( \mathcal{F}_n, \text{In}(h^m(\mathbf{x}_i)) \;:\; 0 \leq m \leq n , 1 \leq i \leq k \bigr ).\end{align*}
For each
$j \geq 1$
,
$\tau_j$
is a stopping time with respect to
$\{ \overline{\mathcal{F}}_n \;:\; n \geq 0\}$
. This allows us to define the filtration
\begin{align}\{ \mathcal{G}_j \;:\!=\; \overline{\mathcal{F}}_{\tau_j} \;:\; j \geq 1 \}.\end{align}
Proposition 2. For any
$j \geq 0$
there exist constants
$C_0, C_1 \gt 0$
, which do not depend on j or on the starting points
$\mathbf{x}_1, \mathbf{x}_2, \ldots, \mathbf{x}_k$
, such that for all
$n \in \mathbb{N}$
we have
\begin{align*} \mathbb{P}(\tau_{j+1} - \tau_j \gt n \mid \mathcal{G}_j) \leq C_0 \exp{(\!-\!C_1 n)}. \end{align*}
Proposition 2 is the main result of this subsection. Before we proceed further, we mention that in several places in this paper we will use
$C_0$
and
$C_1$
to denote two positive constants, whose exact values may change in different places. The important thing is that both
$C_0$
and
$C_1$
are universal constants whose values depend only on p,
$D_0$
,
$D_1$
(where p is the success parameter for the Bernoulli random variable
$B_{\mathbf{u}}$
, and
$D_0$
and
$D_1$
are as in (2)), and k (the number of trajectories considered). Sometimes we may refer them as process parameters.
Definition 1. We say that
$\{X_i \;:\; i \geq 1\}$
has uniform exponential tail decay if there exist constants
$C_0, C_1 \gt 0$
such that
\begin{align*}\sup_{i \geq 1}\mathbb{P}( |X_i| \gt n) \leq C_0\exp{ (\!-\!C_1 n) } \quad \textit{for all }n \in \mathbb{N}.\end{align*}
A family of discrete random variables
$\{X_i \;:\; i \geq 1\}$
is said to have strong uniform exponential tail decay if there exist constants
$C_0, C_1 \gt 0$
such that for all
$i \geq 1$
and
$x_1, \ldots , x_{i-1} \in \mathbb{Z}$
we have
\begin{align*}\mathbb{P} (|X_i| \gt n \mid (X_{i-1} = x_{i-1},\ldots, X_1 = x_1))\leq C_0 \exp{(\!-\!C_1 n)} \quad \text{for all }n \in \mathbb{N}.\end{align*}
We need the following lemma regarding the tail decay of a random sum of random variables with exponential tail decay to prove Proposition 2. We believe that the following lemma could be of inherent interest too.
Lemma 1. Consider a family of discrete random variables
$\{ X_i \;:\; i \geq 1\}$
with strong uniform exponential tail decay and a positive integer-valued random variable Y with exponentially decaying tail. Then there exist
$C_0, C_1 \gt 0$
such that for all
$ n \in \mathbb{N}$
we have
\begin{align*}\mathbb{P}\Bigg( \sum_{i=1}^Y |X_i| \gt n\Bigg) \leq C_0 \exp{(\!-\!C_1 n)}.\end{align*}
Proof. From the definition of strong uniform exponential tail decay we observe that there exists a random variable W independent of the family
$\{X_i \;:\; i \geq 1\}$
such that for all
$i \geq 1$
we have
\begin{align*}\mathbb{P} \bigl ( |X_i| \gt n \mid X_{i-1},\ldots, X_1 \bigr ) \leq \mathbb{P}(W \gt n) \leq C_0 \exp{(\!-\!C_1 n)} \text{ for all }n \in \mathbb{N}.\end{align*}
We consider
$W_1, W_2, \dotsc $
i.i.d. copies of W independent of the family
$\{X_i \;:\; i \geq 1\}$
. Because of Lemma 2.7 in [Reference Roy, Saha and Sarkar25], to prove Lemma 1 it is enough to show that for all
$j \geq 1$
we have
\begin{align}\mathbb{P}\Bigg( \sum_{i=1}^j |X_i| \gt n\Bigg) \leq \mathbb{P}\Bigg( \sum_{i=1}^j W_i \gt n\Bigg).\end{align}
We prove (11) using the method of induction. Clearly, (11) holds for
$j = 1$
.
Assuming that (11) holds for
$j \geq 1$
, we obtain
\begin{align*}\mathbb{P} \Bigg(\sum_{ i=1}^{j+1} |X_i| \gt n \Bigg) & = \sum_{ m \geq 0} \mathbb{P} \Bigg( |X_{j+1}| \gt n - m | \sum_{ i=1}^{j} |X_i| = m \Bigg) \mathbb{P} \Bigg(\sum_{ i=1}^{j} |X_i| = m \Bigg)\\[5pt] & \leq \sum_{ m \geq 0 } \mathbb{P} (W_{j+1} \gt n-m) \mathbb{P} \Bigg(\sum_{ i=1}^{j} |X_i| = m \Bigg) \\[5pt] & = \mathbb{P} \Bigg( \bigcup_{m\geq 0} \Bigg\{\sum_{ i=1}^{j} |X_i| = m, W_{j+1} \gt n-m \Bigg\}\Bigg) \\[5pt] & = \mathbb{P} \Bigg(\sum_{ i=1}^{j} |X_i| + W_{j+1} \gt n\Bigg) \\[5pt] & = \sum_{ m \geq 0} \mathbb{P} \Bigg(\sum_{ i=1}^{j} |X_i| \gt n - m , W_{j+1} = m \Bigg) \\[5pt] & = \sum_{ m \geq 0} \mathbb{P} \Bigg(\sum_{ i=1}^{j} |X_i| \gt n - m \Bigg) \mathbb{P} ( W_{j+1} = m )\\[5pt] & \leq \sum_{ m \geq 0} \mathbb{P} \Bigg(\sum_{ i=1}^{j} W_i \gt n - m \Bigg) \mathbb{P} ( W_{j+1} = m )\\[5pt] & = \mathbb{P} \Bigg(\sum_{ i=1}^{j+1} W_i \gt n\Bigg) .\end{align*}
The last inequality follows from the induction hypothesis. This completes the proof.
Proposition 2 will be proved through a sequence of lemmas. In the next lemma, we show that given
$\mathcal{F}_n$
, the probability of the occurrence of an ‘In’ event at the nth step
$(h^n(\mathbf{x}_1), \ldots , h^n(\mathbf{x}_k))$
has a strictly positive lower bound which does not depend on
$n \geq 1$
or on the choice of the starting points
$\mathbf{x}_1, \ldots, \mathbf{x}_k$
.
Lemma 2. There exists
$p_0 \gt 0$
such that we have
\begin{align*}\mathbb{P}\Bigg(\bigcap_{i=1}^k \text{In}(h^n(\mathbf{x}_i)) \mid \mathcal{F}_n \Bigg) \geq p_0^k\; \textit{ for all }n \geq 0.\end{align*}
To prove Lemma 2 we need to introduce a ‘special’ subset of V denoted by
$V_{\text{sp}}$
defined as
\begin{align*}V_{\text{sp}} \;:\!=\; \big\{ \mathbf{u} \in \mathbb{Z}^2 \;:\; B_{\mathbf{u}} = 1, X_{\mathbf{u}} = Y_{\mathbf{u}} = 0 \big\}.\end{align*}
In other words,
$V_{\text{sp}}$
represents the collection of source vertices in V with no perturbations at all. The distribution of the random vector
$\Gamma_{\mathbf{u}}$
, defined as in (1), ensures that the set
$V_{\text{sp}}$
must be non-empty a.s., and for any
$\mathbf{u} \in \mathbb{Z}^2$
we have
\begin{align}\mathbb{P}(\mathbf{u} \in V_{\text{sp}}) = \mathbb{P}(B_{\mathbf{u}} = 1, X_{\mathbf{u}} = Y_{\mathbf{u}} = 0)= \mathbb{P}(B_{\mathbf{u}} = 1)\mathbb{P}( X_{\mathbf{u}} = Y_{\mathbf{u}} = 0) = \tilde{p} \gt 0.\end{align}
Observe that, for any
$n \in \mathbb{N}$
, the distribution of special points in the upper half-plane
$\mathbb{H}^+(n)$
, given by
$V_{\text{sp}} \cap \mathbb{H}^+(n)$
, is independent of the
$\sigma$
-field
$\mathcal{F}_n$
. This observation enables us to obtain exponential tail decay for the increments of the path process. For
$\mathbf{u} \in \mathbb{Z}^2$
let
\begin{align*}J_{\text{sp}}(\mathbf{u}) \;:\!=\; \min\{ k \geq 0 \;:\; \mathbf{u} + (k, 1)\in V_{\text{sp}} \text{ or }\mathbf{u} + (\!-k, 1) \in V_{\text{sp}}\}\end{align*}
denote the distance of the nearest special point on the line
$y = \mathbf{u}(2) + 1$
from
$\mathbf{u}$
. Given
$\mathcal{F}_n$
, for any
$\mathbf{w} \in \mathbb{H}^+(n)$
we obtain
\begin{align*}\mathbb{P}((h(\mathbf{w}) - \mathbf{w})(1) \gt m \mid \mathcal{F}_n ) \leq\mathbb{P}(J_{\text{sp}}(\mathbf{w}) \gt m \mid \mathcal{F}_n ) =(1 - \tilde{p})^{2m + 1} \text{ for all }m \in \mathbb{N}.\end{align*}
The above observation together with a straightforward application of the union bound gives us the following lemma.
Lemma 3. Fix any
$\alpha, \beta \gt 0$
with
$\alpha \gt \beta \gt 0$
. Then, for all large n, we have
\begin{align*}\mathbb{P} ( \max\{ |h^j(\mathbf{0})(1)| \;:\; 1 \leq j \leq n^\beta \} \gt n^\alpha \mid \mathcal{F}_0 )\leq C_0 \exp{\big(\!-\!C_1 n^{\alpha - \beta}\big)}.\end{align*}
We describe a Fortuin–Kasteleyn–Ginibre (FKG) property among ‘increasing’ events expressed in terms of special vertices only, which will be needed for the proof of Lemma 2. We consider a partial order relation on the space
$\{0,1\}^{\mathbb{Z}^2}$
given as follows: for
$\omega, \omega^\prime \in \{0,1\}^{\mathbb{Z}^2}$
\begin{align*}\omega \leq \omega^\prime \text{ if }\omega(\mathbf{w})\leq \omega^\prime(\mathbf{w}) \text{ for all }\mathbf{w} \in \mathbb{Z}^2.\end{align*}
Definition 2. An event A, which is measurable with respect to the
$\sigma$
-field generated by the collection of indicator random variables
$\{ \mathbf{1}_{\{\mathbf{w} \in V_{\text{sp}}\}} \;:\; \mathbf{w} \in \mathbb{Z}^2\}$
, is said to be increasing if
\begin{align*}\omega \in A \Rightarrow \omega^\prime \in A \textit{ for all } \omega^\prime \geq \omega.\end{align*}
Observe that
$\{ \mathbf{1}_{\{\mathbf{w} \in V_{\text{sp}}\}} \;:\; \mathbf{w} \in \mathbb{Z}^2 \}$
is a collection of i.i.d. Bernoulli random variables with success probability
$p_0$
, where
$p_0$
is as in (12). Hence, the following lemma regarding the FKG property between increasing events (expressible in terms of special vertices only) follows directly.
Lemma 4 (FKG property.) For any two increasing events
$A, B \in \sigma (\{ \mathbf{1}_{\{\mathbf{w} \in V_{\mathrm{sp}}\}} \;:\; \mathbf{w} \in \mathbb{Z}^2 \})$
we have
\begin{align*}\mathbb{P}(A \cap B) \geq \mathbb{P}(A) \mathbb{P}(B).\end{align*}
Proof of Lemma 2. The idea behind the proof is to create a ‘shield’ of special points which would keep the path inside the parabolic region. This shield should be sufficiently spread out to ensure that the probability of the occurrence of such a shield is positive. This motivates our choice of a parabolic region in the definition of the ‘In’ event.
To formalize the above idea, we need to introduce some notation. For
$m \in \mathbb{N}$
, let
$I^R_m, I^L_m \subset \mathbb{Z}^2$
denote the sets
\begin{align*}I^R_m = I^R_m(\mathbf{0}) \;:\!=\; \{(u,m) \in \mathbb{Z}^2 \;:\; u \in [(m-1)^2 + 1, m^2] \}\end{align*}
and
\begin{align*}I^L_m = I^L_m(\mathbf{0}) \;:\!=\; \{(u,m) \in \mathbb{Z}^2 \;:\; u \in [\!-\! m^2, - (m-1)^2 - 1] \}.\end{align*}
We make certain observations about the above defined sets, and we refer the reader to Figure 2. For any
$m \geq 1$
, by construction of the sets
$I^R_m $
and
$I^L_m$
we have the following.
-
(i) The right endpoint of the set
$I^R_m$
and the left endpoint of the set
$I^L_m$
lie on the parabolic curve
$\Upsilon = \{ (\pm y^2, y) \;:\; y \geq 0\}$
. -
(ii) The x coordinate of the left endpoint of the set
$I^R_{m+1}$
on the line
$y = m + 1$
is (strictly) larger than the x coordinate of the right endpoint of
$I^R_{m}$
on the line
$y = m $
. On the other hand, the x coordinate of the right endpoint of the set
$I^L_{m+1}$
on the line
$y = m + 1$
is (strictly) smaller than the x coordinate of the left endpoint of
$I^L_{m}$
on the line
$y = m $
.
The event
$A_{\text{sp}}(\mathbf{0})$
creates a shield of ‘special’ points which ensures that the PH path
$\{ h^{j}(\mathbf{0}) \;: j \geq 1\}$
stays inside the region
$\nabla(\mathbf{0})$
. Black points represent special points, and grey points are versions of open vertices from some other locations. There might be some points of V in the intermediate region too.
We define the event
$A_{\text{sp}}= A_{\text{sp}}(\mathbf{0})$
as
\begin{align}A_{\text{sp}}(\mathbf{0}) \;:\!=\; \bigcap_{m=1}^\infty \big\{ I^R_m\cap V_{\text{sp}}\neq \emptyset \big\}\cap \big\{ I^L_m\cap V_{\text{sp}}\neq \emptyset \big\}.\end{align}
The event
$A_{\text{sp}}(\mathbf{0})$
ensures that for all
$m \geq 1$
, each of the sets
$I^R_m$
and
$I^L_m$
has at least one special point. Figure 2 presents an illustration of the event
$A_{\text{sp}}(\mathbf{0})$
. The event
$A_{\text{sp}}(\mathbf{0})$
prepares a ‘shield’ using special points which ensures that the path
$\{h^j(\mathbf{0}) \;:\; j \geq 1\}$
cannot cross the parabolic curve
$\Upsilon$
and must stay inside the region
$\nabla(\mathbf{0})$
throughout. Hence, we have
$A_{\text{sp}}(\mathbf{0}) \subseteq \text{In}(\mathbf{0})$
. For
$\mathbf{u} \in \mathbb{Z}^2$
, the notation
$A_{\text{sp}}(\mathbf{u})$
denotes the event
$A_{\text{sp}}(\mathbf{0})$
translated to the point
$\mathbf{u}$
. Therefore, the occurrence of the event
$A_{\text{sp}}(h^j(\mathbf{x}_1))$
implies the occurrence of the event
$\text{In}(h^j(\mathbf{x}_1))$
. We observe that the event
$A_{\text{sp}}(h^j(\mathbf{x}_1))$
involves points from the set
$V^{+}_{j}$
only (recall that
$\mathbf{x}_1(2)=0 $
) and it is independent of the
$\sigma$
-field
$\mathcal{F}_j$
. This gives
\begin{align*}\mathbb{P}(\text{In}(h^j(\mathbf{x}_1)) \mid \mathcal{F}_j) & \geq \mathbb{P}\big(A_{\text{sp}}\big(h^j(\mathbf{x}_1)\big) \mid \mathcal{F}_j\big)\\[5pt] & = \mathbb{P}\big(A_{\text{sp}}\big(h^j(\mathbf{x}_1)\big)\big)\\[5pt] & = \mathbb{P}(A_{\text{sp}}(\mathbf{0})) \\[5pt] & = \prod_{m=1}^{\infty} \big(1 - (1- \tilde{p})^{2m-1}\big)^2 \gt 0,\end{align*}
where
$\tilde{p}$
is as in (12). In the penultimate equality we have used the translation invariance nature of our model. This completes the proof for the case
$k=1$
.
We note here that the ‘shield’ construction using the event
$A_{\text{sp}}$
, which is based on special points, uses the fact that
$V \subset \mathbb{Z}^2$
. We now complete the proof for
$k \geq 2$
. For any
$j \geq 1$
, we observe the following inclusion of events:
\begin{align*}\bigcap_{i=1}^k A_{\text{sp}}\big(h^j(\mathbf{x}_i)\big) \subseteq\bigcap_{i=1}^k \text{In}\big(h^j(\mathbf{x}_i)\big).\end{align*}
Further, given
$(h^j(\mathbf{x}_1), \ldots, h^j(\mathbf{x}_k)) = (\mathbf{w}_1, \ldots, \mathbf{w}_k)$
, the events
$A_{\text{sp}}(h^j(\mathbf{x}_i)) = A_{\text{sp}}(\mathbf{w}_i)$
for
$1 \leq i \leq k$
are expressed in terms of special points only in the upper half-plane
$\mathbb{H}^+(j)$
, and all of them are increasing. Noting that the
$\sigma$
-field
$\mathcal{F}_j$
does not have any information about the point set
$V^+_j$
, we find that an application of the FKG property together with the translation invariance of our model gives
\begin{align*}\mathbb{P} \Bigg( \bigcap_{i=1}^k A_{\text{sp}}\big(h^j(\mathbf{x}_i)\big) \mid \mathcal{F}_j\Bigg )\geq \mathbb{P} (A_{\text{sp}}(\mathbf{0}))^k \gt 0.\end{align*}
This completes the proof.
We are now ready to prove Proposition 2. Our idea is to look for the occurrence of the ‘In’ event at the first step
$(h(\mathbf{x}_1), \ldots , h(\mathbf{x}_k))$
, which, we know from Lemma 2, has a strictly positive probability of occurrence. It is important to observe that given that the ‘In’ event has not occurred at the first step this gives us some information about the point set
$V^+_1$
which prevents us from applying Lemma 2 directly at the next step
$(h^{2}(\mathbf{x}_1), \ldots, h^{2}(\mathbf{x}_k))$
. We first prove Proposition 2 for
$j=0$
, and then we prove it for general
$j\geq 1$
.
Proof of Proposition 2 for
$j = 0$
. Given
$\mathcal{F}_1$
, we test for the occurrence of the ‘In’ event at the first step
$(h(\mathbf{x}_1), \ldots, h(\mathbf{x}_k))$
. By Lemma 2 we see that
When the ‘In’ event does not occur at the first step
$(h(\mathbf{x}_1), \ldots, h(\mathbf{x}_k))$
, we wait for the joint exploration process to discover this fact, i.e. until the first time one of the k paths steps outside its respective parabolic region. For
$\mathbf{u} \in \mathbb{Z}^2$
, let
$\beta(\mathbf{u})$
denote the random variable defined as
\begin{align*}\beta(\mathbf{u}) \;:\!=\;\min\{ n \in \mathbb{N} \;:\; h^{n}(\mathbf{u}) \notin \nabla(\mathbf{u}) \}.\end{align*}
Set
$\beta_0 = 0$
and
$\beta_1 \;:\!=\; \min\{\beta(h(\mathbf{x}_i)) \;:\; 1 \leq i \leq k\}$
.
The random variable
$\beta_1 $
may take the value
$+ \infty$
with positive probability, which implies the occurrence of the ‘In’ event. Also, on the event
$\{\tau_1 \gt 1\}$
the random variable
$\beta_1$
is finite. Indeed, the two events,
$\{\tau_1 \gt 1\}$
and
$\{\beta_1 \lt + \infty \}$
, are equal. Further, we observe that
$\beta_1$
is a stopping time with respect to the filtration
$\{\mathcal{F}_n \;:\; n \in \mathbb{N}\}$
, and we have
\begin{align*}\{\tau_1 \gt 1\} = \{\beta_1 \lt + \infty \} \in \mathcal{F}_{\beta_1}.\end{align*}
On the event
$ \{\beta_1 \lt + \infty \}$
, the
$\sigma$
-field
$\mathcal{F}_{\beta_1}$
does not have any information about the set
$V^+_{\beta_1}$
where
$V^+_{\beta_1}$
is defined as in (7). We can check for the occurrence of the ‘In’ event again at the
$(\beta_1 + 1)$
th step and apply Lemma 2 here. Let
$\mathbf{1}_{A}$
denote the indicator random variable for the event A. Thus we have
On the event
$\{\beta_1 \lt \infty\}$
, starting from the
$(\beta_1 + 1)$
th step, we define the random variable
$\beta_2 \;:\!=\; \beta_1 + \min\{\beta(h^{\beta_1 + 1}(\mathbf{x}_i)) \;:\; 1 \leq i \leq k\}$
, which is also a stopping time.
The event
$\{\beta_2 = + \infty\}$
implies the occurrence of the event
$\bigcap_{i=1}^k \text{In}(h^{\beta_1 + 1}(\mathbf{x}_i))$
, and we have
$\tau_2 = \beta_1 + 1$
. Otherwise, on the event
$\{\beta_2 \lt \infty\}$
the
$\sigma$
-field
$\mathcal{F}_{\beta_2}$
does not have information about the set
$V^+_{\beta_2}$
, and we have
Continuing in this fashion, we obtain that the number of
$\beta_j$
’s explored to find
$\tau_1$
is dominated by a geometric random variable with success probability
$p_0^k$
, where
$p_0^k$
is as in Lemma 2. Unfortunately, we do not have independence of
$\beta_j$
’s. Because of Lemma 1, to prove Proposition 2 it suffices to show that for any
$j \geq 0$
, given
$\beta_j \lt \infty$
, the tail probability
$\mathbb{P}( n \lt (\beta_{j+1} - \beta_{j})\mathbf{1}_{\{\beta_j \lt \infty\}} \lt \infty \mid \mathcal{F}_{\beta_j} )$
decays exponentially in n.
We show this for
$j = 0$
. The same argument works for general
$j \geq 1$
. We observe that
\begin{align} \mathbb{P}( n \lt (\beta_1 - \beta_0 ) \mathbf{1}_{\{\beta_0 \lt \infty\}} \lt \infty) = \mathbb{P}( n \lt \beta_1 \lt \infty ) = \sum_{\ell =1}^\infty \mathbb{P}(\beta_1 = n + \ell ).\end{align}
To estimate the probability
$\mathbb{P}(\beta_1 = n + \ell )$
, we observe that the path starting from
$\mathbf{x}_i$
exits the parabolic region
$\nabla(\mathbf{x}_i)$
for the first time at the
$(n + \ell)$
th step only if there is no point of V, in particular, no special point within
$n+\ell$
distance of the vertex
$h^{n + \ell -1}(\mathbf{x}_i)$
on the line
$y = n + \ell$
. Hence, (14) becomes
\begin{align}\sum_{\ell =1}^\infty \mathbb{P}(\beta_1 = n + \ell ) & \leq \sum_{ \ell =1}^\infty \mathbb{P}\big( J_{\text{sp}}\big(h^{n + \ell -1}(\mathbf{x}_i)\big) \gt2(n + \ell ) - 1 \text{ for some }1 \leq i \leq k\big) \nonumber \\[5pt] & \leq k\sum_{\ell =1}^\infty (1 - \tilde{p})^{ 2(n + l) - 1} \nonumber \\[5pt] & \leq C_0 \exp{(\!-\!C_1 n)}\end{align}
for some
$C_0, C_1 \gt 0$
. This completes the proof of Proposition 2 for
$j = 0$
.
We now prove Proposition 2 for general
$j \geq 1$
. The problem is that the occurrence of the ‘In’ event depends on the infinite future. For
$j \geq 1$
, the collection of random vectors
$\{\Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{Z}^2, \mathbf{w}(2) \gt h^{\tau_j}(\mathbf{x}_1)(2) \}$
is no longer independent of the
$\sigma$
-field
$\mathcal{G}_j$
. To deal with this, for any
$j \geq 1$
, we represent the occurrence of the
$\tau_j$
th step as an intersection of the ‘In’ event at the last step and a
$\mathcal{F}_{\tau_j}$
measurable event. As an example, for the marginal process
$\{h^n(\mathbf{x}_1) \;:\; n \geq 0\}$
, the occurrence of the event
$(h^{\tau_1}(\mathbf{x}_1), \ldots , h^{\tau_j}(\mathbf{x}_1)) = ( \mathbf{v}_1, \ldots, \mathbf{v}_j)$
is represented as an intersection of the event
$\text{In}(\mathbf{v}_j)$
and an
$\mathcal{F}_{\mathbf{v}_j(2)}$
measurable event. For simplicity of notation we prove this for
$k=1$
, i.e. for the marginal process only. The same argument holds for general
$k \geq 1$
. Using this representation, we show that given
$\{(h^{\tau_1}(\mathbf{x}_1), \ldots , h^{\tau_j}(\mathbf{x}_1)) = (\mathbf{v}_1, \ldots, \mathbf{v}_j)\}$
, the probability of the occurrence of the ‘In’ event at the
$(\tau_j + l)$
th step is still bounded below by
$p_0$
for any
$l \geq 1$
. We recall that the random variable
$\beta(\mathbf{v})$
is defined as
$ \beta(\mathbf{v}) \;:\!=\; \inf\{ l \geq 1\;:\; h^{l}(\mathbf{v}) \notin \nabla(\mathbf{v})\}$
.
Lemma 5. For any
$\mathbf{v} \in \mathbb{H}^+(0)$
with
$\ell = \mathbf{v}(2)$
we have the following equality of events:
\begin{align*} \{ h^{\tau_1}(\mathbf{x}_1) = \mathbf{v}, \tau_1 = \ell \} & = \Bigg [ \big\{ h^\ell(\mathbf{x}_1) = \mathbf{v} \big\} \cap\Bigg [ \bigcap_{j=1}^{ \ell -1}\bigl ( \big\{ \beta(h^j(\mathbf{x}_1)) \leq \ell - j \big\} \bigr ) \Bigg ] \Bigg ]\cap (\text{In}(\mathbf{v})).\end{align*}
Proof. By the definition of the
$\tau_1$
step, we have
\begin{align*}\big\{\tau_1 = \ell, h^\ell(\mathbf{x}_1) = \mathbf{v} \big\} &= \big\{h^\ell(\mathbf{x}_1) = \mathbf{v}, \text{In}(\mathbf{v})\big\}\cap \Bigg [ \bigcap_{j=1}^{\ell - 1}\big( \big\{h^j(\mathbf{x}_1) \text{ is not a }\tau\text{ step}\big\}\big) \Bigg]\\[5pt] & = \big\{h^\ell(\mathbf{x}_1) = \mathbf{v}, \text{In}(\mathbf{v})\big\} \cap \Bigg[ \bigcap_{j=1}^{\ell-1} \big(\big\{\beta(h^j(\mathbf{x}_1)) \lt \infty \big\}\big) \Bigg].\end{align*}
To complete the proof, for
$1 \leq j \leq \ell-1$
we need to show that
\begin{align*} \big\{h^\ell(\mathbf{x}_1) = \mathbf{v}, \text{In}(\mathbf{v}), \beta\big(h^j(\mathbf{x}_1)\big) \lt \infty \big\} =\big\{h^\ell(\mathbf{x}_1) = \mathbf{v}, \text{In}(\mathbf{v}),\beta\big(h^j(\mathbf{x}_1)\big) \leq \ell - j \big\}. \end{align*}
We prove it for
$j =1$
, and the argument is exactly the same for general
$j \geq 1$
. On the event
$\{h^\ell(\mathbf{x}_1) = \mathbf{v}, \text{In}(\mathbf{v}), \beta(h(\mathbf{x}_1)) \gt \ell \}$
, we must have
\begin{align*}h^{\ell}(\mathbf{x}_1) = \mathbf{v} \in \nabla(\mathbf{x}_1).\end{align*}
Otherwise
$\beta(\mathbf{x}_1)$
must be smaller than
$\ell$
. Furthermore, on the event
\begin{align*}\text{In}(\mathbf{v}) \cap \big\{h^j(\mathbf{x}_1) = \mathbf{v} \in \nabla(\mathbf{x}_1)\big\},\end{align*}
the nesting property as mentioned in (9) implies that
\begin{align*}h^{\ell + m}(\mathbf{x}_1) = h^m(\mathbf{v}) \in \nabla(\mathbf{v}) \subset \nabla(\mathbf{x}_1) \text{ for all }m \geq 1.\end{align*}
Hence, on the event
$\{h^\ell(\mathbf{x}_1) = \mathbf{v}, \text{In}(\mathbf{v}), \beta(\mathbf{x}_1) \gt \ell \}$
, the random variable
$\beta(\mathbf{x}_1)$
must take the value
$+\infty$
. This implies that the events
$ \{ h^\ell(\mathbf{x}_1) = \mathbf{v}, \text{In}(\mathbf{v})\}$
and
$ \{ \ell \lt \beta(\mathbf{x}_1) \lt +\infty \}$
cannot occur simultaneously, and this completes the proof.
Remark 2. We observe that in Lemma 5 the event
\begin{align*}\big\{ h^\ell(\mathbf{x}_1) = \mathbf{v} \big\} \cap \Bigg[ \bigcap_{j=0}^{\ell-1} \big( \big\{ \beta\big(h^j(\mathbf{x}_1)\big) \leq \ell - j \big\} \big) \Bigg ]\end{align*}
is
$\mathcal{F}_\ell$
measurable by construction.
We would like to have a similar result for the
$\tau_j$
th (
$ j \geq 2$
) step. Considering the event
\begin{align*}\big\{ \tau_1 = \ell_1, h^{l_1}(\mathbf{x}_1) = \mathbf{v}_1, \tau_2 = \ell_1 + \ell_2, h^{\ell_1 + \ell_2}(\mathbf{x}_1) = \mathbf{v}_2 \big\},\end{align*}
the main difficulty is that both events,
$\text{In}(\mathbf{v}_1)$
and
$\text{In}(\mathbf{v}_2)$
, depend on the infinite future. To deal with this, for
$\ell \in \mathbb{N}$
and
$\mathbf{v} \in \mathbb{Z}^2$
, we define the event
$\text{In}^{(\ell)}(\mathbf{v})$
, which is a truncated version of the event
$\text{In}(\mathbf{v}_1)$
, as
\begin{align*}\text{In}^{(\ell)}(\mathbf{v}) \;:\!=\; \{h^m(\mathbf{v}) \in \nabla(\mathbf{v}) \text{ for all }1 \leq m \leq \ell \}.\end{align*}
Clearly, for any
$\ell \in \mathbb{N}$
we have
$\text{In}(\mathbf{v}) \subset \text{In}^{(\ell)}(\mathbf{v})$
. We observe that the event
$\text{In}^{(\ell)}(\mathbf{v})$
is
$\mathcal{F}_{\mathbf{v}(2) + \ell}$
measurable.
The nesting property as mentioned in (9) ensures that on the event
$\text{In}(\mathbf{v})$
for any
$\ell \geq 1$
we have
$ \nabla(h^\ell(\mathbf{v})) \subset \nabla(\mathbf{v}) $
. This allows us to have the following equality of events:
\begin{align*} \text{In}(\mathbf{v}) \cap \text{In}(h^j(\mathbf{v})) & = \text{In}^{(j)}(\mathbf{v})\cap \text{In}(h^j(\mathbf{v})) \text{ for any }j \geq 1.\end{align*}
Using the above reasoning, we express the event
\begin{align*}\big\{ \tau_1 = m_1, \tau_2 = m_2, h^{m_1}(\mathbf{x}_1) = \mathbf{v}_1, h^{m_2}(\mathbf{x}_1) = \mathbf{v}_2 \big\}\end{align*}
as
\begin{align}& \big [ \big\{ h^j(\mathbf{x}_1) \text{ is not a }\tau \text{ step for any } 1 \leq j \lt m_1, h^{m_1}(\mathbf{x}_1) = \mathbf{v}_1,\text{In}^{ (m_2 - m_1)}(\mathbf{v}_1) \big\} \nonumber\\[5pt] & \cap\big\{ h^j(\mathbf{x}_1) \text{ is not a }\tau \text{ step for any } m_1 \lt j \lt m_2,h^{m_2}(\mathbf{x}_1) = \mathbf{v}_2\big\} \big ]\cap \text{In}(\mathbf{v}_2).\end{align}
As observed earlier, other than the event
$\text{In}(\mathbf{v}_2)$
in (16), the rest of the events are
$\mathcal{F}_{m_2}$
measurable. In fact, (16) can be further strengthened for any
$j \geq 1$
as described in the following remark.
Remark 3. For any
$j \geq 1$
we have the following equality of events:
\begin{align*}\bigcap_{\ell = 1}^j \big\{\tau_\ell = m_\ell,h^{m_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell \big\} =& \Bigg [ \bigcap_{\ell = 1}^j \big\{ h^{m_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell\big\}\cap \Bigg \{ \bigcap_{n = m_{\ell-1}+ 1}^{m_\ell - 1}\big( \beta\big(h^n(\mathbf{x}_1)\big) \leq m_\ell - n\big)\Bigg \}\\[5pt] & \cap \Bigg(\bigcap_{ \ell = 1}^{j-1}\text{In}^{ (m_{(\ell + 1)} - m_\ell)}(\mathbf{v}_\ell) \Bigg)\Bigg ]\cap \text{In}(\mathbf{v}_j).\end{align*}
Other than the event
$\text{In}(\mathbf{v}_j)$
, the rest of the events on the right-hand side are
$\mathcal{F}_{\mathbf{v}_\ell(2)} = \mathcal{F}_{m_\ell}$
measurable.
For simplicity of notation, we write
\begin{align*}E(\mathbf{v}_1, \ldots , \mathbf{v}_j) \;:\!=\;\Bigg [ & \bigcap_{\ell = 1}^j \big\{ h^{m_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell\big\}\cap \Bigg \{ \bigcap_{n = m_{\ell - 1} + 1}^{m_\ell - 1}\big( \beta\big(h^n(\mathbf{x}_1)\big) \leq m_\ell - n\big)\Bigg \} \\[5pt] & \cap \Bigg(\bigcap_{l=1}^{j-1}\text{In}^{( m_{\ell + 1} - m_\ell)}(\mathbf{v}_\ell) \Bigg)\Bigg ].\end{align*}
Now we are ready to prove Proposition 2 for
$j \geq 1$
.
Proof of Proposition
2 for
$j \geq 1$
. Fix
$j \geq 1$
. Given
$(h^{\tau_1}(\mathbf{x}_1), \ldots , h^{\tau_j}(\mathbf{x}_1)) = (\mathbf{w}_1,\ldots , \mathbf{w}_j)$
, for any
$\ell \geq 1$
we obtain
\begin{align*}& \mathbb{P} \bigl( \text{In}\big(h^{\tau_j + \ell}(\mathbf{x}_1)\big) \mid \big(h^{\tau_1}(\mathbf{x}_1), \ldots , h^{\tau_j}(\mathbf{x}_1)\big) = (\mathbf{w}_1,\ldots , \mathbf{w}_j)\bigr) \\[5pt] & = \mathbb{P} \bigl( \text{In}\big(h^{\ell}(\mathbf{w}_j)\big) \mid ( E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}(\mathbf{w}_j))\bigr) \\[5pt] & = \mathbb{P} \bigl ( \text{In}\big(h^{\ell}(\mathbf{w}_j)\big) \cap ( E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}(\mathbf{w}_j) )\bigr )/\mathbb{P}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}(\mathbf{w}_j) ) \\[5pt] & = \mathbb{P} \bigl ( \text{In}\big(h^{\ell}(\mathbf{w}_j)\big) \cap ( E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}^{(\ell)}(\mathbf{w}_j) )\bigr )/\mathbb{P}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}(\mathbf{w}_j) ) \\[5pt] & \geq \mathbb{P} \bigl ( A_{\text{sp}}\big(h^{\ell}(\mathbf{w}_j)\big) \cap ( E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}^{(\ell)}(\mathbf{w}_j) )\bigr )/\mathbb{P}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}(\mathbf{w}_j) ) \\[5pt] & = \mathbb{P}\big(A_{\text{sp}}\big(h^{\ell}(\mathbf{w}_j)\big)\big)\bigl ( \mathbb{P} \bigl ( E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}^{(\ell)}(\mathbf{w}_j) \bigr )/\mathbb{P}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}(\mathbf{w}_j) ) \bigr) \\[5pt] & \geq \mathbb{P}(A_{\text{sp}}(\mathbf{0})).\end{align*}
In the last step, together with the translation invariance nature of our model, we use the fact that
\begin{align*}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}(\mathbf{w}_j) )\subset\bigl ( E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}^{(\ell)}(\mathbf{w}_j) \bigr ).\end{align*}
The penultimate step follows from the fact that the event
$A_{\text{sp}}(h^{\ell}(\mathbf{w}_j))$
depends on the collection
$\{\Gamma_w \;:\; \mathbf{w}(2) \gt \mathbf{w}_j(2) + l \}$
and is independent of the event
$( E(\mathbf{w}_1,\ldots , \mathbf{w}_j)\cap \text{In}^{(\ell)}(\mathbf{w}_j) )$
as it is
$\mathcal{F}_{\mathbf{w}_j(2) + \ell}$
measurable.
Given
$(h^{\tau_1}(\mathbf{x}_1), \ldots , h^{\tau_j}(\mathbf{x}_1)) = (\mathbf{w}_1,\ldots , \mathbf{w}_j)$
, using a similar argument, for any
$\mathbf{v} \in \mathbb{H}^+(\mathbf{w}_j)(2)$
and
$\ell \geq 1$
, we have
\begin{align}& \mathbb{P} ( J_{\text{sp}}(\mathbf{v}) \gt \ell \mid (h^{\tau_1}(\mathbf{x}_1), \ldots , h^{\tau_j}(\mathbf{x}_1)) = (\mathbf{w}_1,\ldots , \mathbf{w}_j) ) \nonumber \\[5pt] & = \mathbb{P} ( J_{\text{sp}}(\mathbf{v}) \gt \ell \mid E(\mathbf{w}_1,\ldots , \mathbf{w}_j) \cap \text{In}(\mathbf{w}_j) ) \nonumber \\[5pt] & = \mathbb{P} ( (J_{\text{sp}}(\mathbf{v}) \gt \ell ) \cap E(\mathbf{w}_1,\ldots , \mathbf{w}_j) \cap \text{In}(\mathbf{w}_j) ) /\mathbb{P}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j) \cap \text{In}(\mathbf{w}_j))\nonumber \\[5pt] & \leq \mathbb{P} ( (J_{\text{sp}}(\mathbf{v}) \gt \ell ) \cap E(\mathbf{w}_1, \ldots , \mathbf{w}_j) ) /\mathbb{P}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j) \cap \text{In}(\mathbf{w}_j))\nonumber \\[5pt] & \leq \mathbb{P} ( ( J_{\text{sp}}(\mathbf{v}) \gt \ell ) \cap E(\mathbf{w}_1, \ldots , \mathbf{w}_j) ) /\mathbb{P}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j) \cap A_{\text{sp}}(\mathbf{w}_j))\nonumber \\[5pt] & = \mathbb{P} ( J_{\text{sp}}(\mathbf{v}) \gt \ell ) \mathbb{P} ( E(\mathbf{w}_1,\ldots , \mathbf{w}_j) )( \mathbb{P}(E(\mathbf{w}_1,\ldots , \mathbf{w}_j)) \mathbb{P}(A_{\text{sp}}(\mathbf{w}_j)) )^{-1}\nonumber \\[5pt] & = \mathbb{P} ( J_{\text{sp}}(\mathbf{v}) \gt \ell ) \mathbb{P}(A_{\text{sp}}(\mathbf{0}))^{-1}\nonumber \\[5pt] & \leq C_0 \exp{(\!-\!C_1 \ell)}\end{align}
for some
$C_0, C_1 \gt 0$
that do not depend on j. In the penultimate equality, we have used the fact that the event
$E(\mathbf{w}_1, \ldots , \mathbf{w}_j)$
is
$\mathcal{F}_{\mathbf{w}_j(2)}$
measurable and independent of the events
$\{J_{\text{sp}}(\mathbf{v}) \gt \ell \}$
and
$A_{\text{sp}}(\mathbf{w}_j)$
. The last step follows from the translation invariance nature of our model.
Equation (17) allows us to repeat the calculations in (15) for general
$j \geq 1$
. The rest of the argument is exactly the same as in the case of
$j=0$
. This completes the proof.
3. Renewal steps
Fix
$j \geq 1$
. For each
$1 \leq i \leq k$
the path starting from
$h^{\tau_j}(\mathbf{x}_i)$
given by
$\{h^{\tau_j + n}(\mathbf{x}_i) \;:\; n \geq 1 \}$
must stay inside the region
$\nabla(h^{\tau_j}(\mathbf{x}_i))$
. Note that for an open vertex
$\mathbf{w} \in \mathbb{H}^-(\tau_j)$
, its perturbed version
$\tilde{\mathbf{w}}$
can affect the distribution of the joint process starting from
$(h^{\tau_j}(\mathbf{x}_1), \ldots , h^{\tau_j}(\mathbf{x}_k))$
only if
$\tilde{\mathbf{w}} \in \bigcup_{i=1}^k \nabla(h^{\tau_j}(\mathbf{x}_i)) \text{ for some }1 \leq i \leq k$
. This motivates us to consider the set
\begin{align}H_{\tau_j} = H_{\tau_j}(\mathbf{x}_1, \ldots , \mathbf{x}_k) \;:\!=\; I_{\tau_j}(\mathbf{x}_1, \ldots , \mathbf{x}_k) \cap \Bigg ( \bigcup_{i=1}^k \nabla\big(h^{\tau_j}(\mathbf{x}_i)\big) \Bigg),\end{align}
where
$I_n$
is defined as in (8). Below, we define a sequence of what we call renewal steps. Set
$\gamma_0 = 0$
, and for
$\ell \geq 1$
define
\begin{align*}\gamma_\ell = \gamma_\ell(\mathbf{x}_1, \ldots , \mathbf{x}_k) \;:\!=\; \inf\{ j \gt \gamma_{\ell - 1} \;:\;H_{\tau_j}(\mathbf{x}_1, \ldots , \mathbf{x}_k) = \emptyset \},\end{align*}
where
$H_{\tau_j}(\mathbf{x}_1, \ldots , \mathbf{x}_k)$
is defined as in (18).
Joint renewal for two paths. The ‘In’ event condition ensures that PH paths must stay inside the respective
$\nabla(\!\cdot\!)$
regions. The ‘Out’ event condition ensures that perturbed versions of all open points in the lower half-plane (grey shading) must be outside the
$\nabla(\!\cdot\!)$
regions.
We need to show that for all
$\ell \geq 1$
the random variable
$\gamma_\ell$
is well defined in the sense that
$\gamma_\ell$
is finite a.s. A stronger result is proved in Proposition 4. For the moment, we proceed by assuming that
$\gamma_\ell$
is a.s. finite for all
$\ell \geq 1$
. Note that
$\gamma_\ell$
denotes the total number of
$\tau$
steps, i.e. the number of ‘In’ steps required for the
$\ell$
th renewal step, and the random variable
$\sigma_\ell \;:\!=\; \tau_{\gamma_\ell}$
denotes the total number of steps required for the
$\ell$
th occurrence of the renewal event.
We observe that the condition
$H_{\tau_j}(\mathbf{x}_1, \ldots , \mathbf{x}_k) = \emptyset$
implies that points from the lower half-plane
$\mathbb{H}^-(\tau_j)$
are not allowed to be perturbed inside
$\bigcup_{i=1}^k \nabla(h^{\tau_j}(\mathbf{x}_i))$
. For
$\mathbf{u} \in \mathbb{Z}^2$
we define the event
$\text{Out}(\mathbf{u})$
as
\begin{align*}\text{Out}(\mathbf{u}) \;:\!=\; \{ V^-_{\mathbf{u}(2)} \cap \nabla(\mathbf{u}) = \emptyset \} .\end{align*}
For the joint process
$\{(h^j(\mathbf{x}_1), \ldots , h^j(\mathbf{x}_k)) \;:\; j \geq 1\}$
we say that the ‘Out’ event occurs at the nth step if the event
$\bigcap_{i=1}^k \text{Out}(h^n(\mathbf{x}_i))$
occurs. In other words, the occurrence of a renewal event implies the joint occurrence of the ‘In’ event and the ‘Out’ event. For an illustration, see Figure 3.
The event
$ \text{Out}(\mathbf{u})$
is
$\mathcal{F}_{\mathbf{u}(2)}$
measurable, and for any
$\ell \geq 1$
the random variable
$\gamma_\ell$
is a stopping time with respect to the filtration
$\{\mathcal{G}_j \;:\; j \geq 1\}$
as defined in (10). This allows us to define the filtration
\begin{align}\{\mathcal{S}_\ell \;:\!=\; \mathcal{G}_{\gamma_\ell} \;:\; \ell \geq 1\}.\end{align}
For each
$\ell \geq 1$
, the random variable
$\sigma_\ell$
and the random vector
$(h^{\sigma_\ell}(\mathbf{x}_1), \ldots, h^{\sigma_\ell}(\mathbf{x}_k))$
are
$\mathcal{S}_\ell$
measurable. The next proposition is the main result of this section, and states that the total number of steps between any two successive renewal steps has strong uniform exponential tail decay.
Proposition 3. Fix any
$\ell \geq 0$
. For all
$n \in \mathbb{N}$
we have
\begin{align*}\mathbb{P}((\sigma_{\ell + 1} - \sigma_{\ell}) \gt n \mid \mathcal{S}_\ell)\leq C_0 \exp{(\!-\!C_1 n)}\end{align*}
for some
$C_0, C_1 \gt 0$
that do not depend on
$\ell$
or on the starting points.
Proposition 4 shows that the family of random variables
$\{\gamma_\ell \;:\;\ell \geq 1\}$
, denoting the number of
$\tau$
steps required between two successive renewals, exhibits strong uniform exponential tail decay (see Definition 1).
Proposition 4. Fix
$\ell \geq 0$
. The number of
$\tau$
steps between the
$(\ell + 1)$
th renewal and the
$\ell$
th renewal is represented by
$(\gamma_{\ell + 1} - \gamma_{\ell})$
, and for all
$n \in \mathbb{N}$
we have
\begin{align*}\mathbb{P}((\gamma_{\ell + 1} - \gamma_{\ell}) \gt n \mid \mathcal{S}_\ell)\leq C_0 \exp{(\!-\!C_1 n)}\end{align*}
for some
$C_0, C_1 \gt 0$
which does not depend on
$\ell$
.
Assuming Proposition 4, we complete the proof of Proposition 3.
Proof of Proposition
3. By definition, for
$\ell \geq 1$
the random variable
$\sigma_\ell$
satisfies
\begin{align*}\sigma_\ell = \sum_{j = \gamma_{\ell-1}}^{\gamma_{\ell}} \tau_j .\end{align*}
Proposition 2 gives us that the family
$\{\tau_j \;:\; j \geq 1\}$
has a strong uniform exponential tail decay, and Proposition 4 gives us the same for the family
$\{\gamma_\ell \;:\; \ell \geq 1\}$
; therefore, Proposition 3 follows from Lemma 1.
To prove Proposition 4, we define a height process
$\{ L_j \;:\; j \geq 1 \}$
such that
$L_j$
equals zero if and only if the set
$H_{\tau_j} $
(as defined in (18)) becomes empty. We recall that the joint exploration process of k paths starts from
$\mathbf{x}_1,\ldots, \mathbf{x}_k$
with
$\mathbf{x}_1(2) = \cdots = \mathbf{x}_k(2) = 0$
. We define our height process as follows. Set
$L_0 = 0$
and define
$L_1$
as
\begin{align*}L_1 \;:\!=\; \sup\{ \mathbf{w}(2) - \tau_1 \;:\; \mathbf{w} \in H_{\tau_1} \!\}\vee 0= \inf\{n \geq 0 \;:\; \mathbb{H}^+(\tau_1 + n) \cap H_{\tau_1} = \emptyset \},\end{align*}
where
$H_1$
is defined as in (18). More generally, for
$j \geq 1$
we define the height process
$L_j$
as
\begin{align*}L_j \;:\!=\; \sup\{ \mathbf{w}(2) - \tau_j \;:\; \mathbf{w} \in H_{\tau_j} \}\vee 0= \inf\{n \geq 0 \;:\; \mathbb{H}^+(\tau_j + n) \cap H_{\tau_j} = \emptyset \}.\end{align*}
By definition, we have
\begin{align*}\{L_j = 0\} = \{H_{\tau_j}= \emptyset\}.\end{align*}
Hence, for any
$\ell \geq 1$
we have the equivalent representation of the random variable
$\gamma_\ell$
as
$\gamma_\ell \;:\!=\; \inf\{j \gt \gamma_{\ell-1} \;:\; L_j = 0\}$
.
We note that the height process
$\{L_j \;:\; j \geq 0\}$
is non-negative and not Markov. Regarding the evolution of this process:
-
(i) we obtain an important recursion relation (see (20)) in Subsection 3.1;
-
(ii) we show that the incremental increase of the height process,
$(L_{j+1} - L_{j})\mathbf{1}_{\{ L_{j+1} \gt L_{j} \}}$
, for
$j \geq 0$
exhibits strong uniform exponentially decaying tail behaviour; -
(iii) Lemma 9 in Subsection 3.2 gives us a strictly positive uniform lower bound for the probability that
$L_j$
decreases by at least 1 at the next step.
These properties allow us to construct a non-negative integer-valued geometrically ergodic Markov chain which stochastically dominates the evolution of
$\{L_j \;:\; j \geq 0\}$
and prove Proposition 4. The details are presented in Subsections 3.1 and 3.2.
3.1. A (stochastic) bound to control the increase in
$L_j$
Fix
$j \geq 0$
. Given the
$\sigma$
-field
$\mathcal{G}_j$
, we consider the evolution of the joint process between the
$\tau_j$
th step and the
$\tau_{j+1}$
th step. The ‘newly’ explored vertices are perturbed versions of open vertices coming from the region
$\mathbb{H}^-(\tau_{j+1}) \setminus \mathbb{H}^-(\tau_{j})$
, i.e. vertices that are explored between the
$\tau_j$
th step and the
$\tau_{j+1}$
th step. The contribution of these newly explored vertices to
$L_{j+1}$
is denoted by a random variable
$X_{j+1}$
defined as
\begin{align*}X_{j+1} \;:\!=\; 1 +\sup \Bigg\{ (\tilde{\mathbf{w}}(2) - \tau_{j+1})\vee 0 \;:\; \mathbf{w} \in \mathbb{H}^-(\tau_{j+1}) \setminus\mathbb{H}^-(\tau_{j}), \tilde{\mathbf{w}} \in \bigcup_{i=1}^k \nabla(h^{\tau_{j+1}}(\mathbf{x}_i)) \Bigg\}.\end{align*}
Actually, the random variable
$X_{j+1}$
represents one excess to the actual contribution. The reason behind this modification is to ensure that the recursion relation (20) holds with probability 1. The following lemma gives a recursion relation which bounds the amount of increase in
$L_j$
.
Lemma 6. For
$j \geq 1$
we have
\begin{align}L_{j+1} \leq \max\{ L_j, X_{j+1}\} - 1 \textit{ a.s.}\end{align}
Proof. For
$\mathbf{w} \in \mathbb{H}^-(\tau_j)$
the corresponding random vector
$\Gamma_{\mathbf{w}}$
(defined as in (1)) has already been explored by the
$\sigma$
-field
$\mathcal{G}_j$
; henceforth, such vertices will be called an older vertex. We observe that for any ‘older’ lattice point
$\mathbf{w}$
, which does not contribute to
$L_j$
, two situations can occur:
-
(i)
$\mathbf{w}$
is closed, i.e. it is not open; -
(ii)
$\mathbf{w}$
is a open but
$\tilde{\mathbf{w}} \notin \bigcup_{i=1}^k \nabla(h^{\tau_j}(\mathbf{x}_i))$
.
By the nesting property (9), we have
$\nabla(h^{\tau_{j+1}}(\mathbf{x}_i))\subseteq \nabla(h^{\tau_{j}}(\mathbf{x}_i))$
for all
$1 \leq i \leq k$
. It follows that in both situations (i) and (ii), such an older vertex
$\mathbf{w}$
, which does not contribute to
$L_j$
, cannot contribute to
$L_{j+1}$
as well. Since at each time the path goes up by one step, for any older vertex
$\mathbf{w}$
contributing to
$L_{j}$
, its contribution to
$L_{j+1}$
decreases by at least 1 compared with its contribution to
$L_{j}$
.
The above discussion suggests that we can have
$L_{j+1} \geq L_j$
because of contributions from newly explored vertices only. Hence, the recursion relation (20) follows from the definition of the random variable
$X_{j+1}$
.
Next we show that the family of random variables
$\{ X_j \;:\; j \geq 1\}$
exhibits strong uniform exponentially decaying tail behaviour such that the positive constants
$C_0, C_1$
in (21) do not depend on the choice of starting points
$\mathbf{x}_1, \ldots, \mathbf{x}_k$
or on j.
Lemma 7. Fix any
$j \geq 1$
. For all large n there exist
$C_0, C_1 \gt 0$
such that we have
\begin{align}\mathbb{P}(X_{j} \gt n \mid \mathcal{G}_{j-1}) \leq C_0 \exp{(\!-\!C_1 n)}.\end{align}
To prove Lemma 7 we need some notation. For
$\mathbf{w} \in \mathbb{Z}^2$
we define the ‘total’ perturbation random variable as
$T_{\mathbf{w}} \;:\!=\; |X_{\mathbf{w}}| + Y_{\mathbf{w}}$
. The distribution of the random vector
$\Lambda_{\mathbf{w}}$
ensures that the tail of the random variable
$T_{\mathbf{w}}$
decays exponentially. For
$\mathbf{w} \in \mathbb{Z}^2$
and
$m \in \mathbb{Z}$
we denote the infinite downward ray of lattice points starting from
$\mathbf{w} + (m,0)$
as
\begin{align*}\mathbf{w}^{\downarrow}_m \;:\!=\; \{\mathbf{w} + (m, -\ell) \;:\; \ell \in \mathbb{N} \cup \{0\}\}.\end{align*}
A vertical ‘overshoot’ random variable, which represents the amount of overshoot in the upper half-plane
$\mathbb{H}^+(\mathbf{w}(2))$
, based on the collection
$\{T_{\mathbf{v}} \;:\; \mathbf{v} \in \mathbf{w}^{\downarrow}_m \}$
is defined as
\begin{align*}T^{\uparrow}_m(\mathbf{w}) \;:\!=\; \sup\{ T_{\mathbf{v}} - \ell \;:\; \mathbf{v} \in \mathbf{w}^{\downarrow}_m \text{ with } \mathbf{v}(2) = \mathbf{w}(2) - \ell \}.\end{align*}
The random variable
$T^{\uparrow}_m(\mathbf{w})$
is non-negative, and we have
\begin{align}\mathbb{P}\big(T^{\uparrow}_m(\mathbf{w}) \gt n\big) \leq \sum_{ \ell = 0}^\infty \mathbb{P}( T_{\mathbf{w} + (m, - \ell)} \gt n + \ell)\leq C_0 \exp{(\!-\!C_1 n)}\end{align}
for some
$C_0, C_1 \gt 0$
that do not depend on
$\mathbf{w}$
or m.
Remark 4. Note that to obtain (22) we require only a uniform exponential tail for the family
$\{ T_{\mathbf{v}} \;:\; \mathbf{v} \in \mathbf{w}^{\downarrow}_m \}$
.
Below we prove Lemma 7 for
$j = 1$
, and later we will indicate the modification required for general
$j \geq 2$
.
Proof of Lemma
7 for
$j = 1$
. We prove it for
$k = 1$
. The proof for general
$k \geq 1$
is exactly the same. Consider the following events:
\begin{align*}E^1_n & \;:\!=\; \{ \tau_1 \leq n/2 \} \quad\text{ and }\quad \\[5pt] E^2_n & \;:\!=\; \big\{ |\big(h^{j+1}(\mathbf{x}_1) - h^{j}(\mathbf{x}_1)\big)(1)| \leq n \text{ for all }0 \leq j \leq n/2 \big\},\end{align*}
and note that
\begin{align}\mathbb{P}(L_1 \geq n) = \mathbb{P}(X_1 \geq n) \leq \mathbb{P}\big( X_1 \geq n, E^1_n\cap E^2_n\big) +\mathbb{P}\big(\big(E^1_n\big)^c\big) + \mathbb{P}\big(\big(E^2_n\big)^c\big).\end{align}
From Proposition 2 it follows that
$\mathbb{P}((E^1_n)^c) \to 0 \text { as } n \to \infty$
, and we have
\begin{align*}& \mathbb{P}\big(\big(E^2_n\big)^c\big) \\[5pt] & \leq \mathbb{P}\Bigg( \bigcup_{j=0}^{\lfloor n/2 \rfloor } |\big(h^{j+1}(\mathbf{x}_1)-h^{j}(\mathbf{x}_1)\big)(1)| \gt n \Bigg)\\[5pt] & \leq \mathbb{P} \Bigg( \bigcup_{j=0}^{\lfloor n/2 \rfloor }\big(J_{\text{sp}}\big(h^{j}(\mathbf{x}_1)\big) \gt n\big) \Bigg )\\[5pt] & \leq (\lfloor n/2 \rfloor + 1) \mathbb{P}( J_{\text{sp}}(\mathbf{0}) \gt n ) \\[5pt] & \leq (\lfloor n/2 \rfloor + 1)(1 - p_0)^{n} \to 0 \text { as } n \to \infty,\end{align*}
where
$\tilde{p}$
is as in (12). We observe that on the event
$E^1_n \cap E^2_n$
we must have
$h^{\tau_1}(\mathbf{x}_1) \in [\!-\!n^2, n^2]\times$
$[0, n/2]$
. Consider the projections of the starting point
$\mathbf{x}_1$
on the lines
$y = - n$
and
$y = n$
respectively denoted as
$\mathbf{x}^{n,\downarrow}_1 = \mathbf{x}_1 + (0, - n)$
and
$\mathbf{x}^{n,\uparrow}_1 \;:\!=\; \mathbf{x}_1 + (0, \lfloor n/2 \rfloor)$
. The nesting property (9) ensures that on the event
$E^1_n \cap E^2_n$
we have
\begin{align*}\nabla\big(h^{\tau_1}(\mathbf{x}_1)\big) \subseteq \nabla\big(\mathbf{x}^{n,\downarrow}_1\big).\end{align*}
We refer the reader to Figure 4. On the event
$E^1_n \cap E^2_n\cap \{ X_1 \geq n\}$
, the random variable
$X_1$
is dominated by the maximum of the overshoot random variables
$\{ T_m(\mathbf{x}^{n,\uparrow}_1) \;:\; m \in \mathbb{Z} \}$
when overshoot is restricted to the region
$\nabla(\mathbf{x}^{n,\downarrow}_1)$
.
If the
$\tau_1$
step occurred within the rectangular box then
$\nabla(h^{\tau_1}(\mathbf{x}_1))$
is contained in
$\nabla(\mathbf{x}^{n,\downarrow}_1)$
. Therefore, on this event the maximum overshoot amount due to the total perturbation random variables attached to lattice points in the shaded region (which extends to the infinite lower half-plane) dominates
$L_1$
as well as the random variable
$X_1$
.
On the event
$ E^1_n\cap E^2_n$
in order to have
$X_1 \gt n$
, we must have either of the following:
-
(i)
$T^\uparrow_m(\mathbf{x}^{n,\uparrow}_1) \gt n/2$
for some
$m \in[\!-(3n/2)^2, (3n/2)^2]\cap \mathbb{Z}$
; -
(ii)
$T^\uparrow_m(\mathbf{x}^{n,\uparrow}_1) \gt n/2 + l$
for some m in either
$[-(3n/2 + l)^2,-(3n/2 + (l-1))^2]\cap \mathbb{Z}$
or
$[(3n/2 + (l-1))^2,(3n/2 + l)^2]\cap \mathbb{Z}$
for some
$l \geq 1$
.
The exponential tail decay (22) of the overshoot random variable
$T^{\uparrow}_0(\mathbf{0})$
in (22), the translation invariance of our model together with the union bound completes the proof.
Before proving Lemma 7 for general
$j \geq 1$
we recall that given
$\mathcal{G}_j$
, the distribution of the random vectors in the upper half-plane
$\{\Gamma_{\mathbf{w}} \;:\;\mathbf{w} \in \mathbb{H}^+(\tau_j)\}$
no longer remains i.i.d. However, for
$\mathbf{w} \in \mathbb{H}^+(\tau_j)$
, irrespective of the location of
$\mathbf{w}$
, and for any
$m \in \mathbb{Z}$
, we still have uniform exponential tail decay for
$J_{\text{sp}}(\mathbf{w})$
and the total perturbation random variable
$T(\mathbf{w})$
. Also, for any
$m \in \mathbb{Z}$
we consider the overshoot random variable
$T^\uparrow_m(\mathbf{w})$
and obtain an exponentially decaying tail for the same.
Lemma 8. Given
\begin{align*}\big(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_1}(\mathbf{x}_k)\big) = \big(\mathbf{w}^1_1, \ldots , \mathbf{w}^1_k\big) , \ldots , \big(h^{\tau_j}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_k)\big) = \big(\mathbf{w}^j_1, \ldots , \mathbf{w}^j_k\big),\end{align*}
for any
$\mathbf{v} \in \mathbb{H}^+(\mathbf{w}^j_1(2))$
and
$0 \lt \beta \lt \alpha$
there exist constants
$C_0, C_1 \gt 0$
that do not depend on the vertices
$(\mathbf{w}^1_1, \ldots , \mathbf{w}^1_k), \ldots ,(\mathbf{w}^j_1, \ldots , \mathbf{w}^j_k), \mathbf{v}$
such that for all
$n \in \mathbb{N}$
we have the following:
-
(i)
$\mathbb{P}(\mathbf{v} \in V_{\text{sp}} \mid \mathcal{G}_j ) \geq \mathbb{P}(\mathbf{v} \in V_{\text{sp}})$
and
$\mathbb{P}(T_{\mathbf{v}} \gt n \mid \mathcal{G}_j) \leq C_0 \exp{(\!-\!C_1 n)}$
; -
(ii)
$\mathbb{P}(J_{\text{sp}}(\mathbf{v}) \gt n \mid \mathcal{G}_j) \leq C_0 \exp{(\!-\!C_1 n)}$
; -
(iii)
$\mathbb{P} ( T^\uparrow_m(\mathbf{v}) \gt n \mid \mathcal{G}_j ) \leq C_0 \exp{(\!-\!C_1 n)}$
for any
$m \in \mathbb{Z}$
; -
(iv) for all
$1 \leq i \leq k$
\begin{align*}\mathbb{P} \bigl ( \max\big\{ |\big(h^\ell\big(\mathbf{w}^j_i\big) - \mathbf{w}^j_i\big)(1)| \;:\; 1 \leq \ell \leq n^\beta \big\} \gt n^\alpha \mid \mathcal{G}_j \bigr ) \leq C_0 \exp{\big(\!-\!C_1 n^{\alpha - \beta}\big)}.\end{align*}
Proof. We prove the lemma for
$k = 1$
. The argument is the same for general
$k \geq 1$
. Given
$(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_1)) = (\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j)$
for any
$\mathbf{v} \in \mathbb{H}^+(\mathbf{w}_1^j(2))$
we obtain
\begin{align*}& \mathbb{P} \bigl ( \mathbf{v} \in V_{\text{sp}} \mid \big(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_1)\big) =\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big)\bigr ) \\[5pt] & = \mathbb{P} \bigl ( (\mathbf{v} \in V_{\text{sp}}) \cap \text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr )/\mathbb{P} \bigl ( \text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr ) \\[5pt] & \geq \mathbb{P} \bigl ( ( \mathbf{v} \in V_{\text{sp}}) \cap A_{\text{sp}}\big(\mathbf{w}_1^j\big) \cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr )/\mathbb{P} \bigl ( \text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr ) \\[5pt] & = \mathbb{P} \bigl ( ( \mathbf{v} \in V_{\text{sp}}) \cap A_{\text{sp}}\big(\mathbf{w}_1^j\big) \bigr ) \mathbb{P}(E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big))/\mathbb{P} \bigl ( \text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr ) \\[5pt] & = \mathbb{P} ( \mathbf{v} \in V_{\text{sp}}) \times \bigl[ \mathbb{P} ( A_{\text{sp}}\big(\mathbf{w}_1^j\big) ) \mathbb{P}(E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big))/\mathbb{P} \bigl ( \text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr ) \bigr ] \\[5pt] & = \mathbb{P} ( \mathbf{v} \in V_{\text{sp}}) \times \bigl[ \mathbb{P} \bigl ( A_{\text{sp}}\big(\mathbf{w}_1^j\big) \cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr )/\mathbb{P} \bigl ( \text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr ) \bigr ] \\[5pt] & \geq \mathbb{P}( \mathbf{v} \in V_{\text{sp}}) .\end{align*}
For the second term in (i) we have
\begin{align*}& \mathbb{P} \bigl ( T_{\mathbf{v}} \gt n \mid \big(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_1)\big) =\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big)\bigr ) \\[5pt] & = \mathbb{P} \bigl ( (T_{\mathbf{v}} \gt n )\cap \text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big))/\mathbb{P}\big(\text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big) \bigr ) \\[5pt] & \leq \mathbb{P}( (T_{\mathbf{v}} \gt n) \cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big))/\mathbb{P}\big(\text{In}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big)\big) \\[5pt] & \leq \mathbb{P}( T_{\mathbf{v}} \gt n )\mathbb{P}\big(E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big)\big)/\mathbb{P}\big(A_{\text{sp}}\big(\mathbf{w}_1^j\big)\cap E\big(\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j\big)\big) \\[5pt] & = \mathbb{P}(T_{\mathbf{v}} \gt n )/\mathbb{P}(A_{\text{sp}}(\mathbf{0})) \\[5pt] & \leq C_0 \exp{(\!-\!C_1 n)}.\end{align*}
Clearly, the values of the positive constants
$C_0$
and
$C_1$
do not depend on the point
$\mathbf{v}$
or on
$(\mathbf{w}^1_1, \ldots , \mathbf{w}_1^j)$
.
The argument for (ii) is similar to that for (i), and hence we skip it.
For (iii) we observe that given
$(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_1))= (\mathbf{w}^1_1, \ldots, \mathbf{w}_1^j)$
, the definition of the ‘Out’ event gives
\begin{align}T^\uparrow_m(\mathbf{w}) \mid \mathcal{G}_j = \max \big\{ T_{\mathbf{v}} - \ell \;:\; \mathbf{v} \in \mathbf{w}^{\downarrow}_m \text{ with }\mathbf{v}(2) = \ell \text{ for some }0 \leq \ell \leq \mathbf{w}(2) - \mathbf{w}_1^j(2) \big\}.\end{align}
In other words, the random variables
$\{ T_{\mathbf{v}} \;:\; \text{ with }\mathbf{v}(2) \leq \mathbf{w}_1^j(2)\}$
do not contribute towards the overshoot amount in
$\mathbb{H}^+(\mathbf{w}(2))$
. From (i) we have that the family of random variables on the right side of (24) has uniform exponential tail decay. Hence, the same argument for exponential tail decay of the overshoot random variable, as given in (22), proves (iii).
The proof of (iv) follows from (ii) together with an application of the union bound.
We now prove Lemma 7 for general
$j \geq 2$
.
Proof of Lemma
7 for
$j \geq 2$
. The proof for general
$j \geq 2$
is very similar to that for
$j =1$
, and we mention here the required modifications only. In the proof for
$j =1$
, we did not really use the fact that
$\{T_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{Z}^2\}$
is an i.i.d. collection. Our proof essentially uses the union bound and uniform exponential tail decay of marginal distributions of total perturbation random variables. Given
$\mathcal{G}_j$
, although the collection
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\tau_j)\}$
is no longer an i.i.d. collection of random vectors, Lemma 8(i) provides uniform exponential tail decay for the family of total perturbation random vectors
$\{ T_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\tau_j)\}$
. We observe that given
$\mathcal{G}_j$
, Lemma 7(ii) ensures uniform exponential tail decay for the collection
$\{ J_{\text{sp}}(\mathbf{w}) \;:\; \mathbf{w} \in \mathbb{H}^+(\tau_j) \}$
. On the other hand, Lemma 7(iv) gives us that the probability of the corresponding version of the event
$(E^2_n)^c$
goes to 0 exponentially as
$n \to \infty$
. Finally, the definition of the ‘Out’ event guarantees that the family of previously explored perturbation random vectors
$\{ \Lambda_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^-(\tau_j)\}$
does not contribute to the random variable
$X_{j+1}$
. Therefore, Lemma 7(iii) allows us to apply the same argument as for
$j = 1$
, which completes the proof.
3.2. A uniform lower bound for probability of decrease of
$L_j$
Here we show that, for
$j \geq 1$
given
$\tau_j$
, the probability that the value of
$L_{j+1}$
reduces by at least 1 is uniformly bounded away from zero.
Lemma 9. For any
$j \geq 1$
given
$L_j \gt 0$
, there exists
$\bar{p} \gt 0$
(which does not depend on j) such that we have
\begin{align*}\mathbb{P}( (L_{j+1} - L_{j}) \leq - 1 \mid \mathcal{G}_j) \geq \mathbb{P}( X_{j+1} = 1 \mid \mathcal{G}_j)\geq \bar{p}.\end{align*}
Proof. We prove the case
$k = 1$
; the proof for general k is similar. For
$\mathbf{u} \in \mathbb{Z}^2$
we define the event
\begin{align*}B(\mathbf{u}) = \{ \mathbf{u} + (0,1) \in V_{\text{sp}}\}\cap \{\tilde{\mathbf{v}} \notin \nabla(\mathbf{u} + (0,1)) \;:\;\text{ for all }\mathbf{v} \in \mathbb{Z}^2, \mathbf{v}(2) = \mathbf{u}(2) + 1\}.\end{align*}
Given
$h^{\tau_j}(\mathbf{x}_1) = \mathbf{w}_j$
and
$L_j \gt 0$
, we claim that
\begin{align} (B(\mathbf{w}_j)\cap A_{\text{sp}}(\mathbf{w}_j + (0,1)))\subseteq \{(L_{j+1} - L_{j}) \leq - 1 \}. \end{align}
Indeed, the occurrence of the event
$B(\mathbf{w}_j)$
implies that the vertex
$\mathbf{w}_j + (0,1)$
must be a special point, and consequently we must have
$h(\mathbf{w}_j) = \mathbf{w}_j + (0,1)$
. Also, the occurrence of the event
$A_{\text{sp}}(\mathbf{w}_j + (0,1))$
ensures that the ‘In’ event occurs at the next step, which makes it a
$\tau$
step as well and gives us
$\tau_{j+1} = \tau_j + 1 $
. Finally, the event
$B(\mathbf{w}_j)$
ensures that none of the newly explored vertices with
$\mathbf{w}(2) = \mathbf{w}_j(2) + 1$
can have their perturbed version in
$\nabla(\mathbf{w}_j + (0,1))$
. Since there are no new contributions, we have
$X_{j + 1} = 1$
. The recursion relation (20) justifies the event inclusion as in (25) and hence, given
$(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_1)) = (\mathbf{w}_1, \ldots, \mathbf{w}_j)$
, we have
\begin{align}& \mathbb{P} \bigl( (L_{j+1} - L_{j}) \leq - 1 \mid\big(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_1)\big) = (\mathbf{w}_1, \ldots, \mathbf{w}_j) \bigr) \nonumber\\[5pt] & \geq \mathbb{P} ( B(\mathbf{w}_j )\cap A_{\text{sp}}(\mathbf{w}_j + (0,1)) \mid E(\mathbf{w}_1, \ldots , \mathbf{w}_j)\cap \text{In}(\mathbf{w}_j) )\nonumber\\[5pt] & = \mathbb{P} ( B(\mathbf{w}_j)\cap A_{\text{sp}}(\mathbf{w}_j + (0,1)) \cap \text{In}(\mathbf{w}_j) \cap E(\mathbf{w}_1, \ldots , \mathbf{w}_j) )/\mathbb{P} (\text{In}(\mathbf{w}_j) \cap E(\mathbf{w}_1, \ldots , \mathbf{w}_j) ) \nonumber\\[5pt] & = \mathbb{P} ( B(\mathbf{w}_j )\cap A_{\text{sp}}(\mathbf{w}_j + (0,1)) \cap E(\mathbf{w}_1, \ldots , \mathbf{w}_j) )/\mathbb{P} ( \text{In}(\mathbf{w}_j) \cap E(\mathbf{w}_1, \ldots , \mathbf{w}_j) ) \nonumber \\[5pt] & = \mathbb{P} ( B(\mathbf{w}_j )\cap A_{\text{sp}}(\mathbf{w}_j + (0,1)) ) \times \mathbb{P}(E(\mathbf{w}_1, \ldots , \mathbf{w}_j))/\mathbb{P} ( \text{In}(\mathbf{w}_j) \cap E(\mathbf{w}_1, \ldots , \mathbf{w}_j) ).\end{align}
The last equality follows from the observation that the events
$B(\mathbf{w}_j)$
and
$A_{\text{sp}}(\mathbf{w}_j + (0,1))$
depend on the collection
$\{\Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\mathbf{w}_j(2))\}$
, and hence they are independent of
$E(\mathbf{w}_1, \ldots , \mathbf{w}_j)$
. Therefore, (26) gives us
\begin{align*}& \mathbb{P} \bigl( (L_{j+1} - L_{j}) \leq - 1 \mid\big(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_1)\big) = (\mathbf{w}_1, \ldots, \mathbf{w}_j) \bigr) \nonumber\\[5pt] & = \mathbb{P} ( B(\mathbf{w}_j )\cap A_{\text{sp}}(\mathbf{w}_j + (0,1)) )\times ( \mathbb{P}( E(\mathbf{w}_1, \ldots , \mathbf{w}_j)) /\mathbb{P} ( \text{In}(\mathbf{w}_j) \cap E(\mathbf{w}_1, \ldots , \mathbf{w}_j) ) )\\[5pt] & \geq \mathbb{P} ( B(\mathbf{w}_j )\cap A_{\text{sp}}(\mathbf{w}_j + (0,1)) ).\end{align*}
The penultimate equality follows from the observation that the intersection of the two events
$ B(\mathbf{w}_j) $
and
$ A_{\text{sp}}(\mathbf{w}_j + (0,1))$
is contained in the event
$\text{In}(\mathbf{w}_j)$
.
Therefore, using the translation invariance of our model, we have
\begin{align*}& \mathbb{P} \bigl( (L_{j+1} - L_{j}) \leq - 1 \mid \big(h^{\tau_1}(\mathbf{x}_1), \ldots, h^{\tau_j}(\mathbf{x}_1)\big)= (\mathbf{w}_1, \ldots, \mathbf{w}_j) \bigr) \\[5pt] & \geq \mathbb{P} ( B(\mathbf{w}_j )\cap A_{\text{sp}}(\mathbf{w}_j + (0,1)) )\\[5pt] & = \mathbb{P} ( B(\mathbf{w}_j ) \mathbb{P}(A_{\text{sp}}(\mathbf{w}_j + (0,1)) )\\[5pt] & = \mathbb{P}( B(\mathbf{0})) \mathbb{P}(A_{\text{sp}}(\mathbf{0})) \gt 0.\end{align*}
In the last step we have used the fact that
$\mathbb{P}(B(\mathbf{0})) \gt 0$
, which follows from a simple construction. This completes the proof.
Proof of Proposition
4. Note that the family
$\{ X_j \;:\; j \geq 1\}$
has a strong uniform exponential tail decay (see Lemma 7). So we may assume that there exists an i.i.d. family of non-negative integer-valued random variables
$\{ R_j \;:\; j \geq 1\}$
with exponential tail decay such that for all
$j , m \geq 1$
we have
\begin{align*}\mathbb{P}( X_j \geq m \mid X_{j-1}, \ldots, X_1) \leq \mathbb{P}(R_j \geq m) \quad\text{ and }\quad \mathbb{P}(R_1 = 1) \geq \bar{p},\end{align*}
where
$\bar{p}$
is as in Lemma 9. Using the family
$\{ R_j \;:\; j \geq 1\}$
, we construct a non-negative integer-valued Markov chain
$\{M_j \;:\; j \geq 0\}$
such that
$M_0 = 0$
, and for
$j \geq 1$
, we define
$M_j$
as
$M_j \;:\!=\; \max \{M_{j-1} , R_j\} - 1$
.
The recursion relation (20) ensures that the Markov chain
$\{M_j \;:\; j \geq 0\}$
stochastically dominates the height process
$\{ L_j \;:\; j \geq 0\}$
. Let
$\tau^M \;:\!=\; \inf\{ j \geq 1 \;:\; M_j = 0\}$
denote the return time to state zero for this Markov chain. To prove Proposition 4 it is enough to show that the tail of the random variable
$\tau^M$
decays exponentially, and this follows from Lemma 2.6 in [Reference Roy, Saha and Sarkar25].
4. Renewal properties for a single path
In this section, we consider
$k= 1$
and explain the renewal properties of the marginal process
$\{h^{\sigma_\ell}(\mathbf{x}_1) \;:\; \ell \geq 0\}$
. More precisely, we show that the sequence of renewal steps gives rise to a random walk process with i.i.d. increments. We define the sequence of successive renewal steps as
\begin{align*}\{ Y_{\ell + 1} = Y_{\ell + 1}(\mathbf{x}_1) \;:\!=\; h^{\sigma_{\ell+1}}(\mathbf{x}_1) \;:\; \ell \geq 0\} .\end{align*}
We observe that
$\sigma_{\ell + 1}(\mathbf{x}_1) - \sigma_{\ell}(\mathbf{x}_1) =(Y_{\ell + 1}(\mathbf{x}_1) - Y_{\ell}(\mathbf{x}_1))(2)$
represents the total time taken between the
$(\ell + 1)$
th renewal and the
$\ell$
th renewal. The next proposition explains the renewal structure observed at these random steps.
Proposition 5.
$\{ (Y_{\ell+1}-Y_{\ell}) \;:\; \ell \geq 1\}$
is a collection of i.i.d. random vectors taking values in
$\mathbb{Z}\times \mathbb{N}$
whose distribution does not depend on the choice of the starting point
$\mathbf{x}_1$
.
We observe that the above proposition gives i.i.d. increments with a lag. Since the starting condition is not the same as the renewal conditions, the first increment random vector given by
$(Y_1 - \mathbf{x}_1)$
has a different distribution. We note that the above proposition also implies that
$\{ \sigma_{\ell + 1}(\mathbf{x}_1) - \sigma_{\ell}(\mathbf{x}_1) \;:\; \ell \geq 1\}$
forms an i.i.d. sequence whose distribution does not depend on
$\mathbf{x}_1$
. This provides a strong uniform exponential tail decay for the family
$\{ \sigma_{\ell}(\mathbf{x}_1) \;:\; \ell \geq 1 \}$
.
Proposition 5 will be proved through a sequence of lemmas. We need to introduce some notation first. In what follows, together with the usual step
$h(\mathbf{u}) = h(\mathbf{u}, V)$
, where
$h(\mathbf{u}, V)$
is defined as in (4), we will also consider
$h(\mathbf{u}, V^+_{\mathbf{u}(2)})$
. The step
$h(\mathbf{u}, V^+_{\mathbf{u}(2)})$
is taken considering only the set
$V^+_{\mathbf{u}(2)}$
. For simplicity of notation,
$h(\mathbf{u}, V^+_{\mathbf{u}(2)})$
will simply be denoted as
$h(\mathbf{u}, V^+)$
, and for
$j \geq 1$
, the jth step
$h^j(\mathbf{u}, V^+_{\mathbf{u}(2)})$
(taking into account only the set
$V^+_{\mathbf{u}(2)}$
) will be denoted as
$h^j(\mathbf{u}, V^+)$
. In general, this modified step
$h^j(\mathbf{u}, V^+_{\mathbf{u}(2)})$
need not be the same as that of the usual jth step
$h^j(\mathbf{u}, V) = h^j(\mathbf{u})$
.
On the event
$\text{In}(\mathbf{u}) \cap \text{Out}(\mathbf{u})$
we must have
\begin{align}h^j(\mathbf{u}, V^+_{\mathbf{u}(2)}) = h^j(\mathbf{u}, V^+) = h^j(\mathbf{u}, V) = h^j(\mathbf{u}) \in \nabla(\mathbf{u})\text{ for all }j \geq 1.\end{align}
This motivates us to define another event
$\text{In}^+(\mathbf{u})$
similar to the event
$\text{In}(\mathbf{u})$
but in terms of the path using the set
$V^+_{\mathbf{u}(2)}$
only, as
\begin{align*}\text{In}^+(\mathbf{u}) \;:\!=\; \{ h^j(\mathbf{u},V^+) \in \nabla(\mathbf{u}) \text{ for all }j \geq 1\}.\end{align*}
The observation (27) implies
\begin{align}\text{In}(\mathbf{u}) \cap \text{Out}(\mathbf{u}) = \text{In}^+(\mathbf{u}) \cap \text{Out}(\mathbf{u}).\end{align}
Similarly, the occurrence of the renewal event at the nth step
$h^n(\mathbf{x}_1)$
can be equivalently represented as the occurrence of the event
$\text{In}^+(h^n(\mathbf{x}_1))\cap \text{Out}(h^n(\mathbf{x}_1))$
. The usefulness of this representation is that events
$\text{In}^+(\mathbf{u})$
and
$ \text{Out}(\mathbf{u})$
are supported on disjoint sets of random vectors and, therefore, these two events are independent.
To have a better understanding of the distribution of renewal increments, we decouple our renewal event and express it as a joint occurrence of two independent events. The same argument as that in Remark 3 gives us the next remark.
Remark 5. For any
$j \geq 1$
we have the following equality of events:
\begin{align}& \bigcap_{\ell = 1}^j \big\{\sigma_\ell = m_\ell, h^{m_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell \big\} \nonumber \\[2pt] & = \Bigg [ \bigcap_{ \ell = 1}^j \big\{ h^{m_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell,\rm{Out}(\mathbf{v}_\ell)\big\}\cap \Bigg \{ \bigcap_{n = m_{\ell - 1} + 1}^{m_\ell - 1} \big(\gamma\big(h^n(\mathbf{x}_1)\big)\leq m_\ell - n\big) \nonumber\\[2pt] & \quad \cup \big(\rm{Out}\big(h^n(\mathbf{x}_1)\big)\big)^c \Bigg \} \cap \Bigg(\bigcap_{\ell = 1}^{j-1}\text{In}^{ m_{(\ell + 1)} - m_\ell}(\mathbf{v}_\ell) \Bigg)\Bigg ]\cap \text{In}^+(\mathbf{v}_j).\end{align}
The event
$\text{In}^+(\mathbf{v}_j)$
is independent of the rest of the events on the right-hand side of (29), all of which are
$\mathcal{F}_{\mathbf{v}_j(2)} = \mathcal{F}_{m_j}$
measurable.
Remark 5 allows us to obtain the following distributional equality:
\begin{align}\{\Lambda_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\mathbf{v}_\ell(2))\} \mid \big(h^{\sigma_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell\big)& \stackrel{\mathrm{d}}{=} \{\Lambda_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\mathbf{v}_\ell(2))\} \mid \text{In}^+(\mathbf{v}_\ell) \nonumber \\[2pt] & \stackrel{\mathrm{d}}{=} \{\Lambda_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(0)\} \mid \text{In}^+(\mathbf{0}).\end{align}
Equation (28) together with Remark 5 gives us the first equality. The last equality follows from the translation invariance nature of our model. Equation (30) allows us to obtain the next proposition, which proves the equality of increment distributions between successive renewal steps for the marginal process
$\{h^j(\mathbf{x}_1) \;:\; j \geq 1\}$
.
Proposition 6. Fix
$\ell \geq 1$
. We have the following equality of distributions of the conditional random variables:
\begin{align*} \big\{ \big(h^{\sigma_{\ell} + m}(\mathbf{x}_1) - \mathbf{v}_\ell \big) \;:\; m \geq 1 \mid \big( h^{\sigma_{\ell}}(\mathbf{x}_1) = \mathbf{v}_{\ell}\big)\big\} \stackrel{\mathrm{d}}{=} \{ h^{m}(\mathbf{0}, V^+) \;:\; m \geq 1 \mid (\text{In}^+(\mathbf{0}))\}.\end{align*}
Proof. For
$k \geq 1$
, fix
$n_1, \ldots, n_k \geq 1$
. Given
$h^{\sigma_{\ell}}(\mathbf{x}_1) = \mathbf{v}_{\ell}$
, we consider the joint distribution of the random vector
$(h^{\sigma_{\ell} + n_1}(\mathbf{x}_1), \ldots, h^{\sigma_{\ell} + n_k}(\mathbf{x}_1))$
. Let
$\mathcal{B}$
be an arbitrary Borel set in an appropriate space. It suffices to show that
\begin{align} & \mathbb{P} \big ( \bigl( h^{\sigma_{\ell} + n_1}(\mathbf{x}_1) - \mathbf{v}_\ell, \ldots, h^{\sigma_{\ell} + n_k}(\mathbf{x}_1) - \mathbf{v}_\ell \bigr) \in \mathcal{B} \mid (h^{\sigma_{\ell}}(\mathbf{x}_1) = \mathbf{v}_{\ell}) \big ) \nonumber \\[2pt] & = \mathbb{P} \bigl ( \bigl( h^{n_1}(\mathbf{v}_{\ell}, V^+) - \mathbf{v}_\ell, \ldots, h^{n_k}(\mathbf{v}_{\ell}, V^+)- \mathbf{v}_\ell\bigr) \in \mathcal{B} \mid \text{In}^+(\mathbf{v}_{\ell}) \bigr )\nonumber \\[2pt] & = \mathbb{P} ((h^{n_1}(\mathbf{0}, V^+), \ldots, h^{n_k}(\mathbf{0}, V^+)) \in \mathcal{B} \mid \text{In}^+(\mathbf{0})).\end{align}
The last equality follows from the translation invariance of our model. For the first equality in (31), we observe that
\begin{align*}& \mathbb{P} \bigl ( \bigl( h^{\sigma_\ell + n_1}(\mathbf{x}_1) - \mathbf{v}_\ell, \ldots, h^{\sigma_\ell + n_k}(\mathbf{x}_1)- \mathbf{v}_\ell \bigr ) \in \mathcal{B} \mid \big( h^{\sigma_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell\big) \bigr ) \\[2pt] & = \mathbb{P} \bigl ( \bigl( h^{n_1}(\mathbf{v}_\ell) - \mathbf{v}_\ell, \ldots, h^{n_k}(\mathbf{v}_\ell) - \mathbf{v}_\ell \bigr ) \in \mathcal{B} \mid \big( h^{\sigma_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell\big) \bigr ) \\[2pt] & = \mathbb{P} \bigl ( \bigl( h^{ n_1}(\mathbf{v}_\ell, V^+) - \mathbf{v}_\ell, \ldots, h^{n_k}(\mathbf{v}_\ell, V^+) - \mathbf{v}_\ell \bigr ) \in \mathcal{B} \mid \big(h^{\sigma_\ell}(\mathbf{x}_1) = \mathbf{v}_\ell\big) \bigr ) \\[2pt] & = \mathbb{P} \bigl ( \bigl( h^{ n_1}(\mathbf{v}_\ell, V^+) - \mathbf{v}_\ell, \cdots, h^{n_k}(\mathbf{v}_\ell, V^+) - \mathbf{v}_\ell \bigr ) \in \mathcal{B} \mid \text{In}^+(\mathbf{v}_\ell) \bigr ).\end{align*}
The last equality follows from (30). This completes the proof.
We are now ready to prove Proposition 5.
Proof of Proposition
5. Proposition 6 gives us that the distribution of the increment random vector
$(Y_{\ell + 1} - Y_{\ell})$
for
$\ell \geq 1$
can be reconstructed as follows. Let
$V^{\text{ind}}$
and
$V^{\text{ind},+}_0$
be independent copies of V and
$V^+_0$
, respectively. Conditional on the event
$\text{In}^+({\bf 0})$
, we start a path from
${\bf 0}$
using vertices from the set
$V^{\text{ind},+}_0$
until the occurrence of the next renewal event. Let
$\zeta$
be the position of the above path at the next renewal step. Then Proposition 6 implies that, for
$\ell \geq 1$
, we must have
\begin{align*}(Y_{\ell + 1} - Y_\ell) \stackrel{\mathrm{d}}{=} \zeta.\end{align*}
This proves that the increment random vectors are identically distributed. Next we show that the increments are also independent.
Recall that the random vector
$Y_\ell = h^{\sigma_\ell}(\mathbf{x}_1)$
is
$\mathcal{S}_{\ell}$
measurable, where
$\mathcal{S}_{\ell}$
is as defined in (19). Fix
$ m \geq 1 $
and Borel subsets
$ B_2,\ldots, B_{m+1} $
of
$ \mathbb{Z} \times \mathbb{N}$
. Let
$ I( B_{\ell+1} ) = {\mathbf{1}}_{\{ (Y_{\ell+1} - Y_{\ell}) \in B_{\ell + 1 }\}}$
. Then we have
\begin{align*}& \mathbb{P} ((Y_{\ell + 1} - Y_{\ell }) \in B_{\ell + 1} \text{ for } \ell = 1,\ldots, m )= \mathbb{E} \Bigg( \prod_{ \ell = 1}^{m } I ( B_{\ell+1} )\Bigg) \\[5pt] & = \mathbb{E} \Bigg( \mathbb{E} \Bigg( \prod_{ \ell = 1}^{m } I( B_{\ell+1} )\mid \mathcal{S}_{m} \Bigg) \Bigg) = \mathbb{E} \Bigg( \prod_{ \ell = 1}^{m-1 } I ( B_{\ell+1} )\mathbb{E} \bigl( I ( B_{m+1} ) \mid \mathcal{S}_{m} \bigl) \Bigg),\end{align*}
the random variables
$ I(B_{\ell+1})$
,
$ 1 \leq \ell \leq m-1 $
being measurable with respect to
$ \mathcal{S}_{m} $
.
From the earlier discussion, we have that the conditional distribution of
$ Y_{m+1} - Y_m$
given
$ \mathcal{S}_{m}$
is given by
$\zeta $
. Therefore, we obtain
\begin{align*}\mathbb{P} ( (Y_{\ell+1} - Y_{\ell}) \in B_{\ell+1 } \text{ for } \ell = 1,\ldots, m )& = \mathbb{E} \Bigg( \prod_{ \ell = 1}^{m-1 } I ( B_{\ell+1} )\mathbb{E} (I(B_{m+1} ) \mid \mathcal{S}_{m})\Bigg) \\[5pt] & = \mathbb{P} ( \zeta \in B_{m+1} ) \mathbb{E} \Bigg( \prod_{ \ell = 1}^{m - 1 } I ( B_{\ell+1} ) \Bigg).\end{align*}
Induction on m completes the proof.
Before ending this section, we prove that the distribution of the increment random variable
$(Y_2(1)- Y_1(1))$
is symmetric about zero.
Lemma 10.
$(Y_2(1) - Y_1(1))$
has moments of all orders. Furthermore, for all
$m \in \mathbb{N}$
, we have
\begin{align}\mathbb{P}(Y_2(1)- Y_1(1) = m) = \mathbb{P}( Y_2(1)- Y_1(1) = -m),\end{align}
implying
$\mathbb{E}(Y_2(1)- Y_1(1)) =0$
.
Proof. We observe that
$(Y_2(1)- Y_1(1)) \leq (\sigma_2 - \sigma_1)^2$
, and therefore Proposition 3 proves that
$(Y_2(1)- Y_1(1))$
has moments of all orders. Hence, to prove Lemma 10 it is enough to prove (32). Given
$h^{\sigma_j}(\mathbf{x}_1) = \mathbf{v}_j$
, we recall that the path
$\{ h^n(\mathbf{v}_j) \;:\; n \geq 1\}$
uses the random vectors
$\{\Lambda_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\mathbf{v}_j(2))\}$
only and always stays within the region
$\nabla(\mathbf{v}_j)$
.
The main idea is to show that distribution of the point set
$V^+_{\mathbf{v}_j(2)} $
remains invariant with respect to reflection about the line
$x = \mathbf{v}_j(1)$
. For
$\mathbf{w} = \mathbf{v}_j + (s,t) \in \mathbb{H}^+(\mathbf{v}_j(2))$
we define its copy reflected about the line
$X = \mathbf{v}_j(1)$
as
\begin{align*}\overline{\mathbf{w}} \;:\!=\; \mathbf{v}_j + (\!-\!s, t).\end{align*}
Using the collection
$\{\Gamma_{\mathbf{w}} = (B_{\mathbf{w}}, R_{\mathbf{w}}, \Lambda_{\mathbf{w}})\;:\; \mathbf{w} \in \mathbb{Z}^2 \}$
, we define a new collection
$\{ \Gamma^\prime_{\mathbf{w}} \;:\!=\; B_{\mathbf{w}}^\prime, R_{\mathbf{w}}^\prime, \Lambda^\prime_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{Z}^2\}$
given by
\begin{align*}\bigl ( B_{\mathbf{w}}^\prime, R_{\mathbf{w}}^\prime, \Lambda^\prime_{\mathbf{w}} \;:\!=\; \big(X^\prime_{\mathbf{w}}, Y^\prime_{\mathbf{w}}\big) \bigr )\;:\!=\;\begin{cases}( B_{\overline{\mathbf{w}}}, - R_{\overline{\mathbf{w}}}, (\!-\! X_{\overline{\mathbf{w}}}, Y_{\overline{\mathbf{w}}}))& \text{ if }\mathbf{w} \in \mathbb{H}^+(\mathbf{v}_j(2)),\\[5pt] ( B_{\mathbf{w}}, R_{\mathbf{w}}, (X_{\mathbf{w}}, Y_{\mathbf{w}}))& \text{ if }\mathbf{w} \in \mathbb{H}^-(\mathbf{v}_j(2)).\end{cases}\end{align*}
The resultant point process generated from this collection is defined as
\begin{align*}V^\prime \;:\!=\; \{ \mathbf{w} + \Lambda^\prime_{\mathbf{w}} \;:\; B_{\mathbf{w}}^\prime = 1\}.\end{align*}
We observe that the newly created point process
$V^\prime$
on
$\mathbb{H}^+(\mathbf{v}_j(2))$
gives a reflected copy of the set
$V^+_{\mathbf{v}_j(2)}$
reflected about the line
$x = \mathbf{v}_j(1)$
. More precisely, a point
$\mathbf{w}$
belongs to
$ (V^\prime)^+_{\mathbf{v}_j(2)}$
if and only if
$\overline{\mathbf{w}} \in V^+_{\mathbf{v}_j(2)}$
.
It is also important to observe that for
$\mathbf{w} \in \mathbb{H}^+(\mathbf{v}_j(2))$
we have
$R_{\mathbf{w}}^\prime = - R_{\overline{\mathbf{w}}}$
. This ensures that in the case of a ‘tie’ (with respect to the nearest member from
$V^\prime$
at the next level) the choice of the outgoing edge is reversed appropriately. In this way the newly constructed collection
$\{\Gamma^\prime_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{Z}^2\}$
ensures that
\begin{align}\overline{h^n}(\mathbf{v}_j, V) = \overline{h^n}\big(\mathbf{v}_j, V^+_{\mathbf{v}_j(2)}\big) = h^n\big(\mathbf{v}_j, (V^\prime)^+_{\mathbf{v}_j(2)}\big)\text{ for all }n \geq 1.\end{align}
The first equality follows as
$\mathbf{v}_j$
is a renewal step. As the region
$\nabla(\mathbf{v}_j)$
is symmetric about the line
$X = \mathbf{v}_j(1)$
, (33) ensures that the new point process satisfies the renewal conditions as well:
-
(i)
$h^n(\mathbf{v}_j, V^\prime) = h^n(\mathbf{v}_j, (V^\prime)^+_{\mathbf{v}_j(2)}) \in \nabla(\mathbf{v}_j)$
for all
$n\geq 1$
; -
(ii) the event
$\text{Out}(\mathbf{v}_j)$
occurs with respect to the point set
$V^\prime$
also as
$(V^\prime)^+_{\mathbf{v}_j(2)} = V^-_{\mathbf{v}_j(2)}$
.
Hence, given
$h^{\sigma_j}(\mathbf{x}_1) = \mathbf{v}_j$
, the distribution of the process
$\{h^n(\mathbf{v}_j) \;:\; n \geq 1\}$
starting from
$\mathbf{v}_j$
remains the same when it progresses using the collection
$\{ \Lambda^\prime_{\mathbf{v}} \;:\; \mathbf{v} \in \mathbb{H}^+(\mathbf{v}_j(2))\}$
.
Let
$\mathbf{v}_{j+1} = \mathbf{v}_j + (s_0, t_0)$
be the vertex of the next renewal with respect to the point process V. It suffices to show that the vertex
$\overline{\mathbf{v}}_{j+1} $
is the position of the next renewal with respect to the point set
$V^\prime$
as well. Equation (33) ensures that we have
$h^{t_0}(\mathbf{v}_j, V^\prime) = \overline{\mathbf{v}}_{j+1}$
. From (33) we also obtain that for any
$ 1 \leq n_1 \leq n_2 $
\begin{align}\bigl( h^{n_2}(\mathbf{v}_j, V) - h^{n_1}(\mathbf{v}_j, V) \bigr )(1) =- \bigl( h^{n_2}(\mathbf{v}_j, V^\prime ) - h^{n_1}(\mathbf{v}_j, V^\prime ) \bigr )(1).\end{align}
By taking
$n_1 = t_0$
and
$n_2 \geq t_0 + 1$
in (34), we obtain
\begin{align*}h^{n}(\overline{\mathbf{v}}_{j+1}, V^\prime) = h^{n}\big(\overline{\mathbf{v}}_{j+1}, (V^\prime)^+_{\mathbf{v}_{j+1}(2)}\big) \in \nabla( \overline{\mathbf{v}}_{j+1} ) \text{ for all}\; n \geq 1.\end{align*}
This implies the occurrence of the event
$\text{In}^+(\overline{\mathbf{v}}_{j+1})$
with respect to the point process
$V^\prime$
. Given that the event
$\text{Out}(\mathbf{v}_{j})$
has occurred, the occurrence of the event
$\text{Out}(\overline{\mathbf{v}}_{j+1})$
with respect to the point set
$V^\prime$
depends only on the random vectors
\begin{align*} \{\Lambda^\prime_{\mathbf{w}} \;:\; \mathbf{w}(2) \in [ \mathbf{v}_j(2) + 1, \mathbf{v}_{j+1}(2)]\}. \end{align*}
We show that for
$ \mathbf{w} \in \mathbb{Z}^2$
with
$\mathbf{w}(2) \in [\mathbf{v}_j(2) + 1, \mathbf{v}_{j+1}(2)]$
, we have
\begin{align*} \mathbf{w} + (X_{\mathbf{w}}, Y_{\mathbf{w}}) \in \nabla(\mathbf{v}_{j+1})\; \text{if and only if }\;\overline{\mathbf{w}} + (\!-\!X_{\overline{\mathbf{w}}}, Y_{\overline{\mathbf{w}}})\in \nabla(\overline{\mathbf{v}}_{j+1}).\end{align*}
This follows from the fact that
\begin{align*}(\mathbf{w} - \mathbf{v}_{j+1})(1) + X_{\mathbf{w}} = -(\overline{\mathbf{w}} - \overline{\mathbf{v}}_{j+1})(1) - X_{\overline{\mathbf{w}}}\end{align*}
and
\begin{align*}(\mathbf{w} - \mathbf{v}_{j+1})(2) + Y_{\mathbf{w}} = (\overline{\mathbf{w}} - \overline{\mathbf{v}}_{j+1})(2) + Y_{\overline{\mathbf{w}}}.\end{align*}
Hence, the occurrence of the event
$\text{Out}(\mathbf{v}_{j+1})$
with respect to the point process V implies and is implied by the occurrence of the event
$\text{Out}(\overline{\mathbf{v}}_{j+1})$
with respect to the point process
$V^\prime$
.
Essentially, we proved that for any
$n \geq 1$
, the nth step
$h^n(\mathbf{v}_j) = \mathbf{x}$
is a renewal step (with respect to the point process V) if and only if the corresponding step with respect to
$V^\prime$
is given by
$h^n(\mathbf{v}_j, V^\prime) = \overline{\mathbf{x}}$
is a renewal step as well. This proves that if we start from
$\mathbf{v}_j$
the step
\begin{align*}h^{t_0}(\mathbf{v}_j, V^\prime ) = \overline{\mathbf{v}}_{j+1}\end{align*}
gives the next renewal step with respect to
$V^\prime$
. This completes the proof.
For
$\ell \geq 1$
, the definition of the ‘In’ event at a renewal step ensures that
\begin{align*}|Y_{\ell + 1}(1) - Y_{\ell}(1)| \leq (Y_{\ell + 1}(2) - Y_{\ell}(2))^2\text{ with probability }1.\end{align*}
5. Properties of the joint process at renewal steps
In this section, we study renewal steps for the joint process of paths starting from two vertices
$\mathbf{x}_1$
and
$\mathbf{x}_2$
with
$\mathbf{x}_1(2) = \mathbf{x}_2(2)=0$
. The main objective of this section is to show that if vertices
$h^{\sigma_{\ell}}(\mathbf{x}_1)$
and
$h^{\sigma_{\ell}}(\mathbf{x}_2)$
are far away then the successive increments behave like a mean zero random walk on an event with high probability. This statement is made precise in Proposition 7.
Without loss of generality we assume that
$\mathbf{x}_1 (1) \lt \mathbf{x}_2(1)$
, which ensures that we have
$h^m(\mathbf{x}_1) (1) \leq h^m(\mathbf{x}_2)(1)$
for all
$m \geq 1$
. For
$\ell \geq 0$
we define
\begin{align}Z_\ell = Z_\ell(\mathbf{x}_1, \mathbf{x}_2) \;:\!=\; h^{\sigma_{\ell}}(\mathbf{x}_2)(1) - h^{\sigma_{\ell}}(\mathbf{x}_1)(1).\end{align}
Given
$\mathcal{G}_\ell$
, we now focus on the case where
$Z_{\ell}$
is large, and we show that there exists an event
$F_\ell$
which occurs with high probability such that on this event the increment random variable
$Z_{\ell+1}-Z_{\ell}$
is symmetric about zero. The details are given in Proposition 7, which provides some additional properties of the increment random variables. This result will be crucially used to obtain the tail decay of the coalescence time for paths in Section 6.
The next result says that, far from the origin, the process
$\{Z_\ell \;:\; \ell \geq 0\}$
behaves like a mean zero random walk satisfying certain moment bounds.
Proposition 7. Fix
$\mathbf{x}_1,\mathbf{x}_2\in \mathbb{Z}^2$
with
$\mathbf{x}_1(1) \lt \mathbf{x}_2(1)$
and consider the joint process of the paths starting from these two points until the
$\ell$
th (joint) renewal step. Given the
$\sigma$
-field
$\mathcal{G}_{\ell}$
, there exist positive constants
$M_0$
,
$C_0$
,
$C_1$
,
$C_2$
, and
$c_m$
(depending on m) and an event
$F_\ell$
such that:
-
(i) on the event
$Z_\ell \gt M_0 $
, we have
\begin{align*}\mathbb{P}\big(F^c_\ell \mid \mathcal{G}_{\ell}\big) \leq C_3/(Z_\ell)^3\quad \textit{and} \quad\mathbb{E} [ (Z_{\ell +1} - Z_{\ell}) \mathbf{1}_{F_\ell} \mid \mathcal{G}_{\ell} ] = 0;\end{align*}
-
(ii) on the event
$\{Z_\ell \leq M_0 \}$
, we have
\begin{align*} \mathbb{E} [(Z_{\ell +1} - Z_{\ell} ) \mid \mathcal{G}_\ell] \leq C_0; \end{align*}
-
(iii) for any
$\ell\geq 0$
and
$m\gt0$
, there exists
$c_m\gt0$
such that, on the event
$Z_\ell \leq m$
,
\begin{align*}\mathbb{P} (Z_{\ell+1} = 0 \mid \mathcal{G}_\ell) \geq c_m;\end{align*}
-
(iv) on the event
$Z_\ell \gt M_0 $
, we have
\begin{align*}\mathbb{E} \bigl[ ( Z_{\ell+1} - Z_{\ell} )^2 \mid \mathcal{ G}_\ell \bigr] \geq C_1 \quad \textit{and} \quad\mathbb{E} \bigl[ |Z_{\ell+1} - Z_{\ell} |^3 \mid \mathcal{ G}_\ell \bigr] \leq C_2.\end{align*}
Proof. The required event
$F_\ell$
is defined as an intersection of several other events. We first describe the main idea. Consider two disjoint large rectangles centred at the vertices
$h^{\sigma_\ell}(\mathbf{x}_1)$
and
$h^{\sigma_\ell}(\mathbf{x}_2)$
. We define two events such that their intersection ensures that the next (joint) renewal happens inside these rectangles, and until the next renewal step, both paths use perturbed open vertices from only these two rectangles. We then consider a ‘new’ set of perturbed open vertices where perturbed open vertices within the two rectangular regions are interchanged and perturbed open vertices coming from outside these two regions remain unchanged. Since both (original) paths use perturbed open vertices from only these two rectangles until the next renewal step, the trajectories of the new paths constructed with the ‘new’ point process are interchanged until the next renewal step (with respect to the original point process). We need to define additional events to ensure that the transformed step actually gives the next (joint) renewal step with respect to the transformed point process.
Set
\begin{align*}l_x = \lfloor Z_{\ell}/40 \rfloor \quad\textit{and}\quad l_y = \lfloor \sqrt{Z_{\ell}/40}\rfloor .\end{align*}
Given
$h^{\sigma_\ell}(\mathbf{x}_i) = \mathbf{w}_i$
for
$i = 1,2$
, we define the following three rectangular regions centred at
$\mathbf{w}_i$
:
\begin{align*}\mathcal{R}^1_i & \;:\!=\; \mathbf{w}_i \oplus [\!-\! l_x , l_x] \times [0, l_y]; \\[5pt] \mathcal{R}^2_i & \;:\!=\; \mathbf{w}_i \oplus [\!-\! 9 l_x , 9 l_x] \times [0, 2 l_y];\\[5pt] \mathcal{R}^3_i & \;:\!=\; \mathbf{w}_i \oplus [\!-\! 18 l_x , 18 l_x] \times [0, 3 l_y].\end{align*}
Clearly, we have
$\mathcal{R}^1_i \subseteq \mathcal{R}^2_i \subseteq \mathcal{R}^3_i$
and the outer rectangles
$\mathcal{R}^3_1$
and
$\mathcal{R}^3_2$
are disjoint. As
$(\mathbf{w}_1, \mathbf{w}_2)$
gives a (joint) renewal step, the ‘In’ event condition ensures that for
$i = 1,2$
we have
\begin{align*}h^{ m}(\mathbf{w}_i) = h^{ m}(\mathbf{w}_i, V) \in \mathcal{R}^1_i \text{ for all }1 \leq m \leq l_y\end{align*}
as well as
\begin{align*}h^{ m}(\mathbf{w}_i) = h^{ m}(\mathbf{w}_i, V) \in \mathcal{R}^2_i \text{ for all }1 \leq m \leq3 l_y.\end{align*}
The first step towards defining
$F_\ell$
(see Figure 5) is the following two events:
\begin{align*}F^1_\ell \;:\!=\; \{\sigma_{ \ell + 1}(\mathbf{x}_1, \mathbf{x}_2) - \sigma_{ \ell}(\mathbf{x}_1, \mathbf{x}_2) \leq l_y \}\end{align*}
and
\begin{align*}F^2_\ell \;:\!=\; \Bigg\{ \tilde{\mathbf{w}} \notin \mathcal{R}^2_1 \cup \mathcal{R}^2_2 \text{ for all }\mathbf{w} \in \mathbb{H}^+(\mathbf{w}_1(2)) \setminus \Bigg( \bigcup_{i =1}^2 \mathcal{R}^3_i \Bigg)\Bigg\}.\end{align*}
We observe that on the event
$F^1_\ell\cap F^2_\ell$
, at the next joint renewal step, i.e. the
$\sigma_{\ell + 1}$
th step, the path starting from
$\mathbf{w}_i$
stays inside the innermost rectangle
$\mathcal{R}^1_i$
for
$i = 1,2$
. Moreover, until the
$ l_y$
th step, which includes the next renewal step, the ith path uses perturbed open vertices from the outer rectangle
$\mathcal{R}^3_i$
only.
Occurrence of the
$F_\ell$
event. Points from the shaded (lightly shaded as well as deeply shaded) region are not allowed to be perturbed to the middle rectangles
$\mathcal{R}^2_1$
and
$\mathcal{R}^2_2$
. Points from the deeply shaded region are not allowed to be perturbed to either of the regions
$\nabla(\mathbf{w}_1)$
(which contains
$\nabla(h^{\sigma_{\ell + 1}}(\mathbf{x}_1))$
) and
$\nabla(\mathbf{w}_2)$
(which contains
$\nabla(h^{\sigma_{\ell + 1}}(\mathbf{x}_2))$
). The occurrence of the events
$A^{(l_y)}_{\text{sp}}(\mathbf{w}_1 + (0,2l_y))$
and
$ A^{(l_y)}_{\text{sp}}(\mathbf{w}_2 + (0,2l_y))$
creates a shield using special points in the upper half-plane
$\mathbb{H}^+(\mathbf{w}_1(2) + 3l_y)$
. While crossing the top boundary of the outer rectangle on the line
$y =\mathbf{w}_1(2) + 3l_y$
, if the PH paths stay inside the respective intervals (marked in black) then the so-called shields prevent the PH paths from crossing the respective parabolic curves (marked in black). This ensures the occurrence of the ‘In’ event for the transformed point process.
We interchange the perturbation random vectors inside these two bigger rectangles
$\mathcal{R}^3_1$
and
$\mathcal{R}^3_2$
to obtain a new point process. Consider the paths starting from
$\mathbf{w}_1$
and
$\mathbf{w}_2$
constructed with the resulting point process. Formally, for
$\mathbf{w} \in \mathbb{Z}^2$
, define the transformation
$\overline{\mathbf{w}}$
as
\begin{align*}\overline{\mathbf{w}} \;:\!=\;\begin{cases}\mathbf{w} & \text{ if }\mathbf{w} \notin \mathcal{R}^3_1\cup \mathcal{R}^3_2, \\[5pt] \mathbf{w}_1 + (s,t)& \text{ if }\mathbf{w} \in \mathcal{R}^3_2 \text{ with } \mathbf{w} = \mathbf{w}_2 + (s,t),\\[5pt] \mathbf{w}_2 + (s,t) & \text{ if }\mathbf{w} \in \mathcal{R}^3_1 \text{ with } \mathbf{w} = \mathbf{w}_1 + (s,t).\end{cases}\end{align*}
The collection
$\{ (B_{\overline{\mathbf{w}}}, R_{\overline{\mathbf{w}}},\Lambda_{\overline{\mathbf{w}}} = ( X_{\overline{\mathbf{w}}}, Y_{\overline{\mathbf{w}}})):\; \mathbf{w} \in \mathbb{Z}^2 \}$
gives rise to the point process
\begin{align*}V^\prime \;:\!=\; \big\{ \mathbf{w} + ( X_{\overline{\mathbf{w}}}, Y_{\overline{\mathbf{w}}}):\;\mathbf{w} \in \mathbb{Z}^2, B_{\overline{\mathbf{w}}} = 1 \big\}.\end{align*}
It is not difficult to observe that, on the lower half-plane
$\mathbb{H}^-(\mathbf{w}_1(2))$
, both V and
$V^\prime$
give us the same collection. Considering the evolution with respect to the transformed set
$V^\prime$
(where only the perturbed source vertices from the outer rectangles are interchanged), for all
$1 \leq m \leq l_y$
we have
\begin{align}h^{ m}(\mathbf{w}_1, V^\prime) & = \mathbf{w}_1 + \big(h^{ m}(\mathbf{w}_2, V) - \mathbf{w}_2\big) \in \nabla(\mathbf{w}_1)\cap \mathcal{R}^1_1, \nonumber \\[5pt] h^{ m}(\mathbf{w}_2, V^\prime) & = \mathbf{w}_2 + \big(h^{ m}(\mathbf{w}_1, V) - \mathbf{w}_1\big) \in \nabla(\mathbf{w}_2)\cap \mathcal{R}^1_2.\end{align}
Equation (36) ensures that on the event
$F^1_\ell \cap F^2_\ell$
we have
\begin{align} \sum_{i = 1}^2 \bigl ( h^{ m}(\mathbf{w}_i, V^\prime) - \mathbf{w}_i \bigr ) (1) = - \sum_{i = 1}^2 \bigl ( h^{ m}(\mathbf{w}_i, V) - \mathbf{w}_i \bigr ) (1)\end{align}
for all
$1 \leq m \leq l_y$
. Ideally, (37) should have given us
\begin{align*}\mathbb{E} \Big [ (Z_{\ell + 1} - Z_\ell)\mathbf{1}_{F^1_\ell \cap F^2_\ell } \mid \mathcal{G}_\ell \Big] =0.\end{align*}
Unfortunately, we need to work harder. The issue is that starting from
$\mathbf{w}_1$
and
$\mathbf{w}_2$
, if the
$m_0 (\!\leq l_y)$
th step gives the next (i.e. the
$(\ell + 1)$
th) joint renewal step with respect to the point process V, the corresponding step with respect to
$V^\prime$
given by
$(h^{m_0}(\mathbf{w}_1, V^\prime), h^{m_0}(\mathbf{w}_2, V^\prime))$
need not give the next renewal step with respect to the transformed point process
$V^\prime$
. To ensure that the step
$(h^{m_0}(\mathbf{w}_1, V^\prime), h^{m_0}(\mathbf{w}_2, V^\prime))$
is the next renewal step with respect to
$V^\prime$
, we need to consider three more events. Let
$\nabla_i \;:\!=\; \nabla(\mathbf{w}_i)$
denote the parabolic region centred at
$\mathbf{w}_i$
and let
$F^3_\ell$
denote the event that
\begin{align*}F^3_\ell \;:\!=\; \big\{ & \tilde{\mathbf{w}} \notin \nabla_1 \cup \nabla_2 \text{ for all }\mathbf{w}\text{ with }\mathbf{w}(2) \in [\mathbf{w}_1(2) + 1, \mathbf{w}_1(2) + l_y ] \\[5pt] & \quad\text{ and }\quad \mathbf{w} \notin \mathcal{R}^3_1 \cup \mathcal{R}^3_2 \big\}.\end{align*}
In Figure 5 the event
$F^3_\ell$
means that the source vertices from the grey shaded (light or dark) region are not allowed to be perturbed to the middle rectangular boxes
$\mathcal{R}^2_1$
and
$\mathcal{R}^2_2$
. The nesting property (9) together with (36) ensures that on the event
$F^1_\ell \cap F^2_\ell$
we have (see Figure 5)
\begin{align*}\nabla\big(h^{m_0}(\mathbf{w}_i, V^\prime) \big) \subset \nabla_i \text{ for } i =1,2.\end{align*}
Hence, we observe that the condition defining the ‘Out’ event automatically holds for the
$V^\prime$
perturbed version of all lattice points in the lower half-plane
$\mathbb{H}^-(\mathbf{w}_1(2))$
as well as for lattice points in the region
$(\mathcal{R}^3_1\cup \mathcal{R}^3_2) \cap \mathbb{H}^-(\mathbf{w}_1(2) + m_0)$
. In addition to this, the event
$F^3_\ell$
ensures that the same holds for all lattice points in the set
$\bigl [ \mathbb{H}^-(\mathbf{w}_1(2) + l_y)\setminus \mathbb{H}^-(\mathbf{w}_1(2)) \bigr ]\setminus (\mathcal{R}^3_1\cup \mathcal{R}^3_2)$
(shown as a grey region in Figure 5), which contains all lattice points in the set
$[\mathbb{H}^-(m_0)\setminus \mathbb{H}^-(\mathbf{w}_1(2))]\setminus (\mathcal{R}^3_1\cup \mathcal{R}^3_2)$
. This ensures that on the event
$\bigcap_{j=1}^3 F^j_\ell$
, the ‘Out’ event occurs at
$(h^{m_0}(\mathbf{w}_1, V^\prime), h^{m_0}(\mathbf{w}_2, V^\prime))$
with respect to the point set
$V^\prime$
.
To complete the proof, we need to ensure the occurrence of the ‘In’ event with respect to
$V^\prime$
at
$(h^{m_0}(\mathbf{w}_1, V^\prime), h^{m_0}(\mathbf{w}_2, V^\prime))$
. Observe that the event
$\bigcap_{i = 1}^3 F^i_\ell$
ensures occurrence of the ‘In’ event at
$h^{m_0}(\mathbf{w}_i, V^\prime)$
with respect to
$V^\prime$
until the time the paths cross the line
$y = \mathbf{w}_1(2) + 3 l_y$
. Note that on the event
$F^1_\ell \cap F^2_\ell $
we have
\begin{align}\nabla (\mathbf{w}_i + (0,2l_y)) \subseteq \nabla \bigl( h^{m_0}(\mathbf{w}_i, V^\prime)\bigr)\text{ for all }i = 1,2.\end{align}
Recall the definition of the event
$A_{\text{sp}} = A_{\text{sp}}(\mathbf{0})$
as given in (13), and for
$l \in \mathbb{N}$
we define
\begin{align*}A_{\text{sp}}^{(l)}(\mathbf{0}) \;:\!=\; \bigcap_{m=l}^\infty \big\{ I^R_m\cap V^{\text{sp}}\neq \emptyset \big\}\cap \big\{ I^L_m\cap V^{\text{sp}}\neq \emptyset \big\}.\end{align*}
For
$\mathbf{w} \in \mathbb{Z}^2$
the notation
$A_{\text{sp}}^{(l)}(\mathbf{w})$
denotes the translated version of the event
$A_{\text{sp}}^{(l)}(\mathbf{0})$
translated at
$\mathbf{w}$
. Finally, (38) motivates us to construct the last two events
$F^4_\ell $
and
$F^5_\ell $
, respectively, as
\begin{align*} F^4_\ell \;:\!=\; \bigcap_{i=1}^2 A_{\text{sp}}^{(l_y)} \bigl( \mathbf{w}_i + (0,2l_y) \bigr )\end{align*}
and
\begin{align*}F^5_\ell \;:\!=\; \bigcap_{i=1}^2 \big\{ h^{3l_y}(\mathbf{w}_i)(1) - \mathbf{w}_i(1) \in [-l_x , l_x] \big\}.\end{align*}
We observe that on the event
$\bigcap_{i=1}^5 F^i_\ell$
, at the
$3l_y$
th step the
$V^\prime$
driven paths do not deviate too much and this ensures that
$h^{3l_y}(\mathbf{w}_i, V^\prime) \in \nabla(\mathbf{w}_i + (0, 2l_y))$
(marked as a black interval in Figure 5). The other event,
$F^4_\ell$
, makes a shield of special points over the time interval
$[3l_y, \infty)$
. We have
$h^{3l_y}(\mathbf{w}_i, V^\prime) \in \nabla(\mathbf{w}_i + (0, 2l_y))$
, and thus the truncated shield created by the event
$F^4_\ell$
ensures the occurrence of a truncated version of the ‘In’ event at
$\mathbf{w}_1 + (0,2l_y)$
and
$\mathbf{w}_2 + (0,2l_y))$
over the time interval
$[\mathbf{w}_1(2) + 3l_y, \infty)$
. Finally, the nesting property as observed in (38) guarantees that on the event
$\bigcap_{i=1}^5 F^i_\ell$
, the ‘In’ events occur jointly
$h^{m_0}(\mathbf{w}_1, V^\prime)$
and
$h^{m_0}(\mathbf{w}_2, V^\prime)$
with respect to the point set
$V^\prime$
as well. See Figure 5 for an illustration of the event
$F_\ell$
defined as
\begin{align}F_\ell \;:\!=\; \bigcap_{i =1}^5 F^i_\ell.\end{align}
Hence, on the event
$F_\ell$
the next (joint) renewal with respect to
$V^\prime$
occurs at
$h^{m_0}(\mathbf{w}_1, V^\prime)$
and
$h^{m_0}(\mathbf{w}_2, V^\prime)$
. Lemma 11 shows that the probability of
$(F_\ell)^c$
satisfies the required tail bound and thereby completes the proof of item (i).
Item (ii) of Proposition 7 follows readily from the fact that
\begin{align*}\mathbb{E} [(Z_{\ell + 1} - Z_\ell) \mid \mathcal{G}_\ell ] & \leq\mathbb{E} \Bigg[\sum_{i=1}^2|\big(h^{\sigma_{\ell + 1}}(\mathbf{x}_i) - h^{\sigma_{\ell}}(\mathbf{x}_i)\big)(1)| \mid \mathcal{G}_\ell\Bigg] \\[5pt] & \leq 2 \mathbb{E}\big((\sigma_{\ell + 1} - \sigma_\ell)^2 \mid \mathcal{G}_\ell\big) \lt \infty.\end{align*}
The finiteness of the expectation follows from Proposition 3, and the penultimate inequality follows from the ‘In’ event at the renewal step.
For (iii), on the event
$\{ Z_{\ell} \leq m\}$
, we need to show that the conditional probability
$\mathbb{P}(Z_{\ell + 1} = 0 \mid \mathcal{G}_\ell)$
is uniformly bounded away from zero such that the lower bound depends only on m. Given
$(h^{\sigma_\ell}(\mathbf{x}_1),h^{\sigma_\ell}(\mathbf{x}_2)) = (\mathbf{w}_1,\mathbf{w}_2)$
, we have
$\mathbf{w}_1(1) \lt \mathbf{w}_2(1)$
. We consider the event that
\[\bigcap_{i=1}^2 \bigl( (h(\mathbf{w}_i) = \mathbf{w}_i + (0,1))\cap \big(h^{k+1}(\mathbf{w}_i)(1) = h^{k}(\mathbf{w}_i)(1) = (\!-\!1)^{i+1}2 \text{ for all }1\leq k \lt m/4\big)\bigr ) .\]
We observe that the occurrence of the event ensures that the next renewal step has not occurred until the next
$\lfloor m/4 \rfloor$
steps, and the horizontal distance between two paths at the
$\lfloor m/4 \rfloor$
th step is bounded by 6. By constructing a suitable event, we can make the paths coalesce at the next step.
Then it remains to check (iv). We observe that
\begin{align*}\mathbb{E} \bigr [ (Z_{\ell + 1} - Z_\ell)^2 \mid \mathcal{G}_\ell \bigl] =\mathbb{E} \bigr [ (Z_{\ell + 1} - Z_\ell)^2\mathbf{1}_{ \{ |Z_{\ell + 1} - Z_\ell |^2 \geq 1 \}} \mid \mathcal{G}_\ell \bigl] \geq \mathbb{P}\big((Z_{\ell + 1} - Z_\ell )^2 \geq 1 \mid \mathcal{G}_\ell\big).\end{align*}
On the event
$\{Z_\ell \gt M_0\}$
, we observe that the intersection of the two events,
$A_1\cap A_2$
, where
$A_1$
and
$A_2$
are
\begin{align*}A_1 \;:\!=\; \big(h^{\sigma_\ell + 1}(\mathbf{x}^1(1) - h^{\sigma_\ell}(\mathbf{x}^1)(1) = -1)\cap\big(h^{\sigma_\ell + 1}\big(\mathbf{x}^2(1) - h^{\sigma_\ell}(\mathbf{x}^2)(1) = +1\big)\end{align*}
and
\begin{align*}A_2 \;:\!=\; \bigcap_{i=1}^2 \big(h^{\sigma_{\ell} + 2}(\mathbf{x}^i)(1) - h^{\sigma_\ell + 1}(\mathbf{x}^i)(1) = 0\big) \big)\cap ( \sigma_{\ell + 1} - \sigma_{\ell} =2 ),\end{align*}
is contained in the event
$(Z_{\ell + 1} - Z_\ell \geq 1)$
. This gives
\begin{align*}\mathbb{P}\big((Z_{\ell + 1} - Z_\ell )^2 \geq 1 \mid \mathcal{G}_\ell\big) \geq C_{M_0} \gt 0,\end{align*}
where
$C_{M_0}$
depends only on
$M_0$
.
For the third moment, from Proposition 3, we have the uniform bound
\begin{align*}\mathbb{E}\big[(Z_{\ell + 1} - Z_\ell)^3 \mid \mathcal{ G}_\ell \big]\leq 8 \mathbb{E}\big[ (\sigma_{\ell + 1} - \sigma_{\ell})^6 \mid \mathcal{G}_\ell \big] \leq 8 C^\prime\text{ for some }C^\prime \gt 0.\end{align*}
The next lemma shows that for large
$Z_\ell$
, the event
$F_\ell$
has the required tail decay.
Lemma 11. Consider the event
$F_\ell$
as defined in (39). Then for all large
$Z_\ell$
there exists
$C^\prime \gt 0$
, which does not depend on
$Z_\ell$
, such that we have
$ \mathbb{P}( F^c_\ell \mid \mathcal{G}_\ell) \leq C^\prime/( Z_\ell )^3 $
.
Proof. It suffices to show that for all
$1 \leq i \leq 5$
we have
\begin{align*}\mathbb{P}\big(\big(F^i_\ell\big)^c \mid \mathcal{G}_\ell\big) \leq C_0/( Z_\ell )^3\end{align*}
for some
$C_0 \gt 0$
. In this paper we have used a similar argument multiple times and we present only a sketch here. The required bound for
$\mathbb{P}( (F^1_\ell)^c \mid \mathcal{G}_\ell)$
follows from Proposition 3. We observe that there are
$3 l_y$
many horizontal lines of lattice points and the event
$(F^1_\ell)^c $
may occur because of large x coordinate perturbation from one of the vertices on these horizontal lines only. Given the
$\sigma$
-field
$\mathcal{G}_\ell$
, the same argument as in Lemma 8 gives the exponential tail decay for overshoot random variables
$T^{\rightarrow}(\mathbf{w})$
and
$T^{\leftarrow}(\mathbf{w})$
for
$\mathbf{w} \in \mathbb{Z}^2$
with
$\mathbf{w}(2) \gt \mathbf{w}_1(2)$
. This allows us to obtain the required tail decay estimate for
$\mathbb{P}( (F^2_\ell)^c \mid \mathcal{G}_\ell)$
.
For the event
$F^3_\ell$
, we observe that outside the boxes
$\mathcal{R}^1_1$
and
$\mathcal{R}^1_2$
, the boundaries of both parabolic regions,
$\nabla_1$
and
$\nabla_2$
, are at a height of at least
$2l_y$
from the line
$x = l_y$
. Hence, a similar argument as in Lemma 7 gives us the required estimate. For the event
$F^4_\ell$
, we need to bound the probability of the complement of the truncated version of the event
$A_{\text{sp}}(\!\cdot\!)$
. We observe that for any
$ i = 1,2$
,
\begin{align}& \mathbb{P}\Big(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c \mid \mathcal{G}_\ell\Big) \nonumber\\[5pt] & = \mathbb{P}\Big(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c \mid \text{In}^+(\mathbf{w}_1)\cap \text{In}^+(\mathbf{w}_2) \Big)\nonumber\\[5pt] & = \mathbb{P}\Big(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c \cap \text{In}^+(\mathbf{w}_1)\cap \text{In}^+(\mathbf{w}_2)\Big)/\mathbb{P}\big(\text{In}^+(\mathbf{w}_1)\cap \text{In}^+(\mathbf{w}_2)\big)\nonumber\\[5pt] & \leq \mathbb{P}\Big(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c\Big)/\mathbb{P}\big(\text{In}^+(\mathbf{w}_1)\cap \text{In}^+(\mathbf{w}_2)\big)\nonumber\\[5pt] & \leq \mathbb{P}\Big(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c\Big)/\mathbb{P} \Bigl( A^{\text{sp}}(\mathbf{w}_1)\cap A^{\text{sp}}(\mathbf{w}_2) \Bigr )\nonumber\\[5pt] & \leq \mathbb{P}\Big(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c\Big)/\mathbb{P} ( A^{\text{sp}}(\mathbf{0}))^2 \nonumber \\[5pt] & = C_0\mathbb{P}\Big(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c \Big).\end{align}
The first equality in (40) follows from the fact that the occurrence of the event
$A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))$
depends on the collection of random vectors
$\{\Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\mathbf{w}_1(2))\}$
. To bound the probability
$\mathbb{P}(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c )$
, we observe that there must be an interval,
$I^L_m(\mathbf{w}_i + (0, 2l_y))$
or
$I^R_m(\mathbf{w}_i + (0, 2l_y))$
for some
$m \gt l_y$
, which does not contain any special vertices. Therefore, from (40) we obtain
\begin{align*}\mathbb{P}\Big(A_{\text{sp}}^{l_y}(\mathbf{w}_i + (0, 2l_y))^c \mid \mathcal{G}_\ell\Big)\leq C^\prime_0 \exp{\big(\!-\!C^\prime_1 l_y\big)}\end{align*}
for some
$C^\prime_0, C^\prime_1 \gt 0$
. This gives us the required tail decay estimate for
$\mathbb{P}((F^4_\ell)^c)$
.
Finally, Lemma 8(iv) ensures that
$\mathbb{P}((F^5_\ell)^c)$
decays subexponentially in
$Z_\ell$
and thereby completes the proof of Lemma 11.
Remark 6. Proposition 3 gives us that for
$k= 2$
, the family
$\{ \sigma_{\ell + 1}(\mathbf{x}_1, \mathbf{x}_2) - \sigma_\ell(\mathbf{x}_1, \mathbf{x}_2) \;:\; \ell \geq 1\}$
is a collection of non-negative integer-valued random variables with strong uniform exponential decay such that the decay constants do not depend on the choice of the starting points
$\mathbf{x}_1, \mathbf{x}_2$
. We will use this later to obtain the tail estimate for the coalescence time of two paths.
6. Proof of Theorem 1: coalescence time of two paths
For
$\mathbf{x}_1, \mathbf{x}_2 \in \mathbb{Z}^2$
with
$\mathbf{x}_1(2) = \mathbf{x}_2(2)$
the coalescence time of two paths
$\pi^{\mathbf{x}_1}$
and
$\pi^{\mathbf{x}_2}$
starting from
$\mathbf{x}_1$
and
$\mathbf{x}_2$
, respectively, is denoted by
\begin{align*} T(\mathbf{x}_1,\mathbf{x}_2) \;:\!=\; \inf \big\{ t \geq 0 \;:\; \pi^{\mathbf{x}_1}(t) = \pi^{\mathbf{x}_2}(t) \big\} . \end{align*}
In this section, we prove the following theorem on the tail decay of
$T(\mathbf{x}_1, \mathbf{x}_2)$
, which is a key result for proving convergence to the Brownian web.
Theorem 3. For
$\mathbf{x}_1, \mathbf{x}_2 \in \mathbb{Z}^2$
with
$\mathbf{x}_1(2) = \mathbf{x}_2(2)$
and
$\mathbf{x}_1(1) \lt \mathbf{x}_2(1)$
, there exists a constant
$C_{0}\gt0$
which does not depend on
$\mathbf{x}_1,\mathbf{x}_2$
such that, for any
$t\gt0$
,
\begin{align*}\mathbb{P}(T(\mathbf{x}_1,\mathbf{x}_2) \gt t ) \leq \frac{C_{0}(\mathbf{x}_2(1)-\mathbf{x}_1(1))}{\sqrt{t}} .\end{align*}
To prove Theorem 3 we follow a robust technique developed by Coupier et al. [Reference Coupier, Saha, Sarkar and Tran8]. This technique is applicable for a general class of processes which need not be Markov but behave like mean zero random walks away from the origin and satisfy certain moment bounds (see Corollary 1). Proposition 7 ensures that the difference between two paths observed at renewal steps satisfies these properties and allows us to apply this technique to get a suitable tail decay in terms of the number of (joint) renewal steps. With some additional work, we obtain the tail estimate for the coalescence time in terms of the total number of steps.
For completeness we quote the following corollary from [Reference Coupier, Saha, Sarkar and Tran8].
Corollary 1. (Corollary 5.6 in [Reference Coletti and Valle10].) Let
$\{Y_t \;:\; t \geq 0\}$
be a
$\{\mathcal{G}_t \;:\; t \geq 0\}$
adapted process taking values in
$\mathbb{R}_+$
. Let
$\nu^Y \;:\!=\; \inf\{t \geq 1 \;:\; Y_t = 0\}$
be the first hitting time to 0. Suppose for any
$t \geq 0$
there exist positive constants
$ M_0$
,
$C_0$
,
$C_1$
,
$C_2$
, and
$C_3 $
such that:
-
(i) there exists an event
$F_t$
such that, on the event
$\{Y_t\gt M_0\}$
, we have
\begin{align*}\mathbb{P}\big(F^c_t \mid \mathcal{G}_t\big) \leq C_0 / Y^3_t \quad\textit{and}\quad \mathbb{E} [ (Y_{t+1}-Y_t) \mathbf{1}_{F_t} \mid \mathcal{G}_t] = 0;\end{align*}
-
(ii) for any
$t\geq 0$
, on the event
$\{Y_t \leq M_0\}$
,
\begin{align*}\mathbb{E} [(Y_{t+1}-Y_t) \mid \mathcal{G}_t] \leq C_1;\end{align*}
-
(iii) for any
$t\geq 0$
and
$ m \gt 0 $
, there exists
$c_m \gt 0 $
such that, on the event
$\{Y_t \in (0, m]\}$
,
\begin{align*}\mathbb{P} ( Y_{t+1} = 0 \mid \mathcal{G}_t) \geq c_m;\end{align*}
-
(iv) for any
$t \geq 0$
, on the event
$\{Y_t\gt M_0\}$
, we have
\begin{align*}\mathbb{E} \bigl[ (Y_{t+1} - Y_t)^2 \mid \mathcal{ G}_t \bigr] \geq C_2 \; \quad\text{ and }\quad \; \mathbb{E} \bigl[ |Y_{t+1} - Y_t|^3 \mid \mathcal{ G}_t \bigr] \leq C_3.\end{align*}
Then
$\nu^Y\lt\infty $
a.s. Further, there exist positive constants
$C_4$
and
$C_5$
such that for any
$y\gt0$
and any integer n, we have
\begin{align*}\mathbb{P}( \nu^Y \gt n \mid Y_0 = y) \leq \frac{C_4 + C_5 y}{\sqrt{n}}.\end{align*}
Proposition 7 ensures that (i)–(iv) of Corollary 1 are satisfied by the process
$\{Z_\ell \;:\; \ell \geq 0\}$
defined in (35), and thus we have the required decay estimate in terms of the number of (joint) renewal steps before coalescence. Using these estimates, we proceed to establish Theorem 3.
Proof of Theorem
3. If
$h^{\sigma_{\ell}}(\mathbf{x}_1) = h^{\sigma_{\ell}}(\mathbf{x}_2)$
then
$ h^{m}(\mathbf{x}_1) = h^{m}(\mathbf{x}_2)$
for some
$m\leq \sigma_{\ell}$
. Let
$\nu \;:\!=\; \min\{l\;:\; Z_l(\mathbf{x}_1, \mathbf{x}_2) = 0\}$
denote the number of (joint) regeneration steps required for coalescence, and
$Z_\ell$
is defined as in (35). Clearly, we have
$T(\mathbf{x}_1, \mathbf{x}_2) \leq \sigma_\nu$
.
Consider an i.i.d. sequence
$\{ W_\ell \;:\; \ell \geq 1\}$
with an exponentially decaying tail such that, for each
$\ell \geq 1$
, the conditional distribution of
$(\sigma_{\ell + 1}(\mathbf{x}_1, \mathbf{x}_2) -\sigma_{\ell}(\mathbf{x}_1, \mathbf{x}_2))$
given
$ \mathcal{S}_{\ell}$
is stochastically dominated by
$W_{\ell+1}$
. This is possible because the family
$\{(\sigma_{\ell + 1}(\mathbf{x}_1, \mathbf{x}_2) -\sigma_{\ell}(\mathbf{x}_1, \mathbf{x}_2)) \;:\; \ell \geq 1\}$
has strong uniform exponential tail decay. For
$c = 1/\mathbb{E}(2W_1)$
we have
\begin{align*}\mathbb{P}(\sigma_{\nu} \gt t) & \leq \mathbb{P} \Bigg( \sum_{\ell = 1}^{\lfloor ct \rfloor + 1} W_{\ell} \geq t \Bigg) + \mathbb{P} ( \nu \gt ct ) \\[5pt] & \leq \mathbb{P} \Bigg( \sum_{\ell = 1}^{\lfloor ct \rfloor + 1} (W_{\ell} - \mathbb{E}(W_1)) \geq t(1- c\mathbb{E}(W_1)) \Bigg) + \frac{C_{0}}{\sqrt{ct}} (\mathbf{x}_2(1)-\mathbf{x}_1(1)) \\[5pt] & \leq \frac{\text{Var} \Big( \sum_{\ell = 1}^{\lfloor ct \rfloor + 1} W_{\ell} \Big)} { (t(1- c\mathbb{E}(W_1)))^2} + \frac{C_{0}}{\sqrt{ct}} (\mathbf{x}_2(1)-\mathbf{x}_1(1))\\[5pt] & \leq \frac{(\lfloor ct \rfloor + 1)\text{Var}(W_1)}{(t/2 )^2} +\frac{C_{0}}{\sqrt{ct}} (\mathbf{x}_2(1)-\mathbf{x}_1(1)) \\[5pt] & \leq \frac{C_{1}}{\sqrt{t}} (\mathbf{x}_2(1)-\mathbf{x}_1(1))\end{align*}
for a suitable choice of a constant
$C_1 \gt 0$
. This completes the proof.
We observe that Theorem 3 is applicable for paths starting from
$\mathbf{x}_1, \mathbf{x}_2 \in \mathbb{Z}^2$
with
$\mathbf{x}_1(2) = \mathbf{x}_2(2)$
and with no information about the collection of random vectors
$\{\Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^-(\mathbf{x}_1(2))\}$
. However to apply this result we need to estimate the coalescence time of two paths after they come close enough. We need to be careful as perturbed source vertices in the upper half-plane need not be independent. We develop a modified version of Theorem 3 which would be applicable in such situations. Before ending this section, we state such a version of Theorem 3, and this version would be more useful in proving the finite-dimensional convergence to coalescing Brownian motions. We need to introduce some notation.
Fix
$\beta \in (0, 1/2)$
and lattice points
$\mathbf{w}_1, \mathbf{w}_2 \in \mathbb{Z}^2$
with
$\mathbf{w}_1(2) = \mathbf{w}_2(2) = 0$
and
$\mathbf{w}_1(1) \lt \mathbf{w}_2(1)$
. Let
$\mathcal{R} \subset \mathbb{H}^-(0)$
be a bounded region. Proposition 8 gives us that given any realizations of the collection of random vectors
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}_n\}$
satisfying
$\tilde{\mathbf{w}} \in \mathbb{H}^-(n^\beta)$
for all
$\mathbf{w} \in \mathcal{R}$
, the same tail estimate for the coalescence time of paths as in Theorem 3 holds.
Proposition 8. For
$\mathbf{w}_1, \mathbf{w}_2 \in \mathbb{Z}^2$
with
$\mathbf{w}_1(2) = \mathbf{w}_2(2)$
and
$\mathbf{w}_1(1) \lt \mathbf{w}_2(1)$
, there exists
$C_0 \gt 0$
(not depending on
$\mathbf{w}_1, \mathbf{w}_2$
) such that for all large n we have
\begin{align*}\mathbb{P} \bigl( T(\mathbf{w}_1, \mathbf{w}_2) \gt n \mid \bigl ( \{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}\} & \text{ such that }\tilde{\mathbf{w}} \in \mathbb{H}^-(n^\beta) \text{ for all }\mathbf{w} \in \mathcal{R} \bigr ) \bigr )\leq C_0\frac{(\mathbf{w}_2(1) - \mathbf{w}_1(1))}{\sqrt{n}}.\end{align*}
Proof. Choose
$\alpha \in (0, 1/2)$
such that
$\alpha \gt \beta$
, and define the events
$B^1_n$
and
$B^2_n$
, respectively, as
\begin{align*}B^1_n \;:\!=\; \big\{ \sigma_1 = \sigma_1(\mathbf{w}_1, \mathbf{w}_2) \lt 2 n^\beta \big\}\end{align*}
and
\begin{align*}B^2_n \;:\!=\; \bigcap_{i=1}^2 \bigl \{ \max \{|(h^{j}(\mathbf{w}_i) - \mathbf{w}_i)(1)| \;:\; 1 \leq j \lt 2n^\beta \} \leq n^\alpha \bigr \}.\end{align*}
The event
$B^1_n$
says that the first (joint) renewal step
$\sigma_1(\mathbf{w}_1, \mathbf{w}_2)$
occurs within the next
$\lfloor 2n^\beta \rfloor$
many steps. Recall that we have obtained strong uniform exponential tail decay in Proposition 2 for the family
$\{\tau_{j+1}(\mathbf{w}_1, \mathbf{w}_2) - \tau_j(\mathbf{w}_1, \mathbf{w}_2) \;:\; j \geq 0\}$
through repeated occurrences of
$A_{\text{sp}}()$
events. These events depend only on the collection
$\{\Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(0)\}$
. Also, given any realization of the collection
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}\}$
satisfying
$\tilde{\mathbf{w}} \in \mathbb{H}^-(n^\beta)$
for all
$\mathbf{w} \in \mathcal{R}$
, the probability of the occurrence of the ‘Out’ event at a
$\tau_j$
step with
$\tau_j \geq n^\beta$
becomes higher than having no information on
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}\}$
. Therefore, given any realization of the collection
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}\}$
satisfying
$\tilde{\mathbf{w}} \in \mathbb{H}^-(n^\beta)$
for all
$\mathbf{w} \in \mathcal{R}$
, the argument of Proposition 3 still ensures that
$\mathbb{P}((B^1_n)^c)$
decays subexponentially in n. Since, the proof of Lemma 8(iv) uses ‘special’ points in the upper half-plane
$\mathbb{H}^+(0)$
, given any realization of the collection
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}_n\}$
, the probability
$\mathbb{P}((B^2_n)^c)$
decays subexponentially.
Let
$\sigma$
be the first joint renewal step after crossing the line
$y = n^\beta$
. On the event
$B^1_n \cap B^2_n$
, the coalescence time
$T(\mathbf{w}_1, \mathbf{w}_2)$
is dominated by
$T(h^{\sigma}(\mathbf{w}_1), h^{\sigma}(\mathbf{w}_2)) + 2n^\beta$
. We observe that the coalescence time
$T(h^{\sigma}(\mathbf{w}_1), h^{\sigma}(\mathbf{w}_2))$
depends on the collection of random vectors
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(\sigma)\}$
which is contained in the collection
$\{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathbb{H}^+(n^\beta)\}$
. Therefore, for all large n we obtain
\begin{align*}& \mathbb{P} \bigl( T(\mathbf{w}_1, \mathbf{w}_2) \gt n \mid \bigl ( \{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}\} \text{ such that }\tilde{\mathbf{w}} \in \mathbb{H}^-\big(n^\beta\big) \text{ for all }\mathbf{w} \in \mathcal{R} \bigr ) \bigr )\\[2pt] & \leq \mathbb{P} \bigl( (T(\mathbf{w}_1, \mathbf{w}_2) \gt n)\cap B^1_n \cap B^2_n\mid \bigl ( \{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}\} \text{ such that }\tilde{\mathbf{w}} \in \mathbb{H}^-\big(n^\beta\big) \\[2pt] & \qquad \qquad \text{ for all }\mathbf{w} \in \mathcal{R} \bigr ) \bigr ) + \mathbb{P}\big(\big(B^1_n\big)^c\big) + \mathbb{P}\big(\big(B^2_n\big)^c\big)\\[2pt] & \leq \mathbb{P} \bigl( (T(h^{\sigma}(\mathbf{w}_1), h^{\sigma}(\mathbf{w}_2)) + 2n^\beta \gt n)\cap B^1_n \cap B^2_n\mid \bigl ( \{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}\} \text{ such that }\\[2pt] & \qquad \qquad \tilde{\mathbf{w}} \in \mathbb{H}^-\big(n^\beta\big) \text{ for all }\mathbf{w} \in \mathcal{R} \bigr ) \bigr ) + \mathbb{P}\big(\big(B^1_n\big)^c\big) + \mathbb{P}\big(\big(B^2_n\big)^c\big)\\[2pt] & \leq \mathbb{P} \bigl( (T(h^{\sigma}(\mathbf{w}_1), h^{\sigma}(\mathbf{w}_2)) \gt n/2)\cap B^1_n \cap B^2_n\mid \bigl ( \{ \Gamma_{\mathbf{w}} \;:\; \mathbf{w} \in \mathcal{R}\} \text{ such that }\\[2pt] & \qquad \qquad \tilde{\mathbf{w}} \in \mathbb{H}^-\big(n^\beta\big) \text{ for all }\mathbf{w} \in \mathcal{R} \bigr ) \bigr ) + \mathbb{P}\big(\big(B^1_n\big)^c\big) + \mathbb{P}\big(\big(B^2_n\big)^c\big)\\[2pt] & = \mathbb{P} \bigl( (T(h^{\sigma}(\mathbf{w}_1), h^{\sigma}(\mathbf{w}_2)) \gt n/2)\cap B^1_n \cap B^2_n \bigr ) + \mathbb{P}\big(\big(B^1_n\big)^c\big) + \mathbb{P}\big(\big(B^2_n\big)^c\big)\\[2pt] & \leq C_0 (\mathbf{w}_2(1) - \mathbf{w}_1(1) + 2n^\alpha)/\sqrt{n} \\[2pt] & \leq C^\prime_0 (\mathbf{w}_2(1) - \mathbf{w}_1(1))/\sqrt{n}\end{align*}
for some
$C^\prime_0 \gt 0$
. This completes the proof.
We are now ready to prove Theorem 1.
Proof of Theorem
1. We prove that the network G is a.s. connected. Theorem 3 gives us that the coalescence time of two paths starting from
$\mathbf{w}_1, \mathbf{w}_2 \in \mathbb{Z}^2$
with
$\mathbf{w}_1(2) =\mathbf{w}_2(2)$
is finite a.s. Therefore, we have
\begin{align}\mathbb{P} \Bigg [ \bigcap_{\mathbf{w}_1, \mathbf{w}_2 \in \mathbb{Z}^2, \mathbf{w}_1(2) = \mathbf{w}_2(2)} \big\{\text{the paths }\pi^{\mathbf{w}_1}, \pi^{\mathbf{w}_2} \text{ coalesce eventually}\big\}\Bigg ] = 1.\end{align}
It is straightforward to observe that (41) proves Theorem 1.
7. Convergence to the Brownian web
This section is devoted to the proof of Theorem 2. In Subsection 7.1 we present a brief introduction to the Brownian web and its dual and to the relevant topological details of the space of convergence and convergence conditions applicable for non-crossing path models. In Subsection 7.2, we prove a stronger version of Theorem 2 and show that under diffusive scaling the network together with its dual process jointly converges to the Brownian web and its dual.
7.1. The Brownian web and its dual
We recall the relevant topological details from [Reference Fontes, Isopi, Newman and Ravishankar14]. Let
$\mathbb{R}^{2}_{\mathrm{c}}$
denote the completion of the space–time plane
$\mathbb{R}^2$
with respect to the metric
\begin{align*}\rho((x_1,t_1),(x_2,t_2))=|\tanh(t_1)-\tanh(t_2)|\vee \Bigl| \frac{\tanh(x_1)}{1+|t_1|}-\frac{\tanh(x_2)}{1+|t_2|} \Bigr|.\end{align*}
As a topological space
$\mathbb{R}^{2}_{\mathrm{c}}$
can be identified with the continuous image of
$[\!-\!\infty,\infty]^2$
under a map that identifies the line
$[\!-\!\infty,\infty]\times\{\infty\}$
with the point
$(\ast,\infty)$
, and the line
$[\!-\!\infty,\infty]\times\{-\infty\}$
with the point
$(\ast,-\infty)$
. A path
$\pi$
in
$\mathbb{R}^{2}_{\mathrm{c}}$
with starting time
$\sigma_{\pi}\in [\!-\!\infty,\infty]$
is a mapping
$\pi \;:\; [\sigma_{\pi},\infty]\rightarrow [\!-\!\infty,\infty]$
such that
$\pi(\infty)= \pi(-\infty)= \ast$
and
$t\rightarrow (\pi(t),t)$
is a continuous map from
$[\sigma_{\pi},\infty]$
to
$(\mathbb{R}^{2}_{\mathrm{c}},\rho)$
. We then define
$\Pi$
to be the space of all paths in
$\mathbb{R}^{2}_{\mathrm{c}}$
with all possible starting times in
$[\!-\!\infty,\infty]$
equipped with the metric
\begin{align*}d_{\Pi} (\pi_1,\pi_2)= |\tanh(\sigma_{\pi_1})-\tanh(\sigma_{\pi_2})|\vee\sup_{t\geq\sigma_{\pi_1}\wedge\sigma_{\pi_2}} \Bigl|\frac{\tanh(\pi_1(t\vee\sigma_{\pi_1}))}{1+|t|}-\frac{\tanh(\pi_2(t\vee\sigma_{\pi_2}))}{1+|t|}\Bigr|\end{align*}
for
$\pi_1,\pi_2\in \Pi$
. This metric makes
$\Pi$
a complete, separable metric space. Convergence in this metric can be described as locally uniform convergence of paths as well as convergence of starting times. Let
$\mathcal{H}$
be the space of compact subsets of
$(\Pi,d_{\Pi})$
equipped with the Hausdorff metric
$d_{\mathcal{H}}$
given by
\begin{align*}d_{\mathcal{H}}(K_1,K_2)= \sup_{\pi_1 \in K_1} \inf_{\pi_2 \in K_2}d_{ \Pi} (\pi_1,\pi_2)\vee\sup_{\pi_2 \in K_2} \inf_{\pi_1 \in K_1} d_{\Pi} (\pi_1,\pi_2).\end{align*}
The space
$(\mathcal{H},d_{\mathcal{H}})$
is a complete separable metric space. Let
$B_{\mathcal{H}}$
be the Borel
$\sigma$
-algebra on the metric space
$(\mathcal{H},d_{\mathcal{H}})$
. The Brownian web
${\mathcal W}$
is then defined and characterized as an
$(\mathcal{H}, B_{\mathcal{H}})$
-valued random variable by the following result obtained by Fontes et al. [Reference Fontes, Isopi, Newman and Ravishankar14] which shows that the Brownian web is a.s. determined by countably many coalescing Brownian motions.
Theorem 4. (Theorem 2.1 in [Reference Ghosh and Saha16].) There exists an
$({\mathcal H}, {\mathcal B}_{{\mathcal H}})$
-valued random variable
${\mathcal W}$
whose distribution is uniquely determined by the following properties.
-
(a) From any deterministic point
$\mathbf{x}\in\mathbb{R}^2$
, there is a.s. a unique path
$\pi^{\mathbf{x}}\in {\mathcal W}$
starting from
$\mathbf{x}$
. -
(b) For a finite set of deterministic points
$\mathbf{x}_1,\dotsc, \mathbf{x}_k \in \mathbb{R}^2$
, the collection
$(\pi^{\mathbf{x}_1},\dotsc,\pi^{\mathbf{x}_k})$
is distributed as coalescing Brownian motions starting from
$\mathbf{x}_1,\dotsc,\mathbf{x}_k$
. -
(c) For any countable deterministic dense set
${\mathcal D}$
of
$\mathbb{R}^2$
,
${\mathcal W}$
is the closure of
$\{\pi^{\mathbf{x}}\;:\; \mathbf{x}\in {\mathcal D} \}$
in
$(\Pi, d_{\Pi})$
a.s.
Let
$\Xi \subset \Pi$
. For
$t \gt 0$
and
$t_0, a, b \in\mathbb{R}$
with
$a \lt b$
, consider the counting random variable
$\eta_{\Xi}(t_0, t;\; a, b)$
defined as
\begin{align*}\eta_{\Xi}(t_0, t;\; a, b) \;:\!=\; \#\{ \pi(t_0 + t)\;:\; \pi \in \Xi, \sigma_\pi \leq t_0\quad\text{ and }\quad \pi(t_0) \in [a, b]\},\end{align*}
i.e. paths in
$\Xi$
, start before time
$t_0$
, those pass through [a, b] at time
$t_0$
, and counts the number of different positions these paths occupy at time
$t_0 + t$
. In Theorem 2.2 in [Reference Fontes, Isopi, Newman and Ravishankar14], Fontes et al. provided the first set of convergence criteria to the Brownian web applicable for models with non-crossing paths. A survey article by Schertzer et al. [Reference Schertzer, Sun, Swart, Contucci and Giardinà29] provides an excellent comprehensive overview of this topic.
Theorem 5. (Theorem 2.2 in [Reference Ghosh and Saha16].) Let
$\{ \Xi_n \;:\; n \in \mathbb{N} \}$
be a sequence of
$(\mathcal{H}, \mathcal{B}_{\mathcal{H}})$
-valued random variables with non-crossing paths. Assume that the following conditions hold:
-
(I1) Fix a deterministic countable dense set
$\mathcal{D}$
of
$\mathbb{R}^2$
. For each
$\mathbf{x} \in \mathcal{D}$
, there exists
$\pi^{\mathbf{x}}_n \in \Xi_n$
such that for any finite set of points
$\mathbf{x}_1, \ldots , \mathbf{x}_k \in \mathcal{D}$
, as
$n \to \infty$
, we have
$(\pi^{\mathbf{x}_1}_n , \ldots , \pi^{\mathbf{x}_k}_n )$
converges in distribution to
$(W^{\mathbf{x}_1}, W^{\mathbf{x}_2}, \ldots ,W^{\mathbf{x}_k})$
, where
$(W^{\mathbf{x}_1}, W^{\mathbf{x}_2}, \ldots ,W^{\mathbf{x}_k})$
denotes coalescing Brownian motions starting from the points
$\mathbf{x}^1, \ldots, \mathbf{x}^k$
. -
(B1) For all
$t \gt 0$
,
$ \frac{1}{\epsilon}\limsup_{n\to \infty} \sup_{(a,t_0) \in \mathbb{R}^2} \mathbb{P}( \eta_{\Xi_n}(t_0, t;\; a, a + b) \geq 2) \to 0$
as
$\epsilon \downarrow 0$
. -
(B2) For all
$t \gt 0$
,
$\limsup_{n\to \infty} \sup_{(a,t_0) \in \mathbb{R}^2} \mathbb{P}( \eta_{\Xi_n}(t_0, t;\; a, a + b) \geq 3) \to 0$
as
$\epsilon \downarrow 0$
.
We note that for our model, the paths are a.s. non-crossing. As a result, for any
$n \geq 1$
, the scaled collection of paths
$\mathcal{X}_n(\gamma, \sigma)$
(defined as in (42)) a.s. forms a family of non-crossing paths. Its closure is denoted by
$\overline{\mathcal{X}}_n(\gamma, \sigma)$
. In this paper we apply an alternative set of convergence conditions, which hold only for non-crossing path models (see [Reference Coupier, Saha, Sarkar and Tran8]). For that we need to introduce the notion of dual paths for a collection of coalescing non-crossing paths. Corresponding to any collection of non-crossing coalescing paths from
$\Pi$
, where paths are moving in the upward direction of time, we define a dual collection of non-crossing coalescing paths going in the downward direction of time such that the forward paths and the backward paths do not cross each other. In general, such a dual collection is not uniquely defined. As in the case of forward paths, we can consider a similar metric space of a collection of backward paths denoted by
$(\widehat{\Pi}, d_{\widehat{\Pi}})$
. Let
$(\widehat{{\mathcal H}}, d_{\widehat{{\mathcal H}}})$
denote the corresponding Polish space of compact collections of backward paths with the induced Hausdorff metric. The Brownian web and its dual denoted by
$({\mathcal W},\widehat{{\mathcal W}})$
is a
$({\mathcal H}\times \widehat{{\mathcal H}}, {\mathcal B}_{{\mathcal H}\times \widehat{{\mathcal H}}})$
-valued random variable such that:
-
(i)
$\widehat{{\mathcal W}}$
is distributed as the Brownian web rotated
$180^{\circ}$
about the origin; -
(ii)
${\mathcal W}$
and
$\widehat{{\mathcal W}}$
uniquely determine each other in the sense that the paths of
$\mathcal{W}$
a.s. do not cross with (backward) paths in
$\widehat{\mathcal{W}}$
; the interaction between the paths in
${\mathcal W}$
and
$\widehat{\mathcal W}$
is that of Skorohod reflection (see [Reference Soucaliuc, Tóth and Werner30]).
We are now ready to state Theorem 6 from [Reference Coupier, Saha, Sarkar and Tran8], which provides conditions for joint convergence to the Brownian web and its dual and which will be used in proving Theorem 2.
Theorem 6 (Theorem 6.3 in [Reference Coletti and Valle10].) Let
$\{(\Xi_n, \widehat{\Xi}_n) \;:\; n\geq 1\}$
be a sequence of
$(\mathcal{H}\times\widehat{\mathcal{H}}, \mathcal{B}_{\mathcal{H}\times\widehat{\mathcal{H}}})$
-valued random variables with non-crossing paths only, satisfying the following assumptions:
-
(i) for each
$n \geq 1$
, paths in
$\Xi_n$
do not cross (backward) paths in
$\widehat{\Xi}_n$
a.s., i.e. there does not exist any
$\pi\in\Xi_n$
,
$\widehat{\pi}\in\widehat{\Xi}_n$
, and
$t_1,t_2\in (\sigma_{\pi},\sigma_{\widehat{\pi}})$
such that
$(\widehat{\pi}(t_1) - \pi(t_1))(\widehat{\pi}(t_2) - \pi(t_2))\lt0$
a.s.; -
(ii)
$\{\Xi_n \;:\; n \in \mathbb{N} \}$
satisfies
$(I_1)$
, where (
$I_1$
) is given as in Theorem 5; -
(iii)
$\{(\widehat{\pi}_n(\sigma_{\widehat{\pi}_n}),\sigma_{\widehat{\pi}_n}) \;:\; \widehat{\pi}_n \in \widehat{\Xi}_n \}$
, the collection of starting points of all the backward paths in
$\widehat{\Xi}_n$
, as
$n \to \infty$
, becomes dense in
$\mathbb{R}^2$
; -
(iv) for any subsequential limit
$(\mathcal{Z},\widehat{\mathcal{Z}})$
of
$\{(\Xi_n,\widehat{\Xi}_n) \;:\; n \in \mathbb{N} \}$
, paths of
$\mathcal{Z}$
do not spend positive Lebesgue measure time together with paths of
$\widehat{\mathcal{Z}}$
, i.e. a.s. there is no
$\pi\in\mathcal{Z}$
and
$\widehat{\pi}\in\widehat{\mathcal{Z}}$
such that
$\int_{\sigma_\pi}^{\sigma_{\widehat{\pi}}} \mathbf{1}_{\pi(t)=\widehat{\pi}(t)} \,{\rm d}t \gt 0$
.
Then
$( \overline{\mathcal{X}}_n(\gamma,\sigma) , \overline{\widehat{\mathcal{X}}}_n(\gamma,\sigma) )$
converges in distribution
$(\mathcal{W}, \widehat{\mathcal{W}})$
as
$n \to \infty$
.
We now construct a dual graph for our network. The construction of the dual graph
$\widehat{G}$
for the network is not unique, and our construction is inspired from the construction of the dual network for Howard’s model in [Reference Roy, Saha and Sarkar26]. For our dual graph
$\widehat{G}$
, the dual vertices are precisely the midpoints between two consecutive vertices in V on each horizontal line
$y = m$
for
$m \in \mathbb{Z}$
. We ensure that each dual vertex has a unique offspring dual vertex in the negative direction of the y-axis. Before giving a formal definition, we direct the reader to Figure 6.
The black and grey points together represent points of V and the black arrows represent PH paths. The white points are the points of the dual process and the grey (dashed) paths are the dual paths.
For
$\mathbf{u} \in \mathbb{Z}^2$
, we define
\begin{align*}\begin{split}J^{+}_{\mathbf{u}} & \;:\!=\; \inf\{k\;:\; k \geq 1, \mathbf{u} + (k,0) \in V\}, \\[2pt] J^{-}_{\mathbf{u}} & \;:\!=\; \inf \{k\;:\; k\geq 1, \mathbf{u} - (k,0) \in V\}.\end{split}\end{align*}
Next we define
$r(\mathbf{u})\;:\!=\; \mathbf{u} + (J^{+}_{\mathbf{u}},0)$
and
$\ell(\mathbf{u})\;:\!=\;u\mathbf{u} + (\!-\!J^{+}_{\mathbf{u}},0)$
as the first open point to the right (open right neighbour) and the first open point to the left (open left neighbour) of
$\mathbf{u}$
at the same level
$y = \mathbf{u}(2)$
, respectively. For
$\mathbf{u} \in V$
, let
$\widehat{r}(\mathbf{u}) \;:\!=\; \mathbf{u} + ( J^{+}_{\mathbf{u}}/2,0)$
and
$\widehat{\ell}(\mathbf{u}) \;:\!=\; \mathbf{u} -(J^{-}_{\mathbf{u}}/2,0)$
respectively denote the right dual neighbour and the left dual neighbour of
$\mathbf{u}$
in the dual vertex set. Finally, the dual vertex set is given by
\begin{align*}\widehat{V} \;:\!=\; \{\widehat{r}(\mathbf{u}),\widehat{\ell}(\mathbf{u})\;:\;(\mathbf{u}) \in V \}.\end{align*}
For a vertex
$ \mathbf{v} \in \widehat{V} $
, let
$ \mathbf{w} \in \widehat{V} $
with
$\mathbf{w}(2) = \mathbf{v}(2) - 1$
be such that the straight line segment joining
$ \mathbf{v}$
and
$\mathbf{w}$
does not cross any edge in G. The dual edges are edges joining all such
$ \mathbf{v}$
and
$ \mathbf{w} $
. Formally, for
$\mathbf{v} \in \widehat{V}$
, we define
\begin{align*}\begin{split}a^{\ell} (\mathbf{v}) & \;:\!=\; \sup \{ \mathbf{u}(1) \;:\; \mathbf{u} \in V, \mathbf{u}(2) = \mathbf{v}(2) - 1, h(\mathbf{u})(1) \lt \mathbf{v}(1) \}, \\[5pt] a^{r} (\mathbf{v}) & \;:\!=\; \inf\{ \mathbf{u}(1) \;:\; \mathbf{u} \in V,\mathbf{u}(2) = \mathbf{v}(2) - 1, h(\mathbf{u})(1) \gt \mathbf{v}(1) \},\end{split}\end{align*}
and set
$ \widehat{h} ( \mathbf{v}) \;:\!=\; ( (a^{\ell} (\mathbf{v})+a^{r} (\mathbf{v}))/2, \mathbf{v}(2)- 1) $
. Note that
$ ( a^{r} (\mathbf{v}), \mathbf{v}(2)-1) $
and
$ (a^{\ell} (\mathbf{v}), \mathbf{v}(2)-1) $
are the nearest vertices in V to the right and left, respectively, of the dual vertex
$ \widehat{h} (\mathbf{v}) $
. Finally, the edge set of the dual graph
$\widehat{G} \;:\!=\; (\widehat{V}, \widehat{E})$
is given by
\begin{align*}\widehat{E} \;:\!=\; \{ \langle \mathbf{v}, \widehat{h}(\mathbf{v}) \rangle \;:\; \mathbf{v} \in \widehat{V}\}.\end{align*}
Clearly, each dual vertex has exactly one outgoing edge, which goes in the downward direction. Hence, the dual graph
$\widehat{G}\;:\!=\; (\widehat{V},\widehat{E})$
does not contain any cycle or loop. This forest
$\widehat{G}$
is entirely determined from G.
The dual (or backward) path
$\widehat{\pi}^{\mathbf{y}} \in \widehat{\Pi}$
starting at
$\mathbf{y} \in \widehat{V}$
is constructed by linearly joining successive
$\widehat{h}(\!\cdot\!)$
steps. Thus,
$\widehat{\mathcal{X}}\;:\!=\;\{\widehat{\pi}^{(y,s)} \;:\; (y,s) \in \widehat{V}\}$
denotes the collection of all dual paths obtained from
$\widehat{G}$
.
Let us recall that
$\mathcal{X}_n=\mathcal{X}_n(\gamma,\sigma)$
for
$\gamma,\sigma\gt0$
and
$n\geq 1$
is the collection of nth-order diffusively scaled paths with normalization constants
$\gamma$
and
$\sigma$
(see (5)). In the same way, we define
$\widehat{\mathcal{X}}_n=\widehat{\mathcal{X}}_n(\gamma,\sigma)$
as the collection of diffusively scaled dual paths. For any dual path
$\widehat{\pi}$
with starting time
$\sigma_{\widehat{\pi}}$
, the scaled dual path
$\widehat{\pi}_n(\gamma,\sigma) \;:\; [\!-\!\infty , \sigma_{\widehat{\pi}}/n\gamma] \to [\!-\!\infty, \infty]$
is given by
\begin{align}\widehat{\pi}_n(\gamma,\sigma) (t) \;:\!=\; \widehat{\pi}(n\gamma t)/\sqrt{n }\sigma.\end{align}
For each
$n\geq 1$
, the closure of
$\widehat{\mathcal{X}}_n$
in
$(\widehat{\Pi},d_{\widehat{\Pi}})$
, denoted by
$\overline{\widehat{\mathcal{X}}}_n$
, is an
$(\widehat{\mathcal{H}}, \mathcal{B}_{\widehat{\mathcal{H}}})$
-valued random variable. We are now ready to state our result regarding the joint convergence to the Brownian web and its dual for our model and its dual.
Theorem 7. There exist
$\sigma, \gamma \gt0$
such that the sequence
\begin{align*}\big\{\big( \overline{\mathcal{X}}_n , \overline{\widehat{\mathcal{X}}}_n \big) = \big( \overline{\mathcal{X}}_n(\gamma,\sigma) , \overline{\widehat{\mathcal{X}}}_n(\gamma,\sigma) \big) \;:\; n \geq 1 \big\}\end{align*}
converges in distribution to
$(\mathcal{W}, \widehat{\mathcal{W}})$
as
$(\mathcal{H}\times \widehat{\mathcal{H}},\mathcal{B}_{\mathcal{H}\times \widehat{\mathcal{H}}})$
-valued random variables as
$n\rightarrow\infty$
.
7.2. Verification of conditions of Theorem 6
In this subsection, we show that the sequence of diffusively scaled path families
$\{(\overline{\mathcal{X}}_n,\overline{\widehat{\mathcal{X}}}_n) \;:\; n \geq 1\}$
obtained from the network and its dual satisfies the conditions in Theorem 6.
Conditions (i) and (iii) of Theorem 6 hold by construction. Indeed, paths of
$\mathcal{X}$
do not cross the (backward) paths of
$\widehat{\mathcal{X}}$
with probability 1, and the same holds for
$\overline{\mathcal{X}}_n$
and
$\overline{\widehat{\mathcal{X}}}_n$
for any
$n \geq 1$
and for their respective closures as well. Moreover, as
$n \to \infty$
, the set of all starting points of the scaled backward paths in
$\widehat{\mathcal{X}}_n$
becomes dense in
$\mathbb{R}^2$
. We prove condition (ii) in the following subsection.
7.2.1. Verification of condition (ii) of Theorem 6
In this subsection, we show that condition (ii) holds for the sequence
$\{\overline{\mathcal{X}}_n \;:\; n\geq 1\}$
, i.e. criterion
$(\mathrm{I}_1)$
of Theorem 6 holds.
We first focus on a single path,
$\pi^{\mathbf{0}}$
starting at the origin. The main ingredient here is the construction of i.i.d. pieces through (marginal) renewal steps. As shown in Proposition 5, the sequence of renewal steps
$\{ h^{\sigma_\ell}(\mathbf{0})(1) \;:\; \ell \geq 1\}$
decomposes the path
$\pi^{\mathbf{0}}$
into independent pieces. Let
$\pi^{\mathbf{0}}_n$
be the scaled version of the path
$\pi^{\mathbf{0}}$
starting from
$\mathbf{0}$
as in (5) and take
\begin{align*}\sigma^2 \;:\!=\; \text{Var}(Y_2(1) - Y_1(1)) = \text{Var} ((h^{\sigma_2}(\mathbf{0}) -h^{\sigma_1}(\mathbf{0}))(1))\end{align*}
and
\begin{align*}\gamma \;:\!=\; \mathbb{E}(Y_2(2) - Y_1(2)) = \mathbb{E} ( h^{\sigma_2}(\mathbf{0})(2) - h^{\sigma_1}(\mathbf{0})(2)).\end{align*}
These are the parameters
$\gamma$
and
$\sigma$
required in Theorem 2; however, for ease of notation we drop
$(\gamma,\sigma)$
from
$\mathcal{X}_n(\gamma, \sigma)$
. Proposition 5 allows us to apply Donsker’s invariance principle to show that
$\pi^{\mathbf{0}}_n$
converges in distribution in
$(\Pi,d_{\Pi})$
to
$B^{\mathbf{0}}$
, a standard Brownian motion starting at
$\mathbf{0}$
.
The above argument proves criterion
$(\mathrm{I}_1)$
for
$k=1$
. To prove criterion
$(\mathrm{I}_1)$
for general
$k \geq 1$
we follow the method of induction. We proceed to prove it for
$k \geq 2$
assuming it is true for
$k -1$
. The strategy that we adopt is to show that the kth path can be approximated by an independent path until it comes ‘sufficiently close’ to one of the other
$(k-1)$
paths. Thereafter, it quickly coalesces with the path which is close to it, and both of them converge to the same Brownian motion. Proposition 8, which was derived from Theorem 3, allows us to show that after two paths come sufficiently close, they coalesce quickly. This strategy was successfully applied in several papers to deal with dependent paths with bounded range interactions as well as long-range interactions (see [Reference Coupier and Tran9], [Reference Coupier, Saha, Sarkar and Tran8], [Reference Ferrari, Fontes and Wu12], and [Reference Roy, Saha and Sarkar25]). The essential idea of the proof of convergence to coalescing Brownian motions is the same as that in [Reference Coupier, Saha, Sarkar and Tran8], and therefore we do not provide the full details and refer the reader to Subsection 6.2.1 of [Reference Coupier, Saha, Sarkar and Tran8]. However, to take care of additional dependency in our model, we need to make some modifications.
We have shown that for
$\mathbf{v} \in \mathbb{R}^2$
and for any sequence
$\mathbf{v}^n \in \mathbb{Z}^2$
such that
\begin{align*}( \mathbf{v}^n(1)/\sqrt{n}\sigma, \mathbf{v}^n(2)/n\gamma) \to \mathbf{v} \text{ as }n \to \infty\end{align*}
the scaled path
$\pi^{\mathbf{v}^n}_n$
converges in distribution to
$B^{\mathbf{v}}$
, the Brownian motion starting from
$\mathbf{v}$
. The non-crossing property of paths implies that for another sequence
$\{ \mathbf{w}^n \;:\; n \geq 1\} \subset \mathbb{Z}^2$
with
$\mathbf{v}^n(2) = \mathbf{w}^n(2) $
, and
$( \mathbf{v}^n(1) - \mathbf{w}^n(1))/\sqrt{n} \to 0$
, the vector
$(\pi^{\mathbf{w}^n}_n , \pi^{\mathbf{v}^n}_n )$
converges in distribution to
$(B^{\mathbf{v}},B^{\mathbf{v}})$
, i.e. to the same Brownian motion starting from
$\mathbf{v}$
. This completes the proof of condition
$(\mathrm{I}_1)$
for
$k=1$
.
For
$(\Pi, d_\Pi)$
, as in Subsection 7.1, we recall the metric on the space
$\Pi^k$
given by
\begin{align*}d^k_{\Pi} ((\pi_1,\ldots,\pi_k),(\theta_1,\ldots,\theta_k)) \;:\!=\; \sum_{i=1}^{k}d_{\Pi}(\pi_i,\theta_i).\end{align*}
We now define a sequence of subsets of
$ \Pi^k$
where the kth path comes sufficiently close to one of the
$k-1$
paths. We fix
$ \alpha \in (0,1/2)$
for the rest of this subsection. For
$n \geq 1$
, define
\begin{align*} A_n^\alpha = & \big\{ (\pi_1,\dotsc,\pi_k) \in \Pi^k \;:\; \pi_i \text{'s satisfy the following conditions } \nonumber \\[5pt] & (a) \quad \pi_i(\sigma_{\pi_i}) \neq \pi_j(\sigma_{\pi_j}) \text{ for all }1 \leq i \lt j \leq k; \nonumber \\[5pt] & (b) \quad t^{k}_n \;:\!=\; \inf\{t\geq 0\;:\; |\pi_i(t)-\pi_k(t)|\leq 3n^{\alpha - 1/2} \text{ for some }1 \leq i\leq k-1\} \lt \infty \big\}.\end{align*}
Next we define the ‘
$\alpha$
-coalescence map’
$f_n^{(\alpha)}\;:\; \Pi^k \to \Pi^k$
, which is a modification of the coalescence map
$f_n$
introduced in Ferrari et al. [Reference Ferrari, Fontes and Wu12], as follows:
\begin{align*}f_n^{(\alpha)} (\pi_1,\dotsc,\pi_{k}) \;:\!=\;\begin{cases}(\pi_1,\dotsc,\pi_{k-1},\overline{\pi}_{k}) & \text{for }(\pi_1,\dotsc,\pi_{k}) \in A_n^\alpha, \\[5pt] (\pi_1,\dotsc,\pi_{k}) & \text{ otherwise, }\end{cases}\end{align*}
with
\begin{align*}\overline{\pi}_{k}(t) \;:\!=\;\begin{cases} \pi_{k}(t) & \text{ for } t \leq t^{k}_n,\\[5pt] \pi_{k}\big(t^{k}_n\big) +n \big( t - t^{k}_n\big) \bigl[ \pi_{i}\big( t^{k}_n+ \frac{1}{n} \big) - \pi_{k}\big( t^{k}_n\big) \bigr] & \text{ for } t^{k}_n \lt t \leq t^{k}_n+ \frac{1}{n}, \\[5pt] \overline{\pi}_{i}(t) & \text{ for } t \gt t^{k}_n + \frac{1}{n},\end{cases}\end{align*}
where i is the index such that
$|\pi_{i}( t^{k}_n) - \pi_{k}( t^{k}_n)|\leq 3 n^{\alpha - 1/2}$
and
$|\pi_{j}( t^{k}_n) - \pi_{k}( t^{k}_n)| \gt 3 n^{\alpha - 1/2}$
for all
$ 1 \leq j \lt i$
.
Fix any set of k points
$\mathbf{y}_1, \ldots , \mathbf{y}_k$
in
$\mathbb{R}^2$
and let
$(W^{\mathbf{y}_1},\ldots, W^{\mathbf{y}_k})$
denote coalescing Brownian motions starting from these points. Let
$\{(\mathbf{y}^n_1, \ldots , \mathbf{y}^n_k)\;:\; n \in \mathbb{N} \}$
be such that for all
$1 \leq i \leq k$
we have
\begin{align*}\big(\mathbf{y}^n_i(1)/\sqrt{n}\sigma, \mathbf{y}^n_i(1)/n\gamma\big) \to \mathbf{y}_i \text{ as } n \to \infty.\end{align*}
Let
$\pi^i$
denote the path starting from
$\mathbf{y}^n_i$
and let
$\pi^i_n$
represent the nth diffusively scaled version. In what follows, the notation
$\Rightarrow$
denotes convergence in distribution. The following proposition completes the verification of condition
$(\mathrm{I}_1)$
.
Proposition 9. We have, as
$ n \to \infty $
,
\begin{align*}(a)\; & f^{(\alpha)}_n \big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \pi^{k}_n\big)\Rightarrow (W^{\mathbf{y}_1},\ldots, W^{\mathbf{y}_k}); \\[5pt] (b)\; & \big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \pi^{k}_n\big)\Rightarrow (W^{\mathbf{y}_1},\ldots, W^{\mathbf{y}_k}). \end{align*}
Proof. For
$\pi \in \Pi$
and
$t \gt \sigma_\pi$
, let
$\pi_{[\sigma_\pi, t]} = \pi_{(-\infty, t]}$
denote the restriction of
$\pi$
over the time interval
$[\sigma_\pi, t]$
. For
$(\pi_1, \ldots , \pi_k) \in \Pi^k$
and for
$t \gt\max\{\sigma_{\pi_i} \;:\; 1\leq i \leq k\}$
, let
$(\pi_1, \ldots , \pi_k)_{(-\infty, t]}$
denote the tuple of respective restrictions of the individual paths. Fix any
$t \gt \max\{\mathbf{y}_i(2) \;:\; 1\leq i \leq k\}$
, and we observe that for (a) it is enough to show that
\begin{align} f^{(\alpha)}_n \big(\big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \pi^{k}_n\big)_{(-\infty, t]}\big)\Rightarrow \big(W^{\mathbf{y}_1},\ldots, W^{\mathbf{y}_k}\big)_{(-\infty, t]} \text{ as }n \to \infty. \end{align}
Further, to prove (43) it suffices to show that for any bounded continuous function
$g \;:\; \Pi^k \mapsto \mathbb{R}$
we have
\begin{align} \mathbb{E} \bigl [ g \bigl ( f^{(\alpha)}_n \big(\big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \pi^{k}_n\big)_{(-\infty, t]}\big) \bigr ) \bigr ]\Rightarrow \mathbb{E} \bigl [ g \bigl ( \big(W^{\mathbf{y}_1},\ldots, W^{\mathbf{y}_k}\big)_{(-\infty, t]} \bigr ) \bigr ]\text{ as }n \to \infty. \end{align}
We need to introduce some notation. Our idea is to show that with high probability a path uses perturbed versions of lattice points which are nearby, and therefore if two paths are far away, they evolve independently.
Fix
$ \beta \in (0,\alpha)$
, where
$\alpha$
is as in (23), and consider ‘tubes’ of width
$n^\alpha$
and
$n^\beta$
around each of the k (unscaled) paths as defined below:
\begin{align*} \mathbb{T}^\alpha_{n,i} & \;:\!=\; \big\{ (y,s) \in \mathbb{Z}^2 \;:\; ||(y,s) - h^m\big(\mathbf{y}^n_i\big)||_1 \leq n^\alpha \text{ for some } 0 \leq m \leq \lfloor n\gamma t - \mathbf{y}^n_i(2) \rfloor\big\},\\[5pt] \mathbb{T}^\beta_{n,i} & \;:\!=\; \big\{ (y,s) \in \mathbb{Z}^2 \;:\; ||(y,s) - h^m\big(\mathbf{y}^n_i\big)||_1 \leq n^\beta \text{ for some } 0 \leq m \leq \lfloor n\gamma t - \mathbf{y}^n_i(2) \rfloor\big\},\end{align*}
where t is as in (43). Recall that
$\tilde{\mathbf{w}}$
denotes the perturbed version of
$\mathbf{w}$
. The event
$E_n$
is defined as
\begin{align*} E_n \;:\!=\; \bigcap_{i=1}^k & \bigl\{ \text{there does not exist any } \mathbf{w} \text{ in }\mathbb{Z}^2 \setminus \mathbb{T}^\alpha_{n,i} \text{ with } \tilde{\mathbf{w}} \in \mathbb{T}^\beta_{n,i} \bigr \}.\end{align*}
Exponential tail decay of perturbation random vectors gives us that
$\mathbb{P}(E_n)$
converges to 1 as
$n \to \infty$
; therefore, we can modify (44) as
\begin{align}\mathbb{E} \bigl [ g \bigl ( f^{(\alpha)}_n \big(\big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \pi^{k}_n\big)_{(-\infty, t]}\big) \bigr )\mathbf{1}_{E_n} \bigr ] \to \mathbb{E} \bigl [ g \bigl ( \big(W^{\mathbf{y}_1},\ldots, W^{\mathbf{y}_k}\big)_{(-\infty, t]} \bigr ) \bigr ] \text{ as }n \to \infty.\end{align}
For each
$n \geq 1$
, let
$\overline{\pi}^k_n$
denote a scaled path which has the same marginal distribution as that of
$\pi^k_n$
and evolves independently of
$(\pi^1_n, \ldots, \pi^{k-1}_n)$
.
We observe that on the event
$E_n$
, until time
$t \wedge t^{k}_n$
, the path
$\pi^k_n$
is supported on disjoint sets of random vectors, and hence its evolution is independent of all of the
$k-1$
paths
$\pi^1_n, \ldots, \pi^{k-1}_n$
. Therefore, we have
\begin{align*}\mathbb{E} \bigl [ g \bigl ( f^{(\alpha)}_n \big(\big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \pi^{k}_n\big)_{(-\infty, t]}\big) \bigr )\mathbf{1}_{E_n} \bigr ] \stackrel{\mathrm{d}}{=} \mathbb{E} \bigl [ g \bigl ( f^{(\alpha)}_n \big(\big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \overline{\pi}^{k}_n\big)_{(-\infty, t]}\big) \bigr )\mathbf{1}_{E_n} \bigr ].\end{align*}
The same argument as in the proof of Proposition 5.6(a) in [Reference Roy, Saha and Sarkar25] gives
\begin{align*}\mathbb{E} \bigl [ g \bigl ( f^{(\alpha)}_n \big(\big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \overline{\pi}^{k-1}_n\big)_{(-\infty, t]}\big) \bigr ) \bigr ] \to \mathbb{E} \bigl [ g \bigl ( (W^{\mathbf{y}_1},\ldots, W^{\mathbf{y}_k})_{(-\infty, t]} \bigr ) \bigr ] \text{ as }n \to \infty.\end{align*}
Since
$\mathbb{P}(E_n)$
converges to 1 as
$n \to \infty$
, (45) follows from the observation that
\begin{align*}\lim_{n \to \infty}\mathbb{E} \bigl [ g \bigl ( f^{(\alpha)}_n \big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \overline{\pi}^{k}_n\big)_{(-\infty, t]} \big) \bigr ) \mathbf{1}_{E_n} \bigr ] = \mathbb{E} \bigl [ g \bigl ( f^{(\alpha)}_n \big(\big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \overline{\pi}^{k}_n\big)_{(-\infty, t]}\big) \bigr ) \mathbf{1}_{E_n} \bigr ].\end{align*}
This proves (a).
For (b) we first consider the situation
$t^{k}_n \geq t$
. On the event
$t^{k}_n \geq t$
, (b) follows trivially because
\begin{align*}\big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \pi^{k}_n\big)_{(-\infty, t]} =f^{(\alpha)}_n \big(\pi^{1}_n,\ldots, \pi^{k-1}_n, \pi^{k}_n\big)_{(-\infty, t]} \text{ a.s. }\end{align*}
Next we consider the situation
$ t \gt t^{k}_n$
. Without loss of generality, assume that at time
$t^{k}_n$
, paths
$\pi^i_n$
and
$\pi^k_n$
have come close enough. We need to show that after time
$t^{k}_n$
these two paths coalesce quickly. Proposition 8 would help us to achieve this. Towards this we define the event
\begin{align*} F_n \;:\!=\; \bigcap_{i=1}^k & \bigl\{ \tilde{\mathbf{w}} \in \mathbb{H}^-\big(n\gamma t^{k}_n + n^\beta\big) \text{ for all } \mathbf{w} \in \mathbb{T}^\beta_{n,i} \cap \mathbb{H}^-\big(n\gamma t^{k}_n\big) \bigr \},\end{align*}
and observe that
$\mathbb{P}(F_n)$
converges to 1 as
$n \to \infty$
. Finally, on the event
$F_n$
, Proposition 8 gives us the required tail estimate for the coalescence time of
$\pi^k_n$
and
$\pi^i_n$
, which completes the proof.
7.2.2. Verification of condition (iv) of Theorem 6
To show condition (iv), we follow Subsection 6.2.2 of [Reference Coupier, Saha, Sarkar and Tran8], and again the coalescence time estimate given in Proposition 8 serves as a key ingredient. Let
$(\mathcal{Z}, \widehat{\mathcal{Z}})$
be any subsequential limit of
$\{(\overline{\mathcal{X}}_n, \overline{\widehat{\mathcal{X}}}_n)\;:\; n \geq 1\}$
. By Skorohod’s representation theorem we may assume that we are working on a probability space such that the convergence happens a.s. With slight abuse of notation, we continue to denote that subsequence also by
$\{(\overline{\mathcal{X}}_n, \overline{\widehat{\mathcal{X}}}_n)\;:\; n\geq 1\}$
.
We have to prove that, with probability 1, paths in
$\mathcal{Z}$
do not spend a positive Lebesgue measure of time together with the dual paths in
$\widehat{\mathcal{Z}}$
. This means that for any
$\delta\gt0$
and any integer
$m\geq 1$
, the probability of the event
\begin{align*}A(\delta, m) \;:\!=\; \left\lbrace\begin{array}{l}\text{there exist paths $\pi\in \mathcal{Z}, \widehat{\pi}\in \widehat{\mathcal{Z}},$and $t_0 \in \mathbb{R}$ s.t. $-m\lt\sigma_{\pi}\lt t_0\lt t_0 + \delta\lt\sigma_{\widehat{\pi}}\lt m$} \\[5pt] \text{and $- m \lt \pi(t) = \widehat{\pi}(t)\lt m $ for all $t\in [t_0, t_0+\delta]$}\end{array}\right\rbrace\end{align*}
has to be 0.
To show that
$\mathbb{P}(A(\delta,m))=0$
, we introduce a generic event
$B^{\epsilon}_n(\delta, m)$
defined as follows. Given an integer
$m\geq 1$
and
$\delta,\epsilon\gt0$
,
\begin{align*}B^{\epsilon}_n(\delta, m) \;:\!=\; \bigl \{ & \text{there exist paths }\pi_1^n,\pi_2^n,\pi_3^n \in \mathcal{X}_n \text{ s.t. }\sigma_{\pi_1^n},\sigma_{\pi_2^n} = 0, \sigma_{\pi_3^n} \leq \delta \\[5pt] & \text{and }\pi_1^n(0),\pi_1^n(\delta)\in [\!-\!m,m]\; \text{with }|\pi_1^n(0)-\pi_2^n(0)|\lt\epsilon \text{ but }\pi_1^n(\delta) \not= \pi_2^n(\delta) \\[5pt] & \text{and with }|\pi_1^n(\delta)-\pi_3^n(\delta)|\lt\epsilon \text{ but }\pi_1^n(2\delta) \not= \pi_3^n(2\delta) \bigr \}.\end{align*}
It was shown in Subsection 6.2.2 of [Reference Coupier, Saha, Sarkar and Tran8] that to show
$\mathbb{P}(A(\delta, m) = 0)$
it suffices to prove the following lemma.
Lemma 12. For any integer
$m\geq 1$
and real numbers
$\epsilon,\delta\gt0$
, there exists a constant
$C_0(\delta,m)\gt0$
(depending only on
$\delta$
and m) such that for all large n,
\begin{align*}\mathbb{P}\big(B^{\epsilon}_n (\delta, m)\big) \leq C_0(\delta, m) \, \epsilon.\end{align*}
For the proof of Lemma 12 we essentially follow [Reference Coupier, Saha, Sarkar and Tran8]. Note that the discrete nature of the perturbed point process V requires some modifications. We need to deal with the non-Markovian nature of the paths.
Proof of Lemma
12. We define the event
$ D^{\epsilon}_n $
as the unscaled version of the event
$ B^{\epsilon}_n $
in the following way:
\begin{align*}D^{\epsilon}_n \;:\!=\; \bigl\{ & \text{there exist }x, y, z \in \mathbb{Z}\text{ such that } x \in [\!-\!m \sqrt{n} \sigma, m \sqrt{n} \sigma ], x - y | \lt \sqrt{n} \epsilon \sigma \\[5pt] & \quad\text{ and }\quad \pi^{(x,0)}(\lfloor n \gamma \delta \rfloor) \neq \pi^{(y,0)}(\lfloor n \gamma \delta \rfloor), | \pi^{(x,0)}(\lfloor n \gamma \delta \rfloor) - z | \lt \sqrt{n} \epsilon \sigma, \\[5pt] & \pi^{(x,0)}(2\lfloor n\gamma \delta \rfloor) \neq\pi^{(z,0)}(2\lfloor n \gamma \delta \rfloor)\bigr\}.\end{align*}
For
$ \omega \in D^{\epsilon}_n$
, suppose x and y are as in the definition above and assume that
$ x \lt y $
. Set
$ l = \max \{ x + j \;:\; \pi^{(x,0)}(\lfloor n\gamma \delta \rfloor) =\pi^{(x+j,0)}(\lfloor n \gamma \delta \rfloor) \}$
. Clearly, we have
\begin{align*} - m \sqrt{n} \sigma \leq x \leq l \lt y \leq ( m+\epsilon) \sqrt{n} \sigma\end{align*}
and
\begin{align*} \pi^{(x,0)}(\lfloor n \gamma \delta \rfloor) = \pi^{(l,0)}(\lfloor n \gamma \delta \rfloor) \lt \pi^{(l+1,0)}(\lfloor n \gamma \delta \rfloor) \leq \pi^{(y, 0)}(\lfloor n \gamma \delta \rfloor).\end{align*}
Assume that
$ \pi^{(x, -\delta)}(\lfloor n \gamma \delta \rfloor) = k$
for some
$k \in \mathbb{Z} $
. Then z in the definition above satisfies
$ z \in (k - \sqrt{n} \epsilon \sigma, k + \sqrt{n} \epsilon \sigma)$
and
$ \pi^{( k,\lfloor n \gamma \delta \rfloor)}(2\lfloor n \gamma \delta \rfloor) \neq\pi^{(z, \lfloor n \gamma \delta \rfloor)}(2\lfloor n \gamma \delta \rfloor)$
. So, by the non-crossing property of paths, it must be the case that
\begin{align*}\pi^{( k - \lfloor \sqrt{n} \epsilon \sigma \rfloor- 1,\lfloor n \gamma \delta \rfloor)}(2\lfloor n\gamma \delta \rfloor) \neq \pi^{(k + \lfloor \sqrt{n} \epsilon \sigma \rfloor+ 1,\lfloor n \gamma \delta \rfloor)}(2\lfloor n \gamma \delta \rfloor).\end{align*}
Thus, we must have
$ \omega \in H^{(L)} (n, \delta, \epsilon) $
, where for
$ l \in \mathbb{Z} $
,
\begin{align*} H_{l, k}^{(L)} (n, \epsilon) \;:\!=\; & \bigl\{ \pi^{(l, 0)}(\lfloor n \gamma \delta \rfloor) = k \neq \pi^{(l+1,0)}(\lfloor n \gamma \delta \rfloor) \quad\text{ and }\quad \\[5pt] & \pi^{( k - \lfloor \sqrt{n} \epsilon \sigma \rfloor- 1,\lfloor n \gamma \delta \rfloor)}(2\lfloor n \gamma \delta \rfloor) \neq \pi^{(k + \lfloor \sqrt{n} \epsilon \sigma \rfloor+ 1, \lfloor n \gamma \delta \rfloor)}(2\lfloor n \gamma \delta \rfloor) \bigr\}, \\[5pt] H^{(L)} (n, \delta, \epsilon) \;:\!=\; & \bigcup_{ l = - \lfloor 2 m \sqrt{n} \sigma \rfloor }^{ \lfloor 2 m \sqrt{n} \sigma \rfloor} \bigcup_{k \in \mathbb{Z} } H_{l, k}^{(L)} (n, \delta, \epsilon) .\end{align*}
Similarly, for
$ \omega \in D^{\epsilon}_n$
such that
$ x \gt y $
, set
$ r = \min \{ x - j \;:\; \pi^{(x, -\delta)}(\lfloor n \gamma \delta \rfloor) = \pi^{(x-j, -\delta)}(\lfloor n \gamma \delta \rfloor) \} $
. As earlier,
$ \omega \in H^{(R)} (n, \delta, \epsilon) $
, where for
$ r \in \mathbb{Z} $
,
\begin{align*}H_{r, k}^{(R)} (n, \delta, \epsilon) \;:\!=\; & \bigl\{ \pi^{(r, 0)}(\lfloor n \gamma \delta \rfloor)= k \neq \pi^{(r-1, 0)}(\lfloor n \gamma \delta \rfloor) \quad\text{ and }\quad \\[5pt] & \pi^{( k - \lfloor \sqrt{n} \epsilon \sigma \rfloor- 1,\lfloor n \gamma \delta \rfloor )}(2\lfloor n \gamma \delta \rfloor) \neq\pi^{(k + \lfloor \sqrt{n} \epsilon \sigma \rfloor+ 1, \lfloor n \gamma \delta \rfloor )}(2\lfloor n \gamma \delta \rfloor) \bigr\}, \\[5pt] H^{(R)} (n, \delta, \epsilon) \;:\!=\; & \bigcup_{ r = - \lfloor 2 m \sqrt{n} \sigma \rfloor }^{ \lfloor 2 m \sqrt{n} \sigma \rfloor} \bigcup_{k \in \mathbb{Z} } H_{r, k}^{(R)} (n, \delta, \epsilon) .\end{align*}
Thus,
$ D^{\epsilon}_n \subseteq H^{(L)} (n, \delta, \epsilon) \cup H^{(R)} (n, \delta, \epsilon) $
.
The remaining argument is very similar to Proposition 9, and we give only a sketch here. We consider tubes of width
$n^\alpha$
and
$n^\beta$
around the paths
$\pi^{(l,0)}$
and
$\pi^{(l+1,0)}$
over the time interval
$[0, \lfloor n\gamma\delta \rfloor]$
. We observe that the probability of the event that these two paths do not use random vectors associated with lattice points outside these ‘
$n^\alpha$
’ tubes and the perturbed versions of all the lattice points inside these two tubes are confined to the lower half-plane
$\mathbb{H}^-(\lfloor n\gamma\delta \rfloor + n^\beta)$
converges to 1 as
$n \to \infty$
. Therefore, for all large n, on the said event we can apply Proposition 8 to obtain
\begin{align*} & \mathbb{P} \big\{ \pi^{( k - \lfloor \sqrt{n} \epsilon \sigma \rfloor - 1, \lfloor n \gamma \delta \rfloor )}(2\lfloor n \gamma \delta \rfloor) \neq\pi^{(k + \lfloor \sqrt{n} \epsilon \sigma \rfloor + 1,\lfloor n \gamma \delta \rfloor )}(2\lfloor n \gamma \delta \rfloor)\mid \pi^{(l, 0)}(\lfloor n \gamma \delta \rfloor)\\ & = k\neq \pi^{(l+1,0)}(\lfloor n \gamma \delta \rfloor) \big\} \\[5pt] & \leq \frac{C_2 (2\lfloor \sqrt{n} \sigma \epsilon \rfloor + 3) }{\sqrt{ \lfloor n \gamma \delta \rfloor}} \leq C_3 (\delta) \epsilon,\end{align*}
where
$ C_2, C_3 (\delta) \gt 0 $
are constants. Hence,
\begin{align*} \mathbb{P} \Big( H_{k}^{(L),1} (n, \delta, \epsilon)\Big) \leq C_3 (\delta) \epsilon \; \mathbb{P} \big\{ \pi^{(l,0)}(\lfloor n \gamma \delta \rfloor) = k \neq \pi^{(l+1, 0)} (\lfloor n \gamma \delta \rfloor) \big\} .\end{align*}
The events
$ \{ \pi^{(l,0)}(\lfloor n \gamma \delta \rfloor) = k\neq \pi^{(l+1, 0)}(\lfloor n \gamma \delta \rfloor) \} $
are disjoint for distinct values of k; hence,
\begin{align*}\mathbb{P} \Bigg( \bigcup_{k \in \mathbb{Z} } H_{ k}^{(L),1} (n, \delta, \epsilon)\Bigg) & \leq \sum_{ k \in \mathbb{Z}} \mathbb{P} \Big( H_{k}^{(L),1} (n, \delta, \epsilon) \Big) \\[5pt] & \leq C_3 (\delta) \epsilon \sum_{ k \in \mathbb{Z}} \mathbb{P}\big\{ \pi^{(l,0)}(\lfloor n \gamma \delta \rfloor) = k \neq \pi^{(l+1,0)}(\lfloor n \gamma \delta \rfloor) \big\} \\[5pt] & = C_3 (\delta) \epsilon \; \mathbb{P} \big\{ \pi^{(l,0)}(\lfloor n \gamma \delta \rfloor)\neq \pi^{(l+1,0)}(\lfloor n \gamma \delta \rfloor) \big\}.\end{align*}
The above argument also holds for
$ \bigcup_{k \in \mathbb{Z} } H_{r, k}^{(R)} (n, \delta, \epsilon)$
. Thus, combining the above terms and applying Proposition 8, we have
\begin{align*}\mathbb{P} \big(D^{\epsilon}_n \cap F_n(k)\big) & \leq \mathbb{P} \bigl( H^{(L)} (n, \delta, \epsilon) \bigr)+ \mathbb{P} \bigl( H^{(R)} (n, \delta, \epsilon) \bigr) \\[5pt] & \leq \sum_{ l = - \lfloor 2 m \sqrt{n} \sigma \rfloor }^{ \lfloor 2 m \sqrt{n} \sigma \rfloor}\mathbb{P} \Bigg(\bigcup_{k \in \mathbb{Z} } H_{ k}^{(L)} (n, \delta, \epsilon) \Bigg) +\sum_{ r = - \lfloor 2 m \sqrt{n} \sigma_0 \rfloor }^{ \lfloor 2 m \sqrt{n} \sigma \rfloor}\mathbb{P} \Bigg( \bigcup_{k \in \mathbb{Z} } H_{r, k}^{(R)} (n, \delta, \epsilon) \Bigg) \\[5pt] & \leq 16 m \sqrt{n} \sigma C_3 ( \delta ) \epsilon C_2 / \sqrt{\lfloor n \gamma \delta \rfloor } \leq C_1 ( \delta, m ) \epsilon\end{align*}
for a proper choice of
$ C_1 ( \delta, m) $
. This completes the proof.
Acknowledgements
We thank the referee for their comments which led to a significant improvement of this paper.
Funding information
Kumarjit Saha and Anish Sarkar gratefully acknowledge financial support via CEFIPRA grant 6901/1.
Competing interests
There were no competing interests to declare which arose during the preparation of or the publication process for this article.
{(±y2,y):y≥0}
∇(0)
v∈∇(0)
∇(v)⊆∇(0)
v∈Z2
v
{hj(v):j≥1}
∇(v)
Asp(0)
{hj(0):j≥1}
∇(0)
∇(⋅)
∇(⋅)
τ1
∇(hτ1(x1))
∇(x1n,↓)
L1
X1
Fℓ
R12
R22
∇(w1)
∇(hσℓ+1(x1))
∇(w2)
∇(hσℓ+1(x2))
Asp(ly)(w1+(0,2ly))
Asp(ly)(w2+(0,2ly))
H+(w1(2)+3ly)
y=w1(2)+3ly
