Random directed trees and forest - drainage networks with dependence

Siva R Athreya (Indian Statistical Institute, Bangalore)
Rahul Roy (Indian Statistical Institute, Delhi)
Anish Sarkar (Indian Statistical Institute, Delhi)


Consider the $d$-dimensional lattice $\mathbb 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$ in the $45^\circ$ (downward) light cone generated at $v$. In case of non-uniqueness 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 \geq 4$. In addition, for any dimension, we show that there is no bi-infinite path in the tree.

Full Text: Download PDF | View PDF online (requires PDF plugin)

Pages: 2160-2189

Publication Date: December 1, 2008

DOI: 10.1214/EJP.v13-580


  1. Alexander, Kenneth S. Percolation and minimal spanning forests in infinite graphs. Ann. Probab. 23 (1995), no. 1, 87--104. MR1330762 (96c:60114)
  2. Asmussen, Søren. Applied probability and queues. Wiley Series in Probability and Mathematical Statistics: Applied Probability and Statistics. John Wiley & Sons, Ltd., Chichester, 1987. x+318 pp. ISBN: 0-471-91173-9 MR0889893 (89a:60208)
  3. Baccelli, Francois; Bordenave, Charles. The radial spanning tree of a Poisson point process. Ann. Appl. Probab. 17 (2007), no. 1, 305--359. MR2292589 (2008a:60025)
  4. Bordenave, Charles. Navigation on a Poisson point process. Ann. Appl. Probab. 18 (2008), no. 2, 708--746. MR2399710
  5. Ferrari, P. A.; Fontes, L. R. G.; Wu, Xian-Yuan. Two-dimensional Poisson trees converge to the Brownian web. Ann. Inst. H. Poincaré Probab. Statist. 41 (2005), no. 5, 851--858. MR2165253 (2006h:60143)
  6. Ferrari, P. A.; Landim, C.; Thorisson, H. Poisson trees, succession lines and coalescing random walks. Ann. Inst. H. Poincaré Probab. Statist. 40 (2004), no. 2, 141--152. MR2044812 (2005e:60105)
  7. Fontes, L. R. G.; Isopi, M.; Newman, C. M.; Ravishankar, K. The Brownian web: characterization and convergence. Ann. Probab. 32 (2004), no. 4, 2857--2883. MR2094432 (2006i:60128)
  8. Gangopadhyay, Sreela; Roy, Rahul; Sarkar, Anish. Random oriented trees: a model of drainage networks. Ann. Appl. Probab. 14 (2004), no. 3, 1242--1266. MR2071422 (2005i:60194)
  9. Howard, A. D. Simulation of stream networks by headward growth and branching. Geogr. Anal. , (1971), no. 3, 29--50.
  10. Leopold, L. B.; Langbein, W. B. The concept of entropy in landscape evolution. U.S. Geol. Surv. Prof. Paper (1962), 500-A.
  11. Nandi, A.K.; Manna, S.S. A transition from river networks to scale-free networks. New J. Phys. (2007), {bf 9 }, 30,
  12. Newman, C. M.; Stein, D. L. Ground-state structure in a highly disordered spin-glass model. J. Statist. Phys. 82 (1996), no. 3-4, 1113--1132. MR1372437 (97a:82054)
  13. Pemantle, Robin. Choosing a spanning tree for the integer lattice uniformly. Ann. Probab. 19 (1991), no. 4, 1559--1574. MR1127715 (92g:60014)
  14. Rodriguez-Iturbe, I.; Rinaldo, A. Fractal river basins: chance and self-organization.Cambridge Univ. Press , New York. (1997)
  15. Scheidegger, A. E. A stochastic model for drainage pattern into an intramontane trench. Bull. Ass. Sci. Hydrol. (1967), 12, 15--20.
  16. Spitzer, Frank. Principles of random walk. The University Series in Higher Mathematics D. Van Nostrand Co., Inc., Princeton, N.J.-Toronto-London 1964 xi+406 pp. MR0171290 (30 #1521)
  17. Tóth, Bálint; Werner, Wendelin. The true self-repelling motion. Probab. Theory Related Fields 111 (1998), no. 3, 375--452. MR1640799 (99i:60092)

Creative Commons License
This work is licensed under a Creative Commons Attribution 3.0 License.