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

exceptional graphsrandom walksrecurrencetransiencetraversal sequences

Mathematics Subject Classification ID

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

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.

Review text

This paper studies exceptional graphs for random walks on \(\mathbb{Z}^2\). If \(W\) is a simple random walk on \(\mathbb{Z}^2\), then there almost surely exists a random exceptional subgraph \(H \subseteq\mathbb{Z}^2\) for which the induced walk \(W_H\) visits each node reachable from the origin in \(H\) infinitely many times and fails to visit infinitely many nodes reachable from the origin in \(H\). The question of whether a countably infinite independent set of simple random walks almost surely has the property that at least one of these walks induces a recurrent walk over a given \(G\subseteq\mathbb{Z}^2\) is negatively answered in this paper either. Moreover, for \(d\in\mathbb{N}\) and \(W_i\) \((i\in S)\) being a set of random walks created by a branching random walk over \(\mathbb{Z}^d\) with a nontrivial offspring distribution, it is shown that almost surely for every spanning subgraph \(G\subseteq\mathbb{Z}^d\), there is a \(j\in S\) for which the induced walk \(W_j\) is recurrent.

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

• 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
• 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?)
• Probability and computing. Randomization and probabilistic techniques in algorithms and data analysis
• Recurrence of simple random walk on 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

(3)

• scientific article; zbMATH DE number 1301686 (Why is no real title available?)
• 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)