Variable length memory chains: characterization of stationary probability measures (Q2040105)

Variable length Markov chains (VLMCs) \((U_n)_{n\geq 0}\) are generalisations of finite order Markov chains and a special case of chains with infinite order [\textit{T. E. Harris}, Pac. J. Math. 5, 707--724 (1955; Zbl 0066.11402)]. Their conditional dependence structure is such that the dependence is on a possibly unbounded part of the past whose length is determined by the past itself. Their state space is the set of right-infinite words \(\mathcal{R}\) over a finite alphabet \(\mathcal{A}\). The dependence structure is usually stored in a context tree over \(\mathcal{A}\), where each node has either \(0\) or \(|\mathcal{A}|\) children such that the leaves and the infinite branches correspond to words over \(\mathcal{A}\) and are called contexts. The Markov property takes the form \[\text{ for all } n\geq 0,\text{ for all }\alpha\in\mathcal{A}:\mathbb{P}(U_{n+1}=\alpha U_n|U_n)=q_{\mathrm{cont}(U_n)}(\alpha)\] where \(\mathrm{cont}(u)\) is defined as the only prefix of the right-infinite word \(u\) appearing as a context and \(\sum_{\alpha\in \mathcal{A}}q_{\mathrm{cont}(u)}(\alpha)=1\). The paper investigates conditions ensuring the existence of stationary measures for such VLMCs. The authors introduce several objects associated to VLMCs, namely the set of longest internal suffixes (LIS) associated to words (resp. \(\alpha\)-LIS), cascade series, and a matrix \(Q\) that has at most countably many entries. Their main result establishes that if there exists a stationary probability measure, then the cascade series converges. On the other hand, if the cascade series converge they give an explicit one to one correspondence between stationary measures and nonnegative left-fixed eigenvectors of \(Q\) with some property. Later, they connect the so-called stable VLMCs whose trees have a special shape with semi Markov-chains. Any semi-Markov chain with true jumps on a state space with \(n\) elements is a VLMC on an \(n\)-comb tree, and they provide a neat characterisation of when a unique stationary probability measure exists in the stable case. The paper ends with several conjectures that extend statements concerning the \(Q\)-matrix, convergence or vanishing of cascades. While the paper is stimulating, some notions introduced are difficult to grasp, and, e.g., the first author et al. [Lect. Notes Math. 2046, 1--39 (2012; Zbl 1253.60079)] might give more context and examples. Overall the paper intertwines, explains and connects new concepts to more classical theory, making it a refined and pleasant work to read.