# DIMACS Focus on Discrete Probability Seminar

## Title:

Random Walks on Rooted Trees

## Speaker:

- Martin Ryan
- Rutgers University

## Place:

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

## Time:

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

Abstract:
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