Abstract
Stochastic chains of unbounded memory (SCUMs) are generalization of Markov chains, also known in the literature as “chains with complete connections” or “g-measures”. We obtain Gaussian concentration bounds (GCB) in this large class of models, for general alphabets, under two different conditions on the kernel: (1) when the sum of its oscillations is less than one, or (2) when the sum of its variations is finite, that is, belongs to . We also obtain explicit constants as functions of the parameters of the model. Our conditions are sharp in the sense that we exhibit examples of SCUMs that do not have GCB and for which the sum of oscillations is , or the variation belongs to for any . These examples are based on the existence of phase transitions.
We illustrate our results with four applications. First, we derive a Dvoretzky–Kiefer–Wolfowitz-type inequality which gives a uniform control on the fluctuations of the empirical measure. Second, in the finite-alphabet case, we obtain an upper bound on the -distance between two stationary SCUMs and, as a by-product, we obtain new explicit bounds on the speed of Markovian approximation in . Third, we derive new bounds on the fluctuations of the “plug-in” estimator for entropy. Fourth, we obtain new rate of convergence for the maximum likelihood estimator of conditional probability.
Funding Statement
SG thanks CNRS, FAPESP (BPE: 2017/07084-6 and 2019/23439-4) as well as CNPq Universal (439422/2018-3) for financial support.
Acknowledgments
DYT thanks École Polytechnique for a two-month fellowship. SG and DYT thank the CPHT for its hospitality during several stays.
Citation
Jean-René Chazottes. Sandro Gallo. Daniel Y. Takahashi. "Gaussian concentration bounds for stochastic chains of unbounded memory." Ann. Appl. Probab. 33 (5) 3321 - 3350, October 2023. https://doi.org/10.1214/22-AAP1893
Information