{'fraction_non_alphanumeric': 0.06250860525953462, 'fraction_numerical': 0.017010251210994705, 'mean_word_length': 3.5311932849364793, 'pattern_counts': {'":': 0, '<': 19, '<?xml version=': 0, '>': 27, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 53, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Transmission and navigation on disordered lattice networks, directed spanning forests and scaling limits

Stochastic networks based on random point sets as nodes have attracted considerable interest in many applications, particularly in communication networks, including wireless sensor networks, peer-to-peer networks and so on. The study of such networks generally requires the nodes to be independently and uniformly distributed as a Poisson point process. In this work, we venture beyond this standard paradigm and investigate the stochastic geometry of networks obtained from \textit{directed spanning forests} (DSF) based on randomly perturbed lattices, which have desirable statistical properties as a models of spatially dependent point fields. In the regime of low disorder, we show in 2D and 3D that the DSF almost surely consists of a single tree. In 2D, we further establish that the DSF, as a collection of paths, converges under diffusive scaling to the Brownian web.


Introduction and main results
Spatial networks 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, to name a few. In the mathematical study of such networks, an important modelling hypothesis is the random distribution of their nodes. This often serves to capture the macroscopic properties of highly complex networks, in addition to facilitating theoretical analysis. For a partial overview of the literature, we refer the reader to [BB09], [BB10], [B11], [P03] and the references therein.
In the context of communication networks, the study of particular structures like radial spanning trees and directed spanning forests have gained considerable attention (see, e.g., [BB07], [B08], [BKR99], [EGHK99], and the references contained therein). These structures often represent broadly related concepts, and in fact, DSFs can be seen as the limit of radial spanning trees far away from the origin. Such structures help in the study of localized co-ordination protocols in networks which are also aimed to be scalable with network size. These have applications to a wide variety of problems, including small world phenomena, computational geometry, decentralised navigation in networks, to mention a few (for details, we refer the interested reader to [K00], [KSU99], [PRR99], and the references therein). In summary, network structures such as the DSF are important theoretical models to study fundamental questions of transmission and navigation on real-world networks.
Generally speaking, the distribution of the random nodes in stochastic networks is taken to be the independent and uniform over space, in other words, the Poisson distribution and its variants (see, e.g., [MR96], [P03]). The Poisson model is highly amenable to rigorous mathematical treatment, but is often limited in its effectiveness as a model -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 ground realities (see, e.g., [GL17]). However, little is understood about the stochastic geometry of networks arising from such strongly correlated point processes, principally because the tools and techniques for studying the Poisson model overwhelmingly rely on its exact spatial independence.
In this work, we examine spatial network models, specifically directed spanning forests, on random point sets that are obtained as disordered lattices on Euclidean spaces. Such point processes exhibit much greater measure of spatial homogeneity compared to the Poisson process on one hand, while still retaining a measure of analytical tractability on the other. A powerful manifestation of their relative orderliness is the fact that they are hyperuniform. Hyperuniformity of point processes have attracted a lot of interest in recent years, especially in the statistical physics literature (see, e.g., [T02], [TS03], [GL17] 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 consider a disordered, or perturbed, version of the d dimensional Euclidean lattice Z d . Set δ > 0 and consider the d-dimensional δ box centered at the origin given by S δ := [−δ, δ] d . Let {U x : x ∈ Z d } denote a collection of i.i.d. random variables (r.v.) such that each r.v. is uniformly distributed over the region S δ . For a lattice vertex u := (u(1), u(2), . . . , u(d)) ∈ Z d , the corresponding perturbed point is denoted by u := u+U u . This gives a set V := {u : u ∈ Z d } of (randomly) perturbed lattice points .
Here and henceforth, the quantity ||x|| p for p ≥ 1 denotes the l p norm of x in R d . For x ∈ R d , the notation h(x) denotes the closest perturbed lattice point in V with respect to the || || 1 distance with strictly higher d-th coordinate. Formally h(x) := argmin{||y − x|| 1 : y ∈ V, y(d) > x(d)}. (1) Clearly, for any x ∈ R d , the point h(x) is uniquely defined almost surely (a.s.). We call the point h(x) as the next step starting from the point x. For x ∈ V , the edge joining x and h(x) is denoted by x, h(x) and E := { x, h(x) : x ∈ V } denotes the set of all edges. The directed spanning forest (DSF) on V with direction e d is the random graph G := (V, E) consisting of the vertex set V and the edge set E := { x, h(x) : x ∈ V }. By construction, each vertex x has exactly one outgoing edge, viz., x, h(x) and hence the random graph G does not have a loop or cycle a.s. In this paper, we study the random graph G := (V, E), which we will refer to as the perturbed DSF. We will study it only for dimensions 2 and 3 and for small regime of perturbation, i.e., for small values of δ. More specifically we chose 0 < δ < 1/8. For u ∈ Z d , the δ-box centered at u is denoted by S δ (u) := u + S δ . Note that, the choice of δ ensures that S δ (u) ∩ S δ (v) = ∅ for all u, v ∈ Z d with u = v. Here is our first main result which shows that the random graph G is connected a.s. Theorem 1.1. For d = 2 and d = 3 the random graph G is connected and consists of a single tree a.s.
The study of the directed spanning forest (DSF) on the Poisson point processes was initiated in [BB07]. The intricate dependencies caused by the construction of edges based on Euclidean distances, makes this model hard to study. In fact, the question regarding the connectivity of the DSF on Poisson point processes posed by Baccelli and Bordenave remained open for quite some time and finally, Coupier and Tran [CT11] proved that for d = 2 the DSF is a tree almost surely. Their argument is based on a Burton-Keane type argument and crucially depends on the planarity structure of R 2 and can not be applied for higher dimensions.
There are other random directed graphs studied in the literature for which the dichotomy in dimensions of having a single connected tree vis-a-vis a forest has been studied (see [FLT04], [GRS04], [ARS08]). However, the mechanisms used for construction of edges for all these models mentioned above incorporate much more independence than that is available for the DSF. For these models it has been proved that the random graph is a connected tree in dimensions 2 and 3, and a forest with infinitely many tree components in dimensions 4 and more. It is important to observe that for all the above mentioned models, the vertices are independently distributed over disjoint regions -at small as well as large mutual separations -and this property was crucially used in the analysis of these models. On the other hand, for the disordered lattice models this property no longer holds true in general, even in the regime of low disorder, and we require new stochastic geometric techniques to overcome the difficulties posed by the long-ranged dependencies arising therefrom. It is useful to mention here that though the perturbed DSF is constructed based on || || 1 distance only, because of small regime of perturbations, similar argument holds for || || p for any p ≥ 1.
Our next main result is that for d = 2 the random graph G observed as a collection of paths, converges to the Brownian web under a suitable diffusive scaling. The standard Brownian web originated in the work of Arratia [A79], [A81] as the scaling limit of the voter model on Z. It arises naturally as the diffusive scaling limit of the coalescing simple random walk paths starting from every point on the oriented lattice Z 2 even := {(m, n) : m + n even}. Intuitively, the Brownian web can be thought of as a collection of onedimensional coalescing Brownian motions starting from every point in the space time plane R 2 . Later Fontes et. al. [FINR04] provided a framework in which the Brownian web is realized as a random variable taking values in a Polish space. We recall relevant details from [FINR04].
Ferrari et. al. [FFW05] showed that, for d = 2, the random graph on the Poisson points introduced by [FLT04], converges to the Brownian web under a suitable diffusive scaling. Coletti et. al. [CFD09] has a similar result for the discrete random graph studied in [GRS04]. In [BB07] it has been shown that scaled paths of the successive ancestors in the DSF converges weakly to the Brownian motion and also conjectured that the scaling limit of the DSF on the Poisson points is the Brownian web. This conjecture remained open for long time and very recently it has been proved in [CSST19]. The scaling limit of the collection of all paths is much harder question as one has to deal with the dependencies between different paths also. In this paper we show that the perturbed DSF, which is created on a dependent random environment due to the perturbed lattice points, belongs to the basin of attraction of the Brownian web as well. In Section 5 we prove a stronger result in the sense that we define a dual for the perturbed DSF and show that, under diffusive scaling the perturbed DSF and it's dual jointly converge in distribution to the Brownian web and its dual. This joint convergence further allows us to show that for d = 2, there is no bi-infinite path in the perturbed DSF a.s.
The paper is organized in the following way. In Section 2, a discrete time joint exploration process is introduced to describe the joint evolution of the DSF paths and we show that there are random steps such that the joint exploration process exhibits Markov properties at these random steps. In Section 3 we consider some subset of the earlier random steps, called renewal steps and show that at these renewal steps, the joint exploration process can be restarted in some sense. For multiple paths, the restarted paths may not coincide with the original paths, but the restarted process allows us to construct a well behaved process which behaves like a symmetric random walk away from the origin. Using this in Section 4, we prove Theorem 1.1. An important ingredient is Proposition 4.1, which gives an estimate for coalescing time tail decay for two DSF paths for d = 2. This estimate is crucially used in Section 5 to prove Theorem 1.2, i.e., the scaled DSF converges to the Brownian web. Finally in Section 5, we construct a dual for the perturbed DSF and prove that the DSF and its dual jointly converge to the Brownian web and its dual (Theorem 5.1).

Markov Property
We consider the DSF paths starting from k points u 1 , · · · , u k . As shown in Figure 2, given the past movements we have the information that interior of the shaded region can not have perturbed lattice point(s) in it and because of that, even for k = 1, the process {h n (u 1 ) : n ∈ N} is not Markov. We need to introduce some notations first. Let denote the union of all δ boxes around the lattice points and for l ∈ Z, we define as the union of all δ boxes in the half-plane {x ∈ R d : x(d) ≥ l − δ}. For x ∈ Γ, the notation x ∈ Z d denotes the lattice point such that x ∈ S δ ( x). Note that the choice of δ ensures that S δ (u) ∩ S δ (v) = ∅ for all u, v ∈ Z d with u = v and hence x is uniquely defined for all x ∈ Γ. We choose k points v 1 , · · · , v k ∈ Z d with v 1 (d) = · · · = v k (d) = 0 and we start k paths from the points u 1 − δe d , u 2 − δe d , · · · , u k − δe d where {e 1 , · · · , e d } denote the set of standard orthonormal basis vectors in R d . In this section, starting with these k points we define a joint exploration process so that all the paths move in tandem and we show that there are random times when the joint exploration process exhibits Markov properties. WLOG we take v 1 (d) = 0. For ease of notation we denote the set of points Though the exploration process is defined for general k points, in what follows, only two values of k will be important to us, viz., k = 1 and k = 2. Before we proceed further, it is important to mention that several qualitative 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 δ, the number k of considered trajectories and dimension d.
In order to define the joint exploration process we need to introduce some further notations. For u ∈ Z d , we define the neighbouring set or neighbourhood of u of interest for taking the next step as We will extend this notion of neighbourhood naturally for a general non-lattice point x ∈ Γ as N (x) := N ( x). Observe that, the choice of δ ensures that for all x ∈ Γ, we must have that The joint exploration process starting from the vertices u 1 , · · · , u k is denoted by {(g n (u 1 ), · · · , g n (u k )) : n ≥ 0} and defined inductively as follows.
Set g 0 (u i ) = u i and g 1 (u i ) = h(u i ) for 1 ≤ i ≤ k. Define W move 1 as the unique vertex g 1 (u j ) such that g 1 (u j )(d) ≤ g 1 (u i )(d) for all 1 ≤ i ≤ k. In other words, W move 1 has the smallest d-th coordinate among the vertices {g 1 (u i ) : 1 ≤ i ≤ k}. At the next step, only W move 1 takes the next step and the rest of the vertices stay put. Formally, for 1 ≤ i ≤ k Define W move 2 := g 2 (u j ) such that g 2 (u j )(d) ≤ g 2 (u i )(d) for all 1 ≤ i ≤ k. In general for n ≥ 2 and for 1 ≤ i ≤ k We commented earlier that because of the information generated due to the past movements, the process {(g n (u 1 ), · · · , g n (u k )) : n ≥ 0} is not Markov. We now describe the generated information in terms of a region in the half-plane {x ∈ R d : x(d) ≥ W move n (d)} of which we precisely have the information that it's interior is free of perturbed lattice points.
For x ∈ R and r > 0 let B + (x, r) := {y ∈ R d : ||y − x|| 1 ≤ r, y(d) ≥ x(d)} denote the upper half part of the || || 1 ball B(x, r) centered at x. Set H 0 = ∅. For n ≥ 1 let r n := min{ g n (u i )(d) : 1 ≤ i ≤ k}. For n ≥ 1, we denote the history region as Let denote the natural filtration. Given F n , the explored region H n , which is a finite union of part of || || 1 triangles in Γ(r n ), represents the total information/history region that affects the n + 1-th step and for each of these || || 1 triangles, the corresponding center point has d-th coordinate strictly smaller than that of the point W move n . As observed earlier that the process {(g n (u 1 ), · · · , g n (u k )) : n ≥ 0} is not Markov. Given F n we have the information that the history region H n can not have a perturbed point in its interior and the explored region H n clearly depends on the past movements. At this place it is good to mention here that, as observed for the discrete DSF (defined on a random subset of Z d and studied in [RSS15]), or for the Poisson DSF (studied in [BB07], [CSST19]), it can be shown that the process {(g n (u 1 ), · · · , g n (u k ), H n (u 1 , · · · , u k )) : n ≥ 0} forms a Markov chain over an appropriate state space. But in this paper we follow a different route and we directly show that there are random times such that the joint exploration process {(g n (u 1 ), · · · , g n (u k )) : n ≥ 0} observed at these random times exhibits Markov properties. In order to describe such a sequence of random times we need to introduce few more notations.
Definition 2.1. For x ∈ Γ, among the neighbouring vertices in N (x) ⊂ Z d , the upper neighbouring vertex (w.r.t. the d-th co-ordinate), i.e., x + e d is denoted as x u , where {e 1 , · · · , e d } denotes the standard orthonormal basis set in R d .
For any n ∈ N given F n , the n + 1-th step W move It is important to observe that the 'up' steps are important for us as they do not produce any new history triangles. We will explain this in more detail later.
After defining up steps, for any l ≥ 1 we need to define the 'last l steps' for g n (u i ) for 1 ≤ i ≤ k.
Definition 2.2. Given F n , the 'last l step(s)' for g n (u i ) is defined as the following l step(s) where m < n is such that we have h l (g m (u i )) = g n (u i ) . Now we are ready to define the following sequence of random times. Set τ 0 = 0 and for j ≥ 1 define τ j = τ j (u 1 , · · · , u k ) := inf{n > τ j−1 : g n (u 1 )(d) = · · · = g n (u k )(d) ≥ g τ j−1 (u 1 )(d) + 2 and both the last two steps for g n (u i ) are 'up' steps for all 1 ≤ i ≤ k}.
In other words, this tells us that all the vertices g n (u 1 ), · · · , g n (u k ) are at the same (lattice) level and for each 1 ≤ i ≤ k and for some m = m(i) < n we have that In Figure 2, starting from a single point u, we represent a realization of the step g τ 1 (u) for d = 2. Note that the restriction that g τ j (u 1 )(d) ≥ g τ j−1 (u 1 )(d) + 2 ensures that the set of steps in between τ j−1 and τ j are completely disjoint from the set of steps in between τ j−2 and τ j−1 .
It is not difficult to observe that for each j ≥ 0, the random time τ j is a stopping time with respect to the filtration {F n : n ≥ 0}, defined as in (4) and hence the sequence {τ j : j ≥ 0} of random variables is adapted with respect to the filtration F τ j : j ≥ 0}.
For each j ≥ 0, we need to show that the random time τ j is a.s. finite. We will show a stronger result that the tail of the random increment τ j+1 − τ j decays exponentially for all j ≥ 0.
Proposition 2.3. There exist C 0 , C 1 positive constants which does not depend on F τ j such that for all n ≥ 1 For the moment, assuming Proposition 2.3 holds true we proceed further. The following proposition explains the role of these random steps to recover the Markov properties . Later, we will also discuss why it is difficult to prove Proposition 2.3 for our model.
Proof : The fact that the process {(g τ j (u 1 ), · · · , g τ j (u k )) : j ≥ 0} is adapted w.r.t. the filtration {F τ j : j ≥ 0} follows from the fact that for each j ≥ 0, the random variable τ j is a stopping time w.r.t. the filtration {F n : n ≥ 0}.
To prove the Markov property, we show that the σ-field F τ j does not have any information about the boxes in Recall that for any x ∈ Γ, we have h(x) ∈ v:v∈N (x) S δ (v) and hence i.e., at each step the newly created history region is contained within the neighbouring boxes. It further follows that if x, h(x) is an 'up' step, then In other words, an up step x, h(x) does not produce a new history triangle in Γ( h(x)(d))\ S δ ( h(x)). From the earlier observations it follows that for any n ∈ N, the history region H n is contained in Γ( g n (u 1 )(d) + 1). Since by definition of τ j , the last two steps for g τ j (u i ) are up steps for all 1 ≤ i ≤ k, it follows that This implies that the σ-field F τ j does not have any information about the remaining δ-boxes in Γ( g τ j (u i )(d)), i.e., the δ-boxes associated to the lattice points Hence given F τ j , the perturbed points in the region Γ( g τ j (u 1 )(d)) \ ∪ k i=1 S δ ( g τ j (u i )) can be replaced with an independent and identically distributed point process. This allows a random mapping representation of the conditional distribution (g τ j+1 (u 1 ), · · · , g τ j+1 (u k )) given (g τ j (u 1 ), · · · , g τ j (u k )) = (x 1 , · · · , x k ), (g τ j−1 (u 1 ), · · · , g τ j−1 (u k )) = (y 1 , · · · , y k ), · · · of the following form (g τ j+1 (u 1 ), · · · , g τ j+1 (u k )) | (g τ j (u 1 ), · · · , g τ j (u k )) = (x 1 , · · · , x k ), (g τ j−1 (u 1 ), · · · , g τ j−1 (u k )) = (y 1 , · · · , y k ), where {U (1) v : v ∈ Z d } gives an i.i.d. collection of random variables independent of the collection {U v : v ∈ Z d } that we have started with, such that each random variable is uniformly distributed over the region S δ . This completes the proof by random mapping theorem (see [LPW08]). Now we need to prove Proposition 2.3. In fact, for a technical reason that will be explained later, we will consider a random subsequence {τ j : j ≥ 0} of the original sequence {τ j : j ≥ 0} and show that (6) holds for this subsequence. We will also discuss shortly why it is difficult to prove Proposition 2.3 for our model. In order to define the random subsequence of interest we need to introduce some notations.
For v ∈ Z d , we define the region near the lower face of the δ-box as where c is a small positive constant which will be kept fixed throughout the context of this paper. We are not giving a specific value of c here. Rather, we just comment that there exists c > 0 small enough such that all the favourable conditions that we will define later, are satisfied.
. Now, we are ready to define the random subsequence of our interest.
In Figure 3, starting from a single point u ∈ V , we present a realization of the random step g τ 1 (u) for d = 2. Clearly the sequence {τ j : j ≥ 0} is a subsequence of {τ j : j ≥ 0}. For each j ≥ 0, the random variable τ j is also a stopping time with respect to the filtration {F n : n ≥ 0}. It is useful to note that the same argument as in Proposition 2.4 gives us that the process {(g τ j (u 1 ), · · · , g τ j (u k )) : j ≥ 0} is Markov as well. In order to prove Proposition 2.3 it suffices to show that there exist C 0 , C 1 positive constants depending only on δ > 0, d and k such that This will be proved through a sequence of lemmas. We first present a property of our joint exploration process that will be heavily used in the sequel.
Lemma 2.5. Fix any n ∈ N. Given F n , for each 1 ≤ i ≤ k, the top neighbouring box S δ (g n (u i ) u ) remains unexplored completely, i.e., we have, Proof: The proof is a simple consequence of our movement algorithm and we give a sketch here. Firstly given F n , if we have S δ ( g n (u i )) ∩ H n = ∅ for some 1 ≤ i ≤ k then because of our movement algorithm, that can not happen due to a step W move On the other hand for any x ∈ Γ we have Hence it follows that the region created due to the m-th (m ≤ n−1) The above lemma will be an important tool to prove Proposition 2.3. Heuristically, it appears that since the 'top' box remain unexplored, using it one can construct a favourable configuration so that the vertex g n (u i ) takes two consecutive up steps and the probability of such a favourable configuration is bounded away from zero irrespective of the history region. But because of the dependency of the perturbed lattice points, this strategy does not work for our model and we need to modify this strategy significantly. Let us try to describe the main difficulty in implementing the above mentioned strategy.
For simplicity let us consider the case of k = 1, i.e., we are starting with a single path. Let us try to show that given F n , the probability that the exploration process takes an 'up' step, i.e., P(g n+1 (u 1 ) ∈ S δ (g n (u 1 ) u ) | F n ) has a strictly positive lower bound. We say that the two points x, y ∈ Γ are at the same lattice level if x(d) = y(d). Next for x ∈ Γ, the part of the neighbourhood N (x) that consists of vertices at the same lattice level is given by In order to show that the up step probability has a fixed strictly positive lower bound irrespective of the history region, a natural strategy is that, for all the partially explored neighbouring boxes at the same lattice level, we place the unexplored perturbed lattice points in the respective far corners of those boxes and use the unexplored top box to create a favourable configuration for taking an up step. Because of the strong dependency of the perturbed points, it is difficult to implement this strategy. To illustrate this difficulty, we consider the situation as depicted in Figure 4. Figure 4: For the left neighbouring box of g n (u 1 ), the perturbed point (shaded as gray) belongs to the near corner of g n (u 1 ) with a very high probability and that makes it difficult to give a strictly positive lower bound for an up step independent of F n . Figure 4 represents a situation unfavourable for taking an up step for d = 2. In the given situation, one of the neighbouring δ-boxes of g n (u) with an unexplored perturbed lattice point (i.e., this box potentially may have the candidate for the next step) is explored 'too much' and hence very little unexplored region is left. Since the unexplored perturbed point is uniformly distributed over the unexplored area and in the given situation, the far corner of the right neighbour of g n (u) is almost completely explored (in the figure it is completely explored), the corresponding perturbed point belongs to the near corner with a very high probability. This shows that it is impossible to obtain a fixed positive lower bound for the probability of an up step, given by It is important to mention here that, the use of such 'favourable upward ' steps to kill the accumulated history region is common for DSF type dependent models (see [RSS15], [CSST19]). For both these two models, it was proved that at each step independent of the history set, the probability of taking a favourable upward step (the notion of an appropriate 'upward' step depends on the model) is bounded away from 0 and the constructions of renewal steps for these models use this observation. This further uses the fact that the vertices are independently distributed over disjoint regions. But for the perturbed lattice model, we no longer have that kind of independence and as a result it is not possible to obtain a strictly positive lower bound for the probability of taking an 'up' step independent of the history set.
Before proceeding further we present a brief outline of our strategy to prove Proposition 2.3. The discussion suggests that, exploring too much of a δ box, which is not completely explored yet, i.e., the location of the associated perturbed point is not known yet, is not good for our purpose. In what follows, we will do a more detail analysis of the geometry of the history regions and show that the number of times the joint exploration process {(g n (u 1 ), · · · , g n (u k )) : n ≥ 0} encounters such badly explored neighbouring boxes is well controlled. This allows us to prove (6).
To make these heuristics rigorous, we need to introduce few notations. For u ∈ Z d , we consider the δ-box S δ (u) and define where c is a small positive constant as in (7). The intuition is that, a point in S + δ (u) is very close to the top face of S δ (u) and hence should take an up step quickly.
In what follows, given F n , a δ-box S δ (v) is said to be 'completely explored' if the associated perturbed lattice point v = v + U v belongs to the history region H n , i.e., the σ-field F n has complete information about the location of the perturbed point v . If a box is not completely explored, it is called partially explored.
for some positive constant p 0 which depends only on δ and d.
Proof : We need to define the following regions in the δ box S δ (v). For x ∈ {+1, −1} d−1 let x + ∈ {+1, −1} d be defined as x + = (x, +1). We consider the || || 1 triangle of width cδ centred at the point v + δx + defined as where c is as in (7). We note that the set of the points {v + x + : x ∈ {+1, −1} d−1 } covers all the 'corner' points on the top face of the δ-box S δ (v).
our movement algorithm ensures that any || || 1 history triangle intersecting with a x (v) for some x ∈ {+1, −1} d−1 must be such that the d-th coordinate of it's center is strictly smaller than W move n (d). Further from the geometry of || || 1 triangle it follows that the ratio of the Lebesgue measure of the unexplored part in S + δ (v) and the Lebesgue measure of the unexplored part in S δ (v) is uniformly bounded from below. Mathematically, there exists a positive constantĉ which depends only on c, δ and dimension d such that where for any Borel A ⊂ R d , the number (A) denotes the corresponding Lebesgue measure (area or volume). In order to show (13) we note that || || 1 triangular history region intersecting with S δ (v) must be such that the d-th coordinate of the corresponding triangular region is strictly smaller than W move n (d). Hence the unexplored part in S δ (v), i.e., S δ (v) \ H n can be expressed as finite unions of regions of the form B(y, l) for some For any such region B(y, l), we have which depends only on l ∈ (0, 2δ], δ, dimension d and c. For l ≤ cδ we have c l = 1. Further for l ∈ [cδ, 2δ] the above boundĉ l varies continually with l. Hence the choicê Now, since for any partially explored box, the corresponding perturbed point uniformly distributed over the unexplored region, (13) completes the proof. The intuitive idea is that, whenever the DSF path reaches S + δ (v) for some v ∈ Z d , it almost reaches the top face and therefore, it can not take too many steps at the same lattice level and will take an upward step quickly. Unfortunately Corollary 2.6 does not hold if we don't have v(d) ≥ W move n (d) + 1. In order to deal with the general case, we need to introduce another notation. Fix n ∈ N.
We note that given F n , for a partially explored box S δ (v) if the corresponding perturbed point is in S (n),− δ (v), then by definition of h(·) step we must have that g m (u i ) / ∈ S δ (v) for all 1 ≤ i ≤ k and m > n. In other words, all of the k DSF paths avoid the box S δ (v).
Corollary 2.7. Fix n ∈ N. Given F n , for any partially explored box S δ (v) we have for some positive constant p 1 which depends only on δ and d.
Proof : As observed in the proof of the earlier corollary, if we have We observe that the unexplored region S δ (v) \ H n can be expressed as disjoint unions: This observation together with (15) completes the proof. Before proving Proposition 2.3 we need one more lemma which states that given F n , the time taken so that, the last step for g n (u i ) for all 1 ≤ i ≤ k is a 'special up step' and all the vertices are at same lattice level, is stochastically dominated by a geometric random variable. Given F n let us define ν n := inf{m ≥ 1 : the last step for g n+m (u i ) is a special up step for all 1 ≤ i ≤ k The next lemma shows that the random variable ν n is finite and in fact, it's tail decays exponentially.
Lemma 2.8. Fix n ∈ N. Given F n there exist positive constants C 0 , C 1 which does not depend on F n and a positive integer m d,k which depends only on d, k such that for all l ≥ 1 we have Proof : We first prove it for k = 1, i.e., starting with a single path and for d = 2. Then we will discuss the modifications required for 3 dimensions. Finally we will deal with the general case of k ≥ 1 and d ≥ 2. Given F n we define the event A 1 n which ensures that the unexplored perturbed points in all the partially explored neighbouring δ-boxes at the same lattice level, are either close to their respective top faces or below (w.r.t. d-th coordinate) the point W move n . Mathematically, Because of Corollary 2.7 we have P(A 1 n |F n ) ≥ (p 1 ) 2d . We need to define a second event A 2 n using the unexplored δ-box S δ (g n (u 1 ) u ). We need some notations for that. For x ∈ Γ, let where c is a small positive constant chosen as in (7). The next event A 2 n states that the perturbed point associated to the unexplored top box S δ (g n (u 1 ) u ) belongs to the region ∆ (1) n , i.e., We note that for the probability P(A 1 n ∩ A 2 n | F n ) we have where p 2 is a strictly positive lower bound for P(A 2 n | F n ) that does not depend F n . Since g n (u 1 ) always connects to the nearest (|| || 1 sense) perturbed point in the half-plane {x ∈ R d : x(d) > g n (u 1 )(d)}, it is not difficult to observe that on the event A 1 n ∩ A 2 n , either of the following happens: n , i.e., the point g n (u 1 ) takes a special up step; (ii) h(g n (u 1 )) ∈ S + δ (v) for some v ∈ N 0 (g n (u 1 )). In case (i) we have nothing to prove. In case (ii), the point h(g n (u 1 )) = g n+1 (u 1 ) belongs to very close to the top face of a δ-box and we show that it will take a special up step very quickly. It actually belongs to a very specific region near the top face. Firstly for d = 2 and since g n (u 1 )(d) = g n+1 (u 1 )(d), there is only one neighbouring δ-box at the same lattice level which is not completely explored. W.l.o.g. let us assume that the right neighbouring δ-box is not completely explored. Since c is very small, the presence of perturbed point in ∆ (1) n ensures that in case (ii) the point g n+1 (u 1 ) belongs to very close to the left corner g n (u 1 )+(1−δ, δ) which is the nearer corner on the top face of S δ ( g n (u 1 )) to the point g n (u 1 ). Given F n+1 , now we define the events A 1 n+1 and A 2 n+1 similarly. We observe that the top boxes S δ (g n (u 1 ) u ) and S δ (g n+1 (u 1 )) are disjoint and both the points g n (u 1 ) and g n+1 (u 1 ) may or may not share some neighbours. But the good thing is that the favourable conditions are the same for all neighbouring boxes at the same lattice level. Hence we have In case (ii), we can consider the event ∩ n+1 l=n (A 1 l ∩ A 2 l ) and then the point g n+1 (u 1 ) must take a special up step since the corner nearer to the point g n+1 (u 1 ) belongs to the completely explored δ-box S δ (g n (u 1 )) and the directed nature of our navigation ensures that h(g n+1 (u 1 )) = g n+2 (u 1 ) can not belong to the same box. In other words, g n+1 (u 1 ) must take a special up step. Hence on the event (A 1 n ∩ A 2 n ) ∩ ((A 1 n+1 ∩ A 2 n+1 ) we must have ν n ≤ 3. This completes the proof for k = 1 and d = 2 with the choice m 2,1 = 2.
For d = 3 and for k = 1 the argument is essentially the same. One just needs to observe that in higher dimensions there are more options for near corners (specifically at most 4 for d = 3) than those are available for d = 2 and hence the DSF path can spend more time in the top parts of the δ-boxes implying that the number m 3,1 would be different.
Next we consider the general case of multiple paths, i.e., k ≥ 2. We first consider the situation that g n (u 1 )(d) = · · · = g n (u k )(d), i.e., all the vertices are at the same lattice level. In such a case, given F n we need to consider the events and where ∆ (i) . In other words, for all the vertices g n (u 1 ), · · · , g n (u k ), we are creating favourable configurations using respective neighbouring vertices. It is also not difficult to argue that P(A 1,(k) n ∩ A 2,(k) n | F n ) has a strictly positive lower bound which does not depend on F n . The main issue is that in case of multiple paths, the point g n (u i ) may have a completely explored neighbouring δ-box which belongs to the trajectory of u j for some , there is one more option that the vertex g n (u i ) may coalesce with the trajectory of some other vertex. In that case, we can not control it's location and more specifically, it need not belong to the top part of some box. This means that such a step may not be an useful step towards getting ν n . We present a brief sketch here. We wait till all of the points g n (u 1 ), · · · , g n (u k ) take their steps. As discussed, some of these points take special up step, some may coalesce with others and some of these take steps to the regions S + δ (·). Next we consider an event similar to A 1,(k) n ∩ A 2,(k) n where we seek favourable configurations only around the vertices at lower (lattice) level. Repeating the same procedure, all of the k paths (finally) take special up steps and before that it might have coalesced with one of the remaining (k − 1) paths. Note that we can have at most (k − 1) such coalescences and thereafter a single path only remains. This completes the proof for the situation g n (u 1 )(d) = · · · = g n (u k )(d). It is also clear that after taking special up steps all of the k paths (some of them might have coalesced already) remain at the same lattice level.
Finally we need to consider the situation that all the vertices are not at same lattice level. The argument is essentially the same and we give a sketch here. In this situation we need to modify the event A 1,(k) n so that we seek favourable configurations only around the points g n (u j ) with g n (u j )(d) = W move n (d), i.e., around the points g n (u j ) at lower (lattice) level. As in the earlier situation, for a lower level vertex instead of a favourable step we may have a coalescence step. From our movement algorithm it also follows that if we have a coalescence step for a lower level vertex, then it must coalesce with another lower level vertex only. Hence we have that with a laziness of at most k − 2 steps due to coalescence of different trajectories, in geometric number of steps the lower level vertices take special up steps to be at the same lattice level with the remaining ones. For the remaining ones, i.e., for the top ones, the last steps are all up steps, but they need not be special up steps. But now we are back to the situation g n (u 1 )(d) = · · · = g n (u k )(d) and can apply the earlier argument to complete the proof. Now we are ready to prove Proposition 2.3. Proof of Proposition 2.3: We first prove (6) for k = 1 and later we will consider the general case of k ≥ 2 paths. Firstly, we observe that the random variable ν n is a stopping time w.r.t. the filtration {F n+j : j ≥ 1}. To prove (6), it suffices to show that there exists p 3 > 0 independent of n such that P(h(g n+νn (u 1 )) ∈ ∆ (1) As in the earlier proof, in order to obtain this we create a favourable configuration using the neighbouring δ-boxes around g n+νn (u 1 ). Conditionally on the σ-filed F n+νn , we define the event Since the last step is an (special) up step, the argument of Corollary 2.6 holds and as the top box S δ (g n+νn (u 1 ) u ) is unexplored given F n+νn , there exists p 3 > 0 which does not depend on F n+νn such that P(A 3 n+νn | F n+νn ) ≥ p 3 . It is not difficult to see that for all small enough c > 0, on the event A 3 n+νn we must have h(g n+νn (u 1 )) ∈ ∆ (1) n+νn . With the help of Lemma 2.7 of [RSS15] this completes the proof for k = 1.
For general k ≥ 2 paths, the argument is essentially the same. Given F n+νn , we need to create favourable configurations using neighbouring boxes around each point g n+νn (u i ). It is not difficult to argue that the probability of such a favourable configuration has a strictly positive lower bound which does not depend on F n+νn . Again the complication arises due to the presence of completely explored δ boxes which are on the trajectory of some other point. Let us consider the case of k = 2. Similar argument holds for general k ≥ 2. Consider the event W.l.o.g. let us assume that g n+νn (u 1 )(d) < g n+νn (u 2 )(d). Now on the event A 3,(2) n+νn for the point g n+νn (u 1 ) it is possible that instead of taking a special up step, we have h(g n+νn (u 1 )) = g n+νn (u 2 ). But in that case we must have h(g n+νn (u 2 )) = h 2 (g n+νn (u 1 )) ∈ ∆ (2) n+νn . Now we can create a similar favourable configuration around the point h(g n+νn (u 2 )) = h 2 (g n+νn (u 1 )) so that it takes a special up step as well. This completes the proof.
From here onwards, with a slight abuse of notation, we use the same notation {τ j : j ≥ 0} to denote the random subsequence. In the next section we use these τ -steps to construct certain special steps referred as renewal steps.

Renewal steps
This section is motivated from the construction of renewal steps in [CSST19]. Before we describe the mathematical details of renewal steps, we provide the general idea. For x ∈ Γ let x := x u − δe d denote the projection of x u ∈ Z d on the lower face of the δ-box S δ (x u ). The || || 1 triangle of width δ/10, is denoted by where c is a small positive constant as in (7). For 1 ≤ i ≤ k and for j ≥ 1 consider the || || 1 triangles ∆(g τ j (u i )). We note that the projected points g τ j (u i )'s are distinct if and only if the corresponding perturbed points g τ j (u i )'s are different. We are now going to define what we will call as our renewal event. We first define the renewal event for the choice k = 1, i.e., for a single path. The definition for the renewal event in the context of two paths is more complex and we will give it later.

Renewal event for k = 1
We consider the process {g n (u 1 ) : n ≥ 1} and for any j ≥ 1, corresponding to the j-th τ step τ j , the renewal event E j = E j (u 1 ) is defined as follows: In Figure 5, we present a realization of the event E 1 = E 1 (u) for k = 1 and d = 1. It is important to observe that, the definition of the event E j is associated with the τ j -th step and the definition ensures that, on this event, the point g τ j (u 1 ) must take a special up step to the uniformly distributed perturbed point in ∆(g τ j (u 1 )). It would be also useful to comment that because of our modified definition of τ steps which ensures that the last two steps are special up steps, the definition of renewal event becomes simpler. Given F τ j , since we know that g τ j (u 1 ) ∈ ∆(g τ j −1 (u 1 )), on the event E j we must have a special up step.
Before giving the mathematical details, let us first discuss the heuristic idea of a renewal event. As commented earlier, on the renewal event E j the point g τ j (u 1 ) takes an up step to the uniformly distributed perturbed point in ∆(g τ j (u 1 )). Given that the event E j has occurred, we do not have any information about the δ-boxes Γ(g τ j (u 1 ) u (d)) \ S δ (g τ j (u 1 ) u ) and the exact location of the perturbed point in ∆(g τ j (u 1 )) is not known to us. It is useful to observe that on the event E j , if we start from the point g τ j (u 1 ), we only have the information that there is a perturbed point uniformly distributed in the || || 1 triangle ∆(g τ j (u 1 )) and the point g τ j (u 1 ) takes step to the same perturbed point. The symmetry of the region ∆(g τ j (u 1 )) together with the i.i.d. nature of the perturbations in the unexplored δ-boxes Γ(g τ j (u 1 ) u (d)) \ S δ (g τ j (u 1 ) u ) allow us to restart the process from the point g τ j (u 1 ) and recover renewal properties (see Propostion 3.3).
It is useful to mention here that given F τ j , we do not have any information about the δ-boxes Γ( g τ j (u 1 )(d)) \ S δ (g τ j (u 1 )). But the σ-field F τ j knows the exact location of the point g τ j (u 1 ) and because of lack of symmetry this process is difficult to handle, e.g., for d = 2 and for any j ≥ 1, we don't able to show that E[g τ j+1 (u 1 )(1) − g τ j (u 1 )(1)|F τ j ] = 0. This is the motivation of going through renewal steps.
Corresponding to renewal events, we are now going to define the renewal steps. Set γ 0 = 0 and for ≥ 1 let γ = γ (u 1 ) denote the number of τ steps required for the -th renewal step: γ := inf j > γ −1 : the event E j occurs , and let β := τ γ denote the total number of steps required for the -th renewal step.
Since the event E j depends on the perturbed lattice points in S δ (v) for v ∈ N (g τ j (u 1 )), it is not measurable w.r.t. the σ-field F τ j . Hence for any ≥ 1, the r.v. γ is not a (F τ j )stopping time. To deal with this issue, we need to consider an enhanced filtration. Set S 0 = F 0 and for j ≥ 1 we define It follows that for any ≥ 0, the r.v. γ is a stopping time with respect to the enhanced filtration {S j : j ≥ 0}. Next we consider the filtration Clearly the sequence of r.v.'s {β : ≥ 0} denoting the total number of steps required for -th renewal step is adapted to the filtration {G : ≥ 0}. Let us show that for any ≥ 1, the random integer β is almost surely finite. Towards this we would first show that the probability of occurrence of a renewal event at a τ step is strictly bounded away from both 0 and 1. Using this we show that the renewal steps must occur and at most a geometric number of τ steps would be required to reach the next renewal step. Finally this would give us that the number of intermediate steps between any two successive renewal steps, given by β +1 − β decays exponentially.
Proposition 3.1. Fix ≥ 0. Then, for all n ≥ 1, where C 0 , C 1 are positive constants which depend only on δ and d.
In order to prove the above proposition, we need the following corollary which states that the probability of renewal event at any τ -step is bounded away from both 0 and 1.
Corollary 3.2. There exist p 5 , p 6 ∈ (0, 1) depending only on δ and d such that, for all j ≥ 1 we have, where for any event A, the notation 1 A denotes the corresponding indicator random variable.
Proof. We first show that (28) holds for j = 1. Given F τ 1 , we do not have any information about the neighbouring δ-boxes S δ (v) for v ∈ N (g τ j (u 1 )). Hence it is straightforward to see that there exists p 5 , p 6 ∈ (0, 1) depending only on δ such that Next consider Equation (28) for j = 2. Recall that the random variable 1 E 1 depends only on the perturbed points in the (neighbouring) δ-boxes S δ (v) for v ∈ N (g τ 1 (u 1 )). On the other hand, by definition we have that g τ j+1 (u 1 )(d) − g τ j (u 1 )(d) ≥ 2. This ensures that given F τ 2 , the subsequent steps as well as the event E 2 depend only on the perturbed points in Γ( g τ 2 (u 1 )(2)). Hence we have and then the proof follows using the same argument as in the case of j = 1. Finally for general j ≥ 1, the proof follows by method of induction. Now we are ready to prove Proposition 3.1.
Proof. We work conditionally on G , for ≥ 0. We first show that where G is a geometric r.v. with success probability p 0 . In other words, the r.v. γ +1 − γ is stochastically dominated by G. First we prove it for = 0. The argument for general ≥ 0 is the same.
In the penultimate step, we have used the upper bound obtained from the previous lemma and the last step follows by following the same argument repeatedly.
Observe that, knowing about occurrence or non-occurrence of the event E j means having extra information about the δ-boxes S δ (v) for v ∈ N (g τ j (u 1 )), along with the σ-field F τ j . Next we show that given S j (= σ(F τ j , 1 E 1 , . . . , 1 E j )), the random variable τ j+1 − τ j still decays exponentially fast. .
Observe that the events E 1 , . . . , E j−1 depend only on the perturbed lattice points in the Hence given F τ j , the random variable τ j+1 − τ j is independent of the events E 1 , . . . , E j−1 . So, using Proposition 2.3 we have, Therefore, Lemma 3.2 gives where C 2 = C 0 ( 1 1−p 5 + 1 p 6 ). Therefore, we can construct a random variable T such that P(T ≥ n) ≤ C 2 exp (−C 1 n) and (τ j+1 − τ j ) | S j is stochastically dominated by T . Now, let 0 < ϑ small enough so that E(e ϑT ) < ∞. Then, for any constant c > 0, where {T j : j ≥ 1} are i.i.d. copies of T defined above. This completes the proof of (27) by choosing c = c(ϑ) sufficiently small.
Next we explain the renewal properties of our renewal steps for k = 1. Later for general k ≥ 2 we will define the renewal steps and show that for k = 2 the process satisfy certain nice properties which will be useful to us to prove convergence to the Brownian web.
The next proposition explains the renewal properties of the constructed renewal steps. It is important to observe that the random vector Y 1 − Y 0 has different distribution since the initial conditions are different at start. First of all any renewal step must be a τ step and for any j ≥ 1, the event E j involves perturbed points only in the boxes S δ (v) for v ∈ N (g τ j (u 1 )). Hence we first observe that for v(2) ≥ g β m−1 (u 1 ) u (d), the σ-field G m−1 does not have any information about the boxes S δ (v) except the choice v = g β m−1 (u 1 ) u . Further given G m−1 , the perturbed points in the neighbouring boxes of g β m−1 (u 1 ) at the same lattice level are such that, the next step starting from g β m−1 (u 1 ) must be an up step to the uniformly distributed point in the || || 1 triangular region ∆(g β m−1 (u 1 )). Hence the newly constructed path starting from the point g β m−1 (u 1 ) coalesce with the original path at the point h(g β m−1 (u 1 )) and the only information of relevance carried at the (m − 1)-th renewal step for constructing the path starting from g β m−1 (u 1 ) is that the triangular region ∆(g β m−1 (u 1 )) contains a perturbed lattice point (which is the point h(g β m−1 (u 1 ))) uniformly distributed over there. Now, suppose we start from the point 0 := 0 − δe d with the information that that there is a perturbed point uniformly distributed over the region B(0 , δ/10) and consider the process till it's first renewal step β 1 (0 ). Let z 0 := g β 1 (0 ) (0 )−0 denote the increment. The earlier observations, together with the i.i.d. nature of perturbations, allow us to say that Induction on m completes the proof.
Since at each step, the increment ||g n−1 (u 1 ) − g n (u 1 )|| 1 (or more generally ||W move n−1 − h(W move n−1 )|| 1 for multiple k ≥ 1 paths) is bounded by 2, for each 1 ≤ j ≤ d the increment random variable Y +1 (j) − Y (j) has moments of all orders. Below we list out some further properties of these random variables which follows from the symmetry of the region ∆(g β (u 1 )) in the following corollary. (ii) Consider j, l ∈ {1, · · · , d − 1} with j = l. By reflection symmetry along the j-th coordinate, with other coordinates being fixed, we observe that the joint distribution of ( for m 1 , m 2 ≥ 1 with at least one of them being odd.
Hence, Corollary 3.4 give us that for d = 2, the diffusively scaled DSF path converges to the Brownian motion.

Renewal with two paths
Before describing renewal events for two paths, we first discuss our motivation behind this construction. It is useful to observe that while working with a collection of DSF paths, we need to deal with two types of dependencies: for the same path we need to deal with dependencies between the steps, on the other hand we need to tackle dependencies between different paths as well. In the earlier section, through the construction of renewal step for a single path we able to deal with the dependencies between steps for the same path. In this section while working with two paths we show that when these two paths are far apart, they behave like independent random walks and this enables us to obtain suitable estimates for their coalescing time.
Coming to the renewal events with paths starting from two points, again our idea is to create some favourable configurations at the τ steps, so that both the paths are forced to take special up steps and then to restart the process from the projected points as in case of single path. However, in case of multiple paths there is a crucial difference that when the paths are close enough, then it is not possible to ensure upward steps for both the paths. In such a situation the restarted paths may not represent the original paths. Nevertheless we will see that for our model and for k = 2, coalescence of the restarted paths would certainly imply coalescence of the original paths. Now we proceed with the definition of the renewal event.
With the updated definition of renewal event E j (u 1 , u 2 ) for two paths, the renewal steps β( ) : ≥ 1 and the associated enhanced filtration {G = G (u 1 , u 2 ) : ≥ 1} are defined accordingly. It is also not difficult to observe that at each τ step the probability of the renewal event is uniformly bounded away from 0 and 1 and the same arguments as in the case of single would give us exponential decay for (β − β −1 ), the number of intermediate steps in between − 1-th and -th renewals. As in the case of a single path, at a renewal step β , we want to restart the process from g β (u 1 ) and g β (u 2 ). But it is important to observe that at β , if both the paths are close enough, more specifically if || g β (u 1 ) − g β (u 2 )|| 1 = 1, i.e., they become neighbours, then both the paths may not take up steps. Instead one may coalesce with the other. In such case the restarted process may not match the original process. The good thing is that the original process differs from the restarted process only if instead of taking a special up step, one of the path coalesces with the another one (recall that in this section we are working with k = 2) and hence the coalescence of the restarted process would imply coalescence of the original process as well. Now we will spend some time to define rigorously our restarted process which are going to restart from the projected point at each renewal step.
We first start with the points u 1 , u 2 ∈ Z d with u 1 (d) = u 2 (d) and consider the DSF paths till their (joint) renewal {(g n (u 1 ), g n (u 2 )) : 0 ≤ n ≤ β 1 }. At their first renewal step β 1 , we consider the restarted paths starting from g β 1 (u 1 ) and g β 1 (u 1 ) till their first renewal.
{(g n (g β 1 (u 1 )), g n (g β 1 (u 2 )) : n ≥ 0} We note that these restarted paths start with the information that both the regions ∆(g β 1 (u 1 )) and ∆(g β 1 (u 2 )) contain exactly one perturbed point and using the perturbed points over the unexplored region. This allows us to recursively define a sequence of restarted processes and corresponding renewal steps.
2 ) = (u 1 , u 2 ) and β 1 = β(u ) for some ≥ 1, we set: The random integer β corresponds to the number of steps until the first renewal event of the ( − 1)-th restarted process starting from {u } with the initial information that the both the regions ∆(u ( −1) 1 ) and ∆(u ( −1) 2 ) contain exactly one perturbed point. It is important to observe for any ≥ 1 if we have h(g β (u ). In other words at the renewal step old paths differ with the restarted paths from the projected points only if the old paths coalesce. Now we consider the process {(u In this regard it is useful to comment that the process {(g β (u 1 ), g β (u 2 )) : ≥ 0} is not Markov.
which gives a Z d−1 valued Markov chain. We observe that 0 = (0, · · · , 0) ∈ Z d−1 is the only absorbing state for this Markov chain.
In the next section we show that, Corollary 4.3 allows us to obtain tail distribution of the coalescence time of two DSF paths.

Proof of Theorem 1.1
In this section we prove Theorem 1.1. For d = 2, 3, we need to show that for u, v ∈ V , the DSF paths π u and π v coincide eventually, i.e., there exists t 0 < ∞ such that π u (s) = π v (s) for all s ≥ t 0 . As observed in [RSS15], it suffices to prove that π u and π v coincide eventually for all u, v ∈ V with u(d) = v(d). (33) This follows from the simple observation that for and (33) gives us that { the paths π u and π x coincide eventually } = 1. Now to show that for any vertices x, y ∈ V with x(d) = y(d) we consider the Z d−1 valued Markov chain Z (u 1 , u 2 ) : ≥ 1 and show that this Markov chain hits 0 ∈ Z d−1 almost surely.

The case d = 2
In this section we prove Theorem 1.1 for d = 2 by showing that for x, y ∈ V with x(d) = y(d), the DSF paths π x , π y coincide eventually with probability 1. To do that, in the following section we prove a stronger result by showing that the tail of the coalescing time decays as in case of coalescing time of two independent random walks (with finite variance). This estimate is crucial to show convergence to the Brownian web. Because of (33), this completes the proof of Theorem 1.1 for d = 2.
We prove the following proposition on tail decay of T (u 1 , u 2 ).
Proposition 4.1. For u 1 , u 2 ∈ V with u 1 (1) < u 2 (1) and u 1 (2) = u 2 (2), there exists a constant C 0 > 0, which does not depend on u 1 , u 2 such that, for any t > 0, We first observe that the above proposition tells us that T (u 1 , u 2 ) is almost surely finite and because of (33), it further proves that the 2-dimensional perturbed DSF is connected with probability 1.
In order to get the required estimate, we will apply a robust technique that was developed in [CSST19]. We first quote Corollary 27 from [CSST19] which essentially states that for a process which behaves like a symmetric random walk far from the origin and satisfy certain moment bounds, similar tail estimate holds.
Corollary 4.2. Let {Y t : t ≥ 0} be a {G t : t ≥ 0} adapted stochastic process taking values in R + . Let ν Y := inf{t ≥ 1 : Y t = 0} be the first hitting time to 0. Suppose that there exist positive constants M 0 , C 0 , C 1 , C 2 , C 3 with 0 < C 0 < 1 such that (i) for any t ≥ 0, (iii) for any t ≥ 0 and m > 0, there exists α m > 0 such that Then, ν Y < ∞ almost surely. Further, there exist positive constants C 4 , C 5 such that for any y > 0 and any integer n, In order to apply the above corollary for DSF paths, we recall the process {Z : ≥ 1} (see (32)). It useful to observe that the DSF paths are non-crossing a.s. and hence for the given choice of u 1 , u 2 ∈ V , {Z : ≥ 1} gives a non-negative process with the only absorbing state at 0. We first obtain a suitable estimate on the number of renewal steps required by the process {Z : ≥ 1} to hit 0 denoted by ν = ν(u 1 , u 2 ) : The following corollary, states that the non-negative process {Z : ≥ 1} satisfies the conditions of Corollary 4.2 and therefore have the required tail estimate in terms of number of renewal steps. This indeed completes the proof of Theorem 1.1 for d = 2. In order to complete the proof of Proposition 4.1, we further need to show that the coalescing time T (u 1 , u 2 ) decays in a similar manner.
Corollary 4.3. There exist positive constants M 0 , C 0 , C 1 and C 2 such that: (i) For any ≥ 1, (ii) For any ≥ 1, (iii) For any ≥ 1 and m > 0, there exists p m > 0 such that (iv) For any ≥ 0, there exist positive constants C 1 and C 2 such that Proof. We first consider part (i). Since at each step the increment of the DSF path is bounded by 2, it is useful to note that for all 1 ≤ i ≤ 2, the region explored by the DSF path starting from u i in between β -th and β +1 -th (joint) renewal step is enclosed within the rectangle g β (u i ) ]. Now take M 0 (≥ 2) sufficiently large and let us consider the trajectories of π u 1 and π u 2 in between -th and ( + 1)-th (joint) renewal steps. The choice of M 0 ensures that the original paths agree with the restarted paths starting from g β (u 1 ) and g β (u 2 ). Note that the trajectories of these restarted paths can be reconstructed with resampled perturbed points over the regions Γ(g β (u 1 ) u (2)) \ ∪ 2 i=1 S(g β (u i ) u ) and resampled independent uniformly distributed perturbed points over the (disjoint) regions ∆(g β (u 1 )) and ∆(g β (u 2 )) without changing the joint distribution of the restarted trajectories.
We construct a new point process in the following way: (1) The realizations of perturbed point process in the rectangles (2) The realization of the perturbed point process outside these two rectangles is kept as it is.
We should note that both the triangular regions ∆(g β (u 1 )) and ∆(g β (u 2 )) contain perturbed points independently and uniformly distributed over these regions. Now, we restrict our attention to the event {(β +1 − β ) < M 0 /4} and consider the trajectories in between the -th and ( + 1)-th (joint) renewal steps using the newly constructed point process. We remark that for this "new" regenerated paths, the number of steps until the next renewal step and the size of the corresponding renewal block have not changed. In fact, the increments of each path between the -th and ( + 1)-th renewal steps have been interchanged. This means that the increment I +1 has become −I +1 . This completes the proof of part (1).

Part (ii) follows readily from the fact that
where T is a non-negative random variable with exponential tail such that for all ≥ 0, the conditional distribution of (β +1 − β ) | G is stochastically dominated by T (see proof of Proposition 3.1). For part (iii) we recall the fact that the σ-field G does not contain any information about the perturbed point in the region Γ(g β (u 1 ) u (2) + 1) and suitable configurations are easy to build so that the conditional probability P(Z +1 = 0 | G ) is strictly positive .
For part (iv) we observe that This completes the proof.
The above corollary shows that the process {Z : ≥ 1} satisfies the conditions of Corollary 4.2, and hence we have the following tail estimate on ν. For all integer n ∈ N, there exists a positive constant C 0 which does not depend on u 2 (1) − u 1 (1) such that, Since, the number of steps between two consecutive renewal steps decay exponentially, using the above lemma we prove Proposition 4.1. Proof of Proposition 4.1: For our DSF model, it is clear that T (u 1 , u 2 ) ≤ β ν . Hence we have that, Recall that the r.v.'s (β − β −1 )|G −1 are uniformly stochastically dominated with a random variable with exponential tail. Hence, it is not difficult to obtain for a constant c > 0 small enough. To sum up, we have: from which we conclude using (36).

The case d = 3
In this section we prove Theorem 1.1 for d = 3. To do that we first describe simultaneous renewal of two independent DSF paths and we use it to approximate the joint distribution of DSF paths at (joint) renewal steps when the paths are far apart. This section is motivated from [RSS15] and we only give a brief sketch here. For details we refer the reader to Sections 3.2 and 3.3 of [RSS15].
In order to construct two independent DSF paths, we start with two independent collections {U a w : w ∈ Z 3 } and {U b w : w ∈ Z 3 } of i.i.d. random variables where each random variable is uniformly distributed over S δ . These collections give two independent copies of perturbed point process given as V a := {u + U a u : u ∈ Z 3 } and V b := {u + U b u : u ∈ Z 3 }. The process {g Ind n (u 1 ) : n ≥ 0}, starting from u 1 , uses the perturbed points V a and the process {g Ind n (u 2 ) : n ≥ 0}, starting from u 2 , uses the perturbed points V b . For 1 ≤ i ≤ 2 and ≥ 0, let β Ind (u i ) denote the -th marginal renewal step for the marginal process {g Ind n (u i ) : n ≥ 0}. It follows that the collections, {(β Ind +1 (u 1 ) − β Ind (u 1 )) : ≥ 1} and {(β Ind +1 (u 2 ) − β Ind (u 2 )) : ≥ 1} form independent collections of i.i.d. renewal times with exponentially decaying tails. Now we define the sequence of simultaneous renewal steps for the two independent paths. We set J 0 , J 0 := 0. For m ∈ N let It follows that for all m ≥ 0, the r.v.'s J m and J m are finite a.s. Then for m ≥ 0 β Ind m (u 1 , u 2 ) := β Ind Jm (u 1 ) = β Ind J m (u 2 ), gives the sequence simultaneous renewals for two independent paths.
It follows that {β Ind m+1 (u 1 , u 2 ) − β Ind m (u 1 , u 2 ) : m ≥ 1} forms an i.i.d. collection of random variables. Further by Proposition 3.3 of [RSS15] we have that there exists positive constants C 0 , C 1 such that for all n ∈ N and for all m ≥ 0 we have Next we observe both the independent processes from the restarted points at the simultaneous renewal steps, i.e., {g Ind We observe that both the vertices have the same d-th coordinate. Recall that for x ∈ R d , the notation x = (x(1), · · · , x(d − 1)) ∈ R d−1 denotes the projection in terms of the first d − 1 coordinate axes. Then it follows that for d = 3, the processes {g Ind respectively. Clearly, both ψ u 1 m+1 and ψ u 2 m+1 have moments of all orders. The following properties of moments of these Z 2 -valued random vectors were observed in Proposition 3.4 of [RSS15].
(ii) E[(ψ u 1 (l)) m 1 (ψ u 1 (l)) m 2 ] depends only on m 1 and m 2 and becomes zero if at least one of m 1 and m 2 is odd.
Next we describe a coupling procedure which will allow us to compare the independent DSF paths at simultaneous renewal steps with joint DSF paths at (joint) renewal steps when the paths are far apart. We consider another collection {U c w : w ∈ Z 3 } of i.i.d. random variables independent of the collections {U a w : w ∈ Z 3 } and {U a w : w ∈ Z 3 }, such that U c w is uniformly distributed over S δ . We use these collections to construct a perturbed point process to construct the joint paths starting from u 1 and u 2 .
Set d min := ||u 1 − u 2 || 1 . With a slight abuse of notation, here || · || 1 gives the l 1 norm in R d−1 . Fix r < d min /3 and construct the new collection of i.i.d. random variables {Ũ w : w ∈ Z 3 } as follows:Ũ Using the collection {Ũ w : w ∈ Z 3 } we obtain a new perturbed point processṼ := {v +Ũ w : v ∈ Z 3 } (which has the same distribution as V ) and use it to construct the joint process {(g n (u 1 ), g n (u 2 )) : n ≥ 0} starting from u 1 and u 2 till their first joint renewal step β 1 (u 1 , u 2 ).
We observe that on the event A Good r := {2β 1 (u 1 , u 2 ) < r} we have β 1 (u 1 , u 2 ) = β Ind 1 (u 1 , u 2 ). Not only that, the trajectory of the independent DSF paths coincide with that of the joint paths till β 1 (u 1 , u 2 ) = β Ind 1 (u 1 , u 2 ). In particular, we have, where the last inequality follows from Proposition 3.1. The Markov property allows to extend this coupling for each subsequent renewal steps where for the -th renewal, the value of d min is updated as ||g β 1 (u 1 ,u 2 )) (u 1 ) − g β 1 (u 1 ,u 2 )) (u 2 )|| 1 . We follow the method used in [RSS15] to prove that the perturbed DSF is connected a.s. for d = 3. We recall that the auxiliary process obtained from restarted paths at (joint) renewal steps denoted by {Z (u 1 , u 2 ) : ≥ 1} (see (32)) forms a Z 2 valued Markov chain. Because of (33), it suffices to show that this Markov chain hits (0, 0) a.s. and to do that as in [RSS15], we apply Foster's criterion (see [A03], Proposition 5.3 of Chapter 1). We change the transition probability of Z from the state (0, 0) in any reasonable way so that this state no longer remains an absorbing state and the resulting Markov chain becomes irreducible. With slight abuse of notation, we continue to denote the modified chain by {Z : ≥ 0} and show that this chain is recurrent.
Next, exactly the argument as in Proposition 4.2 of [RSS15] gives us that, when the paths are far apart, Z (u 1 , u 2 ) is well approximated by the independent process in expectation. More precisely for m ≥ 1 we have where C (m) , C ). Clearly f (v) → ∞ as ||v|| → ∞. Using Taylor's expansion of the function h(t) = log(1 + t) and observing that the fourth derivative of h is always negative, we have where h (m) represents m-th derivative of h and the last inequality follows from (39). Now in order to calculate (40) we use properties of ψ = ψ (0,0) 1 that we observed earlier and obtain Putting the above values of moments and plugging the expressions for h (m) in (40) we have that the first sum in (40) is bounded by α||v|| 2 2 /[8(1 + ||v|| 2 2 ) 2 (log(1 + ||v|| 2 2 )) 3 /2] whereas the second sum is bounded by C 2 exp (−C 3 ||v|| 2 ) for a proper choice of C 2 , C 3 > 0. Hence we obtain that for all ||v|| 2 large enough. This implies that the modified Markov chain {Z : ≥ 1} is recurrent and completes the proof of Theorem 1.1 for d = 3.

Convergence to the Brownian web
This section is devoted to the proof of Theorem 1.2, i.e, that for d = 2 the scaled perturbed DSF converges to the Brownian web (BW). In fact we prove a stronger version of the theorem in the sense that we construct a dual process and show that under diffusive scaling the original process together with the dual process jointly converge to the BW and its dual. Towards this we will apply a robust technique that was developed in [CSST19] to study convergence to the BW for non-crossing path models. We first start with introducing the dual BW W. As in case of forward paths, one can consider a similar metric space of collection of backward paths denoted by ( Π, d Π ). The interaction between the paths in W and W is that of Skorohod reflection (see [STW00]). Now it is time to specify a dual graph G to the DSF G. The construction of the dual graph is not unique and though, using the discrete nature of the perturbed point process V , the construction of the dual graph can be made simpler in this case, we follow the construction of the dual graph from [CSST19].
We start by constructing the dual vertex set V . For any (x, t) ∈ R 2 , let (x, t) r ∈ V be the unique perturbed point such that • (x, t) r (2) < t, h((x, t) r )(2) ≥ t and π (x,t)r (t) > x where π (x,t)r denotes the path in X starting from (x, t) r ; • there is no path π ∈ X with σ π < t and π(t) ∈ (x, π (x,t)r (t)).
Hence, π (x,t)r is the nearest path in X to the right of (x, t) starting strictly before time t.
It is useful to observe that π (x,t)r is defined for any (x, t) ∈ R 2 . Similarly, π (x,t) l denotes the nearest path to the left of (x, t) which starts strictly before time t. Now, for each (x, t) ∈ V , the nearest left and right dual vertices are respectively defined as r (x,t) := (x + π (x,t)r (t))/2, t and l (x,t) := (x + π (x,t) l (t))/2, t .
Then, the dual vertex set V is given by V := { r (x,t) , l (x,t) : (x, t) ∈ V }. Next, we need to define the dual ancestor h(y, s) of (y, s) ∈ V as the unique vertex in V given by h(y, s) := l (y,s)r if (y, s) r (2) > (y, s) l (2) r (y,s) l otherwise.
The dual edge set E is then given by E := { (y, s), h(y, s) : (y, s) ∈ V }. Clearly, each dual vertex has exactly one outgoing edge which goes in the downward direction. Hence, the dual graph G := ( V , E) does not contain any cycle or loop. This forest G is entirely determined from G without any extra randomness. The dual (or backward) path π (y,s) ∈ Π starting at (y, s) is constructed by linearly joining the successive h(·) steps. Thus, X := { π (y,s) : (y, s) ∈ V } denotes the collection of all dual paths obtained from G.
For each n ≥ 1, the closure of X n in ( Π, d Π ), still denoted by X n , is a ( H, B H )-valued random variable.
Recall that the perturbed DSF paths are non-crossing and the convergence criteria to the BW for non-crossing path models are provided in [FINR04]. The reader may refer to [SSS17] for a very complete overview on the topic. Let Ξ ⊂ Π. For t > 0 and t 0 , a, b ∈ R with a < b, consider the counting random variable η Ξ (t 0 , t; a, b) defined as η Ξ (t 0 , t; a, b) := # π(t 0 + t) : π ∈ Ξ, σ π ≤ t 0 and π(t 0 ) ∈ [a, b] which considers all paths in Ξ, born before t 0 , that intersect [a, b] at time t 0 and counts the number of different positions these paths occupy at time t 0 + t. Theorem 2.2 of [FINR04] lays out the following convergence criteria .
Theorem 5.2 (Theorem 2.2 of [FINR04]). Let {Ξ n : n ∈ N} be a sequence of (H, B H ) valued random variables with non-crossing paths. Assume that the following conditions hold: (I 1 ) Fix a deterministic countable dense set D of R 2 . For each x ∈ D, there exists π x n ∈ Ξ n such that for any finite set of points x 1 , . . . , x k ∈ D, as n → ∞, we have (π x 1 n , . . . , π x k n ) converges in distribution to (W x 1 , . . . , W x k ), where (W x 1 , . . . , W x k ) denotes coalescing Brownian motions starting from the points x 1 , . . . , x k .
Then Ξ n converges in distribution to the standard Brownian web W as n → ∞.
Let us first mention that for a sequence of (H, B H )-valued random variables {Ξ n : n ∈ N} with non-crossing paths, Criterion (I 1 ) implies tightness (see Proposition B.2 in the Appendix of [FINR04] or Proposition 6.4 in [SSS17]) and hence subsequential limit(s) always exists. Moreover, Criterion (B 1 ) has in fact been shown to be redundant with (I 1 ) for models with non-crossing paths (see Theorem 6.5 of [SSS17]). Actually Condition (I 1 ) implies that subsequential limit Ξ contains coalescing Brownian motions starting from all rational vectors and hence contain a copy of the standard Brownian web (W). Criterion (B 2 ) ensures that the limiting random variable does not have extra paths and hence the limit must be W.
Criterion (B 2 ) is often verified by applying an FKG type correlation inequality together with an estimate on the distribution of the coalescence time between two paths. However, FKG is a strong property and very difficult to obtain for models with complicate dependencies. We will follow a more robust technique developed in [CSST19] and applicable for non-crossing path models. We apply Theorem 32 of [CSST19] to obtain joint convergence for the DSF and its dual to the Brownian web and its dual. (i) For each n ≥ 1, paths in Ξ n do not cross (backward) paths in Ξ n almost surely: there does not exist any π ∈ Ξ n , π ∈ Ξ n and t 1 , t 2 ∈ (σ π , σ π ) such that ( π(t 1 ) − π(t 1 ))( π(t 2 ) − π(t 2 )) < 0 almost surely.
It is useful to mention here that there are several other approaches to replace Criterion (B 2 ). Long before, Criterion (E) was proposed by Newman et al [NRS05] which is applicable even for models with crossing paths. [SSS17] provided a new criterion in Theorem 6.6 replacing (B 2 ), called the wedge condition. Theorem 5.3 appears as a slight generalization of Theorem 6.6 of [SSS17] by considering the joint convergence and it replaces the wedge condition by the fact that no limiting primal and dual paths can spend positive Lebesgue time together. In the next section we show that the conditions of Theorem 5.3 hold for the diffusively scaled DSF and its dual {(X n , X n ) : n ∈ N}. Finally we make the following remark regarding the existence of bi-infinite path for the perturbed DSF for d = 2. We mention that following the arguments arguments of Section 4 of [GRS04], which is based on a Burton-Keane argument, one can show that there is no bi-infinite path for the perturbed DSF a.s. for any d ≥ 2.
Remark 5.4. From the construction of the dual graph it is evident that the DSF has a bi-infinite path if and only if the dual graph is not connected. If there are scaled dual paths which do not coalesce but converge to coalescing Brownian motions then there must be scaled forward paths entrapped between these scaled dual paths. Further, the joint convergence to the double Brownian web (W, W) forces that there must be a limiting forward Brownian path approximating this sequence of entrapped forward scaled paths. Further this limiting forward Brownian path must spend positive Lebesgue measure time together with a backward Brownian path which contradicts the properties of (W, W).

Verification of conditions of Theorem 5.3
In this section, we show that the sequence of diffusively scaled path families {(X n , X n ) : n ≥ 1} obtained from the DSF and its dual forest satisfies the conditions in Theorem 5.3.
Conditions (i) and (iii) of Theorem 5.3 hold by construction. Indeed, paths of X do not cross (backward) paths of X with probability 1 and the same holds for X n and X n for any n ≥ 1. Moreover, the collection {( π n (σ πn ), σ πn ) : π n ∈ Ξ n } of all starting points of the scaled backward paths in Ξ n becomes dense in R 2 as n → ∞.
From now on, the diffusively scaled sequence {X n : n ≥ 1} is considered w.r.t. these parameters, but for ease of writing, we drop (γ, σ) from our notation. Proposition 3.3 together with Corollary 3.4 allow us to apply Donsker's invariance principle to show that π 0 n converges in distribution in (Π, d Π ) to B 0 a standard Brownian motion started at 0. While working with multiple paths the essential idea is that the multiple paths of the DSF, when they are far away, can be approximated as independent DSF paths. Using Proposition 4.1 we can show that when two DSF paths are close enough, they coalesce quickly. This strategy was first developed by Ferrari et al in [FFW05] to deal with dependent paths, and later modified in [RSS15] and [CSST19] to deal with long range interactions. Since the proof here is the same to that of [CSST19] we do not provide the details here and for more details we refer the reader to Section 6, Section 5.1 of [RSS15] and Section 6.2.1 of [CSST19].
To show condition (iv), we mainly follow Section 6.2.2 of [CSST19] and the coalescence time estimate given in Proposition 4.1 serves as a key ingredient. Let (Z, Z) be any subsequential limit of {(X n , X n ) : n ≥ 1}. By Skorohod's representation theorem we may assume that the convergence happens almost surely. With slight abuse of notation we continue to denote that subsequence by {(X n , X n ) : n ≥ 1}.
It was shown in Section 6.2.2 of [CSST19] that to show P(A(δ, m) = 0) it suffices to prove the following lemma.
For the proof of Lemma 5.5 we essentially follow [CSST19] but the discrete nature of the perturbed point process makes the proof easier. It is useful to mention that still we have to deal with the non-Markovian nature of DSF paths.

Appendix
In order to make this article complete, in this section we give more details to prove that for γ and σ > 0 as specified in (43), the sequence X n (γ, σ) satisfies condition (I 1 ). In Section 3 we proved a renewal property for perturbed DSF paths which will be used to show that an appropriately scaled perturbed DSF path converges to a Brownian motion. The essential idea is that, perturbed DSF paths behave independently when they are far apart and coalesce very quickly when they come close. This idea was initially introduced by Ferrari et. al. [FFW05] and later modified in [RSS15] and [CSST19] to deal with more complex dependencies. Here, we follow a combination of arguments in [RSS15] and [CSST19] to prove condition (I 1 ) for our model. We first recall that for a path π u starting from u, the scaled path is defined by π u n = π u n (γ, σ) : [u(2)/nγ, ∞] → [−∞, ∞] such that π u n (t) = π(nγt)/ √ nσ where γ, σ > 0 as specified in (43). Proposition 3.3 together with Corollary 3.4 allow us to apply the same arguments of Proposition 5.2 [RSS15] to conclude that the scaled DSF path π 0 n converges to the Brownian motion B 0 starting from origin.
By translation invariance of our model, it also follows that Fix x ∈ R 2 . Now for any {x n : n ∈ N} with (x n (1)/ √ nσ, n/γ) → x as n → ∞ we have that the DSF paths π xn starting at x n converges to the Brownian motion starting at x. This completes the proof for condition (I 1 ) for k = 1.
For verifying condition (I 1 ) for multiple paths, we require an estimate on the displacements of the DSF paths in the presence of some information. The next proposition gives such an estimate and is motivated from Proposition 35 of [CSST19].
only points in V ∩ R. We can then write: where the last equality follows since the path π ( 2m α ,0) new uses independently distributed perturbed points inside this rectangle R and hence the event A does not depend on the information about V inside the rectangle R. We conclude using Proposition 3.1.
Similar argument using paths starting from the point (− 2m α , 0) completes the proof.
Note that A consists of all k-tuples of continuous paths such that the k th path intersects at least one of the other k − 1 paths π 1 , . . . , π k−1 and it immediately crosses one particular such path. Let B x k be a standard Brownian motion starting at x k and independent of (W x 1 , . . . , W x k−1 ), independent coalescing Brownian motions starting from x 1 , . . . , x k−1 . From the path property of independent Brownian motions, it follows that P (W x 1 , . . . , W x k−1 , B x k ) ∈ A = 1.