Locally Markov Walks on Finite Graphs
Abstract
ABSTRACT Locally Markov walks are natural generalizations of classical Markov chains, where instead of a particle moving independently of the past, it decides where to move next depending on the last action performed at the current location. We introduce the concept of locally Markov walks and we describe their stationary distribution and recurrent states, and we prove several properties such as irreducibility and ergodicity. For a particular locally Markov walk‐the uniform unicycle walk on the complete graph‐we investigate the mixing time, and we prove that it exhibits cutoff.
Fields of Study & Subjects
Markov Chains and Monte Carlo Methods
Stochastic processes and statistical mechanics
Advanced Queuing Theory Analysis
Publication details
- Journal / source
- Random Structures and Algorithms
- Publisher
- Wiley
- Volume
- 68
- Issue
- 1
- Publication date
- 1 January 2026
- Language
- EN