Height of a Random Tree

M. Krikun

2000, v.6, Issue 2, 135-146


We consider continuous time countable Markov chain $G(t)$, the states are finite trees. At $t=0$ the tree consists of one only vertex $V_{0}$, we call it the root. There are two types of transitions. For each vertex $V$ one appends with rate $\lambda>0$ a new link, incident to $V$ and having one new vertex. Each link can be deleted with rate $\mu \geq 0$. When a link is deleted, its ends are identified, being glued into one vertex. We define the height of a tree, $H(t)$, as the length of the maximal path from the root. We prove that if $\mu =0$, then the height has a linear growth. If $\mu >0$, then the growth of the height is nonlinear.

Keywords: random trees,graph grammars


Please log in or register to leave a comment

There are no comments yet