# Scaling limit of a drainage network model on perturbed lattice

Rahul Roy  Indian Statistical Institute, Delhi  Kumarjit Saha  Ashoka
University, Sonipat  Anish Sarkar  Indian Statistical Institute, Delhi

###### Abstract

Study of random networks generally requires the nodes to be independently and
uniformly distributed such as a Poisson point process. In this work, we
venture beyond this standard paradigm and investigate a stochastic forest
obtained from a drainage network model constructed on a randomly perturbed
subset of ${\mathbb{Z}}^{2}$, where both horizontal and vertical perturbations
are given by exponentially decaying unbounded discrete random variables and
vertical perturbations are allowed in the upward direction only. We show that
the resultant stochastic network is a single tree a.s. We further establish
that as a collection of paths, under diffusive scaling the resultant network
converges to the Brownian web.

##  1 Introduction and main results

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, 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. Leopold and Langbein [LL62] first
carried out studies of drainage basins by simulating drainage networks through
random walks in a rectangular region. Scheidegger [S67] was the first to
introduce a directed network by imposing a preferential flow condition where
each source emptying to one of it’s two neighbours in a preferred direction.
Howard [H71] removed the restriction of drainage to neighbouring sites only.
Iturbe and Rinaldo [RR97] presented an excellent survey of development in this
field.

Informally drainage network models can be described in the following way. A
random subset of ${\mathbb{Z}}^{d}$ or ${\mathbb{R}}^{d}$ is selected as a
collection of ‘source’ vertices. From each source
${\mathbf{x}}=({\mathbf{x}}(1),\cdots,{\mathbf{x}}(d))\in{\mathbb{R}}^{d}$
exactly one directed edge is drawn to another source vertex ${\mathbf{y}}$
with ${\mathbf{y}}(d)>{\mathbf{x}}(d)$, representing the flow from
${\mathbf{x}}$ to ${\mathbf{y}}$. We briefly describe the Howard’s model here.
Each vertex in ${\mathbb{Z}}^{d}$ is a source vertex independently with
probability $p\in(0,1)$ and a source vertex $u\in{\mathbb{Z}}^{d}$ connects to
the nearest source at the next level
$\\{{\mathbf{w}}\in{\mathbb{Z}}^{d}:{\mathbf{w}}(d)=u(d)+1\\}$. If there are
more than one closest source, one of them is chosen uniformly. For this model
Gangopadhyay et.al. [GRS04] showed that the random graph is a (connected) tree
a.s. for $d=2,3$ and it is a forest with infinitely many disjoint tree
components for $d\geq 4$. Since then various other drainage network models
with complex dependencies in constructing edges have been proposed and the
tree-forest dichotomy problem depending on dimensions has been studied for
these models (see [FLT04], [ARS08], [CT13],[RSS16A]).

In the mathematical study of such networks, an important modelling hypothesis
is the random distribution of their nodes. Generally speaking, the
distribution of the random nodes in stochastic networks is often taken to be
uniform over space and independently distributed over disjoint regions, like,
the Poisson point process and its variants. Such distribution of nodes is
comparatively easily amenable to rigorous mathematical treatment, but is often
limited in its effectiveness to model the reality, e.g., on a global scale the
homogeneous Poisson process exhibits clusters of points interspersed with
vacant spaces, whereas a more spatially uniform distribution might be a closer
representation of the reality (see, e.g., [GL17]). However, little is
understood about stochastic geometry of networks arising from such strongly
correlated point processes, principally because the tools and techniques for
studying the Poisson model heavily rely on its exact spatial independence
property.

This motivates the authors of [GS20] to study a drainage network model
constructed on a point process obtained from perturbations of lattice points
where perturbations are restricted to compact domains. The question of tree-
forest dichotomy depending on dimensions has been explored in [GS20] for the
resultant network and it’s scaling limit has also been studied. This work has
initiated the analysis of directed networks constructed on disordered lattice
points, though working with perturbations restricted to compact domain is
certainly a limitation of [GS20]. In this paper, we remove this limitation and
examine a set of disordered lattice points for $d=2$ generated due to
‘unbounded’ i.i.d. perturbations along $x$-axis and $y$ axis with
exponentially decaying tails. The generated set of perturbed lattice points
exhibit much greater measure of spatial homogeneity compared to the Poisson
process. It is important to observe that the generated point process is
hyperuniform. Hyperuniformity of point processes have attracted a lot of
interest in recent years, especially in the statistical physics literature
(see, e.g., [GL17], [T02], [TS03] and the references therein). A point process
is said to be hyperuniform if the variance of the number of points in an
expanding domain scales like its surface area (or slower), rather than its
volume, which is the case for Poisson or any other extensive system that
exhibits FKG-type properties. In fact, hyperuniformity is closely related to
negative association at the spatial level, which precludes the application of
many arguments that are ordinarily staple in stochastic geometry. In the
subsequent paragraphs, we lay out the details of the model and give an account
of our principal results.

We are going to define our model now. In what follows, for
${\mathbf{x}}\in{\mathbb{R}}^{2}$, the notation ${\mathbf{x}}(i)$ denotes the
$i$-th coordinate of ${\mathbf{x}}$ for $1\leq i\leq 2$. We consider an i.i.d.
family of random vectors

$\displaystyle\\{\Gamma_{\mathbf{u}}:=(B_{\mathbf{u}},R_{\mathbf{u}},\Lambda_{\mathbf{u}}):{\mathbf{u}}\in{\mathbb{Z}}^{2}\\}$
(1)

such that the following holds:

  * (i)

$B_{\mathbf{u}}$ is a Bernoulli r.v. with success probability $p\in(0,1)$
which indicates whether a lattice point ${\mathbf{u}}$ is an open (source)
vertex or not;

  * (ii)

$R_{\mathbf{u}}$ is a Rademacher r.v. associated to ${\mathbf{u}}$ which helps
to resolve a tie (in case there is one) for deciding the Howard step;

  * (iii)

$\Lambda_{\mathbf{u}}:=(X_{\mathbf{u}},Y_{\mathbf{u}})$ denotes the
perturbation random vector associated to ${\mathbf{u}}$ where $X_{\mathbf{u}}$
and $Y_{\mathbf{u}}$ denote the $x$ coordinate perturbation and $y$ coordinate
perturbation r.v.’s respectively. Set $\theta_{x},\theta_{y}\in(0,1)$ and the
respective p.m.f.’s for $X_{\mathbf{u}}$ and $Y_{\mathbf{u}}$ are given by:

$\displaystyle P(X_{\mathbf{u}}=j)$
$\displaystyle=\theta_{x}((1-\theta_{x})/2)^{|j|}\text{ for
}j\in{\mathbb{Z}}\text{ and }$ $\displaystyle P(Y_{\mathbf{u}}=j)$
$\displaystyle=\theta_{y}(1-\theta_{y})^{j}\text{ for }j\geq 0.$ (2)

Let $\\{{\mathbf{u}}\in{\mathbb{Z}}^{2}:B_{\mathbf{u}}=1\\}$ denote the
collection of open (source) vertices. Using (random) perturbation vector
$\Lambda_{\mathbf{w}}=(X_{\mathbf{w}},Y_{\mathbf{w}})$ a lattice point
${\mathbf{w}}\in{\mathbb{Z}}^{2}$ gets perturbed to a new location
${\mathbf{w}}+\Lambda_{\mathbf{w}}$ and this perturbed version is denoted by
$\tilde{{\mathbf{w}}}$. Note that two vertices ${\mathbf{u}}$ and
${\mathbf{w}}$ may perturb to the same location (i.e.,
$\tilde{{\mathbf{u}}}=\tilde{{\mathbf{w}}}$) and in that case, we don’t
distinguish between them. We consider the set of perturbed open vertices
denoted by $V$ and defined as

$\displaystyle
V:=\\{\tilde{{\mathbf{u}}}={\mathbf{u}}+\Lambda_{\mathbf{u}}:{\mathbf{u}}\in{\mathbb{Z}}^{2},B_{\mathbf{u}}=1\\}.$
(3)

Based on the point process $V$ we construct the Howard’s network as follows.
For ${\mathbf{u}}\in{\mathbb{Z}}^{2}$ we define the non-negative integer
valued random variable $J({\mathbf{u}})$ as

$\displaystyle
J({\mathbf{u}}):=\min\\{|{\mathbf{w}}(1)-{\mathbf{u}}(1)|:{\mathbf{w}}\in
V,{\mathbf{w}}(2)={\mathbf{u}}(2)+1\\}.$ (4)

In other words, $J({\mathbf{u}})$ denotes the distance of the nearest point in
$V$ from ${\mathbf{u}}$ having $y$ coordinate as ${\mathbf{u}}(2)+1$.

Starting from ${\mathbf{u}}\in{\mathbb{Z}}^{2}$, based on the set $V$ we
define the ‘perturbed Howard’ (PH) step $h({\mathbf{u}})=h({\mathbf{u}},V)$ as
the almost surely (a.s.) unique point in $V$ with
$h({\mathbf{u}})(2)={\mathbf{u}}(2)+1$ such that:

$\displaystyle
h({\mathbf{u}},V)=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\\\
{\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\\\
{\mathbf{u}}+(R_{\mathbf{u}}J({\mathbf{u}}),1)&\text{ if
}{\mathbf{u}}+(-J({\mathbf{u}}),1),{\mathbf{u}}+(J({\mathbf{u}}),1)\in
V.\end{cases}$ (5)

We drop the point set $V$ from the notation $h({\mathbf{u}},V)$ when it is
clear from the context and denote it simply as $h({\mathbf{u}})$. We consider
the random graph $G:=(V,E)$ with vertex set $V$ and edge set
$E:=\\{\langle{\mathbf{u}},h({\mathbf{u}})\rangle:{\mathbf{u}}\in V\\}$ and
call it the perturbed Howard (PH) model. We observe that each ${\mathbf{u}}\in
V$ has exactly one outgoing edge and therefore, the generated random graph
does not have any cycle or loop a.s.

In what follows, we assume 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 independent
of each other. We do not require independence of $x$ coordinate and $y$
coordinate perturbation random variables. Rather, we assume that the joint
distribution of the perturbation random vector
$\Lambda_{\mathbf{u}}=(X_{\mathbf{u}},Y_{\mathbf{u}})$ is such that we have
${\mathbb{P}}(X_{\mathbf{u}}=Y_{\mathbf{u}}=0)>0$ and
$X_{\mathbf{u}},Y_{\mathbf{u}}$ respectively follow marginal distributions as
specified in (1). Based on these assumptions our first result shows that the
random graph $G$ is connected a.s.

######  Theorem 1.1.

The perturbed Howard network $G=(V,E)$ is connected and consists of a single
tree a.s. Further, there is no bi-infinite path in $G$ a.s.

Our next main result is that the graph $G$ observed as a collection of paths,
converges to the Brownian web under a suitable diffusive scaling. The standard
Brownian web is originated in the work of Arratia [A79] 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}$. Later
[FINR04] provided a framework in which the Brownian web is realized as a
random variable taking values in a Polish space. In Subsection 1.1 we present
the relevant topological details from [FINR04].

Set $h^{0}({\mathbf{u}})={\mathbf{u}}$ and for $k\geq 1$, let
$h^{k}({\mathbf{u}})=h(h^{k-1}({\mathbf{u}}))$ denote the $k$-th step starting
from ${\mathbf{u}}$. Joining successive steps $\langle
h^{k-1}({\mathbf{u}}),h^{k}({\mathbf{u}})\rangle$ for all $k\geq 1$ linearly,
we get the PH path $\pi^{\mathbf{u}}$ starting from ${\mathbf{u}}$ constructed
using the point set $V$. Sometimes we call this path as the process
$\\{h^{k}({\mathbf{u}}):k\geq 0\\}$ of successive steps also. We consider this
two-dimensional PH network as a collection of paths and want to study it’s
scaling limit under diffusive scaling. We need some notations.

Let ${\cal X}:=\\{\pi^{{\mathbf{u}}}:{\mathbf{u}}\in V\\}$ denote the
collection of all PH paths. For given $\gamma,\sigma>0$ and for any
$n\in{\mathbb{N}}$, the scaled path is given by

$\displaystyle\pi_{n}(\gamma,\sigma)(t):=\pi(n\gamma t)/(\sqrt{n}\sigma)\text{
and }{\cal
X}_{n}(\gamma,\sigma):=\\{\pi_{n}^{{\mathbf{u}}}(\gamma,\sigma):{\mathbf{u}}\in
V\\}$ (6)

denotes the collection of the scaled paths. Let $\bar{{\cal
X}}_{n}(\gamma,\sigma)$ denote the closure of ${\cal X}_{n}(\gamma,\sigma)$
w.r.t. certain metric which is explained in detail in SubSection 1.1. Now we
are ready to state our second theorem regarding the convergence of the
diffusively scaled PH network to the Brownian web.

######  Theorem 1.2.

There exist $\sigma=\sigma(p,\theta_{x},\theta_{y})>0$ and
$\gamma=\gamma(p,\theta_{x},\theta_{y})>0$ such that $\bar{{\cal
X}}_{n}(\gamma,\sigma)$ converges in distribution to the Brownian web ${\cal
W}$ as $n\to\infty$.

We should mention here that though we have assumed particular distributions
for $x$ coordinate and $y$ coordinate perturbation random variables, our
arguments hold in much generality as mentioned in the following remark.

######  Remark 1.3.

All our arguments hold and we have Theorem 1.1 and Theorem 1.2 as long as the
i.i.d. collection of perturbation random vectors
$\\{\Lambda_{\mathbf{u}}=(X_{\mathbf{u}},Y_{\mathbf{u}}):{\mathbf{u}}\in{\mathbb{Z}}^{2}\\}$
satisfies the following assumptions:

  * (i)

${\mathbb{P}}(X_{\mathbf{u}}=Y_{\mathbf{u}}=0)>0$ and
${\mathbb{P}}(Y_{\mathbf{u}}<0)=0$;

  * (ii)

${\mathbb{P}}(X_{\mathbf{u}}=j)={\mathbb{P}}(X_{\mathbf{u}}=-j)$ for all
$j\in{\mathbb{N}}$;

  * (iii)

There exist $C_{0},C_{1}>0$ such that

${\mathbb{P}}(|X_{\mathbf{u}}|\geq n)\vee{\mathbb{P}}(Y_{\mathbf{u}}\geq
n)\leq C_{0}\exp{(-C_{1}n)}\text{ for all }n.$

In particular, if we consider an i.i.d. collection of Gaussian random vectors
$\\{\Psi_{\mathbf{u}}=(\Psi_{\mathbf{u}}(1),\Psi_{\mathbf{u}}(2)):{\mathbf{u}}\in{\mathbb{Z}}^{2}\\}$
and take the perturbation random vector
$\Lambda_{\mathbf{u}}=(X_{\mathbf{u}},Y_{\mathbf{u}})$ defined as

$X_{\mathbf{u}}:=\lfloor\Psi_{\mathbf{u}}(1)\rfloor\text{ and
}Y_{\mathbf{u}}:=\lfloor|\Psi_{\mathbf{u}}(2)|\rfloor,$

still Theorem 1.1 and Theorem 1.2 hold for the Howard’s network constructed on
the point process of perturbed lattice points.

We should mention here that the point process of perturbed lattice points
under Gaussian perturbations have attracted a lot of interests in recent
years. In particular Holroyd and Soo [HS13] showed that in two dimensions, the
resulting Gaussian perturbed lattice point process is ‘rigid’ in the sense
that for this strongly correlated point process, for any bounded domain ${\cal
D}$ point process configuration on ${\cal D}^{c}$ almost surely determines the
number of points inside ${\cal D}$. In three dimensions, Peres and Sly [PS14]
examined rigidity properties of this point process in greater detail and
establish a phase transition.

###  1.1 The Brownian web

Fontes et. al. [FINR04] provided a suitable framework so that the Brownian web
(BW) can be regarded as a random variable taking values in a Polish space. In
this section, we recall the relevant topological details from [FINR04].

Let ${\mathbb{R}}^{2}_{c}$ denote the completion of the space time plane
${\mathbb{R}}^{2}$ with respect to the metric

$\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{|}.$

As a topological space ${\mathbb{R}}^{2}_{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}_{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}_{c},\rho)$. We then
define $\Pi$ to be the space of all paths in ${\mathbb{R}}^{2}_{c}$ with all
possible starting times in $[-\infty,\infty]$ equipped with the following
metric,

$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{|},$

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 ${\cal H}$
be the space of compact subsets of $(\Pi,d_{\Pi})$ equipped with the Hausdorff
metric $d_{{\cal H}}$ given by,

$d_{{\cal 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}).$

The space $({\cal H},d_{{\cal H}})$ is a complete separable metric space. Let
$B_{{\cal H}}$ be the Borel $\sigma-$algebra on the metric space $({\cal
H},d_{{\cal H}})$. The Brownian web ${\mathcal{W}}$ is then defined and
characterized as an $({\cal H},B_{{\cal H}})$ valued random variable by the
following result:

######  Theorem 1.4 (Theorem 2.1 of [FINR04]).

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
almost surely 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})$
almost surely.

The above theorem shows that the collection is almost surely determined by
countably many coalescing Brownian motions.

We present a short introduction on the dual Brownian web
$\widehat{{\mathcal{W}}}$. As in case of forward paths, one can consider a
similar metric space of collection of backward paths denoted by
$(\widehat{\Pi},d_{\widehat{\Pi}})$. The notation
$(\widehat{{\mathcal{H}}},d_{\widehat{{\mathcal{H}}}})$ denotes 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{\mathcal{B}}_{\widehat{{\mathcal{H}}}})$-valued
random variable such that:

  * $(i)$

$\widehat{{\mathcal{W}}}$ is distributed as the Brownian web rotated $180^{0}$
about the origin;

  * $(ii)$

