DIMACS Focus on Discrete Probability Seminar


Random Walks on Rooted Trees


Martin Ryan
Rutgers University


CoRE Building, Room 431
Busch Campus, Rutgers University.


3:30 - 4:30 PM
Thursday, March 13, 1997

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 February 14, 1997