Hoeffding’s inequality for non-irreducible Markov models. (English) Zbl 1518.60065
Summary: In this article, we establish Hoeffding’s inequality for bounded Lipschitz functions of a class of not necessarily irreducible Markov models. The result complements the existing literature on this topic where Hoeffding’s inequality for bounded measurable functions of a class of irreducible Markov models has been considered. Our approach is based on the assumption of uniform ergodicity of the underlying Markov model in \(\mathrm{L}^1\)-Wasserstein space.
MSC:
| 60J05 | Discrete-time Markov processes on general state spaces |
| 60J25 | Continuous-time Markov processes on general state spaces |
References:
| [1] | Adamczak, R.; Bednorz, W., Exponential concentration inequalities for additive functionals of Markov chains, ESAIM Probab. Stat., 19, 440-481 (2015) · Zbl 1364.60028 |
| [2] | Bendikov, A.; Saloff-Coste, L., Random walks on groups and discrete subordination, Math. Nachr., 285, 5-6, 580-605 (2012) · Zbl 1251.60004 |
| [3] | Blumenthal, R. M.; Getoor, R. K., Markov Processes and Potential Theory (1968), Academic Press: Academic Press New York-London · Zbl 0169.49204 |
| [4] | Boucher, T. R., A Hoeffding inequality for Markov chains using a generalized inverse, Statist. Probab. Lett., 79, 8, 1105-1107 (2009) · Zbl 1170.60025 |
| [5] | Butkovsky, O., Subgeometric rates of convergence of Markov processes in the Wasserstein metric, Ann. Appl. Probab., 24, 2, 526-552 (2014) · Zbl 1304.60076 |
| [6] | Choi, M. C.H.; Li, E., A Hoeffding’s inequality for uniformly ergodic diffusion process, Statist. Probab. Lett., 150, 23-28 (2019) · Zbl 1448.60047 |
| [7] | Chung, K.-M.; Lam, H.; Liu, Z.; Mitzenmacher, M., Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified, (29th International Symposium on Theoretical Aspects of Computer Science. 29th International Symposium on Theoretical Aspects of Computer Science, LIPIcs. Leibniz Int. Proc. Inform, vol. 14 (2012), Schloss Dagstuhl. Leibniz-Zent. Inform.: Schloss Dagstuhl. Leibniz-Zent. Inform. Wadern), 124-135 · Zbl 1245.68143 |
| [8] | Deng, C.-S.; Schilling, R. L.; Song, Y.-H., Subgeometric rates of convergence for Markov processes under subordination, Adv. Appl. Probab., 49, 1, 162-181 (2017) · Zbl 1425.60064 |
| [9] | Devroye, L.; Györfi, L.; Lugosi, G., A Probabilistic Theory of Pattern Recognition (1996), Springer-Verlag: Springer-Verlag New York · Zbl 0853.68150 |
| [10] | Douc, R.; Moulines, E.; Olsson, J.; van Handel, R., Consistency of the maximum likelihood estimator for general hidden Markov models, Ann. Statist., 39, 1, 474-513 (2011) · Zbl 1209.62194 |
| [11] | Fan, J.; Jiang, B.; Sun, Q., Hoeffding’s inequality for general Markov chains and its applications to statistical learning, J. Mach. Learn. Res., 22, 35 (2021), Paper No. 139 · Zbl 07415082 |
| [12] | Glynn, P. W.; Meyn, S. P., A Liapounov bound for solutions of the Poisson equation, Ann. Probab., 24, 2, 916-931 (1996) · Zbl 0863.60063 |
| [13] | Glynn, P. W.; Ormoneit, D., Hoeffding’s inequality for uniformly ergodic Markov chains, Statist. Probab. Lett., 56, 2, 143-146 (2002) · Zbl 0999.60019 |
| [14] | Hoeffding, W., Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc., 58, 13-30 (1963) · Zbl 0127.10602 |
| [15] | León, C. A.; Perron, F., Optimal Hoeffding bounds for discrete reversible Markov chains, Ann. Appl. Probab., 14, 2, 958-970 (2004) · Zbl 1056.60070 |
| [16] | Lezaud, P., Chernoff-type bound for finite Markov chains, Ann. Appl. Probab., 8, 3, 849-867 (1998) · Zbl 0938.60027 |
| [17] | Liu, Y.; Liu, J., Hoeffding’s inequality for Markov processes via solution of Poisson’s equation, Front. Math. China, 16, 2, 543-558 (2021) · Zbl 1482.60094 |
| [18] | Meyn, S.; Tweedie, R. L., Markov Chains and Stochastic Stability (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.60001 |
| [19] | Miasojedow, B., Hoeffding’s inequalities for geometrically ergodic Markov chains on general state space, Statist. Probab. Lett., 87, 115-120 (2014) · Zbl 1297.60047 |
| [20] | Ormoneit, D.; Glynn, P. W., Kernel-based reinforcement learning in average-cost problems, IEEE Trans. Automat. Control, 47, 10, 1624-1636 (2002) · Zbl 1364.90349 |
| [21] | Rao, S., A Hoeffding inequality for Markov chains, Electron. Commun. Probab., 24, 11 (2019), Paper No. 14 · Zbl 1412.60049 |
| [22] | Sandrić, N.; Arapostathis, A.; Pang, G., Subexponential upper and lower bounds in Wasserstein distance for Markov processes, Appl. Math. Optim., 85, 3, 45 (2022), Paper No. 24 · Zbl 1497.60097 |
| [23] | Schilling, R. L.; Song, R.; Vondraček, Z., Bernstein Functions (2012), Walter de Gruyter & Co.: Walter de Gruyter & Co. Berlin · Zbl 1257.33001 |
| [24] | Tang, Y., A Hoeffding-type inequality for ergodic time series, J. Theoret. Probab., 20, 2, 167-176 (2007) · Zbl 1158.62057 |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
