Abstract: Directed covers of finite graphs are also known as periodic trees or trees with finitely many cone types. We expand the existing theory of directed covers of finite graphs to those of infinite graphs. While the lower growth rate still equals the branching number, upper and lower growth rates do not longer coincide in general. Furthermore, the behaviour of random walks on directed covers of infinite graphs is more subtle. We provide a classification in terms of recurrence and transience and point out that the critical random walk may be recurrent or transient. Our proof is based on the observation that recurrence of the random walk is equivalent to the almost sure extinction of an appropriate branching process. Two examples in random environment are provided: homesick random walk on infinite percolation clusters and random walk in random environment on directed covers. Furthermore, we calculate, under reasonable assumptions, the rate of escape with respect to suitable length functions and prove the existence of the asymptotic entropy providing an explicit formula which is also a new result for directed covers of finite graphs. In particular, the asymptotic entropy of random walks on directed covers of finite graphs is positive if and only if the random walk is transient.
Recommendations
Cites work
- A criterion for transience of multidimensional branching random walk in random environment
- An index theory for uniformly locally finite graphs
- Asymptotic entropy and Green speed for random walks on countable groups
- Central limit theorems for Gromov hyperbolic groups
- Characterization of critical values of branching random walks on weighted graphs through infinite-type branching processes
- Elements of Information Theory
- Hausdorff dimension of the harmonic measure on trees
- scientific article; zbMATH DE number 3934150 (Why is no real title available?)
- scientific article; zbMATH DE number 3698139 (Why is no real title available?)
- scientific article; zbMATH DE number 2070282 (Why is no real title available?)
- scientific article; zbMATH DE number 3399118 (Why is no real title available?)
- Local spectral radii and Collatz-Wielandt numbers of monic operator polynomials with nonnegative coefficients
- Probability on trees and networks
- Random walk on periodic trees
- Random walks and percolation on trees
- Random walks on discrete groups: Boundary and entropy
- Random Walks on Infinite Graphs and Groups
- Random walks on trees with finitely many cone types
- Rate of escape of random walks on free products
- Survival of branching random walks in random environment
- Topics in the Constructive Theory of Countable Markov Chains
- Tree-indexed random walks on groups and first passage percolation
Cited in
(5)- Coverings, Laplacians, and heat kernels of directed graphs
- scientific article; zbMATH DE number 2094608 (Why is no real title available?)
- Asymptotic entropy of random walks on Fuchsian buildings and Kac-Moody groups
- Cone types and spectral radius of hyperbolic triangle groups and hyperbolic tessellations
- Random walk in a finite directed graph subject to a road coloring
This page was built for publication: Random walks on directed covers of graphs
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q633134)
