Cutpoints and resistance of random walk paths

DOI10.1214/10-AOP569MaRDI QIDQ533749zbMATH OpenOpenAlexFDO

Authors Itai Benjamini, Ori Gurel-Gurevich, Oded Schramm

Publication date 6 May 2011

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

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

zbMATH Keywords

electrical networkgraph cutpointspaths of a random walkrandom walk

Mathematics Subject Classification ID

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

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].

Recommendations

• Cutpoints for simple random walks on quasi-transitive graphs
• scientific article; zbMATH DE number 98308
• 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

Cites work

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

Cited in

(9)

• Growth exponent for loop-erased random walk in three dimensions
• Recurrence of Markov chain traces
• Cutpoints and Exchangeable Events for Random Walks
• Cutpoints for simple random walks on quasi-transitive graphs
• Cutpoints on trees and spherically symmetric graphs
• Cutpoints of non-homogeneous random walks
• Most transient random walks have infinitely many cut times
• Monotonicity of random walks' states on finite grids
• Local time, upcrossing time and weak cutpoints of a spatially inhomogeneous random walk on the line

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)