Hoeffding's inequality for Markov processes via solution of Poisson's equation

Abstract

We investigate Hoeffding's inequality for both discrete-time Markov chains and continuous-time Markov processes on a general state space. 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 reective diffusion processes.

Key words： Hoeffding's inequality; Markov process; Poisson's equation

References

1 Anderson WJ. Continuous-Time Markov Chains: An Applications-Oriented Approach. New York: Springer-Verlag, 1991

2 Asmussen S, Bladt M. Poisson's equation for queues driven by a Markovian marked point process. Queueing Syst, 1994, 17: 235–274

3 Boucher T R. A Hoeffding inequality for Markov chains using a generalized inverse. Statist Probab Lett, 2009, 79: 1105–1107

4 Chen M F. Single birth processes. Chin Ann Math Ser B, 1999, 20(1): 77–82

5 Chen M F, Zhang Y H. Unified representation of formulas for single birth processes. Front Math China, 2014, 9(4): 761–796

6 Chen R R. An extended class of time-continuous branching processes. J Appl Probab, 1997, 34: 14–23

7 Choi M C H, Li E. A Hoeffding's inequality for uniformly ergodic diffusion process. Statist Probab Lett, 2019, 150: 23–28

8 Devroye L, Györfi L, Lugosi G. A Probabilistic Theory of Pattern Recognition.New York: Springer-Verlag, 1996

9 Glynn P W, Meyn S P. A Liapounov bound for solutions of the Poisson equation. Ann Probab, 1996, 24: 916–931

10 Glynn P W, Ormoneit P. Hoeffding's inequality for uniformly ergodic Markov chains. Statist Probab Lett, 2002, 56: 143–146

11 Hoeffding W. Probability inequalities for sums of bounded random variables. J Amer Statist Assoc, 1963, 58: 13–30

12 Jiang S X, Liu Y Y, Yao S. Poisson's equation for discrete-time single-birth processes. Statist Probab Lett, 2014, 85: 78–83

13 Karlin S, Taylor H M. A Second Course in Stochastic Processes.Boston: Academic Press, 1981

14 Lezaud P.Chernoff-type bound for finite Markov chains. Ann Appl Probab, 1998, 8(3): 849–867

15 Liu Y Y. Perturbation bounds for the stationary distributions of Markov chains. SIAM J Matrix Anal Appl, 2012, 33(4): 1057–1074

16 Liu Y Y, Li W D. Error bounds for augmented truncation approximations of Markov chains via the perturbation method. Adv in Appl Probab, 2018, 50(2): 645–669

17 Liu Y Y, Li Y. V-uniform ergodicity for fluid queues. Appl Math J Chinese Univ Ser B, 2019, 34(1): 82–91

18 Liu Y Y, Zhang H J, Zhao Y Q. Computable strongly ergodic rates of convergence for continuous-time Markov chains. ANZIAM J, 2008, 49(4): 463–478

19 Masuyama H.Error bounds for last-column-block-augmented truncations of blockstructured Markov chains. J Oper Res Soc Japan, 2017, 60: 271–320

20 Miasojedow B. Hoeffdings inequalities for geometrically ergodic Markov chains on general state space. Statist Probab Lett, 2014, 87: 115–120

21 Rogers L C G. Fluid models in queueing theory and Wiener-Hopf factorization of Markov chains. Ann Appl Probab, 1994, 4(2): 390–413

22 Seneta E. Coefficients of ergodicity: structure and applications. J Appl Probab, 1979, 11(3): 576–590

23 Sharpe M. General Theory of Markov Processes.New York: Academic, 1988