 |
|
|
| | | | | |
|
|
|
|
|
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
|
Abstract
Consider the d-dimensional lattice 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 degree (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 greater than or equal to 4. In addition, for any dimension, we show that there is no bi-infinite path in the tree.
|
Full text: PDF
Pages: 2160-2189
Published on: December 1, 2008
|
Bibliography
- Alexander, Kenneth S. Percolation and minimal spanning forests in infinite graphs.
Ann. Probab. 23 (1995), no. 1, 87--104. MR1330762 (96c:60114)
- 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)
- 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)
- Bordenave, Charles. Navigation on a Poisson point process.
Ann. Appl. Probab. 18 (2008), no. 2, 708--746. MR2399710
- 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)
- 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)
- 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)
- 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)
- Howard, A. D. Simulation of stream networks by headward growth and branching. Geogr. Anal. , (1971), no. 3, 29--50.
- Leopold, L. B.; Langbein, W. B.
The concept of entropy in landscape evolution. U.S.
Geol. Surv. Prof. Paper (1962), 500-A.
- Nandi, A.K.; Manna, S.S.
A transition from river networks to scale-free networks.
New J. Phys. (2007), {bf 9 }, 30,
- 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)
- Pemantle, Robin. Choosing a spanning tree for the integer lattice uniformly.
Ann. Probab. 19 (1991), no. 4, 1559--1574. MR1127715 (92g:60014)
- Rodriguez-Iturbe, I.; Rinaldo, A.
Fractal river basins: chance and
self-organization.Cambridge Univ. Press , New York. (1997)
- Scheidegger, A. E. A stochastic model
for drainage pattern into an intramontane trench. Bull. Ass.
Sci. Hydrol. (1967), 12, 15--20.
- 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)
- Tóth, Bálint; Werner, Wendelin. The true self-repelling motion.
Probab. Theory Related Fields 111 (1998), no. 3, 375--452. MR1640799 (99i:60092)
|
|
|
|
|
|
|
|
| | | | |
Electronic Journal of Probability. ISSN: 1083-6489 |
|
Context