Variable Length Markov Chains, Persistent Random Walks: A Close Encounter
Peggy Cénac, Brigitte Chauvin, Frédéric Paccaut, Nicolas Pouyanne · 2020
This chapter defines the general model for words produced by a variable length Markov chain (VLMC) and introduces a key combinatorial structure on words. VLMCs are now widely used as random models for character strings. The chapter presents a study of the probabilistic properties of infinite memory VLMC as random processes, and more specifically of the main property of interest for such processes: existence and uniqueness of a stationary measure. A persistent random walk (PRW) is a random walk driven by some VLMC. The chapter describes the behavior of one-dimensional and two-dimensional PRWs. On the one hand, a VLMC is defined by its context tree and its transition probability distributions. On the other hand, for PRW (defined from VLMC), recurrence properties are written in terms of persistence times. The chapter builds a bridge between the PRW and VLMC in terms of their properties.