${\mathcal{W}}$ and $\widehat{{\mathcal{W}}}$ uniquely determine each other in
the sense that the paths of ${\cal W}$ a.s. do not cross with (backward) paths
in $\widehat{{\cal W}}$. The interaction between the paths in ${\mathcal{W}}$
and $\widehat{\mathcal{W}}$ is that of Skorohod reflection (see [STW00]).

Before concluding this section, we explain the notion of ‘non-crossing’ paths
as this notion will be frequently used in this of the paper. Two paths
$\pi_{1},\pi_{2}\in\Pi$ are said to be non-crossing if there does not exist
any $s_{1},s_{2}\in[\sigma_{\pi_{1}}\vee\sigma_{\pi_{2}},\infty)$ such that

$\displaystyle(\pi_{1}(s_{1})-\pi_{2}(s_{1}))(\pi_{1}(s_{2})-\pi_{2}(s_{2}))>0.$
(7)

It follows that for the PH model, paths are a.s. non-crossing. For any $n\geq
1$, clearly ${\cal X}_{n}(\gamma,\sigma)$ a.s. forms a family of non-crossing
paths and it’s closure in $\Pi$ denoted by $\overline{{\cal
X}}_{n}(\gamma,\sigma)$ which is a $({\cal H},{\cal B}_{\cal H})$-valued
random variable a.s. We will show that as $n\to\infty$, the $({\cal H},{\cal
B}_{\cal H})$-valued random variable $\overline{{\cal X}}_{n}(\gamma,\sigma)$
converges in distribution to the Brownian web ${\cal W}$ (see Theorem 1.2).

##  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},\cdots,{\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}),\cdots,h^{n}({\mathbf{x}}_{k}):n\geq 0\\}$. Note
that the starting points ${\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k}$ are not
necessarily in $V$ and $h^{n}({\mathbf{x}}_{i})=h^{n}({\mathbf{x}}_{i},V)$ for
all $1\leq i\leq k$. Without loss of generality we consider
${\mathbf{x}}_{1}(2)=\cdots={\mathbf{x}}_{k}(2)=0$. For $n\in{\mathbb{Z}}$,
let ${\cal F}_{n}$ denote the $\sigma$ field

$\displaystyle{\cal
F}_{n}:=\sigma\bigl{(}\Gamma_{\mathbf{w}}:{\mathbf{w}}(2)\leq n\bigl{)}.$ (8)

We observe that the joint exploration process
$\\{h^{n}({\mathbf{x}}_{1}),\cdots,h^{n}({\mathbf{x}}_{k}):n\geq 0\\}$ is
measurable w.r.t. the filtration $\\{{\cal F}_{n}:n\geq 0\\}$. We note that
the filtration $\\{{\cal 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 notations. For $l\in{\mathbb{Z}}$, let

$\mathbb{H}^{+}(l):=\\{{\mathbf{w}}\in{\mathbb{Z}}^{2}:{\mathbf{w}}(2)>l\\}\text{
and }\mathbb{H}^{-}(l):=\\{{\mathbf{w}}\in{\mathbb{Z}}^{2}:{\mathbf{w}}(2)\leq
l\\}$

respectively denote the (open) upper and (closed) lower half-planes w.r.t. the
line $\\{y=l\\}$. For any $n\geq 0$, we observe that the $\sigma$-field ${\cal
F}_{n}$ has ‘some’ information about certain points in the set
$V\cap\mathbb{H}^{+}(n)$, viz., those vertices in $V$ obtained as
perturbations of open lattice points in $\mathbb{H}^{-}(n)$. The
$\sigma$-field has information about all $\tilde{{\mathbf{w}}}\in
V\cap\mathbb{H}^{+}(n)$ with ${\mathbf{w}}\in\mathbb{H}^{-}(n)$ and
$B_{\mathbf{w}}=1$. Such points can affect the distribution of subsequent
steps and consequently, the joint exploration process
$\\{h^{n}({\mathbf{x}}_{1}),\cdots,h^{n}({\mathbf{x}}_{k}):n\geq 0\\}$ is not
Markov. In the next subsection we show that, together with this information
about ${\cal F}_{n}$ ‘explored’ points in the upper half-plane
$\mathbb{H}^{+}(n)$, the joint exploration process exhibits Markov property.

###  2.1 Markov property of the joint exploration process

We recall that we are studying the joint exploration process of $k$ paths
starting from ${\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k}$ with
${\mathbf{x}}_{1}(2)=\cdots={\mathbf{x}}_{k}(2)=0$. We need to introduce some
more notations. For $l\in{\mathbb{Z}}$ we partition the set $V$ as

$\displaystyle V^{+}_{l}$
$\displaystyle:=\\{\tilde{{\mathbf{w}}}={\mathbf{w}}+\Lambda_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{+}(l),B_{\mathbf{w}}=1\\}\text{
and }$ $\displaystyle V^{-}_{l}$
$\displaystyle:=\\{\tilde{{\mathbf{w}}}={\mathbf{w}}+\Lambda_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{-}(l),B_{\mathbf{w}}=1\\}.$
(9)

We observe that $V^{+}_{l}\subset\mathbb{H}^{+}(l)$ and the $\sigma$-field
${\cal F}_{l}$ does not have any information about the set $V^{+}_{l}$. On the
other hand, the set $V^{-}_{l}$ has been completely explored by ${\cal F}_{l}$
and the set $V^{-}_{l}$ is not necessarily contained in the lower half-plane
$\mathbb{H}^{-}(l)$. As discussed earlier, the information that the
$\sigma$-field ${\cal F}_{l}$ has about the point set
$V\cap\mathbb{H}^{+}(l)$, is given by the set

$\displaystyle
I_{l}:=V^{-}_{l}\cap\mathbb{H}^{+}(l)=\\{\tilde{{\mathbf{w}}}={\mathbf{w}}+\Lambda_{\mathbf{w}}\in\mathbb{H}^{+}(l):{\mathbf{w}}\in\mathbb{H}^{-}(l),B_{\mathbf{w}}=1\\}.$
(10)

In other words, $I_{l}$ represents the information that the $\sigma$-field
${\cal F}_{l}$ has about the point set $V\cap\mathbb{H}^{+}_{l}$. The next
proposition shows that, together with this information set, the joint
exploration process is Markov.

######  Proposition 2.1.

The process
$\\{(h^{n}({\mathbf{x}}_{1}),\cdots,h^{n}({\mathbf{x}}_{k}),I_{n}):n\geq 0\\}$
is Markovian.

###### Proof.

We consider independent collection of i.i.d. random vectors

$\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{\\}}$

independent of the collection
$\\{\Gamma_{\mathbf{w}}:{\mathbf{w}}\in{\mathbb{Z}}^{2}\\}$. Fix $n\geq 1$.
Conditional on the event
$\\{(h^{n}({\mathbf{x}}_{1}),\cdots,h^{n}({\mathbf{x}}_{k}),I_{n})=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{k},\Delta)\\}$,
we consider the point process

$\displaystyle\Psi=\Psi({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{k},\Delta):=\\{{\mathbf{w}}+\Lambda^{\text{ind}}_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{+}(n),B^{\text{ind}}_{\mathbf{w}}=1\\}\cup\Delta$

in the upper half-plane $\mathbb{H}^{+}(n)$.

We observe that starting from ${\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{k}$
together with the information set $\Delta$, the future evolution of the
process has the same distribution as starting with the point process $\Psi$ on
the upper half-plane $\mathbb{H}^{+}(n)$. In other words, we have the
following

$\displaystyle(h^{n+1}({\mathbf{x}}_{1}),\cdots,h^{n+1}({\mathbf{x}}_{k}),I_{n+1})\mid$
$\displaystyle\bigl{(}(h^{n}({\mathbf{x}}_{1}),\cdots,h^{n}({\mathbf{x}}_{k}),I_{n})=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{k},\Delta),{\cal
F}_{n}\bigr{)}$ $\displaystyle\stackrel{{\scriptstyle
d}}{{=}}f\bigl{(}({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{k},\Delta),\\{\Gamma^{\text{ind}}_{\mathbf{w}}:{\mathbf{w}}\in{\mathbb{Z}}^{2}\\}\bigr{)},$

for some measurable function $f$. Hence, by the random mapping theorem (see
[LPW08]) Proposition 2.1 follows. ∎

In the next subsection we define a sequence of random steps such that starting
from these steps, future evolution of each of these $k$ paths stays inside a
specific region. Later we will use this sequence to construct a (random)
subsequence which will give us sequence of renewal steps.

###  2.2 Sequence of ‘In’ steps

We first define a specific 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

$\displaystyle\nabla=\nabla(\mathbf{0}):=\\{(x,y)\in{\mathbb{R}}^{2}:y\geq
0,x\in[-y^{2},y^{2}]\\}.$

For ${\mathbf{x}}\in{\mathbb{R}}^{2}$ and for any subset
$O\subset{\mathbb{R}}^{2}$, the notation ${\mathbf{x}}\oplus O$ denotes the
set $\\{{\mathbf{x}}+{\mathbf{y}}:{\mathbf{y}}\in O\\}$, i.e, the set $O$
translated by ${\mathbf{x}}$. 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}}$. Below we list an important nesting
property between these parabolic regions.

[plotpoints=2000,linecolor=blue]-99 x abs sqrt
[plotpoints=2000,linecolor=blue]-99 x abs sqrt [plotpoints=2000,
linecolor=blue]-17 x 3 sub abs sqrt 2 add
$\mathbf{v}$$\nabla(\mathbf{0})$[gridcolor=lightgray, gridwidth=0.25pt,
subgriddiv=1, gridlabels=7pt](0,0)(-9,0)(9,4.0)  Figure 1:  The parabolic
curve $\\{(\pm y^{2},y):y\geq 0\\}$ is represented in this figure.
$\nabla(\mathbf{0})$ is the gray region inside this curve. Observe that for
any ${\mathbf{v}}\in\nabla(\mathbf{0})\cap{\mathbb{Z}}^{2}$ we have
$\nabla({\mathbf{v}})\subseteq\nabla(\mathbf{0})$ as mentioned in Remark 2.2.
‘In’ event occurs at ${\mathbf{v}}$ as the PH path
$\\{h^{j}({\mathbf{v}}):j\geq 1\\}$ starting from ${\mathbf{v}}$ stays inside
the region $\nabla({\mathbf{v}})$ throughout.

######  Remark 2.2 (Nesting property:).

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
$\nabla({\mathbf{v}})\subseteq\nabla({\mathbf{u}})$ (refer to Figure 1 for an
illustration).

For ${\mathbf{v}}\in{\mathbb{Z}}^{2}$, we define the event
$\text{In}({\mathbf{v}})$ as

$\text{In}({\mathbf{v}}):=\\{h^{n}({\mathbf{v}})=h^{n}({\mathbf{v}},V)\in\nabla({\mathbf{v}})\text{
for all }n\geq 1\\}.$ (11)

We refer the reader to Figure 1 for an example of ‘In’ event.

For the joint exploration process of $k$ paths starting from
${\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k}$, we say that the ‘In’ event occurs
at the $n$-th step if the event
$\cap_{i=1}^{k}\text{In}(h^{n}({\mathbf{x}}_{i}))$ occurs. In other words,
occurrence of the ‘In’ event at the $n$-th step ensures that for each $1\leq
i\leq k$, the PH path starting from $h^{n}({\mathbf{x}}_{i})$ stays inside the
region $\nabla(h^{n}({\mathbf{x}}_{i}))$. Now we are ready to define our
sequence of ‘In’ steps.

Set
$\tau_{0}=\tau_{0}({\mathbf{x}}_{1},{\mathbf{x}}_{2},\cdots,{\mathbf{x}}_{k})=0$.
For $j\geq 1$ we define the random step $\tau_{j}$ as

