Towards a Banach Space Chernoff Bound for Markov Chains via Chaining Arguments
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866911472572956672 |
|---|---|
| author | Rao, Shravas |
| author_facet | Rao, Shravas |
| contents | Let $\{Y_i\}_{i=1}^{\infty}$ be a stationary reversible Markov chain with state space $[N]$, let $(X, \| \cdot \|)$ be a real-valued Banach space and let $f_1, \ldots, f_n: [N] \rightarrow X$ be functions with mean $0$ such that $\|f_i(v)\| \leq 1$ for all $i$ and $v$. We prove bounds on the expected value of and deviation bounds for the random variable $\|f_1(Y_1)+\cdots+f_n(Y_n)\|$. For large enough $n$ that depends on the Banach space (and not $N$), these bounds behave similarly as known bounds for independent random variables. When the Banach space in question is the set of matrices equipped with the $\ell_2 \rightarrow \ell_2$ operator norm, for large enough $n$, our bounds on the expected value improve upon known bounds and match what is known for independent random variables up to a factor in the spectral gap. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2508_02955 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Towards a Banach Space Chernoff Bound for Markov Chains via Chaining Arguments Rao, Shravas Probability Let $\{Y_i\}_{i=1}^{\infty}$ be a stationary reversible Markov chain with state space $[N]$, let $(X, \| \cdot \|)$ be a real-valued Banach space and let $f_1, \ldots, f_n: [N] \rightarrow X$ be functions with mean $0$ such that $\|f_i(v)\| \leq 1$ for all $i$ and $v$. We prove bounds on the expected value of and deviation bounds for the random variable $\|f_1(Y_1)+\cdots+f_n(Y_n)\|$. For large enough $n$ that depends on the Banach space (and not $N$), these bounds behave similarly as known bounds for independent random variables. When the Banach space in question is the set of matrices equipped with the $\ell_2 \rightarrow \ell_2$ operator norm, for large enough $n$, our bounds on the expected value improve upon known bounds and match what is known for independent random variables up to a factor in the spectral gap. |
| title | Towards a Banach Space Chernoff Bound for Markov Chains via Chaining Arguments |
| topic | Probability |
| url | https://arxiv.org/abs/2508.02955 |