𝔖 Bobbio Scriptorium
✦   LIBER   ✦

A bound for the covering time of random walks on graphs

✍ Scribed by JoséLuis Palacios

Publisher
Elsevier Science
Year
1992
Tongue
English
Weight
199 KB
Volume
14
Category
Article
ISSN
0167-7152

No coin nor oath required. For personal study only.

📜 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

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

Expected hitting times for a random walk
Expected hitting times for a random walk on a connected graph
✍ Gregory F Lawler 📂 Article 📅 1986 🏛 Elsevier Science 🌐 English ⚖ 297 KB

A random walk on a graph is defined in which a particle moves from one vertex to any adjoining vertex, each with equal probability. The expected number of steps to get from one point to another is considered. It is shown that the maximum expectation for a graph with N vertices is O(N3). It is also s