$\displaystyle\tau_{j}=\tau_{j}({\mathbf{x}}_{1},{\mathbf{x}}_{2},\cdots,{\mathbf{x}}_{k})$
$\displaystyle:=\inf\\{n>\tau_{j-1}:\text{ `In' event occurs}\\}$
$\displaystyle=\inf\\{n>\tau_{j-1}:\text{ event
}\cap_{i=1}^{k}\text{In}(h^{n}({\mathbf{x}}_{i}))\text{ occurs}\\}.$ (12)

First we need to show that the r.v. $\tau_{j}$ is a.s. finite for all $j\geq
1$. We will do that shortly (in Proposition 2.3). For the moment, we assume
that $\tau_{j}$ is well defined for all $j\geq 1$ and proceed. We observe that
the r.v. $\tau_{j}$ is not a stopping time w.r.t. our filtration $\\{{\cal
F}_{n}:n\geq 0\\}$. We need to extend our filtration to make it a stopping
time. For $n\geq 1$, we define the $\sigma$-field

$\displaystyle\overline{{\cal F}}_{n}:=\sigma\bigl{(}{\cal
F}_{n},\text{In}(h^{m}({\mathbf{x}}_{i}))\text{ for }0\leq m\leq n,1\leq i\leq
k\bigr{)}.$ (13)

For each $j\geq 1$, the r.v. $\tau_{j}$ is a stopping time w.r.t. the extended
filtration $\\{\overline{{\cal F}}_{n}:n\geq 0\\}$. This allows us to define
the filtration

$\displaystyle\\{{\cal G}_{j}:=\overline{{\cal F}}_{\tau_{j}}:j\geq 1\\}.$
(14)

We observe that for all $j\geq 1$, the r.v. $\tau_{j}$ is ${\cal G}_{j}$
measurable. The next proposition implies that for all $j\geq 1$, the stopping
time $\tau_{j}$ is a.s. finite. Before we proceed further, it is important to
mention that several results of this paper involve constants. For the sake of
clarity, we will use $C_{0}$ and $C_{1}$ to denote two positive constants,
whose exact values may change from one line to the other. The important thing
is that both $C_{0}$ and $C_{1}$ are universal constants whose values will
depend only on parameters of the process, viz., $p,\theta_{x},\theta_{y}$ and
$k$ (the number of trajectories considered). We are now ready to state our
result which would imply $\tau_{j}$ is a.s. finite for all $j\geq 1$.

######  Proposition 2.3.

For any $j\geq 0$ there exist constants $C_{0},C_{1}>0$, which do not depend
on $j$, such that for all $n\in{\mathbb{N}}$ we have

${\mathbb{P}}(\tau_{j+1}-\tau_{j}>n\mid{\cal G}_{j})\leq
C_{0}\exp{(-C_{1}n)}.$

We need other results to prove Proposition 2.3. First we need to introduce
certain notions of exponential tails for a general family of random variables.
We require these notions to prove Proposition 2.3 and they will be used
repeatedly in later part of this paper .

######  Definition 2.4.

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

${\mathbb{P}}(X_{i}>n)\leq C_{0}\exp{(-C_{1}n)}\text{ for all
}n,i\in{\mathbb{N}}.$

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

$\displaystyle{\mathbb{P}}\bigl{(}X_{i}>n\mid(X_{i-1},\cdots,X_{1})\bigr{)}\leq
C_{0}\exp{(-C_{1}n)}\text{ for all }n\in{\mathbb{N}}.$ (15)

We need Proposition 2.5 regarding tail decay of a random sum of r.v.’s with
exponential tail decay to prove Proposition 2.3.

######  Corollary 2.5.

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

${\mathbb{P}}(\sum_{i=1}^{Y}X_{i}>n)\leq C_{0}\exp{(-C_{1}n)}.$

###### Proof.

Firstly, we observe that because of (15) in Definition 2.4 there exists a r.v.
$W$ such that for all $i\geq 1$ we have

$\displaystyle{\mathbb{P}}\bigl{(}X_{i}>n\mid(X_{i-1},\cdots,X_{1})\bigr{)}\leq{\mathbb{P}}(W>n)\leq
C_{0}\exp{(-C_{1}n)}\text{ for all }n\in{\mathbb{N}}.$ (16)

Next, independent of the family $\\{X_{i}:i\geq 1\\}$, we generate i.i.d.
copies $W_{1},W_{2},\dotsc,$ of $W$ where $W$ is as in (16). Because of Lemma
of 2.7 [RSS16A] to prove Corollary 2.5 it is enough to show that for all
$j\geq 1$ we have

$\displaystyle{\mathbb{P}}(\sum_{i=1}^{j}X_{i}>n)\leq{\mathbb{P}}(\sum_{i=1}^{j}W_{i}>n).$
(17)

We prove (17) using the method of induction. Clearly, the choice of $W_{1}$ in
(17) holds for $j=1$. Assuming that (17) holds for $j\geq 1$ we obtain

$\displaystyle{\mathbb{P}}(\sum_{i=1}^{j+1}X_{i}>n)$
$\displaystyle=\sum_{m}P(\sum_{i=1}^{j}X_{i}=m)P(X_{j+1}>n-m|X_{1},X_{2},\dotsc,X_{j})$
$\displaystyle\leq\sum_{m}P(\sum_{i=1}^{j}X_{i}=m)P(W_{j+1}\geq n-m)$
$\displaystyle\leq\sum_{m}P(\sum_{i=1}^{j}W_{i}=m)P(W_{j+1}\geq n-m)$
$\displaystyle=P(\sum_{i=1}^{j+1}W_{i}\geq n).$

The last inequality follows from the induction hypothesis. This completes the
proof. ∎

######  Remark 2.6.

We note that Proposition 2.5 does not require $\\{X_{i}:i\in{\mathbb{N}}\\}$
to be a family of i.i.d. r.v.’s. Further, the above corollary does not assume
independence of $Y$ and the family $\\{X_{i}:i\geq 1\\}$. We only require
strong uniform exponential tail decay for the family $\\{X_{i}:i\geq 1\\}$ as
mentioned in Definition (2.4). It should be observed that Proposition 2.3
actually states strong uniform exponential tail decay for the family
$\\{\tau_{j}:j\geq 1\\}$ where the decay constants depend only on parameters
of the process and on $k$ (number of paths considered).

Proposition 2.3 will be proved through a sequence of lemmas. In the next
lemma, we show that given ${\cal F}_{n}$, the probability of occurrence of
‘In’ event at the $n$-th step
$(h^{n}({\mathbf{x}}_{1}),\cdots,h^{n}({\mathbf{x}}_{k}))$ has a strictly
positive lower bound which does not depend on $n\geq 1$ or on the choice of
starting points ${\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k}$.

######  Lemma 2.7.

There exists $p_{\text{in}}=p_{\text{in}}(p,\theta_{x},\theta_{y},k)>0$, which
does not depend on $n$ and the starting points
${\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k}$, such that for any $n\geq 0$ we
have

${\mathbb{P}}(\cap_{i=1}^{k}\text{In}(h^{n}({\mathbf{x}}_{i}))\mid{\cal
F}_{n})\geq p_{\text{in}}.$

In order to prove the above lemma we need to introduce a ‘special’ subset of
$V$ denoted by $V_{\text{sp}}$ and defined as

$\displaystyle
V_{\text{sp}}:=\\{{\mathbf{u}}\in{\mathbb{Z}}^{2}:B_{\mathbf{u}}=1,X_{\mathbf{u}}=Y_{\mathbf{u}}=0\\}.$
(18)

In other words, $V_{\text{sp}}$ represents the collection of open points in
$V$ with no perturbations at all. The distribution of the random vector
$\Gamma_{\mathbf{u}}$, defined as (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

$\displaystyle{\mathbb{P}}({\mathbf{u}}\in
V_{\text{sp}})={\mathbb{P}}(B_{\mathbf{u}}=1){\mathbb{P}}(X_{\mathbf{u}}=Y_{\mathbf{u}}=0)=p_{0}>0.$
(19)

It is not difficult to see that for any $n\in{\mathbb{N}}$, the set 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
${\cal F}_{n}$. This observation enables us to obtain exponential decay for
the increments of the PH process as follows: given ${\cal F}_{n}$ for any
${\mathbf{w}}\in\mathbb{H}^{+}(n)$ we have

${\mathbb{P}}((h({\mathbf{w}})-{\mathbf{w}})(1)>m\mid{\cal
F}_{n})\leq(1-p_{0})^{2m+1}\text{ for all }m\in{\mathbb{N}}.$

This readily gives us the following corollary:

######  Corollary 2.8.

Fix any $\alpha,\beta>0$ with $\alpha>\beta>0$. Then we have

${\mathbb{P}}\bigl{(}\max\\{|h^{j}(\mathbf{0})(1)|:1\leq j\leq
n^{\beta}\\}>n^{\alpha}\mid{\cal F}_{0}\bigr{)}\leq
C_{0}\exp{(-C_{1}n^{\alpha-\beta})}.$

Next we prove Lemma 2.7 for $k=1$, i.e., for the marginal process
$\\{h^{n}({\mathbf{x}}_{1}):n\in{\mathbb{N}}\\}$. Later for general $k\geq 2$,
Lemma 2.7 is proved by invoking the FKG inequality for certain ‘increasing’
events (see Lemma 2.10).

Proof of Lemma 2.7 for $k=1$ :  We first explain the heuristics. The idea is
to create a ‘shield’ of special points which would keep the PH path inside the
parabolic region. This shield should be sufficiently spread out to ensure that
the PH path is enclosed in the parabolic region has a positive probability of
occurrence. This motivates our choice of parabolic regions in the definition
of ‘In’ event. To make everything rigorous, we need to introduce some
notations.

For $m\in{\mathbb{N}}$, let $I^{R}_{m},I^{L}_{m}\subset{\mathbb{Z}}^{2}$
denote the sets

$\displaystyle I^{R}_{m}=I^{R}_{m}(\mathbf{0})$
$\displaystyle:=\\{(u,m)\in{\mathbb{Z}}^{2}:u\in[(m-1)^{2}+1,m^{2}]\\}\text{
and }$ $\displaystyle I^{L}_{m}=I^{L}_{m}(\mathbf{0})$
$\displaystyle:=\\{(u,m)\in{\mathbb{Z}}^{2}:u\in[-m^{2},-(m-1)^{2}-1]\\}.$
(20)

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:

  * (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 end point of the set $I^{R}_{m+1}$ on the line
$y=m+1$ is (strictly) larger than the coordinate of the right end point of
$I^{R}_{m}$ on the line $y=m$. On the other hand, the coordinate of the right
end point of the set $I^{L}_{m+1}$ on the line $y=m+1$ is (strictly) smaller
than the left end point of $I^{L}_{m}$ on the line $y=m$.

[plotpoints=2000,linecolor=blue]-99 x abs sqrt [gridcolor=lightgray,
gridwidth=0.25pt, subgriddiv=1, gridlabels=7pt](0,0)(-9,0)(9,3)  Figure 2: 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 gray
points are perturbed versions of open points from some other locations. There
might be some points of $V$ in the intermediate region too.

Next, we define the event $A_{\text{sp}}=A^{\text{sp}}(\mathbf{0})$ as

$\displaystyle
A_{\text{sp}}(\mathbf{0}):=\bigcap_{m=1}^{\infty}\\{I^{R}_{m}\cap
V_{\text{sp}}\neq\emptyset\\}\cap\\{I^{L}_{m}\cap
V_{\text{sp}}\neq\emptyset\\}.$ (21)

In other words, the event $A_{\text{sp}}(\mathbf{0})$ ensures that for all
$m\geq 1$, both the sets $I^{R}_{m}$ and $I^{L}_{m}$ must have at least one
special point each. Heuristically, 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\\}$ can not cross the parabolic curve $\Upsilon$
and must stay inside the region $\nabla(\mathbf{0})$ throughout. Figure 2
presents an illustration of the event $A_{\text{sp}}(\mathbf{0})$. 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}}$.

Similarly, 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}))$. Also
$A_{\text{sp}}(h^{j}({\mathbf{x}}_{1}))$ involves points from the set
$V^{+}_{j}$ only (because ${\mathbf{x}}_{1}(2)=0$). Therefore, it is
independent of the $\sigma$-field ${\cal F}_{j}$. This gives us that

$\displaystyle{\mathbb{P}}(\text{In}(h^{j}({\mathbf{x}}_{1}))\mid{\cal
F}_{j})$
$\displaystyle\geq{\mathbb{P}}(A_{\text{sp}}(h^{j}({\mathbf{x}}_{1}))\mid{\cal
F}_{j})$ $\displaystyle={\mathbb{P}}(A_{\text{sp}}(h^{j}({\mathbf{x}}_{1})))$
$\displaystyle={\mathbb{P}}(A_{\text{sp}}(\mathbf{0}))$
$\displaystyle=\prod_{m=1}^{\infty}(1-(1-p_{0})^{2m-1})^{2}>0.$

where $p_{0}$ is as in (19). In the penultimate equality we have used the
translation invariance nature of our model. This completes the proof. ∎

For proving Lemma 2.7 for $k\geq 2$ we need an FKG property among ‘increasing’
events expressed in terms of special vertices only. We consider a natural
partial order relation on the space $\\{0,1\\}^{{\mathbb{Z}}^{2}}$ given as :
for $\omega,\omega^{\prime}\in\\{0,1\\}^{{\mathbb{Z}}^{2}}$

$\omega\leq\omega^{\prime}\text{ if
}\omega({\mathbf{w}})\leq\omega^{\prime}({\mathbf{w}})\text{ for all
}{\mathbf{w}}\in{\mathbb{Z}}^{2}.$

######  Definition 2.9.

An event $A$ measurable with respect to the $\sigma$-field generated by the
collection of indicator r.v.’s $\bigl{\\{}\mathbf{1}_{\\{{\mathbf{w}}\in
V_{\text{sp}}\\}}:{\mathbf{w}}\in{\mathbb{Z}}^{2}\bigr{\\}}$ is said to be
increasing if

$\omega\in A\Rightarrow\omega^{\prime}\in A\text{ for all
}\omega^{\prime}\geq\omega.$

We observe that the collection of indicator r.v.’s
$\\{\mathbf{1}_{\\{{\mathbf{w}}\in
V_{\text{sp}}\\}}:{\mathbf{w}}\in{\mathbb{Z}}^{2}\\}$ gives a collection of
i.i.d. Bernoulli r.v.’s with success probability $p_{0}$ where $p_{0}$ is as
in (19). Hence, the following lemma regarding FKG property between increasing
events (expressible in terms of special vertices only) follows directly:

######  Lemma 2.10 (FKG property).

For any two increasing events
$A,B\in\sigma\bigl{(}\\{\mathbf{1}_{\\{{\mathbf{w}}\in
V_{\text{sp}}\\}}:{\mathbf{w}}\in{\mathbb{Z}}^{2}\\}\bigr{)}$ we have

${\mathbb{P}}(A\cap B)\geq{\mathbb{P}}(A){\mathbb{P}}(B).$

We are now ready to prove Lemma 2.7 for general $k\geq 2$.

Proof of Lemma 2.7 for $k\geq 2$: For any $j\geq 1$, we observe the following
inclusion of events

$\cap_{i=1}^{k}A_{\text{sp}}(h^{j}({\mathbf{x}}_{i}))\subseteq\cap_{i=1}^{k}\text{In}(h^{j}({\mathbf{x}}_{i})).$

Further, given
$(h^{j}({\mathbf{x}}_{1}),\cdots,h^{j}({\mathbf{x}}_{k}))=({\mathbf{w}}_{1},\cdots,{\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. Further, the
$\sigma$-field ${\cal F}_{j}$ does not have any information about the point
set $V^{+}_{j}$. Hence, an application of FKG property together with the
translation invariance property of our model give us

${\mathbb{P}}\bigl{(}\cap_{i=1}^{k}A_{\text{sp}}(h^{j}({\mathbf{x}}_{i}))\mid{\cal
F}_{j}\bigr{)}\geq{\mathbb{P}}\bigl{(}A_{\text{sp}}(\mathbf{0})\bigr{)}^{k}>0$

and complete the proof. ∎

We are now ready to prove Proposition 2.3. We first explain our heuristics in
words. We look for the occurrence of ‘In’ event at the first step
$(h({\mathbf{x}}_{1}),\cdots,h({\mathbf{x}}_{k}))$. Because of Lemma 2.7, the
probability of occurrence of the ‘In’ event has a strictly positive lower
bound. But, it is important to observe that on the complementary event, the
non-occurrence of ‘In’ event gives us some information about the point set
$V^{+}_{1}$. This prevents us from applying Lemma 2.7 directly at the next
step $(h^{2}({\mathbf{x}}_{1}),\cdots,h^{2}({\mathbf{x}}_{k}))$. In fact,
given that the ‘In’ event does not occur at
$(h({\mathbf{x}}_{1}),\cdots,h({\mathbf{x}}_{k}))$, we can apply the bound
obtained in Lemma 2.7 only after the effect of this information goes away. We
will make these heuristics rigorous now and first present a formal proof of
Proposition 2.3 for $j=0$. In subsection 2.2.1 we complete the proof of
Proposition 2.3 for general $j\geq 1$.

Proof of Proposition 2.3 for $j=0$ :  Given ${\cal F}_{1}$, at the first step
$(h({\mathbf{x}}_{1}),\cdots,h({\mathbf{x}}_{k}))$ we test for occurrence of
the ‘In’ event. By Lemma 2.7 we have that

${\mathbb{P}}(\text{`In' event occurs at
}(h({\mathbf{x}}_{1}),\cdots,h({\mathbf{x}}_{k}))\mid{\cal F}_{1})\geq
p_{\text{in}}.$

When ‘In’ event does not occur at the first step
$(h({\mathbf{x}}_{1}),\cdots,h({\mathbf{x}}_{k}))$, we wait for the joint
exploration process to discover this fact, i.e., till the time one of the $k$
paths steps outside the respective parabolic region. To make it rigorous for
${\mathbf{u}}\in{\mathbb{Z}}^{2}$ let $\beta({\mathbf{u}})$ denote the r.v.
defined as

$\displaystyle\beta({\mathbf{u}}):=\min\\{n\in{\mathbb{N}}:h^{n}({\mathbf{u}})\notin\nabla({\mathbf{u}})\\}.$
(22)

Set $\beta_{0}=0$ and $\beta_{1}:=\min\\{\beta(h({\mathbf{x}}_{i})):1\leq
i\leq k\\}$.

We mention that the r.v. $\beta_{1}$ takes the value $+\infty$ with positive
probability and this implies occurrence of the ‘In’ event. On the other hand,
on the event $\\{\tau_{1}>1\\}$ the r.v. $\beta_{1}$ becomes finite. In fact,
the two events $\\{\tau_{1}>1\\}$ and $\\{\beta_{1}<+\infty\\}$ are equal.
Further, we observe that $\beta_{1}$ is a stopping time w.r.t. the filtration
$\\{{\cal F}_{n}:n\in{\mathbb{N}}\\}$ and we have

$\\{\tau_{1}>1\\}=\\{\beta_{1}<+\infty\\}\in{\cal F}_{\beta_{1}}.$

On the event $\\{\tau_{1}>1\\}$, which is same as the event
$\\{\beta_{1}<+\infty\\}$, the $\sigma$-field ${\cal F}_{\beta_{1}}$ does not
have any information about the point set $V^{+}_{\beta_{1}}$. We can test for
occurrence of the ‘In’ event again at the $(\beta_{1}+1)$-th step and Lemma
2.7 is applicable here. Thus we have

$\mathbf{1}_{\\{\beta_{1}<\infty\\}}{\mathbb{P}}(\text{In event occurs at the
}(\beta_{1}+1)\text{-th step}\mid{\cal
F}_{\beta_{1}})\geq\mathbf{1}_{\\{\beta_{1}<\infty\\}}p_{\text{in}},$

by Lemma 2.7. On the event $\\{\beta_{1}<\infty\\}$, starting from the
$(\beta_{1}+1)$-th step, we define the r.v.
$\beta_{2}:=\beta_{1}+\min\\{\beta(h^{\beta_{1}+1}({\mathbf{x}}_{i})):1\leq
i\leq k\\}$ which is a stopping time as well.

The event $\\{\beta_{2}=+\infty\\}$ implies occurrence of the event
$\cap_{i=1}^{k}\text{In}(h^{\beta_{1}+1}({\mathbf{x}}_{i}))$ and we have
$\tau_{2}=\beta_{1}+1$. Otherwise, i.e., on the event $\\{\beta_{2}<\infty\\}$
the $\sigma$-field ${\cal F}_{\beta_{2}}$ does not have any information about
the point set $V\cap\mathbb{H}^{+}(\beta_{2})$ giving us that

$\mathbf{1}_{\\{\beta_{2}<\infty\\}}{\mathbb{P}}(\text{In event occurs at the
}(\beta_{2}+1)\text{-th step}\mid{\cal
F}_{\beta_{2}})\geq\mathbf{1}_{\\{\beta_{2}<\infty\\}}p_{\text{in}}.$

By repeating the same argument recursively we get that the number of
$\beta_{j}$’s explored to find the value of $\tau_{1}$ is dominated by a
geometric random variable with success probability $p_{\text{in}}>0$.
Unfortunately, we do not have independence for $\beta_{j}$’s. Because of
Proposition 2.5, to prove Proposition 2.3 it suffices to show that for any
$j\geq 0$ given $\beta_{j}<\infty$, the tail probability
${\mathbb{P}}(n<(\beta_{j+1}-\beta_{j})\mathbf{1}_{\\{\beta_{j}<\infty\\}}<\infty\mid{\cal
F}_{\beta_{j}})$ decays exponentially in $n$.

We show this for $j=0$. The same argument works for general $j\geq 1$. For
${\mathbf{u}}\in{\mathbb{Z}}^{2}$, we define the random variable
$J_{\text{sp}}({\mathbf{u}})$ as the minimum distance from ${\mathbf{u}}$ of a
vertex from the set $V^{\text{sp}}$ at the next level $y={\mathbf{u}}(2)+1$,
i.e.,

$J_{\text{sp}}({\mathbf{u}}):=\min\\{k\geq 0:\text{ either
}{\mathbf{u}}+(k,1)\text{ or }{\mathbf{u}}+(-k,1)\in V_{\text{sp}}\\}.$

We observe that

$\displaystyle{\mathbb{P}}(n<(\beta_{1}-\beta_{0})\mathbf{1}_{\\{\beta_{0}<\infty\\}}<\infty)={\mathbb{P}}(n<\beta_{1}<\infty)=\sum_{l=1}^{\infty}{\mathbb{P}}(\beta_{1}=n+l).$
(23)

In order to estimate the probability ${\mathbb{P}}(\beta_{1}=n+l)$, we observe
that for any $1\leq i\leq k$ the PH path starting from ${\mathbf{x}}_{i}$
exits the parabolic region $\nabla({\mathbf{x}}_{i})$ for the first time at
the $n+l$-th step only if there is no point of $V$, in particular, no special
point within $n+l$ distance of the vertex $h^{n+l-1}({\mathbf{x}}_{i})$ on the
line $y=n+l$. Hence, (23) becomes

