Hoeffding's inequality for Markov processes via solution of Poisson's equation
type: Item
instance of: scholarly article
title: Hoeffding's inequality for Markov processes via solution of Poisson's equation
zbMATH Open document ID: 1482.60094
author: Yanyan Li
published in: Frontiers of Mathematics in China
publication date: 2021-08-05T00:00:00Z
review text: The authors investigate Hoeffding's inequality for both discrete-time Markov chains and continuous-time Markov processes on a general state space. In the words of the authors, ``Our results relax the usual aperiodicity restriction in the literature, and the explicit upper bounds in the inequalities are obtained via the solution of Poisson's equation. The results are further illustrated with applications to queueing theory and reflective diffusion processes.'' The classical Hoeffding's inequality gives an exponentially decaying upper bound to the sample mean of a sequence of independent and identically distributed and bounded random variables. Now, for any bounded real-valued function \(g\), and \(X_n\) a discrete time positive recurrent Markov chain with invariant distribution \(\pi\), one defines \[ S_n(g)=\sum_{i=0}^{n-1}g(X_i)\,, \] and the Hoeffding's inequality in this case gives an upper bound, that decays exponentially in \(n\), to the probability that \(\frac{1}{n}S_n(g)-\pi(g)\ge \varepsilon\). Such an inequality has a lot of applications in probability and statistics. The authors modify the arguments in [\textit{P. W. Glynn} and \textit{D. Ormoneit}, Stat. Probab. Lett. 56, No. 2, 143--146 (2002; Zbl 0999.60019)] to derive a Hoeffding's inequality for discrete time Markov chains by bounding the solution of Poisson's equation through the drift condition and ergodicity coefficient. For continuous time Markov processes, they extend the arguments of \textit{M. C. H. Choi} and \textit{E. Li} [Stat. Probab. Lett. 150, 23--28 (2019; Zbl 1448.60047)] to derive a Hoeffding's inequality by bounding the solution of Poisson's equation in terms of the hitting times and the drift condition.
reviewed by: Sourav Sarkar
Mathematics Subject Classification ID: 60J05
Mathematics Subject Classification ID: 60J25
Mathematics Subject Classification ID: 60F10
zbMATH DE Number: 7379090
zbMATH Keywords: Hoeffding's inequality
zbMATH Keywords: Markov process
zbMATH Keywords: Poisson's equation
MaRDI profile type: Publication
full work available at URL: s11464-021-0898-5
OpenAlex ID: W3158007355
cites work: Continuous-time Markov chains. An applications-oriented approach
cites work: Poisson's equation for queues driven by a Markovian marked point process
cites work: A Hoeffding inequality for Markov chains using a generalized inverse
cites work: Single birth processes
cites work: Unified representation of formulas for single birth processes
cites work: An extended class of time-continuous branching processes
cites work: A Hoeffding's inequality for uniformly ergodic diffusion process
cites work: Q4881152
cites work: A Liapounov bound for solutions of the Poisson equation
cites work: Hoeffding's inequality for uniformly ergodic Markov chains
cites work: Probability Inequalities for Sums of Bounded Random Variables
cites work: Poisson's equation for discrete-time single-birth processes
cites work: Q3923307
cites work: Chernoff-type bound for finite Markov chains
cites work: Perturbation Bounds for the Stationary Distributions of Markov Chains
cites work: Error bounds for augmented truncation approximations of Markov chains via the perturbation method
cites work: \(V\)-uniform ergodicity for fluid queues
cites work: COMPUTABLE STRONGLY ERGODIC RATES OF CONVERGENCE FOR CONTINUOUS-TIME MARKOV CHAINS
cites work: ERROR BOUNDS FOR LAST-COLUMN-BLOCK-AUGMENTED TRUNCATIONS OF BLOCK-STRUCTURED MARKOV CHAINS
cites work: Hoeffding's inequalities for geometrically ergodic Markov chains on general state space
cites work: Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains
cites work: Coefficients of ergodicity: structure and applications
cites work: Q4040434
DOI: 10.1007/S11464-021-0898-5
Recommended article: Hoeffding's inequality for uniformly ergodic Markov chains
Recommended article: Hoeffding's Inequality for Stopped Martingales and Semi-Markov Processes
Recommended article: Exponential concentration inequalities for additive functionals of Markov chains
Recommended article: Bounds on the L 2 Spectrum for Markov Chains and Markov Processes: A Generalization of Cheeger's Inequality
Recommended article: On Dobrushin's inequality
Recommended article: Q5159407
Recommended article: Chernoff-Hoeffding bounds for Markov chains: generalized and simplified
Recommended article: Q4946134
Recommended article: A Hoeffding's inequality for uniformly ergodic diffusion process
description: scientific article; zbMATH DE number 7379090