✦ LIBER ✦

On the Mean and Variance of Cover Times for Random Walks on Graphs

✍ Scribed by Frank Ball; Bruce Dunham; A Hirschowitz

Publisher: Elsevier Science
Year: 1997
Tongue: English
Weight: 141 KB
Volume: 207
Category: Article
ISSN: 0022-247X
DOI: 10.1006/jmaa.1997.5298

No coin nor oath required. For personal study only.

✦ Synopsis

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 results for vertex symmetric graphs. Some examples are given. ᮊ 1997 Academic Press quantities do not depend on ¨, the subscripts will be omitted.

📜 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

On the variance of the random sphere of

On the variance of the random sphere of influence graph

✍ P. Hitczenko; S. Janson; J. E. Yukich 📂 Article 📅 1999 🏛 John Wiley and Sons 🌐 English ⚖ 219 KB 👁 2 views

We show that the variance of the number of edges in the random sphere of influence graph built on n i.i.d. sites which are uniformly distributed over the unit cube in R d , grows linearly with n. This is then used to establish a central limit theorem for the number of edges in the random sphere of i

Volume and time doubling of graphs and r

Volume and time doubling of graphs and random walks: The strongly recurrent case

✍ András Telcs 📂 Article 📅 2001 🏛 John Wiley and Sons 🌐 English ⚖ 223 KB 👁 1 views

On the Analysis of Variance for Time Seq

On the Analysis of Variance for Time Sequenced Samples

✍ W. Schill; T. Louton 📂 Article 📅 1980 🏛 John Wiley and Sons 🌐 English ⚖ 277 KB 👁 2 views

A note on the cover degeneracy of graphs

✍ Li Zhang; Baoyindureng Wu 📂 Article 📅 2005 🏛 John Wiley and Sons 🌐 English ⚖ 64 KB 👁 1 views

## Abstract We give a 4‐chromatic planar graph, which admits a vertex partition into three parts such that the union of every two of them induces a forest. This solves a problem posed by Böhme. Also, by constructing an infinite sequence of graphs, we show that the cover degeneracy can be arbitraril

Minimization of expected variance of com

Minimization of expected variance of completion times on single machine for stochastic jobs

✍ V. Rajendra Prasad; D. K. Manna 📂 Article 📅 1997 🏛 John Wiley and Sons 🌐 English ⚖ 461 KB 👁 2 views

This article deals with the problem of scheduling jobs with random processing times on single machine in order to minimize the expected variance of job completion times. SutTicient conditions for the existence of V-shaped optimal sequences are derived separately for general and ordered job processin