$\displaystyle\sum_{l=1}^{\infty}{\mathbb{P}}(\beta_{1}=n+l)$
$\displaystyle\leq\sum_{l=1}^{\infty}{\mathbb{P}}(J_{\text{sp}}(h^{n+l-1}({\mathbf{x}}_{i})>2(n+l)-1\text{
for some }1\leq i)$ $\displaystyle\leq
k\sum_{l=1}^{\infty}(1-p_{0})^{2(n+l)-1}$ $\displaystyle\leq
C_{0}\exp{(-C_{1}n)},$

for some $C_{0},C_{1}>0$. This completes the proof of Proposition 2.3 for
$j=0$. ∎

####  2.2.1 Proof of Proposition 2.3 for $j\geq 1$

We now prove Proposition 2.3 for general $j\geq 1$. Fix any $j\geq 1$. The
problem is that the occurrence of ‘In’ event depends on the infinite future.
Given that the step $\tau_{j}$ has occurred, the $\sigma$-field ${\cal G}_{j}$
has some information about the random vectors
$\\{\Gamma_{\mathbf{w}}:{\mathbf{w}}(2)>\tau_{j}\\}$. In order to deal with
this, for any $j\geq 1$, we represent the occurrence of the $j$-th $\tau$ step
as an intersection of the ‘In’ event at the last step and a ${\cal
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}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{v}}_{1},\cdots,{\mathbf{v}}_{j})\\}$
is represented as an intersection of the event $\text{In}({\mathbf{v}}_{j})$
and one ${\cal F}_{{\mathbf{v}}_{j}(2)}$ measurable event. For simplicity of
notations we prove this for $k=1$, i.e., for the marginal process only. The
same argument holds for general $k\geq 1$. We use this representation and show
that given
$\\{(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{v}}_{1},\cdots,{\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_{\text{in}}$ for any $l\geq 1$.

Recall that for ${\mathbf{v}}\in{\mathbb{Z}}^{2}$, $\beta({\mathbf{v}})$ is
defined as the (extended) integer valued r.v.

$\beta({\mathbf{v}}):=\inf\\{l\geq
1:h^{l}({\mathbf{v}})\notin\nabla({\mathbf{v}})\\}.$

######  Lemma 2.11.

We have the following equality of events:

$\displaystyle\\{\tau_{1}=l,h^{l}({\mathbf{x}}_{1})={\mathbf{v}}\\}=\Bigl{[}\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}}\\}\cap\bigl{[}\cap_{j=0}^{l-1}\bigl{(}\\{\beta(h^{j}({\mathbf{x}}_{1}))\leq
l-j\\}\bigr{)}\bigr{]}\Bigr{]}\bigcap(\text{In}({\mathbf{v}})).$

###### Proof.

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

$\displaystyle\\{\tau_{1}=l,h^{l}({\mathbf{x}}_{1})={\mathbf{v}}\\}=$
$\displaystyle\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}},\text{In}({\mathbf{v}})\\}\bigcap\bigl{[}\cap_{j=0}^{l-1}(h^{j}({\mathbf{x}}_{1})\text{
is not a }\tau\text{ step})\bigr{]}$ $\displaystyle=$
$\displaystyle\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}},\text{In}({\mathbf{v}})\\}\bigcap\bigl{[}\cap_{j=0}^{l-1}(\beta(h^{j}({\mathbf{x}}_{1}))<\infty)\bigr{]}.$

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

$\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}},\text{In}({\mathbf{v}}),\beta(h^{j}({\mathbf{x}}_{1}))<\infty\\}=\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}},\text{In}({\mathbf{v}}),\beta(h^{j}({\mathbf{x}}_{1}))\leq
l-j\\}.$

We prove it for $j=0$ and the argument is exactly the same for general $j\geq
1$. On the event
$\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}},\text{In}({\mathbf{v}}),\beta({\mathbf{x}}_{1})>l\\}$,
we must have

$h^{l}({\mathbf{x}}_{1})={\mathbf{v}}\in\nabla({\mathbf{x}}_{1}).$

Otherwise, $\beta({\mathbf{x}}_{1})$ must be smaller than $l$. Further, on the
event
$\text{In}({\mathbf{v}})\cap\\{h^{j}({\mathbf{x}}_{1})={\mathbf{v}}\in\nabla({\mathbf{x}}_{1})\\}$
the nesting property mentioned in Remark 2.2 implies that

$h^{l+m}({\mathbf{x}}_{1})=h^{m}({\mathbf{v}})\in\nabla({\mathbf{v}})\subset\nabla({\mathbf{x}}_{1})\text{
for all }m\geq 1.$

Hence, on the event
$\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}},\text{In}({\mathbf{v}}),\beta({\mathbf{x}}_{1})>l\\}$,
the r.v. $\beta({\mathbf{x}}_{1})$ must take the value $+\infty$ implying that

$\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}},\text{In}({\mathbf{v}}),l<\beta({\mathbf{x}}_{1})<+\infty\\}=\emptyset.$

This completes the proof. ∎

######  Remark 2.12.

We observe that in Lemma 2.11, the event

$\\{h^{l}({\mathbf{x}}_{1})={\mathbf{v}}\\}\cap\bigl{[}\cap_{j=0}^{l-1}\bigl{(}\\{\beta(h^{j}({\mathbf{x}}_{1}))\leq
l-j\\}\bigr{)}\bigr{]}$

is ${\cal F}_{l}$ measurable by construction.

We would like to have a similar result for $\tau_{j}$-th ($j\geq 2$) step,
i.e., consider the event

$\\{\tau_{1}=l_{1},h^{l_{1}}({\mathbf{x}}_{1})={\mathbf{v}}_{1},\tau_{2}=l_{1}+l_{2},h^{l_{1}+l_{2}}({\mathbf{x}}_{1})={\mathbf{v}}_{2}\\},$

the difficulty is that, both the events, $\text{In}({\mathbf{v}}_{1})$ and
$\text{In}({\mathbf{v}}_{2})$, depend on the infinite future. In order to deal
with this, for $l\in{\mathbb{N}}$ and ${\mathbf{v}}\in{\mathbb{Z}}^{2}$, we
define the event $\text{In}^{(l)}({\mathbf{v}})$ as

$\displaystyle\text{In}^{(l)}({\mathbf{v}}):=\\{h^{m}({\mathbf{v}})\in\nabla({\mathbf{v}})\text{
for all }1\leq m\leq l\\}.$ (24)

Clearly, for any $l\in{\mathbb{N}}$ we have
$\text{In}({\mathbf{v}})\subset\text{In}^{(l)}({\mathbf{v}})$. We further
observe that the event $\text{In}^{(l)}({\mathbf{v}})$ is ${\cal
F}_{{\mathbf{v}}(2)+l}$ measurable.

The nesting property as mentioned in Remark 2.2 ensures us that, on the event
$\text{In}({\mathbf{v}})$ for any $l\geq 1$ we have
$\nabla(h^{l}({\mathbf{v}}))\subset\nabla({\mathbf{v}})$. This allows us to
have the following equality of events

$\displaystyle\text{In}({\mathbf{v}})\cap\text{In}(h^{j}({\mathbf{v}}))$
$\displaystyle=\text{In}^{(j)}({\mathbf{v}})\cap\text{In}(h^{j}({\mathbf{v}}))\text{
for any }j\geq 1.$

Using the above reasoning, we write the event

$\\{\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}\\}$

as

$\displaystyle\Bigl{[}\\{h^{j}({\mathbf{x}}_{1})\text{ is not a }\tau\text{
step for any }1\leq
j<m_{1},h^{m_{1}}({\mathbf{x}}_{1})={\mathbf{v}}_{1},\text{In}^{(m_{2}-m_{1})}({\mathbf{v}}_{1})\\}$
$\displaystyle\cap\\{h^{j}({\mathbf{x}}_{1})\text{ is not a }\tau\text{ step
for any
}m_{1}<j<m_{2},h^{m_{2}}({\mathbf{x}}_{1})={\mathbf{v}}_{2}\\}\Bigr{]}\bigcap\text{In}({\mathbf{v}}_{2}).$
(25)

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

######  Corollary 2.13.

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

$\displaystyle\bigcap_{l=1}^{j}\\{\tau_{l}=m_{l},h^{m_{l}}({\mathbf{x}}_{1})={\mathbf{v}}_{l}\\}=$
$\displaystyle\Bigl{[}\bigcap_{l=1}^{j}\\{h^{m_{l}}({\mathbf{x}}_{1})={\mathbf{v}}_{l}\\}\cap\bigl{\\{}\cap_{n=m_{l-1}+1}^{m_{l}-1}(\beta(h^{n}({\mathbf{x}}_{1}))\leq
m_{l}-n)\bigr{\\}}$
$\displaystyle\bigcap(\cap_{l=1}^{j-1}\text{In}^{(m_{(l+1)}-m_{l})}({\mathbf{v}}_{l}))\Bigr{]}\bigcap\text{In}({\mathbf{v}}_{j}),$
(26)

and other than the event $\text{In}({\mathbf{v}}_{j})$, rest of the other
events in the r.h.s. of (4.2) are ${\cal F}_{{\mathbf{v}}_{l}(2)}={\cal
F}_{m_{l}}$ measurable.

For simplicity of notation we write

$E({\mathbf{v}}_{1},\cdots,{\mathbf{v}}_{j}):=\Bigl{[}\bigcap_{l=1}^{j}\\{h^{m_{l}}({\mathbf{x}}_{1})={\mathbf{v}}_{l}\\}\cap\bigl{\\{}\cap_{n=m_{l-1}+1}^{m_{l}-1}(\beta(h^{n}({\mathbf{x}}_{1}))\leq
m_{l}-n)\bigr{\\}}\bigcap(\cap_{l=1}^{j-1}\text{In}^{(m_{l+1}-m_{l})}({\mathbf{v}}_{l}))\Bigr{]}.$

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

Proof of Proposition 2.3 :  Fix any $j\geq 1$. Given
$(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})$,
for any $l\geq 1$ we obtain

$\displaystyle{\mathbb{P}}\bigl{(}In(h^{\tau_{j}+l}({\mathbf{x}}_{1}))\mid(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}$
$\displaystyle=$
$\displaystyle{\mathbb{P}}\bigl{(}In(h^{l}({\mathbf{w}}_{j}))\mid(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j}))\bigr{)}$
$\displaystyle=$
$\displaystyle{\mathbb{P}}\bigl{(}In(h^{l}({\mathbf{w}}_{j}))\cap(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j}))\bigr{)}/{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j}))$
$\displaystyle=$
$\displaystyle{\mathbb{P}}\bigl{(}In(h^{l}({\mathbf{w}}_{j}))\cap(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}^{(l)}({\mathbf{w}}_{j}))\bigr{)}/{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j}))$
$\displaystyle\geq$
$\displaystyle{\mathbb{P}}\bigl{(}A_{\text{sp}}(h^{l}({\mathbf{w}}_{j}))\cap(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}^{(l)}({\mathbf{w}}_{j}))\bigr{)}/{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j}))$
$\displaystyle=$
$\displaystyle{\mathbb{P}}(A_{\text{sp}}(h^{l}({\mathbf{w}}_{j})))\Bigl{(}{\mathbb{P}}\bigl{(}E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}^{(l)}({\mathbf{w}}_{j})\bigr{)}/{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j}))\Bigr{)}$
$\displaystyle\geq$ $\displaystyle{\mathbb{P}}(A_{\text{sp}}(\mathbf{0})).$

In the last step together with the translation invariance nature of our model,
we use the fact that

$\bigl{(}E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j})\bigr{)}\subset\bigl{(}E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}^{(l)}({\mathbf{w}}_{j})\bigr{)}.$

The penultimate step follows from the fact that the event
$A_{\text{sp}}(h^{l}({\mathbf{w}}_{j}))$ depends on the collection
$\\{\Gamma_{w}:{\mathbf{w}}(2)>{\mathbf{w}}_{j}(2)+l\\}$ and is independent of
the ${\cal F}_{{\mathbf{w}}_{j}(2)+l}$ measurable event
$(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}^{(l)}({\mathbf{w}}_{j}))$.

Given
$(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})$,
using a similar argument for any
${\mathbf{v}}\in\mathbb{H}^{+}({\mathbf{w}}_{j})(2)$ and for any $l\geq 1$ we
have that

$\displaystyle{\mathbb{P}}\bigl{(}J_{\text{sp}}({\mathbf{v}})>l\mid(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}$
$\displaystyle={\mathbb{P}}\bigl{(}J_{\text{sp}}({\mathbf{v}})>l\mid
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j})\bigr{)}$
$\displaystyle={\mathbb{P}}\bigl{(}J_{\text{sp}}({\mathbf{v}})>l\cap
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j})\bigr{)}/{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j}))$
$\displaystyle\leq{\mathbb{P}}\bigl{(}J_{\text{sp}}({\mathbf{v}})>l\cap
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}/{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j}))$
$\displaystyle\leq{\mathbb{P}}\bigl{(}J_{\text{sp}}({\mathbf{v}})>l\cap
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}/{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}))$
$\displaystyle={\mathbb{P}}(J_{\text{sp}}({\mathbf{v}})>l){\mathbb{P}}\bigl{(}E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}\Bigl{(}{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})){\mathbb{P}}(A_{\text{sp}}({\mathbf{w}}_{j}))\Bigr{)}^{-1}$
$\displaystyle={\mathbb{P}}\bigl{(}J_{\text{sp}}({\mathbf{v}})>l\bigr{)}{\mathbb{P}}(A_{\text{sp}}(\mathbf{0}))^{-1}\leq
C_{0}\exp{(-C_{1}l)},$ (27)

for some $C_{0},C_{1}>0$ which do not depend on $j$. In the penultimate step
we have used the fact that the event
$E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})$ is ${\cal
F}_{{\mathbf{w}}_{j}(2)}$ measurable and hence, independent of the events
$\\{J_{\text{sp}}({\mathbf{v}})>l\\}$ and $A_{\text{sp}}({\mathbf{w}}_{j})$.
The last step follows from the translation invariance nature of our model.

Equation (2.2.1) allows us to repeat the calculations in (LABEL:eq:BetaTail)
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. ∎

Fix $j\geq 1$. Given the $\sigma$-field ${\cal G}_{j}$, for each $1\leq i\leq
k$ the PH 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})$, it’s perturbed version
$\tilde{{\mathbf{w}}}$ can affect the distribution of the joint process
starting from
$(h^{\tau_{j}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{k}))$ only
if

$\tilde{{\mathbf{w}}}\in\cup_{i=1}^{k}\nabla(h^{\tau_{j}}({\mathbf{x}}_{i}))\text{
for some }1\leq i\leq k.$

This motivates us to define the set

$\displaystyle
H_{\tau_{j}}=H_{\tau_{j}}({\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k}):=I_{\tau_{j}}({\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k})\cap\bigl{(}\cup_{i=1}^{k}\nabla(h^{\tau_{j}}({\mathbf{x}}_{i}))\bigr{)},$
(28)

for $j\geq 1$, where $I_{n}$ is defined as in (10).

##  3 Renewal steps

Below, we define a sequence of what we call as ‘renewal steps’. Set
$\gamma_{0}=0$ and for $\ell\geq 1$ define

$\gamma_{\ell}=\gamma_{\ell}({\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k}):=\inf\\{j>\gamma_{\ell-1}:H_{\tau_{j}}({\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k})=\emptyset\\},$
(29)

where $H_{\tau_{j}}({\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k})$ is defined as
in (28).

We need to show that for all $\ell\geq 1$, the r.v. $\gamma_{\ell}$ is well
defined in the sense that $\gamma_{\ell}$ is finite a.s. A stronger result
will be proved in Proposition 3.2. For the moment, we proceed 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., number of ‘In’ steps required
for the $\ell$-th renewal step and the r.v.
$\sigma_{\ell}:=\tau_{\gamma_{\ell}}$ denotes the total number of steps
required for the $\ell$-th occurrence of renewal event.

We observe that the condition
$H_{\tau_{j}}({\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k})=\emptyset$ implies
that no open point from the lower half-plane $\mathbb{H}^{-}(\tau_{j})$ are
allowed to perturb to a vertex inside the parabolic regions
$\nabla(h^{\tau_{j}}({\mathbf{x}}_{i}))$ for any $1\leq i\leq k$. For
${\mathbf{u}}\in{\mathbb{Z}}^{2}$ we define the event
$\text{Out}({\mathbf{u}})$ as

$\displaystyle\text{Out}({\mathbf{u}}):=\\{V^{-}({\mathbf{u}}(2))\cap\nabla({\mathbf{u}})\\}=\emptyset.$
(30)

For the joint PH process
$\\{(h^{j}({\mathbf{x}}_{1}),\cdots,h^{j}({\mathbf{x}}_{k})):j\geq 1\\}$ we
say that the ‘Out’ event occurs at the $n$-th step if the event
$\cap_{i=1}^{k}\text{Out}(h^{n}({\mathbf{x}}_{i}))$ occurs. In other words,
occurrence of a renewal event implies joint occurrence of ‘In’ event and ‘Out’
event. For an illustration we refer the reader to Figure 3.

[plotpoints=2000,linecolor=blue]-9-1 x 5 add abs sqrt
[plotpoints=2000,linecolor=red]-19 x 3 sub abs sqrt
[plotpoints=2000,linecolor=blue]-94 x 5 add abs sqrt
[plotpoints=2000,linecolor=gray]-69 x 3 sub abs sqrt [gridcolor=gray,
gridwidth=0.25pt, subgriddiv=1, gridlabels=7pt](0,0)(-9,-2)(9,3.0)
$h_{\sigma_{\ell}}(\mathbf{x}_{1})$$h_{\sigma_{\ell}}(\mathbf{x}_{2})$$\nabla(h_{\sigma_{\ell}}(\mathbf{x}_{1}))$$\nabla(h_{\sigma_{\ell}}(\mathbf{x}_{2}))$
Figure 3: This figure represents joint renewal for two paths. ‘In’ event
condition ensures that PH paths must stay inside the respective
$\nabla(\cdot)$ regions. ‘Out’ event condition ensures that perturbed versions
of all open points in the lower half-plane (shaded with gray) must be outside
the $\nabla(\cdot)$ regions.

Note that the event $\text{Out}({\mathbf{u}})$ is ${\cal F}_{{\mathbf{u}}(2)}$
measurable and, for any $\ell\geq 1$, the r.v. $\gamma_{\ell}$ is a stopping
time w.r.t. the filtration $\\{{\cal G}_{j}:j\geq 1\\}$ defined as in (14).
This allows us to define the filtration

$\displaystyle\\{{\cal S}_{\ell}:={\cal G}_{\gamma_{\ell}}:\ell\geq 1\\}.$
(31)

For each $\ell\geq 1$, the r.v. $\sigma_{\ell}$ and the random vector
$(h^{\sigma_{\ell}}({\mathbf{x}}_{1}),\cdots,h^{\sigma_{\ell}}({\mathbf{x}}_{k}))$
are ${\cal S}_{\ell}$ measurable. The next proposition is the main result of
this section which states that the total number of steps between any two
successive renewal steps has strong uniform exponential tail decay.

