Random walks on random trees

Abstract

Let T denote one of the n n−2 trees with n labelled nodes that is rooted at a given node x (see [6] or [8] as a general reference on trees). If i and j are any two nodes of T , we write i ∼ j if they are joined by an edge in T . We want to consider random walks on T ; we assume that when we are at a node i of degree d the probability that we proceed to node j at the next step is d i –1 if i ∼ j and zero otherwise. Our object here is to determine the first two moments of the first return and first passage times for random walks on T when T is a specific tree and when T is chosen at random from the set of all labelled trees with certain properties.

Locations

• Journal of the Australian Mathematical Society - View - PDF