𝔖 Bobbio Scriptorium
✦   LIBER   ✦

Random walks and the regeneration time

✍ Scribed by Beveridge, Andrew; Lov�sz, L�szl�

Publisher
John Wiley and Sons
Year
1998
Tongue
English
Weight
218 KB
Volume
29
Category
Article
ISSN
0364-9024

No coin nor oath required. For personal study only.

✦ Synopsis

Consider a graph G and a random walk on it. We want to stop the random walk at certain times (using an optimal stopping rule) to obtain independent samples from a given distribution ρ on the nodes. For an undirected graph, the expected time between consecutive samples is maximized by a distribution equally divided between two nodes, and so the worst expected time is 1/4 of the maximum commute time between two nodes. In the directed case, the expected time for this distribution is within a factor of 2 of the maximum.

📜 SIMILAR VOLUMES

Random walks and cell size
Random walks and cell size
✍ Paul S. Agutter; Denys N. Wheatley 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 98 KB 👁 2 views
Dependent percolation and colliding rand
Dependent percolation and colliding random walks
✍ Peter Winkler 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 315 KB 👁 2 views

Let G be a connected, undirected graph and Let N N be the nonnegative quadrant of the plane grid, and H the subgraph of N N induced by the sites i j for which X i = Y j . We say that G is "navigable" if with probability greater than 0, the origin belongs to an infinite component of H. We determine