######  Proposition 3.1.

Fix any $\ell\geq 0$. For all $n\in{\mathbb{N}}$ we have

${\mathbb{P}}((\sigma_{\ell+1}-\sigma_{\ell})>n\mid{\cal S}_{\ell})\leq
C_{0}\exp{(-C_{1}n)}$

for some $C_{0},C_{1}>0$ which do not depend on $\ell$.

In the next section we will prove Proposition 3.1.

###  3.1 Existence of moments for steps between two successive renewals

Because of Proposition 2.3 and Lemma 3.7, in order to prove Proposition 3.1 it
is enough to prove strong uniform exponential tail decay type behaviour for
number of $\tau$ steps required between two successive renewals as mentioned
in the next proposition.

######  Proposition 3.2.

Fix $\ell\geq 0$. The number of $\tau$ steps between $\ell+1$-th renewal and
$\ell$-th renewal is represented by $(\gamma_{\ell+1}-\gamma_{\ell})$, and for
all $n\in{\mathbb{N}}$ we have

${\mathbb{P}}((\gamma_{\ell+1}-\gamma_{\ell})>n\mid{\cal S}_{\ell})\leq
C_{0}\exp{(-C_{1}n)}$

for some $C_{0},C_{1}>0$ which does not depend on $\ell$.

To prove Proposition 3.2, we define a height process $\\{L_{j}:j\geq 1\\}$
which is such that $L_{j}$ equals zero if and only if the information set
$H_{\tau_{j}}$ becomes empty. We recall that the joint exploration process of
$k$ paths starts from points ${\mathbf{x}}_{1},\cdots,{\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

$\displaystyle 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\\}.$

More generally, for $j\geq 1$ we define the height function $L_{j}$ as

$\displaystyle 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\\}.$

By definition for any $j\geq 1$, the event $L_{j}=0$ implies that the
corresponding information set $H_{\tau_{j}}$ must be empty and vice versa.
Hence, for any $\ell\geq 1$ we also have the following equivalent
representation of the r.v. $\gamma_{\ell}$ as

$\displaystyle\gamma_{\ell}:=\inf\\{j>\gamma_{\ell-1}:L_{j}=0\\}.$

The height process $\\{L_{j}:j\geq 0\\}$ is non-negative and not Markov.
Regarding evolution of this process we obtain the following properties:

  * (i)

We obtain an important recursion relation (see (33)) in Subsection 3.1.1
regarding evolution of $\\{L_{j}:j\geq 0\\}$.

  * (ii)

Further, we show that the amount of increase in the height process, i.e., the
random quantity $(L_{j+1}-L_{j})\mathbf{1}_{\\{L_{j+1}>L_{j}\\}}$ for $j\geq
0$ exhibits strong uniform exponentially decaying tail behaviour.

  * (iii)

Lemma 3.4 gives us a strictly positive uniform lower bound for the probability
that $L_{j}$ decreases by at least one at the next step.

These three properties together allow us to construct a non-negative integer
valued geometrically ergodic Markov chain which stochastically dominates
evolution of $\\{L_{j}:j\geq 0\\}$ and prove Proposition 3.2. Details are
given in Section 3.1.2.

####  3.1.1 A (stochastic) bound to control increase in $L_{n}$

Fix any $j\geq 0$. Given the $\sigma$-field ${\cal G}_{j}$, we consider
evolution of the joint process between $\tau_{j}$-th and $\tau_{j+1}$-th step.
Given ${\cal G}_{j}$, the ‘newly’ explored vertices are perturbed versions of
vertices in the set
$\mathbb{H}^{-}(\tau_{j+1})\setminus\mathbb{H}^{-}(\tau_{j})$, i.e., vertices
those are explored between the $\tau_{j}$-th and the $\tau_{j+1}$-th steps.
The contribution of these newly explored vertices to $L_{j+1}$ is denoted by a
random variable ${\cal N}_{j+1}$ defined as

$\displaystyle{\cal
N}_{j+1}:=1+\sup\\{(\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\cup_{i=1}^{k}\nabla(h^{\tau_{j+1}}({\mathbf{x}}_{i}))\\}.$
(32)

Actually, ${\cal N}_{j+1}$ represents one excess to the actual contribution
and the reason behind this modification is to ensure that the recursion
relation (33) holds with probability $1$. The following lemma gives a
recursion relation which bounds the amount of increase in $L_{j}$.

######  Lemma 3.3.

For all $j\geq 1$ we have

$L_{j+1}\leq\max\\{L_{j},{\cal N}_{j+1}\\}-1.$ (33)

###### Proof.

For any ${\mathbf{w}}\in\mathbb{H}^{-}(\tau_{j})$ the corresponding random
vector $\Gamma_{\mathbf{w}}$ has been explored already by the $\sigma$-field
${\cal G}_{j}$ and will be termed as an ‘older’ vertex henceforth. We observe
that for any ‘older’ lattice point ${\mathbf{w}}$, which does not contribute
to $L_{j}$, two situations can happen:

  * (i)

either ${\mathbf{w}}$ is closed or

  * (ii)

${\mathbf{w}}$ is open but
$\tilde{{\mathbf{w}}}\notin\cup_{i=1}^{k}\nabla(h^{\tau_{j}}({\mathbf{x}}_{i}))$.

By the nesting property as in Remark 2.2, we have that
$\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 PH path goes up by one
step, for any older vertex ${\mathbf{w}}$ contributing to $L_{j}$, it’s
contribution to $L_{j+1}$ decreases by at least one compared to it’s
contribution to $L_{j}$.

Further, the above discussion suggests that we can have $L_{j+1}\geq L_{j}$
due to contributions from newly explored vertices only. Hence, the recursion
relation (33) follows from the definition of the random variable ${\cal
N}_{j+1}$ as in (32). ∎

The next lemma shows that at every $\tau$ step, the probability that the
height random variable reduces by at least one is uniformly bounded away from
zero.

######  Lemma 3.4.

For any $j\geq 1$ given $L_{j}>0$, there exists $\tilde{p}>0$ (which depends
only on parameters of the process and on $k$) such that we have

${\mathbb{P}}((L_{j+1}-L_{j})\leq-1\mid{\cal
G}_{j})\geq{\mathbb{P}}({\mathcal{N}}_{j+1}=1\mid{\cal G}_{j})\geq\tilde{p}.$

###### Proof.

We prove it for $k=1$. The proof for general $k$ is similar. For
${\mathbf{u}}\in{\mathbb{Z}}^{2}$ we define the event

$\displaystyle 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\\}.$

Given $h^{\tau_{j}}({\mathbf{x}}_{1})={\mathbf{w}}_{j}$ and $L_{j}>0$, we
claim that

$\displaystyle(B({\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}+(0,1)))\subseteq\\{(L_{j+1}-L_{j})\leq-1\\}.$
(34)

We need to justify this event inclusion. 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)$. Further, occurrence of the event
$A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))$ ensures that ‘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})$ makes sure
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 ${\cal N}_{j+1}=1$. The recursion relation (33) justifies the event
inclusion as in (34) and hence, given
$(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})$
we have that

$\displaystyle{\mathbb{P}}\bigl{(}(L_{j+1}-L_{j})\leq-1\mid(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}$
$\displaystyle\geq{\mathbb{P}}\bigl{(}B({\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))\mid
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\cap\text{In}({\mathbf{w}}_{j})\bigr{)}$
$\displaystyle={\mathbb{P}}\bigl{(}B({\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))\cap\text{In}({\mathbf{w}}_{j})\cap
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}/{\mathbb{P}}\bigl{(}\text{In}({\mathbf{w}}_{j})\cap
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}$
$\displaystyle={\mathbb{P}}\bigl{(}B({\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))\cap
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}/{\mathbb{P}}\bigl{(}\text{In}({\mathbf{w}}_{j})\cap
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}$
$\displaystyle={\mathbb{P}}\bigl{(}B({\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))\bigr{)}\Bigl{(}{\mathbb{P}}(E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j}))/{\mathbb{P}}\bigl{(}\text{In}({\mathbf{w}}_{j})\cap
E({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}\Bigr{)}$
$\displaystyle\geq{\mathbb{P}}\bigl{(}B({\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))\bigr{)}.$

The penultimate equality follows from the observation that

$B({\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))\subseteq\text{In}({\mathbf{w}}_{j})$

and 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},\cdots,{\mathbf{w}}_{j})$. Further, the events
$B({\mathbf{w}}_{j})$ and $A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))$ depend on
disjoint collection of random vectors which makes them independent. Therefore,
using the translation invariance nature of our model we have that

$\displaystyle{\mathbb{P}}\bigl{(}(L_{j+1}-L_{j})\leq-1\mid(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{j})\bigr{)}$
$\displaystyle\geq{\mathbb{P}}\bigl{(}B({\mathbf{w}}_{j})\cap
A_{\text{sp}}({\mathbf{w}}_{j}+(0,1))\bigr{)}$
$\displaystyle={\mathbb{P}}(B({\mathbf{w}}_{j}){\mathbb{P}}(A_{\text{sp}}({\mathbf{w}}_{j}+(0,1)))$
$\displaystyle={\mathbb{P}}(B(\mathbf{0})){\mathbb{P}}(A_{\text{sp}}(\mathbf{0}))>0.$

In the last step we have used the fact that ${\mathbb{P}}(B(\mathbf{0}))>0$
which actually follows from a simple construction. This completes the proof. ∎

Next, we show that the family of random variables $\\{{\cal N}_{j}:j\geq 1\\}$
exhibits strong uniform exponentially decaying tail behaviour. It is important
to observe that the decay constants do not depend on the choice of starting
points ${\mathbf{x}}_{1},\cdots,{\mathbf{x}}_{k}$.

######  Lemma 3.5.

Fix any $j\geq 1$. For all large $n$ we have

$\displaystyle{\mathbb{P}}({\cal N}_{j}>n\mid{\cal G}_{j-1})\leq
C_{0}\exp{(-C_{1}n)},$

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

In order to prove Lemma 3.5 we need to introduce some notation. For
${\mathbf{w}}\in{\mathbb{Z}}^{2}$ we define the ‘total’ perturbation r.v. 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 r.v.
$T_{\mathbf{w}}$ decays exponentially. For ${\mathbf{w}}\in{\mathbb{Z}}^{2}$
and $m\in{\mathbb{Z}}$ we consider the infinite downward sequence of lattice
points starting from ${\mathbf{w}}+(m,0)$ given by
$\\{{\mathbf{w}}+(m,-l):l\in{\mathbb{N}}\cup\\{0\\}\\}$. A vertical
‘overshoot’ r.v., which represents amount of overshoot in the upper half-plane
$\mathbb{H}^{+}({\mathbf{w}}(2))$, based on the collection of total
perturbation r.v.’s
$\\{T_{{\mathbf{w}}+(m,-l)}:l\in{\mathbb{N}}\cup\\{0\\}\\}$ attached to this
infinite sequence of lattice points
$\\{{\mathbf{w}}+(m,-l):l\in{\mathbb{N}}\cup\\{0\\}\\}$ is defined by

$\displaystyle
T^{\uparrow}_{m}({\mathbf{w}}):=\sup\\{T_{{\mathbf{w}}+(m,-l)}-l:l\in{\mathbb{N}}\cup\\{0\\}\\}.$
(35)

It is not difficult to show that the r.v. $T^{\uparrow}_{m}({\mathbf{w}})$ is
non-negative. Moreover, we have

$\displaystyle{\mathbb{P}}(T^{\uparrow}_{m}({\mathbf{w}})>n)\leq\sum_{l=0}^{\infty}{\mathbb{P}}(T_{{\mathbf{w}}+(m,-l)}>n+l)\leq
C_{0}\exp{(-C_{1}n)},$ (36)

for some $C_{0},C_{1}>0$ which do not depend on ${\mathbf{w}}$ or $m$.

######  Remark 3.6.

In order to obtain (36) we only require uniform exponential tail for the
family $\\{T_{{\mathbf{w}}+(m,-l)}:l\in{\mathbb{N}}\cup\\{0\\}\\}$ as
mentioned in Definition 2.4. For ${\mathbf{w}}\in{\mathbb{Z}}^{2}$ and
$m\in{\mathbb{Z}}$ one can also consider left, rep., horizontal overshoot r.v.
as defined below

$\displaystyle T^{\rightarrow}_{m}({\mathbf{w}})$
$\displaystyle:=\sup\\{T_{{\mathbf{w}}+(-l,m)}-l:l\in{\mathbb{N}}\cup\\{0\\}\\}\text{
and }$ $\displaystyle T^{\leftarrow}_{m}({\mathbf{w}})$
$\displaystyle:=\sup\\{T_{{\mathbf{w}}+(l,m)}-l:l\in{\mathbb{N}}\cup\\{0\\}\\}.$

The same argument as in (36) gives us exponentially decaying tails for both
these r.v.’s, $T^{\leftarrow}_{m}({\mathbf{w}})$ and
$T^{\rightarrow}_{m}({\mathbf{w}})$. We will require these observations later.

Below we prove Lemma 3.5 for $j=1$ and later we will indicate the modification
required for general $j\geq 2$.

Proof of Lemma 3.5 for $j=1$: We prove it for $k=1$. The proof for general
$k\geq 1$ is exactly the same. Consider the following events:

$\displaystyle E^{1}_{n}$ $\displaystyle:=\\{\tau_{1}\leq n/2\\}\text{ and }$
$\displaystyle E^{2}_{n}$
$\displaystyle:=\\{|(h^{j+1}({\mathbf{x}}_{1})-h^{j}({\mathbf{x}}_{1}))(1)|\leq
n\text{ for all }0\leq j\leq n/2\\}.$

We obtain that

$\displaystyle{\mathbb{P}}(L_{1}\geq n)={\mathbb{P}}({\mathcal{N}}_{1}\geq
n)\leq{\mathbb{P}}({\mathcal{N}}_{1}\geq n,E^{1}_{n}\cap
E^{2}_{n})+{\mathbb{P}}((E^{1}_{n})^{c})+{\mathbb{P}}((E^{2}_{n})^{c}).$ (37)

Proposition 2.3 gives us that ${\mathbb{P}}((E^{1}_{n})^{c})$ goes to zero as
$n\to\infty$. Also we obtain:

$\displaystyle{\mathbb{P}}((E^{2}_{n})^{c})$
$\displaystyle\leq{\mathbb{P}}(\cup_{j=0}^{\lfloor
n/2\rfloor}|(h^{j+1}({\mathbf{x}}_{1})-h^{j}({\mathbf{x}}_{1}))(1)|>n)$
$\displaystyle\leq{\mathbb{P}}\bigl{(}\cup_{j=0}^{\lfloor
n/2\rfloor}(J_{\text{sp}}(h^{j}({\mathbf{x}}_{1}))>n)\bigr{)}$
$\displaystyle\leq(\lfloor
n/2\rfloor+1){\mathbb{P}}(J_{\text{sp}}(\mathbf{0})>n)$
$\displaystyle\leq(\lfloor n/2\rfloor+1)(1-p_{0})^{n}.$

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
projection of the starting point ${\mathbf{x}}_{1}$ on the line $y=-n$ denoted
as ${\mathbf{x}}^{n,\downarrow}_{1}={\mathbf{x}}_{1}+(0,-n)$. The notation
${\mathbf{x}}^{n,\uparrow}_{1}$ denotes the lattice point
${\mathbf{x}}_{1}+(0,\lfloor n/2\rfloor)$. The nesting property as mentioned
in Remark 2.2 ensures that on the event $E^{1}_{n}\cap E^{2}_{n}$ we have

$\nabla(h^{\tau_{1}}({\mathbf{x}}_{1}))\subseteq\nabla({\mathbf{x}}^{n,\downarrow}_{1}).$

For an illustration we refer the reader to Figure 4. Therefore, on the event
$E^{1}_{n}\cap E^{2}_{n}\cap\\{{\mathcal{N}}_{1}\geq n\\}$, the r.v.
${\mathcal{N}}_{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})$.

[plotpoints=2000,linecolor=blue]-99 x abs sqrt
[plotpoints=2000,linecolor=blue]-99 x abs sqrt
$n^{\alpha}$[plotpoints=2000,linecolor=blue]-99 x 3 sub abs sqrt 3 add
$\mathbf{x}_{1}$$\mathbf{x}^{n,\uparrow}_{1}$$\mathbf{x}^{n,\downarrow}_{1}$$h^{\tau_{1}}(\mathbf{x}_{1})$
Figure 4:  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 r.v.’s attached to
lattice points in the shaded region (which extends to the infinite lower half-
plane) dominates $L_{1}$ as well as the r.v. ${\mathcal{N}}_{1}$.

Therefore, on the event $E^{1}_{n}\cap E^{2}_{n}$ in order to have
${\mathcal{N}}_{1}>n$, we must have either

  * (i)

$T^{\uparrow}_{m}({\mathbf{x}}^{n,\uparrow}_{1})>n/2$ for some
$m\in[-4n^{2},4n^{2}]\cap{\mathbb{Z}}$ or

  * (ii)

$T^{\uparrow}_{m}({\mathbf{x}}^{n,\uparrow}_{1})>n/2+l$ for some $m$ in either
$[-(2n+l)^{2},-(2n+(l-1))^{2}]\cap{\mathbb{Z}}$ or in
$[(2n+(l-1))^{2},(2n+l)^{2}]\cap{\mathbb{Z}}$ for some $l\geq 1$.

Hence, using the translation invariance nature of our model and applying the
union bound we obtain

$\displaystyle{\mathbb{P}}({\mathcal{N}}_{1}>n)$ $\displaystyle\leq
2{\mathbb{P}}\Bigl{[}\bigl{(}\cup_{m=0}^{(2n)^{2}}T^{\uparrow}_{m}({\mathbf{x}}^{n,\uparrow}_{1})>n/2\bigr{)}\bigcup_{l\geq
1}\bigl{(}\bigcup_{m=(2n+l-1)^{2}+1}^{(2n+l)^{2}\rfloor}T^{\uparrow}_{m}({\mathbf{x}}^{n,\uparrow}_{1})>n/2+l\bigr{)}\Bigr{]}$
$\displaystyle\leq
2\Bigl{(}4n^{2}{\mathbb{P}}(T^{\uparrow}_{0}(\mathbf{0})>n/2)+\sum_{l=1}^{\infty}2(2n+l){\mathbb{P}}(T^{\uparrow}_{0}(\mathbf{0})>n/2+l)\Bigr{)}.$

