𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Collecting coupons on trees, and the cover time of random walks

✍ Scribed by Uriel Feige

Publisher
Springer
Year
1996
Tongue
English
Weight
769 KB
Volume
6
Category
Article
ISSN
1016-3328

No coin nor oath required. For personal study only.

πŸ“œ SIMILAR VOLUMES

Extremal cover times for random walks on
Extremal cover times for random walks on trees
✍ Graham Brightwell; Peter Winkler πŸ“‚ Article πŸ“… 1990 πŸ› John Wiley and Sons 🌐 English βš– 370 KB

## 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 obtain

Random walks on trees and the law of ite
Random walks on trees and the law of iterated logarithm
✍ Mokhtar H. Konsowa πŸ“‚ Article πŸ“… 2002 πŸ› Elsevier Science 🌐 English βš– 80 KB

In this paper we give an alternative proof for the main result of Konsowa and Mitro (J. Theor. Probab. 4 (3) (1991) 535), Konsowa and Mitro found that the simple random walk (SRW) on inΓΏnite trees is transient or recurrent. In part of their work, they considered the case of an N-tree in which all th

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