Hoeffding's inequality for continuous-time Markov chains
Fuente:
arXiv
Guardado en:
| Autores principales: | , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866913325962493952 |
|---|---|
| author | Liu, Jinpeng Liu, Yuanyuan Zhou, Lin |
| author_facet | Liu, Jinpeng Liu, Yuanyuan Zhou, Lin |
| contents | Hoeffding's inequality is a fundamental tool widely applied in probability theory, statistics, and machine learning. In this paper, we establish Hoeffding's inequalities specifically tailored for an irreducible and positive recurrent continuous-time Markov chain (CTMC) on a countable state space with the invariant probability distribution $π$ and an $\mathcal{L}^{2}(π)$-spectral gap $λ(Q)$. More precisely, for a function $g:E\to [a,b]$ with a mean $π(g)$, and given $t,\varepsilon>0$, we derive the inequality \[ \mathbb{P}_π\left(\frac{1}{t} \int_{0}^{t} g\left(X_{s}\right)\mathrm{d}s-π(g) \geq \varepsilon \right) \leq \exp\left\{-\frac{λ(Q)t\varepsilon^2}{(b-a)^2} \right\}, \] which can be viewed as a generalization of Hoeffding's inequality for discrete-time Markov chains (DTMCs) presented in [J. Fan et al., J. Mach. Learn. Res., 22(2022), pp. 6185-6219] to the realm of CTMCs. The key analysis enabling the attainment of this inequality lies in the utilization of the techniques of skeleton chains and augmented truncation approximations. Furthermore, we also discuss Hoeffding's inequality for a jump process on a general state space. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2404_14888 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Hoeffding's inequality for continuous-time Markov chains Liu, Jinpeng Liu, Yuanyuan Zhou, Lin Probability Statistics Theory Hoeffding's inequality is a fundamental tool widely applied in probability theory, statistics, and machine learning. In this paper, we establish Hoeffding's inequalities specifically tailored for an irreducible and positive recurrent continuous-time Markov chain (CTMC) on a countable state space with the invariant probability distribution $π$ and an $\mathcal{L}^{2}(π)$-spectral gap $λ(Q)$. More precisely, for a function $g:E\to [a,b]$ with a mean $π(g)$, and given $t,\varepsilon>0$, we derive the inequality \[ \mathbb{P}_π\left(\frac{1}{t} \int_{0}^{t} g\left(X_{s}\right)\mathrm{d}s-π(g) \geq \varepsilon \right) \leq \exp\left\{-\frac{λ(Q)t\varepsilon^2}{(b-a)^2} \right\}, \] which can be viewed as a generalization of Hoeffding's inequality for discrete-time Markov chains (DTMCs) presented in [J. Fan et al., J. Mach. Learn. Res., 22(2022), pp. 6185-6219] to the realm of CTMCs. The key analysis enabling the attainment of this inequality lies in the utilization of the techniques of skeleton chains and augmented truncation approximations. Furthermore, we also discuss Hoeffding's inequality for a jump process on a general state space. |
| title | Hoeffding's inequality for continuous-time Markov chains |
| topic | Probability Statistics Theory |
| url | https://arxiv.org/abs/2404.14888 |