Exponential tail decay of the overshoot r.v. $T^{\uparrow}_{0}(\mathbf{0})$ as
observed in (36) completes the proof. We emphasize the fact that the choice of
decay constants does not depend on ${\mathbf{x}}_{1}$. ∎

Before proving Lemma 3.5 for general $j\geq 1$ we recall that given ${\cal
G}_{j}$, distribution of the random vectors in the upper half-plane
$\\{\Gamma_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{+}(\tau_{j})\\}$ no longer
remain 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 the r.v.
$T_{m}({\mathbf{w}})$ .

######  Lemma 3.7.

Given
$(h^{\tau_{j}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{k}))=({\mathbf{w}}_{1},\cdots,{\mathbf{w}}_{k})$,
for any ${\mathbf{w}}\in\mathbb{H}^{+}({\mathbf{w}}_{1}(2))$, $\alpha>\beta>0$
and, for all $n\in{\mathbb{N}}$, there exist $C_{0},C_{1}>0$ uniformly, such
that we have the following:

  * (i)

${\mathbb{P}}(T_{\mathbf{w}}>n\mid{\cal G}_{j})\leq C_{0}\exp{(-C_{1}n)}$;

  * (ii)

${\mathbb{P}}(J_{\text{sp}}({\mathbf{w}})>n\mid{\cal G}_{j})\leq
C_{0}\exp{(-C_{1}n)}$;

  * (iii)

${\mathbb{P}}\Bigl{(}\max\bigl{\\{}T_{{\mathbf{w}}+(m,-l)}-l:0\leq
l\leq{\mathbf{w}}(2)-{\mathbf{w}}_{1}(2)\bigr{\\}}>n\mid{\cal
G}_{j}\Bigr{)}\leq C_{0}\exp{(-C_{1}n)}$ for all $m\in{\mathbb{Z}}$;

  * (iv)

${\mathbb{P}}\bigl{(}\max\\{|(h^{l}({\mathbf{w}}_{i})-{\mathbf{w}}_{i})(1)|:1\leq
l\leq n^{\beta},1\leq i\leq k\\}>n^{\alpha}\mid{\cal G}_{j}\bigr{)}\leq
C_{0}\exp{(-C_{1}n^{\alpha-\beta})}$.

###### Proof.

We prove Lemma 3.7 for $k=1$. The argument is same for general $k\geq 1$.
Given
$(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j})$
for any ${\mathbf{v}}\in\mathbb{H}^{+}({\mathbf{w}}_{1}^{j}(2))$ we obtain

$\displaystyle{\mathbb{P}}\bigl{(}T_{\mathbf{v}}>n\mid(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j})\bigr{)}$
$\displaystyle={\mathbb{P}}\bigl{(}(T_{\mathbf{v}}>n)\cap\text{In}({\mathbf{w}}_{1}^{j})\cap
E({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j}))/{\mathbb{P}}(\text{In}({\mathbf{w}}_{1}^{j})\cap
E({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j})\bigr{)}$
$\displaystyle\leq{\mathbb{P}}((T_{\mathbf{v}}>n)\cap
E({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j}))/{\mathbb{P}}(\text{In}({\mathbf{w}}_{1}^{j})\cap
E({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j}))$
$\displaystyle\leq{\mathbb{P}}(T_{\mathbf{v}}>n){\mathbb{P}}(E({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j}))/{\mathbb{P}}(A_{\text{sp}}({\mathbf{w}}_{1}^{j})\cap
E({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j}))$
$\displaystyle={\mathbb{P}}(T_{\mathbf{v}}>n)/{\mathbb{P}}(A_{\text{sp}}(\mathbf{0}))$
$\displaystyle\leq C_{0}\exp{(-C_{1}n)}.$

Clearly, the values of the positive constants $C_{0},C_{1}$ do not depend on
the point ${\mathbf{v}}$ or on
$({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j})$.

The argument for (ii) is exactly the same as that of (i) and hence, we skip
it.

For (iii) we first observe that given
$(h^{\tau_{1}}({\mathbf{x}}_{1}),\cdots,h^{\tau_{j}}({\mathbf{x}}_{1}))=({\mathbf{w}}^{1}_{1},\cdots,{\mathbf{w}}_{1}^{j})$,
the r.v. $\max\\{T_{{\mathbf{w}}+(m,-l)}-l:0\leq
l\leq{\mathbf{w}}(2)-{\mathbf{w}}_{1}^{j}(2)\\}$ is dominated by the overshoot
r.v. $\sup\\{T_{{\mathbf{w}}+(m,-l)}-l:l\geq 0\\}$. By (i) we have that the
family of r.v.’s $\\{T_{{\mathbf{w}}+(m,-l)}:0\leq
l\leq{\mathbf{w}}(2)-{\mathbf{w}}_{1}^{j}(2)\\}$ has uniform exponential tail
decay. Hence, the same argument for exponential tail decay of overshoot random
variable, as given in Remark 3.6, proves (iii).

The proof of (iv) follows from (ii) together with application of union bound.
∎

We now prove Lemma 3.5 for general $j\geq 2$.

Proof of Lemma 3.5 for $j\geq 2$: The proof for general $j\geq 2$ is very
similar to that of $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 r.v.’s. Given
${\cal G}_{j}$, though the collection
$\\{\Gamma_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{+}(\tau_{j})\\}$ is no
longer an i.i.d. collection of random vectors, Lemma 3.7 (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 ${\cal G}_{j}$, Item (ii) of Lemma 3.5 ensures uniform exponential
tail decay for the r.v. $J_{\text{sp}}({\mathbf{w}})$ for
${\mathbf{w}}\in\mathbb{H}^{+}(\tau_{j})$. On the other hand, Item (iv) of
Lemma 3.5 gives us that the probability of the corresponding version of the
event $(E^{2}_{n})^{c}$ exponentially decays to $0$ as $n\to\infty$. Finally,
the ‘Out’ event condition ensures that the family of previously explored
perturbation random vectors
$\\{\Lambda_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{-}(\tau_{j})\\}$ does not
contribute to the r.v. ${\mathcal{N}}_{j+1}$. Therefore, Item (iii) of Lemma
3.5 allows us to apply the same argument for general $j\geq 1$ and completes
the proof. ∎

We are now ready to prove Proposition 3.2.

####  3.1.2 Proof of Proposition 3.2

Proof of Proposition 3.2 is motivated from the proof of Lemma 2.6 of [RSS16A].
We recall the family of r.v.’s $\\{{\mathcal{N}}_{j}:j\geq 1\\}$ as in the
recursion relation (33). We observe that the strong uniform exponential tail
decay behaviour (see Definition 2.4) of this family, as shown in Lemma 3.5,
allows us to assume that there exists an i.i.d. family of non-negative integer
valued r.v.’s $\\{R_{j}:j\geq 1\\}$ with exponential tail decay such that for
all $j,m\geq 1$ we have

$\displaystyle{\mathbb{P}}({\mathcal{N}}_{j}\geq
m\mid{\mathcal{N}}_{j-1},\cdots,{\mathcal{N}}_{1})\leq{\mathbb{P}}(R_{j}\geq
m).$ (38)

Using such an i.i.d. family $\\{R_{j}:j\geq 1\\}$ we construct a non-negative
integer valued Markov chain $\\{M_{j}:j\geq 0\\}$ which stochastically
dominates the height function $\\{L_{j}:j\geq 0\\}$.

Set $M_{0}=0$ and for $j\geq 1$ define $M_{j}$ as
$M_{j}:=\max\\{M_{j-1},R_{j}\\}-1$. The i.i.d. nature of the collection
$\\{R_{j}:j\geq 1\\}$ ensure that the process $\\{M_{j}:j\geq 0\\}$ is a time
homogeneous Markov chain. Let $\tau^{M}:=\inf\\{j\geq 1:M_{j}=0\\}$ denote the
return time to state zero for this Markov chain. The recursion relation (33)
together with the stochastic domination as observed in the inequality (38)
ensure that $\tau^{M}$ stochastically dominates $\gamma$. Hence, in order to
prove Proposition 3.2 it is enough to show that there exist $C_{0},C_{1}>0$
such that

${\mathbb{P}}(\tau^{M}>n)\leq C_{0}\exp{(-C_{1}n)}.$

Lemma 3.4 ensures that we have

${\mathbb{P}}(M_{j+1}\leq M_{j}-1\mid M_{j}=m)\geq\tilde{p}\text{ for all
}m\geq 1.$

Therefore, it is not difficult to see that the Markov chain $M_{j}$ is
irreducible. It suffices to prove that, for some $\alpha>0$, we have
${\mathbb{E}}(\exp{(\alpha\tau M))}<\infty$.

Towards that using Proposition 5.5, Chapter 1 of Asmussen [A03], it suffices
to show that there exist a non-negative function
$f:{\mathbb{N}}\cup\\{0\\}\mapsto{\mathbb{R}}^{+}$, $n_{0}\in{\mathbb{N}}$ and
$r>1$ such that $f(j)>\nu$ for some $\nu>0$ and ${\mathbb{E}}[f(M_{1})\mid
M_{0}=j]<\infty$ for all $j\leq n_{0}$, while for $j>n_{0}$,
${\mathbb{E}}[f(M_{1})\mid M_{0}=j]\leq f(j)/r$.

Taking $f:\\{0,1,2,\cdots\\}\mapsto{\mathbb{R}}$ to be $f(i)=\exp{(\alpha
i)}$, where $\alpha>0$ is small enough so that ${\mathbb{E}}[\exp{(\alpha
R_{1})}]<\infty$ and $\exp{(-\alpha)}<1/r$, we have

$\displaystyle{\mathbb{E}}[\alpha(M_{j+1}-M_{j})\mid M_{j}=m]$
$\displaystyle=\exp{(-\alpha)}{\mathbb{P}}(R_{1}\leq m)+\exp{(-\alpha
m)}{\mathbb{E}}[\mathbf{1}_{\\{R_{j+1}>m\\}}\exp{(\alpha R_{j+1})}]$
$\displaystyle<(1/r)+\exp{(-\alpha
m)}{\mathbb{E}}[\mathbf{1}_{\\{R_{j+1}>m\\}}\exp{(\alpha R_{j+1})}]$
$\displaystyle\leq(1/r)\text{ for }m\text{ sufficiently large}.$

The last inequality follows because ${\mathbb{E}}[\exp(\alpha R_{1})]<\infty$
guarantees

$\exp{(-\alpha m)}{\mathbb{E}}[\mathbf{1}_{\\{R_{1}>m\\}}\exp{(\alpha
R_{1})}]\to 0\text{ as }m\to\infty.$

∎

##  4 Renewal properties for a single path

In this section, we consider $k=1$ and we explain renewal properties of the
marginal process $\\{h^{\sigma_{\ell}}({\mathbf{x}}_{1}):\ell\geq 0\\}$. More
precisely, we will 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

$\displaystyle\\{Y_{\ell+1}=Y_{\ell+1}({\mathbf{x}}_{1}):=h^{\sigma_{\ell+1}}({\mathbf{x}}_{1}):\ell\geq
0\\}.$ (39)

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 number of steps elapsed, i.e., the total time taken between
$\ell+1$-th and $\ell$-th renewal. Our next proposition explains the renewal
structure observed at these random steps.

######  Proposition 4.1.

The sequence $\\{(Y_{\ell+1}-Y_{\ell}):\ell\geq 1\\}$ gives a collection of
i.i.d. random vectors taking values in the space
${\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 emphasize 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 (see
Definition 2.4) for the family $\\{\sigma_{\ell}({\mathbf{x}}_{1}):\ell\geq
1\\}$.

Proposition 4.1 will be proved through a sequence of lemmas. We need to
introduce few notations first. In what follows, together with the usual Howard
step $h({\mathbf{u}})=h({\mathbf{u}},V)$ we will also consider
$h({\mathbf{u}},V^{+}_{{\mathbf{u}}(2)})$, i.e., the step taken considering
only the point set $V^{+}_{{\mathbf{u}}(2)}$. For simplicity of notation,
$h({\mathbf{u}},V^{+}_{{\mathbf{u}}(2)})$ will be simply denoted as
$h({\mathbf{u}},V^{+})$ and for any $j\geq 1$, the $j$-th step
$h^{j}({\mathbf{u}},V^{+}_{{\mathbf{u}}(2)})$ (taken considering only the
point set $V^{+}_{{\mathbf{u}}(2)}$) will also be denoted as
$h^{j}({\mathbf{u}},V^{+})$. In general this modified step
$h^{j}({\mathbf{u}},V^{+}_{{\mathbf{u}}(2)})$ need not be equal to the usual
$j$-th Howard step $h^{j}({\mathbf{u}},V)=h^{j}({\mathbf{u}})$. For
${\mathbf{u}}\in{\mathbb{Z}}^{2}$ we recall the definition of the event
$\text{Out}({\mathbf{u}})$ which ensures that points from the set
$V^{-}_{{\mathbf{u}}(2)}$ must be out of the parabolic region
$\nabla({\mathbf{u}})$.

On the event $\text{In}({\mathbf{u}})\cap\text{Out}({\mathbf{u}})$ we must
have

$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.$ (40)

This motivates us to define another event $\text{In}^{+}({\mathbf{u}})$
similar to the event $\text{In}({\mathbf{u}})$ involving the point set
$V^{+}_{{\mathbf{u}}(2)}$ only as

$\displaystyle\text{In}^{+}({\mathbf{u}}):=\\{h^{j}({\mathbf{u}},V^{+})\in\nabla({\mathbf{u}})\text{
for all }j\geq 1\\}.$ (41)

Observation (40) allows us to have the following equality of events:

$\text{In}({\mathbf{u}})\cap\text{Out}({\mathbf{u}})=\text{In}^{+}({\mathbf{u}})\cap\text{Out}({\mathbf{u}}).$
(42)

Similarly, the occurrence of the renewal event at the $n$-th 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 the representation is that the 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.

In order to have a better understanding of 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 of Corollary 2.13 gives us the
next Corollary.

######  Corollary 4.2.

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

$\displaystyle\bigcap_{l=1}^{j}\\{\sigma_{l}=m_{l},h^{m_{l}}({\mathbf{x}}_{1})={\mathbf{v}}_{l}\\}=$
$\displaystyle\Bigl{[}\bigcap_{l=1}^{j}\\{h^{m_{l}}({\mathbf{x}}_{1})={\mathbf{v}}_{l},\text{Out}({\mathbf{v}}_{l})\\}\cap\bigl{\\{}\cap_{n=m_{l-1}+1}^{m_{l}-1}(\gamma(h^{n}({\mathbf{x}}_{1}))\leq
m_{l}-n)$
$\displaystyle\cup(\text{Out}(h^{n}({\mathbf{x}}_{1})))^{c}\bigr{\\}}\bigcap(\cap_{l=1}^{j-1}\text{In}^{m_{(l+1)}-m_{l}})\Bigr{]}\bigcap\text{In}^{+}({\mathbf{v}}_{j}),$
(43)

and the event $\text{In}^{+}({\mathbf{v}}_{j})$ is independent of rest of the
other events in the r.h.s. of (4.2), all of which are ${\cal
F}_{{\mathbf{v}}_{j}(2)}={\cal F}_{m_{j}}$ measurable.

Corollary 4.2 allows us to obtain the following distributional equality:

$\displaystyle\\{\Lambda_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{+}({\mathbf{v}}_{\ell}(2))\\}\mid(h^{\sigma_{\ell}}({\mathbf{x}}_{1})={\mathbf{v}}_{\ell})$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\\{\Lambda_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{+}({\mathbf{v}}_{\ell}(2))\\}\mid\text{In}^{+}({\mathbf{v}}_{\ell})$
$\displaystyle\stackrel{{\scriptstyle
d}}{{=}}\\{\Lambda_{\mathbf{w}}:{\mathbf{w}}\in\mathbb{H}^{+}(0)\\}\mid\text{In}^{+}(\mathbf{0}).$
(44)

Equation 42 together with Corollary 4.2 give us the first equality. The last
equality follows from the translation invariance nature of our model. Equation
(4) allows us to obtain the next proposition which proves equality of
increment distributions between successive renewal steps for the marginal
process $\\{h^{j}({\mathbf{x}}_{1}):j\geq 1\\}$.

######  Proposition 4.3.

Fix any $\ell\geq 1$ and we have the following equality of distributions:

$\displaystyle\\{(h^{\sigma_{\ell}+m}({\mathbf{x}}_{1})-{\mathbf{v}}_{\ell}):m\geq
1\\}\mid(h^{\sigma_{\ell}}({\mathbf{x}}_{1})={\mathbf{v}}_{\ell})\stackrel{{\scriptstyle
d}}{{=}}\\{h^{m}(\mathbf{0},V^{+}):m\geq 1\\}\mid(\text{In}^{+}(\mathbf{0})).$

###### Proof.

For any $k\geq 1$, fix $n_{1},\cdots,n_{k}\geq 1$. Given that
$h^{\sigma_{\ell}}({\mathbf{x}}_{1})={\mathbf{v}}_{\ell}$, we consider joint
distribution of the random vector
$(h^{\sigma_{\ell}+n_{1}}({\mathbf{x}}_{1}),\cdots,h^{\sigma_{\ell}+n_{k}}({\mathbf{x}}_{1}))$.
Let ${\cal B}$ be an arbitrary Borel set in an appropriate space. It suffices
to show that

$\displaystyle{\mathbb{P}}\Bigl{(}\bigl{(}h^{\sigma_{\ell}+n_{1}}({\mathbf{x}}_{1})-{\mathbf{v}}_{\ell},\cdots,h^{\sigma_{\ell}+n_{k}}({\mathbf{x}}_{1})-{\mathbf{v}}_{\ell})\in{\cal
B}\mid(h^{\sigma_{\ell}}({\mathbf{x}}_{1})={\mathbf{v}}_{\ell})\Bigr{)}$
$\displaystyle={\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})\in{\cal
B}\mid\text{In}^{+}({\mathbf{v}}_{\ell})\bigr{)}$
$\displaystyle={\mathbb{P}}\bigl{(}\bigl{(}h^{n_{1}}(\mathbf{0},V^{+}),\cdots,h^{n_{k}}(\mathbf{0},V^{+}))\in{\cal
B}\mid\text{In}^{+}(\mathbf{0})\bigr{)}.$ (45)

