𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Extremal cover times for random walks on trees

✍ Scribed by Graham Brightwell; Peter Winkler

Publisher
John Wiley and Sons
Year
1990
Tongue
English
Weight
370 KB
Volume
14
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Abstract

Let C~Ξ½~(T) denote the β€œcover time” of the tree T from the vertex v, that is, the expected number of steps before a random walk starting at v hits every vertex of T. Asymptotic lower bounds for C~Ξ½~(T) (for T a tree on n vertices) have been obtained recently by Kahn, Linial, Nisan and Saks, and by Devroye and Sbihi; here, we obtain the exact lower bound (approximately 2__n__ In n) by showing that C~Ξ½~(T) is minimized when T is a star and v is one of its leaves.

In addition, we show that the time to cover all vertices and then return to the starting point is minimized by a star (beginning at the center) and maximized by a path (beginning at one of the ends).

πŸ“œ SIMILAR VOLUMES

On the Mean and Variance of Cover Times
On the Mean and Variance of Cover Times for Random Walks on Graphs
✍ Frank Ball; Bruce Dunham; A Hirschowitz πŸ“‚ Article πŸ“… 1997 πŸ› Elsevier Science 🌐 English βš– 141 KB

A method is described for calculating the mean cover time for a particle performing a simple random walk on the vertices of a finite connected graph. The method also yields the variance and generating function of the cover time. A computer program is available which utilises the approach to provide

On an Extremal Problem for Colored Trees
On an Extremal Problem for Colored Trees
✍ P. Valtr πŸ“‚ Article πŸ“… 1999 πŸ› Elsevier Science 🌐 English βš– 93 KB

Let T be a tree such that there is a proper n-coloring c of the vertices of T which, besides a technical condition, is a k b k a k -free, i.e., T contains no subdivision of a path u 1 , . . . , Then T has O(kn) vertices. (The technical condition requires that T contains no subdivision of a properly

On the complexity of branch-and-bound se
On the complexity of branch-and-bound search for random trees
✍ Luc Devroye; Carlos Zamora-Cura πŸ“‚ Article πŸ“… 1999 πŸ› John Wiley and Sons 🌐 English βš– 256 KB πŸ‘ 2 views

Let T be a b-ary tree of height n, which has independent, non-negative, n identically distributed random variables associated with each of its edges, a model previously considered by Karp, Pearl, McDiarmid, and Provan. The value of a node is the sum of all the edge values on its path to the root. Co