Random oriented trees: a model of drainage networks. (English) Zbl 1047.60098

Summary: 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\) such that the \(d\)th coordinates 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 independent 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 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\).


60K35 Interacting random processes; statistical mechanics type models; percolation theory
05C80 Random graphs (graph-theoretic aspects)
Full Text: DOI arXiv


[1] Aldous, D. and Steele, J. M. (1992). Asymptotics for Euclidean minimal spanning trees on random points. Probab. Theory Related Fields 92 247–258. · Zbl 0767.60005
[2] Asmussen, S. (1987). Applied Probability and Queues . Wiley, Chichester. · Zbl 0624.60098
[3] Billingsley, P. (1979). Probability and Measure . Wiley, New York. · Zbl 0411.60001
[4] Burton, R. M. and Keane, M. S. (1989). Density and uniqueness in percolation. Comm. Math. Phys. 121 501–505. · Zbl 0662.60113
[5] Chow, Y. S. and Teicher, H. (1978). Probability Theory : Independence , Interchangeability , Martingales . Springer, New York. · Zbl 0399.60001
[6] Ferrari, P. A., Landim, C. and Thorisson, H. (2002). Poisson trees and coalescing random walks. · Zbl 1042.60064
[7] Howard, A. D. (1971). Simulation of stream networks by headward growth and branching. Geogr. Anal. 3 29–50.
[8] Leopold, L. B. and Langbein, W. B. (1962). The concept of entropy in landscape evolution. U.S. Geol. Surv. Prof. Paper 500-A.
[9] Newman, C. M. and Stein, D. L. (1996). Ground-state structure in a highly disordered spin-glass model. J. Statist. Phys. 82 1113–1132. · Zbl 1042.82568
[10] Pemantle, R. (1991). Choosing a spanning tree for the integer lattice uniformly. Ann. Probab. 19 1559–1574. JSTOR: · Zbl 0758.60010
[11] Rodriguez-Iturbe, I. and Rinaldo, A. (1997). Fractal River Basins : Chance and Self-Organization. Cambridge Univ. Press. · Zbl 0946.82039
[12] Scheidegger, A. E. (1967). A stochastic model for drainage pattern into an intramontane trench. Bull. Ass. Sci. Hydrol. 12 15–20.
[13] Spitzer, F. (1964). Principles of Random Walk. Van Nostrand, Princeton, NJ. · Zbl 0119.34304
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.