The last equality follows from the translation invariance nature of our model.
For the first equality in (4), we observe that

$\displaystyle{\mathbb{P}}\Bigl{(}\bigl{(}h^{\sigma_{\ell}+n_{1}}({\mathbf{x}}_{1})-{\mathbf{v}}_{\ell},\cdots,h^{\sigma_{\ell}+n_{k}}({\mathbf{x}}_{1})-{\mathbf{v}}_{\ell}\bigr{)}\in{\cal
B}\mid(h^{\sigma_{\ell}}({\mathbf{x}}_{1})={\mathbf{v}}_{\ell})\Bigr{)}$
$\displaystyle={\mathbb{P}}\Bigl{(}\bigl{(}h^{n_{1}}({\mathbf{v}}_{\ell})-{\mathbf{v}}_{\ell},\cdots,h^{n_{k}}({\mathbf{v}}_{\ell})-{\mathbf{v}}_{\ell}\bigr{)}\in{\cal
B}\mid(h^{\sigma_{\ell}}({\mathbf{x}}_{1})={\mathbf{v}}_{\ell})\Bigr{)}$
$\displaystyle={\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{\cal
B}\mid(h^{\sigma_{\ell}}({\mathbf{x}}_{1})={\mathbf{v}}_{\ell})\Bigr{)}$
$\displaystyle={\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{\cal
B}\mid\text{In}^{+}({\mathbf{v}}_{\ell})\Bigr{)}.$

The last equality follows from (4). This completes the proof. ∎

We are now ready to prove Proposition 4.1.

Proof of Proposition 4.1 : Proposition 4.3 gives us that the distribution of
the increment random vector $(Y_{\ell+1}-Y_{\ell})$ for any $\ell\geq 1$ can
be reconstructed as follows. Consider an i.i.d. copy of $V$ as
$V^{\text{ind}}$. As $V^{+}_{0}$, the set $V^{\text{ind},+}_{0}$ is defined
similarly. Conditional to the event $\text{In}^{+}({\bf 0})$ w.r.t. the point
set $V^{\text{ind}}$, start a PH path from ${\bf 0}$ using the point set
$V^{\text{ind},+}_{0}$ only until occurrence of the next renewal event. Let
$\mathbf{Z}_{0}$ be the position of the above path at the next renewal step.
Then, Proposition 4.3 confirms that for any $\ell\geq 1$ we must have

$(Y_{\ell+1}-Y_{\ell})\stackrel{{\scriptstyle d}}{{=}}\mathbf{Z}_{0}.$ (46)

This proves that the increment random vectors are identically distributed.
Next we show that the increments are independent as well.

Recall that the random vector $Y_{\ell}=h^{\sigma_{\ell}}({\mathbf{x}}_{1})$
is ${\cal S}_{\ell}$ measurable where ${\cal S}_{\ell}$ is defined as in
$(\ref{def:S_Filtration})$. Fix $m\geq 1$ and Borel subsets
$B_{2},\dotsc,B_{m+1}$ of ${\mathbb{Z}}\times{\mathbb{N}}$. Let
$I_{\ell+1}(B_{\ell+1})$ be the indicator random variable of the event
$(Y_{\ell+1}-Y_{\ell})\in B_{\ell}$. Then, we have

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

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

By the earlier discussion, we have that the conditional distribution of
$Y_{m+1}-Y_{m}$ given ${\cal S}_{m}$ is given by $\mathbf{Z}_{0}$. Therefore,
we have

$\displaystyle{\mathbb{P}}((Y_{\ell+1}-Y_{\ell})\in B_{\ell+1}\text{ for
}\ell=1,\dotsc,m)$
$\displaystyle={\mathbb{E}}\Bigl{(}\prod_{\ell=1}^{m-1}I_{\ell+1}(B_{\ell+1}){\mathbb{E}}\bigl{(}I_{m+1}(B_{m+1})\mid{\cal
S}_{m}\bigl{)}\Bigr{)}$ $\displaystyle={\mathbb{P}}((\mathbf{Z}_{0}\in
B_{m+1}){\mathbb{E}}\Bigl{(}\prod_{\ell=1}^{m-1}I_{\ell+1}(B_{\ell+1})\Bigr{)}.$

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

The next lemma proves that the distribution of the increment random variable
$(Y_{2}(1)-Y_{1}(1))$ is symmetric about zero.

######  Lemma 4.4.

For all $m\in{\mathbb{N}}$, we have

${\mathbb{P}}(Y_{2}(1)-Y_{1}(1)=m)={\mathbb{P}}(Y_{2}(1)-Y_{1}(1)=-m).$

Given $h^{\sigma_{1}}({\mathbf{x}}_{1})={\mathbf{v}}_{1}$, proof of Lemma 4.4
follows from the observation that distribution of the point set
$V^{+}_{{\mathbf{v}}_{1}(2)}$ remains invariant with respect to reflection
about the line $x={\mathbf{v}}_{1}(1)$. Details of this argument is given in
the appendix section.

For any $\ell\geq 1$, the ‘In’ event condition at renewal step ensures that

$|Y_{\ell+1}(1)-Y_{\ell}(1)|\leq(Y_{\ell+1}(2)-Y_{\ell}(2))^{2}\text{ with
probability }1.$

Hence, Proposition 3.1 and Lemma 4.4 readily give us Corollary 4.5.

######  Corollary 4.5.

The increment r.v. $(Y_{2}(1)-Y_{1}(1))$ has moments of all orders and it’s
mean is zero.

##  5 Properties for the joint process at renewal steps

In this section we consider renewal steps for the joint process of PH 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
increment behaves like a mean zero random walk on an event with high
probability. This statement has been made precise in Proposition 5.1.

W.l.o.g. we assume that ${\mathbf{x}}_{1}(1)<{\mathbf{x}}_{2}(1)$. Non-
crossing property of PH paths 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

$Z_{\ell}=Z_{\ell}({\mathbf{x}}_{1},{\mathbf{x}}_{2}):=h^{\sigma_{\ell}}({\mathbf{x}}_{2})(1)-h^{\sigma_{\ell}}({\mathbf{x}}_{1})(1).$
(47)

Given ${\cal G}_{\ell}$, let us now focus on the case where $Z_{\ell}$ is
large, and we will show that there exists an event $F_{\ell}$ which occurs
with high probability such that on this event, the increment r.v.
$Z_{\ell+1}-Z_{\ell}$ is symmetric about zero. Details are given below in
Proposition 5.1 which obtains some additional properties of the increment
r.v.’s. This result will be crucially used to obtain the tail decay of the
coalescing time for PH paths. For details see 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 5.1.

Fix ${\mathbf{x}}_{1},{\mathbf{x}}_{2}\in{\mathbb{Z}}^{2}$ with
${\mathbf{x}}_{1}(1)<{\mathbf{x}}_{2}(1)$ and consider the joint process of
perturbed Howard paths starting from these two points till the $\ell$-th
(joint) renewal step. Given the $\sigma$-field ${\cal G}_{\ell}$, there exist
positive constants $M_{0},C_{0},C_{1},C_{2}$ and $C_{3}$ and an event
$F_{\ell}$ such that:

  * (i)

On the event $Z_{\ell}>M_{0}$ we have

${\mathbb{P}}(F^{c}_{\ell}\mid{\cal G}_{\ell})\leq C_{3}/(Z_{\ell})^{3}\text{
and }{\mathbb{E}}\big{[}(Z_{\ell+1}-Z_{\ell})\mathbf{1}_{F_{\ell}}\mid{\cal
G}_{\ell}\big{]}=0.$

  * (ii)

On the event $\\{Z_{\ell}\leq M_{0}\\}$ we have

${\mathbb{E}}\big{[}(Z_{\ell+1}-Z_{\ell})\mid{\cal G}_{\ell}\big{]}\leq
C_{0}.$

  * (iii)

For any $\ell\geq 0$ and $m>0$, there exists $c_{m}>0$ such that, on the event
$Z_{\ell}\leq m$,

${\mathbb{P}}\big{(}Z_{\ell+1}=0\mid{\cal G}_{\ell}\big{)}\geq c_{m}~{}.$

  * (iv)

On the event $Z_{\ell}>M_{0}$, we have

${\mathbb{E}}\bigl{[}(Z_{\ell+1}-Z_{\ell})^{2}\mid{\cal G}_{\ell}\bigr{]}\geq
C_{1}\;\text{ and }\;{\mathbb{E}}\bigl{[}|Z_{\ell+1}-Z_{\ell}|^{3}\mid{\cal
G}_{\ell}\bigr{]}\leq C_{2}~{}.$

###### Proof.

The required event $F_{\ell}$ will be defined as an intersection of several
other events. We first describe the heuristics. Consider two disjoint large
rectangles centred around the points $h^{\sigma_{\ell}}({\mathbf{x}}_{1})$ and
$h^{\sigma_{\ell}}({\mathbf{x}}_{2})$. Firstly we will define two events in
such a way so that their intersection ensures that the next (joint) renewal
happens inside these rectangles and till the next renewal step, both the paths
use perturbed open points from these two rectangles only. We then consider a
‘new’ set of perturbed open points where perturbed open points within the two
rectangular regions are interchanged and perturbed open points outside these
two regions remain unchanged. Since both the (original) paths use perturbed
open points from these two rectangles only till the next renewal step,
trajectories of the concerned paths constructed using ‘new’ (transformed)
point process gets interchanged till the next renewal step (w.r.t. the
original point process). We need to define additional events to ensure that
the transformed step actually gives the next (joint) renewal step w.r.t. the
transformed point process.

We need to introduce some notations. For simplicity of notations we first set

$l_{x}=\lfloor Z_{\ell}/40\rfloor\text{ and
}l_{y}=\lfloor\sqrt{Z_{\ell}/40}\rfloor.$

Given $h^{\sigma_{\ell}}({\mathbf{x}}_{i})={\mathbf{w}}_{i}$ for $i=1,2$, we
define the following three rectangular regions both centred at
${\mathbf{w}}_{i}$:

$\displaystyle{\cal R}^{1}_{i}$
$\displaystyle:={\mathbf{w}}_{i}\oplus[-l_{x},l_{x}]\times[0,l_{y}]\text{ and
}$ $\displaystyle{\cal R}^{2}_{i}$
$\displaystyle:={\mathbf{w}}_{i}\oplus[-9l_{x},9l_{x}]\times[0,3l_{y}]$
$\displaystyle.{\cal R}^{3}_{i}$
$\displaystyle:={\mathbf{w}}_{i}\oplus[-18l_{x},18l_{x}]\times[0,3l_{y}].$

Clearly, we have ${\cal R}^{1}_{i}\subseteq{\cal R}^{2}_{i}\subseteq{\cal
R}^{3}_{i}$ and the outer rectangles ${\cal R}^{3}_{1}$ and ${\cal 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

$\displaystyle h^{m}({\mathbf{w}}_{i})$
$\displaystyle=h^{m}({\mathbf{w}}_{i},V)\in{\cal R}^{1}_{i}\text{ for all
}1\leq m\leq l_{y}\text{ as well as }$ $\displaystyle h^{m}({\mathbf{w}}_{i})$
$\displaystyle=h^{m}({\mathbf{w}}_{i},V)\in{\cal R}^{2}_{i}\text{ for all
}1\leq m\leq 3l_{y}.$

The required event $F_{\ell}$ will be defined as intersection of several
events. For an illustration of the event $F_{\ell}$ we refer the reader to
Figure 5. Towards that we first define the following two events :

$\displaystyle F^{1}_{\ell}$
$\displaystyle:=\\{\sigma_{\ell+1}({\mathbf{x}}_{1},{\mathbf{x}}_{2})-\sigma_{\ell}({\mathbf{x}}_{1},{\mathbf{x}}_{2})\leq
l_{y}\\}\text{ and }$ $\displaystyle F^{2}_{\ell}$
$\displaystyle:=\\{\tilde{{\mathbf{w}}}\notin{\cal R}^{2}_{1}\cup{\cal
R}^{2}_{2}\text{ for all
}{\mathbf{w}}\in\mathbb{H}^{+}({\mathbf{w}}_{1}(2))\setminus(\cup_{i=1}^{2}{\cal
R}^{3}_{i})\\}.$

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 PH path starting
from ${\mathbf{w}}_{i}$ stays inside the innermost rectangle ${\cal
R}^{1}_{i}$ for $i=1,2$. Moreover, till the $l_{y}$-th step, which includes
the next renewal step, $i$-th PH path uses perturbed open vertices from the
outer rectangle ${\cal R}^{3}_{i}$ only.

[plotpoints=2000,linecolor=blue]-10.54 x 5 add abs sqrt
[plotpoints=2000,linecolor=blue]-10.50 x 5.5 add abs sqrt .75 add
[plotpoints=2000,linecolor=blue]-310.5 x 6 sub abs sqrt
[plotpoints=2000,linecolor=blue]19 x 6.5 sub abs sqrt .75 add
[plotpoints=2000,linecolor=blue, linestyle = dashed]-5.5-4.5 x 5 add abs sqrt
1.5 add [plotpoints=2000]-7.5-5.5 x 5 add abs sqrt 1.5 add
[plotpoints=2000]-4.5-2.5 x 5 add abs sqrt 1.5 add
[plotpoints=2000,linecolor=blue, linestyle = dashed]5.56.5 x 6 sub abs sqrt
1.5 add [plotpoints=2000]3.55.5 x 6 sub abs sqrt 1.5 add
[plotpoints=2000]6.58.5 x 6 sub abs sqrt 1.5 add
$h_{\sigma_{\ell}}(\mathbf{x}_{1})={\mathbf{w}}_{1}$${\cal R}^{2}_{1}$${\cal
R}^{3}_{1}$${\cal R}^{3}_{2}$${\cal
R}^{2}_{2}$$h_{\sigma_{\ell+1}}(\mathbf{x}_{1})$$h_{\sigma_{\ell}}(\mathbf{x}_{2})={\mathbf{w}}_{2}$$h_{\sigma_{\ell+1}}(\mathbf{x}_{2})$$y={\mathbf{w}}_{1}(2)+3l_{y}$
Figure 5: This figure represents occurrence of the $F_{\ell}$ event. Points
from the shaded (light as well as deep) region are not allowed to perturb to
the middle rectangles ${\cal R}^{2}_{1}$ and ${\cal R}^{2}_{2}$. Points from
the deeply shaded region are not allowed to perturb 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}))$ create 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 to cross 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 bigger rectangles
${\cal R}^{3}_{1}$ and ${\cal R}^{3}_{2}$ to obtain a new point process.
Consider the PH paths starting from ${\mathbf{w}}_{1}$ and ${\mathbf{w}}_{2}$
constructed using the resultant point process. We make it precise as follows.
For ${\mathbf{w}}\in{\mathbb{Z}}^{2}$ we define the transformation
$\overline{{\mathbf{w}}}$ as

$\displaystyle\overline{{\mathbf{w}}}:=\begin{cases}{\mathbf{w}}&\text{ if
}{\mathbf{w}}\notin{\cal R}^{3}_{1}\cup{\cal R}^{3}_{2}\\\
{\mathbf{w}}_{1}+(s,t)&\text{ if }{\mathbf{w}}\in{\cal R}^{3}_{2}\text{ with
}{\mathbf{w}}={\mathbf{w}}_{2}+(s,t)\\\ {\mathbf{w}}_{2}+(s,t)&\text{ if
}{\mathbf{w}}\in{\cal R}^{3}_{1}\text{ with
}{\mathbf{w}}={\mathbf{w}}_{1}+(s,t).\end{cases}$

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

$V^{\prime}:=\\{{\mathbf{w}}+(X_{\overline{{\mathbf{w}}}},Y_{\overline{{\mathbf{w}}}}):{\mathbf{w}}\in{\mathbb{Z}}^{2},B_{\overline{{\mathbf{w}}}}=1\\}.$

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 evolution w.r.t. to the transformed point set
$V^{\prime}$ (where only the perturbed open vertices from the outer rectangles
are interchanged), for all $1\leq m\leq l_{y}$ we have

$\displaystyle h^{m}({\mathbf{w}}_{1},V^{\prime})$
$\displaystyle={\mathbf{w}}_{1}+(h^{m}({\mathbf{w}}_{2},V)-{\mathbf{w}}_{2})\in\nabla({\mathbf{w}}_{1})\cap{\cal
R}^{1}_{1}\text{ and }$ $\displaystyle h^{m}({\mathbf{w}}_{2},V^{\prime})$
$\displaystyle={\mathbf{w}}_{2}+(h^{m}({\mathbf{w}}_{1},V)-{\mathbf{w}}_{1})\in\nabla({\mathbf{w}}_{2})\cap{\cal
R}^{1}_{2}.$ (48)

Equation (5) further ensures that on the event $F^{1}_{\ell}\cap F^{2}_{\ell}$
we have

$\displaystyle\Bigl{[}\sum_{i=1}^{2}\bigl{(}h^{m}({\mathbf{w}}_{i},V^{\prime})-{\mathbf{w}}_{i}\bigr{)}(1)\Bigr{]}=-\Bigl{[}\sum_{i=1}^{2}\bigl{(}h^{m}({\mathbf{w}}_{i},V)-{\mathbf{w}}_{i}\bigr{)}(1)\Bigr{]},$
(49)

