DIMACS Focus on Discrete Probablity Seminar


Random Walks on Rooted Trees


Ryan Martin
Mathematics Department, Rutgers University


Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University.


3:30 PM
Thursday, November 21, 1996

For arbitrary positive integers $h$ and $m$, we consider a family of all rooted trees of height $h$ having exactly $m$ vertices at distance $h$ >from the root. We refer to such trees as $(h,m)$-trees. For a tree $T$ >from this family, we consider a simple random walk on $T$ which stars at the root and terminates when it visits one of the $m$ vertices at distance $h$ from the root. Consider a problem of finding a tree in the family on which the expected time of a random walk is minimal (an extremal tree). In this paper we present some properties of extremal trees for arbitrary $h$ and $m$, completely describe extremal $(2,m)$- and $(3,m)$-trees, describe a tree which provides a lower bound for the expected time of any $(4,m)$-tree, and refute the conjecture that the complete binary tree is extremal in the class of all $(h,2^h)$-trees having degrees of their roots at least 2.

Document last modified on September 24, 1996