{'fraction_non_alphanumeric': 0.06911566294615479, 'fraction_numerical': 0.022323071262112106, 'mean_word_length': 3.433659597607395, 'pattern_counts': {'":': 0, '<': 14, '<?xml version=': 0, '>': 11, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 16, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Random oriented Trees: a Model of drainage networks

Consider the d-dimensional lattice Z^d where each vertex is ``open'' or ``closed'' with probability p or 1-p, respectively. An open vertex v is connected by an edge to the closest open vertex w such that the dth co-ordinates of v and w satisfy w(d)=v(d)-1. In case of nonuniqueness of such a vertex w, we choose any one of the closest vertices with equal probability and independently of the other random mechanisms. It is shown that this random graph is a tree almost surely for d=2 and 3 and it is an infinite collection of distinct trees for d\geq4. In addition, for any dimension, we show that there is no bi-infinite path in the tree and we also obtain central limit theorems of (a) the number of vertices of a fixed degree \nu and (b) the number of edges of a fixed length l.

1. Introduction. Leopold and Langbein (1962) introduced a geometric model of natural drainage network which they described as using a sheet of rectangular cross-section graph paper, each square is presumed to represent a unit area. Each square is to be drained, but the drainage channel from each square has equal chance of leading off in any of the four cardinal directions, subject only to the condition that, having made a choice, flow in the reverse direction is not possible. Under these conditions it is possible for one or more streams to flow into a unit area, but only one can flow out.
Subsequently Scheidegger (1967) introduced a direction of flow. In his study of Alpine valleys, he imposed conditions on the Leopold and Langbein model by requiring that the drainage paths be in the "direction of high gradients between watershed and main valleys." Thus the drainage forms an oriented network, with a square emptying to one of its two neighbors in a preferred direction. Howard (1971) removed the restriction of drainage to a neighboring square and modelled a network to include "headward growth and branching in a random fashion." Rodriguez-Iturbe and Rinaldo (1997) present a survey of the development of this field.
The random graph we study here follows the one described by Howard (1971) with the caveat that a stream is not permitted to terminate or become inactive. Thus we consider the d-dimensional lattice Z d where each vertex is "open" or "closed" with probability p or 1−p, respectively. The open vertices represent the water sources. An open vertex v is connected by an edge to the closest open vertex w such that the dth co-ordinates of v and w satisfy w(d) = v(d) − 1. In case of nonuniqueness of such a vertex w, we choose any one of the closest vertices with equal probability and independently of the other random mechanisms. These edges represent the channels of flow in the drainage network.
Our main result (Theorem 2.1) is that, for d = 2 and 3, all the tributaries connect to form one single delta, while for d ≥ 4, there are infinitely many deltas, each with its own distinct set of tributaries. In this connection it is worth noting that (Theorem 2.2) there is no main river, in the sense that there is no bi-infinite river; instead, each tributary has its own distinct source. In addition, for any dimension, we obtain central limit theorems of (a) the number of sites where a fixed number ν of tributaries drain, as well as of (b) the number of channels of a fixed length l.
Similar tree-forest dichotomies have been studied for the uniform spanning tree model by Pemantle (1991) and for the minimal spanning tree model by Newman and Stein (1996). Ferrari, Landim and Thorisson (2002) have obtained similar results for a continuous version of this model.
In two dimensions we obtain the main result by showing that the distance between two streams starting at two different sites forms a martingale and thereby invoking the martingale convergence theorem. For three dimensions we employ a technique based on Lyapunov functions, while in four or higher dimensions we couple the streams starting at two different sites with two independent and identically distributed random walks starting at these two sites. To show that there are no bi-infinite paths in the graph we utilize the stationarity of the model and use a Burton-Keane type argument. The limit theorems are obtained by checking that the random processes satisfy the conditions needed to apply Lyapunov's central limit theorem.
The formal details of the model and the statements of results are in the next section.
2. The model and statement of results. Let Ω = {0, 1} Z d and let F be the σ algebra generated by finite-dimensional cylinder sets. On (Ω, F) we RANDOM ORIENTED TREES 3 assign a product probability measure P p which is defined by its marginals as d. uniform (0, 1] random variables on some probability space (Ξ, S, µ). Here and subsequently we express the co-ordinates of a vector u as u = (u(1), . . . , u(d)).
For u ∈ Z d , let Note that for p > 0, N u is nonempty almost surely and that N u is defined for all u, irrespective of it being open or closed. For u ∈ Z d , let Again note that for p > 0 and for each u Consider that graph G = (V, E) consisting of the vertex set V and edge set E. For p = 0, V = ∅ almost surely, and, for p = 1, u, v ∈ E if and only if u(i) = v(i) for all i = d and |u(d) − v(d)| = 1. Also, for a vertex u ∈ V(ω, ξ), there is exactly one edge "going down" from u; that is, there is a unique edge u, v with v(d) ≤ u(d). Thus the graph G contains no loops almost surely. Hence, for 0 < p < 1, the graph G consists of only trees. Our first result is Theorem 2.1. Let 0 < p < 1. For d = 2 and d = 3, G consists of one single tree P-almost surely, while for d ≥ 4, G is a forest consisting of infinitely many disjoint trees P-almost surely.
Regarding the geometric structure of the graph G, we have Theorem 2.2. Let 0 < p < 1. For any d ≥ 2, the graph G contains no bi-infinite path P-almost surely. Now for ν ≥ 0, let S n be the number of vertices in V ∩ ([1, n] d ) of the graph G with degree ν + 1. Also, for l ≥ 1, let L n be the number of edges of L 1 -length l in the graph G with one end vertex in V ∩ ([1, n] d ).
Theorem 2.3. As n → ∞: converges weakly to a normal random variable; converges weakly to a normal random variable.
Finally, for d = 2, given that a vertex v is open, the following proposition gives the exact distribution of the degree of v.
Proposition 2.1. Given that a vertex v is open, the degree of the vertex in the graph G has the same distribution as that of 1 + Y + X 1 + X 2 , where Y , X 1 and X 2 are independent nonnegative random variables such that Y = 0, with probability 1 − p, 1, with probability p, Thus the expected degree of a vertex, given that it is open, is 2.
Remark 2.1. As in Lemma 7 of Aldous and Steele (1992), using the ergodicity of the process, it may be shown that in any dimension, the expected degree of a vertex, given that it is open, is 2.
3. Proof of Theorem 2.1. We fix 0 < p < 1 and for u, v ∈ Z d−1 consider the d-dimensional vectors u := (u, 0) and v := (v, 0) and let (X n u , −n) := h n (u), where h n denotes the n-fold composition of h defined in (1). For Z n (= Z n (u, v)) := X n u − X n v , we first observe that it is a time-homogeneous Markov chain with state space Z d−1 ; indeed, this follows on writing {Z n+1 = z n+1 , Z n = z n , . . . ,

5
X n x 0 = x n , X n x 0 +z 0 = x n + z n , . . . , X 0 x 0 = x 0 , X 0 x 0 +z 0 = x 0 + z 0 } and using the Markovian property of the process {(X n u , X n v ) : n ≥ 0}. The connectedness or otherwise of the graph G is equivalent to whether or not Z n is absorbed at the origin. For d = 2 and 3, we show that Z n gets absorbed at the origin, 0 ∈ Z d−1 with probability 1; while for d ≥ 4, Z n is a transient Markov chain and hence has a positive probability of not being absorbed. In this connection observe that instead of the above Z n , if we had considered a modified Markov chainZ n , where 0 is no longer an absorbing state, but from 0 we move in one step to some fixed vertex u = 0 with probability 1 and the other transition probabilities are kept unchanged, then to show that the original process Z n is absorbed at 0 almost surely, it suffices to show that the modified Markov processZ n is recurrent. A more formal argument for this would require Z n andZ n to be coupled together until they hit the origin, which occurs almost surely if the modified process is recurrent. For the case d = 3, we will show thatZ n is recurrent. The proof is divided into three sections according as d = 2, d = 3 and d ≥ 4.
3.1. d = 2. Fix i < j and observe that X n i ≤ X n j for every n ≥ 1, where X n i and X n j are as defined earlier. Thus the Markov chain Z n := X n j − X n i with Z 0 = j − i has as its state space the set of all nonnegative integers. Since the marginal distributions of the increments of X n i and X n j are identical with finite means, {Z n : n ≥ 0} is a nonnegative martingale. Hence, by the martingale convergence theorem [see Billingsley (1979), Theorem 35.4, page 416], Z n converges almost surely as n → ∞. Since {Z n : n ≥ 0} is also a timehomogeneous Markov chain with 0 as the only absorbing state, we must have Z n → 0 as n → ∞ with probability 1. Since this is true for all i < j, we have the result for d = 2.
3.2. d = 3. Throughout this section the letters u, v in bold font denote vectors in Z 3 , u, v in roman font denote vectors in Z 2 and u, v in italic font denote integers. Fix two vectors u := (u, 0) and v := (v, 0) in Z 2 × {0} and let Z n (=Z n (u, v)) be the time-homogeneous Markov chain with state space Z 2 as defined at the beginning of this section. We shall exhibit, by a Lyapunov function technique, that this Markov chainZ n is recurrent, thereby showing that Z n is absorbed at the origin with probability 1.
Consider the function f : Asmussen (1987), Proposition 5.3 of Chapter I, page 18] the following lemma implies thatZ n is recurrent.
which holds because the fourth derivative The first three derivatives of g, which we will be needing shortly, are Note that, for all s large, .
Assuming for the moment that (we will prove this shortly), for some α > 0, as x 2 → ∞, and using the above estimates and expression for derivatives, we have, for all β := x 2 2 large and for some nonnegative constants C 1 and C 2 , .

7
The term inside the square brackets tends to −∞ as β → ∞; therefore, for all sufficiently large β, the term is negative. Thus to complete the proof of the lemma we need to show (3)-(5). Let D k := {v ∈ Z 2 : v 1 ≤ k} denote "L 1 -diamond" of radius k and δD k := {v ∈ Z 2 : v 1 = k} its boundary, where · 1 denotes the L 1 norm. Consider the probability distribution of the step size of the random walk, associated with the tree generated by one particle, that is, the distribution of X 1 o : where o := (0, 0) is the origin and #A denotes the cardinality of the set A.
For any k ≥ 1 and i, j ≥ 0, define Since (−u 1 , −u 2 ) ∈ D k whenever (u 1 , u 2 ) ∈ D k , it is clear that, for every k ≥ 1 we have m i (k) = 0 for all odd i and (7) m i,j (k) = 0 whenever either i or j is odd.
Further, since #D k = 1 + 2k(k + 1) and #δD k = 4k, we have that, for all even i, Similarly, when both i and j are even, Further, p u being the same for every u on δD k , the various quantities m i and m i,j remain unchanged if in their definitions we had considered u 2 instead of u 1 .
= C 5 (k) + C 6 (k)x 2 1 , where, as above, C 5 (k) and C 6 (k) are both polynomials in m i (k) and m i,j (k), each of which converges to the corresponding polynomial in m i and m i,j as k → ∞. Similar calculations show that T 1, as k → ∞. This establishes (5) and completes the proof of Lemma 3.1.
3.3. d ≥ 4. For notational simplicity we present the proof only for d = 4. Throughout this section the letters u, v in bold font denote vectors in Z 4 , u, v in roman font denote vectors in Z 3 and u, v in italic font denote integers. We first show that on Z 4 , the graph G admits two distinct trees with positive probability, that is, Consider a random vector X ∈ Z 3 defined as follows: for k ≥ 0, let ∆ k := {v ∈ Z 3 : v 1 ≤ k} denote the three-dimensional diamond of radius k and let δ∆ k := {v ∈ Z 3 : v 1 = k} denote its boundary. As in (6), the distribution of the random vector X is given by where o := (0, 0, 0) and #A denotes the cardinality of the set A. It may easily be checked that v∈Z 3 P (X = v) = 1.
Next, for a fixed vector u := (u(1), . . . , u(4)) ∈ Z 4 , consider the graph H := (V ∪ {u}, E ∪ { u, h(u) }). For n ≥ 0, let h n (u) := (g n (u), t) for g n (u) ∈ Z 3 and t = u(4)− n ∈ Z. Here we take h 0 (u) = u. Observe that for fixed u, g n (u) has the same distribution as (u(1), u(2), u(3)) + n i=1 X i , where X 1 , X 2 , . . . are i.i.d. copies of X. Hence {g n (u) : n ≥ 0} is a symmetric random walk starting at g 0 (u) = (u(1), u(2), u(3)), with i.i.d. steps, each step size having distribution X. However, for v ∈ Z 4 with v(4) = u(4), in the graph (V ∪ {u, v}, E ∪ { u, h(u) , v, h(v) }) the processes {g n (u)} n≥0 and {g n (v)} n≥0 are not independent and so, to obtain our theorem, we cannot use the fact that, with positive probability, two independent random walks on Z 3 do not intersect. Nonetheless, if u and v are sufficiently far apart, their dependence on each other is weak. In the remainder of this section we formalize this notion of weak dependence by coupling two independent random walks and the processes {g n (u), g n (v) : n ≥ 0} and obtain the desired result.
Lemma 3.2. For 0 < ε < 1/3, there exist constants C, β > 0 and n 0 ≥ 1 such that, for all n ≥ n 0 , Assuming the above lemma, we proceed to complete the proof of (12). We shall return to the proof of the lemma later.
We now describe a method to couple the trees and the independent random walks. Before embarking on the formal details of the coupling procedure, we present the main idea.
From a vertex 0 we construct the "path" If the two diamonds are not disjoint, then we have to define h 1 (v) taking into account the configuration inside the diamond D. Similarly, we may obtain h 2 (v) by considering the diamonds {u ∈ Z 3 : u − X 1 1 ≤ X 2 1 } and {u ∈ Z 3 : u − g 1 (v) 1 ≤ Y 2 1 }. Note that if, for each i = 1, . . . , n, the two diamonds involved at the ith stage are disjoint, then the growth of the tree {(h i (0), h i (v)) : 0 ≤ i ≤ n} is stochastically equivalent to that of the pair of independent "random walks" (0 . We start with two vertices u := (u, 0) and v : Let k u and l v be defined as k u := min{k : U u 1 (z) < p for some z ∈ (u + ∆ k )}, l v := min{l : U v 1 (z) < p for some z ∈ (v + ∆ l )}.
With the above estimate at hand, we look at the process {(φ n (u), ζ n (v)) : n ≥ 0}. Without loss of generality we take u = o. For ε > 0 and constant K > 0 (to be specified later), define B n,ε (v) := {ζ n 4 (v) ∈ φ n 4 (o) + (∆ n 2(1+ε) \ ∆ n 2(1−ε) ), This event is an independent random walk version of the event A n,ε (v, 0) defined in (14), except that here we require that the two random walks come no closer than K log n at any stage. We will show that there exists α > 0 such that for some constant C 3 > 0. Since to prove (19) it suffices to show the following.

S. GANGOPADHYAY, R. ROY AND A. SARKAR
Of the terms in the above inequality, we have and we use Berry-Essen bounds [see Chow and Teicher (1978), Corollary 9.4, page 300], to obtain for some constant C 12 > 0. Combining (22)-(24), we have Lemma 3.3(c).
Thus, by translation invariance and ergodicity, we have that, for all k ≥ 2, P{G contains at least k trees} = 1.
This shows that G contains infinitely many trees almost surely.
To complete the proof, we have to show that En n → 0 in probability as n → ∞. First observe that number of terms in E n is at most ⌊n δ ⌋. Therefore taking δ = 1/2, from (30) we have E(E 4 n ) ≤ Cn 3 . Hence, for ε > 0, P(|E n | > nε) ≤ E(E 4 n ) n 4 ε 4 → 0 as n → ∞.
Note that to compute s 2 we use the fact that {(Y i,j , Y i,j+1 )} i≥1 is an αmixing sequence.
Similarly, in two dimensions, given that a vertex v is open, the distribution of the number of edges of length l "going up" from v is binomial with parameters 2 and (1 − p 2 )(1 − p) 2l−1 .
Remark 6.1. From the above distributions we may calculate the quantities E(S n ), Var(S n ), s 2 and the related quantities involving L n required in Theorem 2.3 for two dimensions.