# DIMACS Focus on Discrete Probablity Seminar

## Title:

Random Walks on Rooted Trees

## Speaker:

- Ryan Martin
- Mathematics Department, Rutgers University

## Place:

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

## Time:

- 3:30 PM
- Thursday, November 21, 1996

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 September 24, 1996