Cutpoints and resistance of random walk paths

DOI10.1214/10-AOP569zbMATH Open1223.60012arXiv0902.0115OpenAlexW3106494167MaRDI QIDQ533749FDOQ533749

Ori Gurel-Gurevich, Itai Benjamini, Oded Schramm

Publication date: 6 May 2011

Published in: The Annals of Probability (Search for Journal in Brave)

Abstract: We construct a bounded degree graph $G$, such that a simple random walk on it is transient but the random walk path (i.e., the subgraph of all the edges the random walk has crossed) has only finitely many cutpoints, almost surely. We also prove that the expected number of cutpoints of any transient Markov chain is infinite. This answers two questions of James, Lyons and Peres [A Transient Markov Chain With Finitely Many Cutpoints (2007) Festschrift for David Freedman]. Additionally, we consider a simple random walk on a finite connected graph $G$ that starts at some fixed vertex $x$ and is stopped when it first visits some other fixed vertex $y$. We provide a lower bound on the expected effective resistance between $x$ and $y$ in the path of the walk, giving a partial answer to a question raised in [Ann. Probab. 35 (2007) 732--738].

Full work available at URL: https://arxiv.org/abs/0902.0115

Recommendations

• Cutpoints for simple random walks on quasi-transitive graphs
• scientific article
• Cutpoints and Exchangeable Events for Random Walks
• Random walks and the effective resistance of networks
• Random Paths and Cuts, Electrical Networks, and Reversible Markov Chains

zbMATH Keywords

random walkelectrical networkgraph cutpointspaths of a random walk

Mathematics Subject Classification ID

Geometric probability and stochastic geometry (60D05) Sums of independent random variables; random walks (60G50)

Cites Work

• Recurrence of random walk traces
• Isoperimetric inequalities and transient random walks on graphs
• Cut times for simple random walk
• A transient Markov chain with finitely many cutpoints
• Cutpoints and Exchangeable Events for Random Walks
• On the number of cutpoints of the transient nearest neighbor random walk on the line

Cited In (5)

• Recurrence of Markov chain traces
• Cutpoints of non-homogeneous random walks
• Most transient random walks have infinitely many cut times
• Growth exponent for loop-erased random walk in three dimensions
• Cutpoints and Exchangeable Events for Random Walks

This page was built for publication: Cutpoints and resistance of random walk paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q533749)