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.

Keywords

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

RIGHTS & PERMISSIONS

Higher Education Press