A short operator proof of Hoeffding inequalities for Markov chains
Abstract
We give a short operator-theoretic proof of the sharp Hoeffding inequality for additive functionals of a Markov chain on a general state space with an L2(π) spectral gap, recovering the bound of Fan et al. (2021). We further show that the same argument yields the Hoeffding inequality of Neeman et al. (2024) for Markov-dependent random matrices. The proof rests on two key observations. First, the transition operator factors as P=Qλ1/2 K Qλ1/2 through the León-Perron operator Qλ, with |K|=1. This bounds the moment generating function by a product of one-step operator norms. Second, each one-step operator is a rank-one perturbation of a multiplication operator, so bounding its norm reduces to verifying a scalar resolvent condition. Scalar convexity and the classical Hoeffding lemma then give the desired estimate. This bypasses the asymptotic cumulant generating function, essential-spectrum analysis, and extremal two-state comparison used in existing proofs. In the matrix setting, the multi-matrix Golden-Thompson inequality first reduces the moment generating function to an operator problem on a lifted Hilbert space. The same two steps then apply: the projection onto constants becomes finite-rank, and a Schur-complement argument yields the same scalar estimate. The matrix Hoeffding inequality of Neeman et al. (2024) follows. For complex Hermitian summands, working directly on the complex Hilbert space improves the bound by a factor of $2$.
Related
BibTeX
@misc{kachaiev2026short,
title = {{A short operator proof of Hoeffding inequalities for Markov chains}},
author = {Oleksii Kachaiev},
howpublished = {arXiv},
year = {2026},
month = sep,
doi = {10.48550/arxiv.2609.23098},
eprint = {2609.23098},
archivePrefix = {arXiv},
url = {https://arxiv.org/abs/2609.23098},
note = {CC BY 4.0},
}
RIS
TY - UNPB
TI - A short operator proof of Hoeffding inequalities for Markov chains
AU - Oleksii Kachaiev
PY - 2026
DA - 2026/09/19
PB - arXiv
DO - 10.48550/arxiv.2609.23098
UR - https://arxiv.org/abs/2609.23098
AB - We give a short operator-theoretic proof of the sharp Hoeffding inequality for additive functionals of a Markov chain on a general state space with an L^2(π) spectral gap, recovering the bound of Fan et al. (2021). We further show that the same argument yields the Hoeffding inequality of Neeman et al. (2024) for Markov-dependent random matrices. The proof rests on two key observations. First, the transition operator factors as P=Q_λ^1/2 K Q_λ^1/2 through the León-Perron operator Q_λ, with |K|=1. This bounds the moment generating function by a product of one-step operator norms. Second, each one-step operator is a rank-one perturbation of a multiplication operator, so bounding its norm reduces to verifying a scalar resolvent condition. Scalar convexity and the classical Hoeffding lemma then give the desired estimate. This bypasses the asymptotic cumulant generating function, essential-spectrum analysis, and extremal two-state comparison used in existing proofs. In the matrix setting, the multi-matrix Golden-Thompson inequality first reduces the moment generating function to an operator problem on a lifted Hilbert space. The same two steps then apply: the projection onto constants becomes finite-rank, and a Schur-complement argument yields the same scalar estimate. The matrix Hoeffding inequality of Neeman et al. (2024) follows. For complex Hermitian summands, working directly on the complex Hilbert space improves the bound by a factor of $2$.
ER -