Exceptional graphs for the random walk

DOI10.1214/19-AIHP1026MaRDI QIDQ2227475zbMATH OpenOpenAlexFDO

Authors Juhan Aru, Carla Groenland, Tom Johnston, Alex Roberts, Bhargav P. Narayanan, Alex Scott

Publication date 15 February 2021

Published in Annales de l'Institut Henri Poincaré. Probabilités et Statistiques (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1805.06277, https://projecteuclid.org/euclid.aihp/1593137317

zbMATH Keywords

random walksrecurrencetransienceexceptional graphstraversal sequences

Mathematics Subject Classification ID

Sums of independent random variables; random walks (60G50) Random walks on graphs (05C81)

Abstract: If $mathcalW$ is the simple random walk on the square lattice $mathbb{Z}^2$, then $mathcalW$ induces a random walk $mathcal{W}_G$ on any spanning subgraph $Gsubsetmathbb{Z}^2$ of the lattice as follows: viewing $mathcalW$ as a uniformly random infinite word on the alphabet $mathbfx,-mathbfx,mathbfy,-mathbfy$, the walk $mathcal{W}_G$ starts at the origin and follows the directions specified by $mathcalW$, only accepting steps of $mathcalW$ along which the walk $mathcal{W}_G$ does not exit $G$. For any fixed subgraph $Gsubsetmathbb{Z}^2$, the walk $mathcal{W}_G$ is distributed as the simple random walk on $G$, and hence $mathcal{W}_G$ is almost surely recurrent in the sense that $mathcal{W}_G$ visits every site reachable from the origin in $G$ infinitely often. This fact naturally leads us to ask the following: does $mathcalW$ almost surely have the property that $mathcal{W}_G$ is recurrent for emph{every} subgraph $Gsubsetmathbb{Z}^2$? We answer this question negatively, demonstrating that exceptional subgraphs exist almost surely. In fact, we show more to be true: exceptional subgraphs continue to exist almost surely for a countable collection of independent simple random walks, but on the other hand, there are almost surely no exceptional subgraphs for a branching random walk.

Recommendations

• Recurrent graphs where two independent random walks collide finitely often
• Branching and tree indexed random walks on fractals
• Collisions of random walks in reversible random graphs
• scientific article; zbMATH DE number 1301686
• scientific article; zbMATH DE number 4072069

Cites work

• scientific article; zbMATH DE number 3934148 (Why is no real title available?)
• scientific article; zbMATH DE number 3936137 (Why is no real title available?)
• scientific article; zbMATH DE number 3068096 (Why is no real title available?)
• 4-dimensional Brownian motion is recurrent with positive capacity
• A probabilistic approach to Carne's bound
• A special set of exceptional times for dynamical random walk on \(\mathbb Z^2\)
• Basic properties of Brownian motion and a capacity on the Wiener space
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Recurrence of simple random walk on \(\mathbb Z^2\) is dynamically sensitive statistics
• Sets avoided by Brownian motion
• Some problems concerning the structure of random walk paths
• Symmetric Markov chains in \({\mathbb{Z}}^ 4:\) How fast can they move?
• Which properties of a random sequence are dynamically sensitive?

Cited in

(2)

• Recurrence of the \(\mathbb{Z}^d\)-valued infinite snake via unimodularity
• Recurrence or transience of random walks on random graphs generated by point processes in \(\mathbb{R}^d\)

This page was built for publication: Exceptional graphs for the random walk

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