Growing Binary Trees in a Random Environment

Abstract

A class of binary trees that grow in a random environment. where the state of the environment can change at every vertex of the trees is studied. The trees considered are single-type and two-type binary trees that grow in a two-state Markovian environment. For each kind of tree, the conditions on the environment process for extinction of the tree are determined, and the problem of calculating the expected number of vertices of the tree is addressed. Different ways of growing the trees are compared. © 1993 IEEE