Theoretical Statistics and Mathematics Unit, ISI Delhi

Random Oriented Trees: A Model of Drainage Networks

by Sreela Gangopadhyay, Rahul Roy and Anish Sarkar

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
co-ordinates of $v$ and $w$ satisfy $w(d) = v(d) - 1$. 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 it is a infinite collection of distinct trees for
$d ≥ 4$. In addition, for any dimension, we obtain central limit theorems of (a) the number of vertices of a fixed
degree $ν$ and (b) of the number of edges of a fixed length $l$. These results are obtained by using the martingale
convergence theorem and a coupling of the process with independent random walks.

isid/ms/2002/05 [fulltext]

Click here to return to Preprints Page