Hostname: page-component-cd9895bd7-8ctnn Total loading time: 0 Render date: 2024-12-24T12:43:02.516Z Has data issue: false hasContentIssue false
  • English
  • Français

Random walks on random trees

Published online by Cambridge University Press:  09 April 2009

J. W. Moon
J. W. Moon
Affiliation:
Mathematical InstituteOxford, OXI 2BA, England
Rights & Permissions [Opens in a new window]

Extract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Let T denote one of the nn−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 di–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.

Type
Research Article
Information
Journal of the Australian Mathematical Society , Volume 15 , Issue 1 , February 1973 , pp. 42 - 53
Copyright
Copyright © Australian Mathematical Society 1973

References

[1]Cayley, A., ‘A theorem on trees’, Quart. J. Math. 23 (1889), 376–378.Google Scholar
[2]Clarke, L. E., ‘On Cayley's formula for counting trees’, J. London Math. Soc. 33 (1958), 471–474.CrossRefGoogle Scholar
[3]Kemeny, J. G. and Snell, J. L., Finite Markov Chains. (van Nostrand, Princeton, 1960).Google Scholar
[4]Meir, A. and Moon, J. W., ‘The distance between points in random trees’, J. Comb. Th. 8 (1970), 99–103.CrossRefGoogle Scholar
[5]Meir, A. and Moon, J. W., ‘Cutting down random trees’, J. Australian Math. Soc. 11 (1970), 313–324.CrossRefGoogle Scholar
[6]Moon, J. W., ‘Enumerating labelled trees’, Graph Theory and Theoretical Physics (Academic Press, New York, 1967, pp. 261–272).Google Scholar
[7]Moon, J. W., ‘The expected number of inversions in a random tree’, Proceedings of the Louisiana Conference on Combinatorics and Graph Theory (York Press, Toronto, 1970, pp. 375–382).Google Scholar
[8]Moon, J. W., Counting Labelled Trees (Canadian Math. Congress, Montreal, 1970).Google Scholar
[9]Riordan, J., Combinatorial Identities (Wiley, New York, 1968).Google Scholar