for all $1\leq m\leq l_{y}$. Ideally, Equation (49) should have given us

${\mathbb{E}}\bigl{[}(Z_{\ell+1}-Z_{\ell})\mathbf{1}_{F^{1}_{\ell}\cap
F^{2}_{\ell}}\mid{\cal G}_{\ell}\bigr{]}=0.$

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 w.r.t. the point
process $V$, the corresponding step w.r.t. $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 w.r.t. 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 w.r.t. $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

$\displaystyle F^{3}_{\ell}:=\\{$
$\displaystyle\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}]$
$\displaystyle\text{ and }{\mathbf{w}}\notin{\cal R}^{3}_{1}\cup{\cal
R}^{3}_{2}\\}.$

In Figure 5 the event $F^{3}_{\ell}$ means that the open points from the gray
shaded (light or deep) region are not allowed to perturb to the middle
rectangular boxes ${\cal R}^{2}_{1}$ and ${\cal R}^{2}_{2}$. The nesting
property (as mentioned in Remark 2.2) together with (5) ensure that on the
event $F^{1}_{\ell}\cap F^{2}_{\ell}$ we have (refer to Figure 5)

$\nabla(h^{m_{0}}({\mathbf{w}}_{i},V^{\prime}))\subset\nabla_{i}\text{ for
}i=1,2.$

Hence, we observe that the ‘Out’ event condition is automatically satisfied
for $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 $({\cal R}^{3}_{1}\cup{\cal
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({\cal
R}^{3}_{1}\cup{\cal R}^{3}_{2})$ (shown as a gray region in Figure 5) which
contains all lattice points in the set
$[\mathbb{H}^{-}(m_{0})\setminus\mathbb{H}^{-}({\mathbf{w}}_{1}(2))]\setminus({\cal
R}^{3}_{1}\cup{\cal R}^{3}_{2})$. This ensures that on the event
$\cap_{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}))$
w.r.t. the point set $V^{\prime}$.

To complete the proof, we need to ensure that the occurrence of the ‘In’ event
w.r.t. $V^{\prime}$ at
$(h^{m_{0}}({\mathbf{w}}_{1},V^{\prime}),h^{m_{0}}({\mathbf{w}}_{2},V^{\prime}))$.
It is important to observe that the event $\cap_{i=1}^{3}F^{i}_{\ell}$ ensures
occurrence of the ‘In’ event at $h^{m_{0}}({\mathbf{w}}_{i},V^{\prime})$
w.r.t. $V^{\prime}$ till the time the concerned PH paths cross the line
$y={\mathbf{w}}_{1}(2)+3l_{y}$. We note that on the event $F^{1}_{\ell}\cap
F^{2}_{\ell}$ we have

$\displaystyle\nabla\bigl{(}{\mathbf{w}}_{i}+(0,2l_{y})\bigr{)}\subseteq\nabla\bigl{(}h^{m_{0}}({\mathbf{w}}_{i},V^{\prime})\bigr{)}\text{
for all }i=1,2.$ (50)

We recall the definition of the event
$A_{\text{sp}}=A_{\text{sp}}(\mathbf{0})$ as in (21) and for
$l\in{\mathbb{N}}$ we define

$\displaystyle
A_{\text{sp}}^{(l)}(\mathbf{0}):=\bigcap_{m=l}^{\infty}\\{I^{R}_{m}\cap
V^{\text{sp}}\neq\emptyset\\}\cap\\{I^{L}_{m}\cap
V^{\text{sp}}\neq\emptyset\\}.$

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,
(50) motivates us to construct our last two events $F^{4}_{\ell}$ and
$F^{5}_{\ell}$ respectively as

$\displaystyle F^{4}_{\ell}$
$\displaystyle:=\cap_{i=1}^{2}A_{\text{sp}}^{(l_{y})}\bigl{(}{\mathbf{w}}_{i}+(0,2l_{y})\bigr{)}\text{
and }$ $\displaystyle F^{5}_{\ell}$
$\displaystyle:=\cap_{i=1}^{2}\\{h^{3l_{y}}({\mathbf{w}}_{i})(1)-{\mathbf{w}}_{i}(1)\in[-l_{x},l_{x}]\\}.$

We observe that on the event $\cap_{i=1}^{5}F^{i}_{\ell}$, at the $3l_{y}$-th
step the $V^{\prime}$ driven PH paths don’t 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)$. As we
have
$h^{3l_{y}}({\mathbf{w}}_{i},V^{\prime})\in\nabla({\mathbf{w}}_{i}+(0,2l_{y}))$,
the truncated shield created by the event $F^{4}_{\ell}$ ensures 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 (50) makes sure that on the event $\cap_{i=1}^{5}F^{i}_{\ell}$,
the ‘In’ event occurs at points $h^{m_{0}}({\mathbf{w}}_{1},V^{\prime})$ and
$h^{m_{0}}({\mathbf{w}}_{2},V^{\prime})$ w.r.t. $V^{\prime}$ as well. We refer
to Figure 5 for an illustration of the event $F_{\ell}$ defined as

$F_{\ell}:=\cap_{i=1}^{5}F^{i}_{\ell}$ (51)

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 5.2 shows that the probability
of $(F_{\ell})^{c}$ satisfies the required tail bound and thereby completes
the proof of item $(i)$.

Item $(ii)$ in Proposition 5.1 follows readily from the fact that

$\displaystyle{\mathbb{E}}[(Z_{\ell+1}-Z_{\ell})\mid{\cal G}_{\ell}]$
$\displaystyle\leq{\mathbb{E}}[\sum_{i=1}^{2}|(h^{\sigma_{\ell+1}}({\mathbf{x}}_{i})-h^{\sigma_{\ell}}({\mathbf{x}}_{i}))(1)|\mid{\cal
G}_{\ell}]$
$\displaystyle={\mathbb{E}}[|(h^{\sigma_{\ell+1}}({\mathbf{x}}_{1})-h^{\sigma_{\ell}}({\mathbf{x}}_{1}))(1)|\mid{\cal
G}_{\ell}]+{\mathbb{E}}[|(h^{\sigma_{\ell+1}}({\mathbf{x}}_{2})-h^{\sigma_{\ell}}({\mathbf{x}}_{2}))(1)|\mid{\cal
G}_{\ell}]$ $\displaystyle\leq
2{\mathbb{E}}((\sigma_{\ell+1}-\sigma_{\ell})^{2}\mid{\cal G}_{\ell})<\infty.$

Finiteness of the expectation follows from Proposition 3.1 and the penultimate
inequality follows from the ‘In’ event condition at the renewal step.

For Item $(iii)$, it is not difficult to convince oneself that the conditional
probability ${\mathbb{P}}(Z_{\ell+1}=0\mid{\cal G}_{\ell})$ is strictly
positive (suitable configurations are easy to build).

It then remains to check Item $(iv)$. We observe that

$\displaystyle{\mathbb{E}}\bigr{[}(Z_{\ell+1}-Z_{\ell})^{2}\mid{\cal
G}_{\ell}\bigl{]}={\mathbb{E}}\bigr{[}(Z_{\ell+1}-Z_{\ell})^{2}\mathbf{1}_{\\{|Z_{\ell+1}-Z_{\ell}|^{2}\geq
1\\}}\mid{\cal G}_{\ell}\bigl{]}\geq{\mathbb{P}}((Z_{\ell+1}-Z_{\ell})^{2}\geq
1\mid{\cal G}_{\ell})~{}.$

Again on the event $\\{Z_{\ell}>M_{0}\\}$, a simple construction gives us that
the probability ${\mathbb{P}}((Z_{\ell+1}-Z_{\ell})^{2}\geq 1\mid{\cal
G}_{\ell})$ is strictly positive. For the third moment, we have an uniform
bound

$\displaystyle{\mathbb{E}}[(Z_{\ell+1}-Z_{\ell})^{3}\mid{\cal G}_{\ell}]\leq
8{\mathbb{E}}[(\sigma_{\ell+1}-\sigma_{\ell})^{6}\mid{\cal G}_{\ell}]\leq
8C^{\prime},$

by Proposition 3.1. ∎

The next lemma shows that as for large $Z_{\ell}$, the event $F_{\ell}$ has
required tail decay.

######  Lemma 5.2.

Consider the event $F_{\ell}$ defined as in (51). Then for all large
$Z_{\ell}$ there exists $C^{\prime}>0$, which does not depend on $Z_{\ell}$,
such that we have ${\mathbb{P}}(F^{c}_{\ell}\mid{\cal G}_{\ell})\leq
C^{\prime}/(Z_{\ell})^{3}$.

###### Proof.

It suffices to show that for all $1\leq i\leq 5$ we have

${\mathbb{P}}((F^{i}_{\ell})^{c}\mid{\cal G}_{\ell})\leq
C_{0}/(Z_{\ell})^{3},$

for some $C_{0}>0$. In this paper we proved similar arguments multiple times
and we present only a sketch here. The required bound for
${\mathbb{P}}((F^{1}_{\ell})^{c}\mid{\cal G}_{\ell})$ follows from Proposition
3.1. Regarding the probability ${\mathbb{P}}((F^{2}_{\ell})^{c}\mid{\cal
G}_{\ell})$ we observe that there are $3l_{y}$ many horizontal lines of
lattice points and the event $(F^{1}_{\ell})^{c}$ may occur due to large
amount of $x$ coordinate perturbation from one of the vertices on these
horizontal lines only. We recall the horizontal right overshoot r.v. and
horizontal left overshoot r.v. as defined in Remark 3.6. Given the
$\sigma$-field ${\cal G}_{\ell}$, the same argument as in Lemma 3.7 gives
exponential tail decay for these horizontal overshoot r.v.’s. This allows us
to obtain the required tail decay estimate for
${\mathbb{P}}((F^{2}_{\ell})^{c}\mid{\cal G}_{\ell})$.

Considering the event $F^{3}_{\ell}$, we observe that outside the boxes ${\cal
R}^{1}_{1}$ and ${\cal R}^{1}_{2}$, boundaries of the parabolic regions,
$\nabla_{1}$ and $\nabla_{2}$, both are at least at a height of $2l_{y}$ from
the line $x=l_{y}$. Hence, similar argument as in Lemma 3.5 gives us the
required estimate. Regarding the event $F^{4}_{\ell}$, we need to bound the
probability of complement of truncated version of the event
$A_{\text{sp}}(\cdot)$. We observe that for any $i=1,2$ we have

$\displaystyle{\mathbb{P}}(A_{\text{sp}}^{l_{y}}({\mathbf{w}}_{i}+(0,2l_{y}))^{c}\mid{\cal
G}_{\ell})$
$\displaystyle={\mathbb{P}}(A_{\text{sp}}^{l_{y}}({\mathbf{w}}_{i}+(0,2l_{y}))^{c}\mid\text{In}^{+}({\mathbf{w}}_{1})\cap\text{In}^{+}({\mathbf{w}}_{2}))$
$\displaystyle={\mathbb{P}}(A_{\text{sp}}^{l_{y}}({\mathbf{w}}_{i}+(0,2l_{y}))^{c}\cap\text{In}^{+}({\mathbf{w}}_{1})\cap\text{In}^{+}({\mathbf{w}}_{2}))/{\mathbb{P}}(\text{In}^{+}({\mathbf{w}}_{1})\cap\text{In}^{+}({\mathbf{w}}_{2}))$
$\displaystyle\leq{\mathbb{P}}(A_{\text{sp}}^{l_{y}}({\mathbf{w}}_{i}+(0,2l_{y}))^{c})/{\mathbb{P}}(\text{In}^{+}({\mathbf{w}}_{1})\cap\text{In}^{+}({\mathbf{w}}_{2}))$
$\displaystyle\leq{\mathbb{P}}(A_{\text{sp}}^{l_{y}}({\mathbf{w}}_{i}+(0,2l_{y}))^{c})/{\mathbb{P}}\bigl{(}A^{\text{sp}}({\mathbf{w}}_{1})\cap
A^{\text{sp}}({\mathbf{w}}_{2})\bigr{)}$
$\displaystyle\leq{\mathbb{P}}(A_{\text{sp}}^{l_{y}}({\mathbf{w}}_{i}+(0,2l_{y}))^{c})/{\mathbb{P}}\bigl{(}A^{\text{sp}}(\mathbf{0})\bigr{)}^{2}$
$\displaystyle=C_{0}{\mathbb{P}}(A_{\text{sp}}^{l_{y}}({\mathbf{w}}_{i}+(0,2l_{y}))^{c})$
(52)

The first equality in (5) 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))\\}$.
In order 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^{R}_{m}({\mathbf{w}}_{i}+(0,2l_{y}))$ or
$I^{R}_{m}({\mathbf{w}}_{i}+(0,2l_{y}))$ for some $m>l_{y}$ which does not
contain any special vertices. Therefore, from (5) we obtain that

${\mathbb{P}}(A_{\text{sp}}^{l_{y}}({\mathbf{w}}_{i}+(0,2l_{y}))^{c}\mid{\cal
G}_{\ell})\leq C^{\prime}_{0}\exp{(-C^{\prime}_{1}l_{y})},$

for some $C^{\prime}_{0},C^{\prime}_{1}>0$. This gives us the required tail
estimate for ${\mathbb{P}}((F^{4}_{\ell})^{c})$.

Finally, Item (iv) of Lemma 3.7 ensures that
${\mathbb{P}}((F^{5}_{\ell})^{c})$ decays sub-exponentially in $Z_{\ell}$ and
thereby completes the proof of Lemma 5.2. ∎

######  Remark 5.3.

Proposition 3.1 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\\}$ gives a collection of non-negative integer valued random variables with
strong uniform exponential decay (see Definition 2.4) such that the decay
constants do not depend on the choice of the starting points
${\mathbf{x}}_{1},{\mathbf{x}}_{2}$.

##  6 Tail distribution for the coalescence time of two PH paths and the proof
of Theorem 1.1

In this section we start with two points ${\mathbf{x}}_{1},{\mathbf{x}}_{2}$
in ${\mathbb{Z}}^{2}$ such that ${\mathbf{x}}_{1}(1)<{\mathbf{x}}_{2}(1)$ and
${\mathbf{x}}_{1}(2)={\mathbf{x}}_{2}(2)=0$. A key result for proving the
convergence of the PH network to the BW, lies in a precise estimate for the
tail distribution of the coalescence time of two PH paths:

$T({\mathbf{x}}_{1},{\mathbf{x}}_{2}):=\inf\\{t\geq
0:\pi^{{\mathbf{x}}_{1}}(t)=\pi^{{\mathbf{x}}_{2}}(t)\\}$ (53)

where $\pi^{{\mathbf{x}}_{i}}=(\pi^{{\mathbf{x}}_{i}}(t))_{t\geq 0}$ denotes
the parametrization of the path $\pi^{{\mathbf{x}}_{i}}$. In this section we
prove the following theorem on tail decay of coalescing time
$T({\mathbf{x}}_{1},{\mathbf{x}}_{2})$ of two perturbed Howard paths
$\pi^{{\mathbf{x}}_{1}}$ and $\pi^{{\mathbf{x}}_{2}}$.

######  Theorem 6.1.

For the above mentioned choice of ${\mathbf{x}}_{1},{\mathbf{x}}_{2}$, there
exists a constant $C_{0}>0$ which does not depend on
${\mathbf{x}}_{1},{\mathbf{x}}_{2}$ such that, for any $t>0$,

${\mathbb{P}}(T({\mathbf{x}}_{1},{\mathbf{x}}_{2})>t)\leq\frac{C_{0}({\mathbf{x}}_{2}(1)-{\mathbf{x}}_{1}(1))}{\sqrt{t}}.$

In order to prove Theorem 6.1 we follow a robust technique developed by
Coupier et. al. in [CSST20]. This technique is applicable for a general class
of processes which need not be Markov but behave like mean zero random walks
away from origin and satisfy certain moment bounds (see Corollary 6.2).
Proposition 5.1 ensures that the difference between two PH paths observed at
renewal steps satisfy these properties and allows us to apply this technique
to get a suitable tail decay in terms of number of (joint) renewal steps. With
some additional work, we obtain the tail estimate for coalescing time in terms
of total number of steps.

For completeness we first quote the following corollary taken from [CSST20]
regarding tail decay of the coalescing time for a suitable class of processes.

######  Corollary 6.2 (Corollary 5.6 of [CSST20]).

Let $\\{Y_{t}:t\geq 0\\}$ be a $\\{{\cal G}_{t}:t\geq 0\\}$ adapted stochastic
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},C_{3}$ such that:

  * (i)

There exists an event $F_{t}$ such that, on the event $\\{Y_{t}>M_{0}\\}$, we
have ${\mathbb{P}}(F^{c}_{t}\mid{\cal G}_{t})\leq C_{0}/Y^{3}_{t}$ and

${\mathbb{E}}\big{[}(Y_{t+1}-Y_{t})\mathbf{1}_{F_{t}}\mid{\cal
G}_{t}\big{]}=0~{}.$

  * (ii)

For any $t\geq 0$, on the event $\\{Y_{t}\leq M_{0}\\}$,

${\mathbb{E}}\big{[}(Y_{t+1}-Y_{t})\mid{\cal G}_{t}\big{]}\leq C_{1}~{}.$

  * (iii)

For any $t\geq 0$ and $m>0$, there exists $c_{m}>0$ such that, on the event
$\\{Y_{t}\in(0,m]\\}$,

${\mathbb{P}}\big{(}Y_{t+1}=0\mid{\cal G}_{t}\big{)}\geq c_{m}~{}.$

  * (iv)

For any $t\geq 0$, on the event $\\{Y_{t}>M_{0}\\}$, we have

${\mathbb{E}}\bigl{[}(Y_{t+1}-Y_{t})^{2}\mid{\cal G}_{t}\bigr{]}\geq
C_{2}\;\text{ and }\;{\mathbb{E}}\bigl{[}|Y_{t+1}-Y_{t}|^{3}\mid{\cal
G}_{t}\bigr{]}\leq C_{3}~{}.$