IDEAS home Printed from https://ideas.repec.org/a/eee/stapro/v56y2002i2p143-146.html
   My bibliography  Save this article

Hoeffding's inequality for uniformly ergodic Markov chains

Author

Listed:
  • Glynn, Peter W.
  • Ormoneit, Dirk

Abstract

We provide a generalization of Hoeffding's inequality to partial sums that are derived from a uniformly ergodic Markov chain. Our exponential inequality on the deviation of these sums from their expectation is particularly useful in situations where we require uniform control on the constants appearing in the bound.

Suggested Citation

  • Glynn, Peter W. & Ormoneit, Dirk, 2002. "Hoeffding's inequality for uniformly ergodic Markov chains," Statistics & Probability Letters, Elsevier, vol. 56(2), pages 143-146, January.
    • Handle: RePEc:eee:stapro:v:56:y:2002:i:2:p:143-146
    as

    Download full text from publisher

    File URL: http://www.sciencedirect.com/science/article/pii/S0167-7152(01)00158-4
    Download Restriction: Full text for ScienceDirect subscribers only
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Balaji, S. & Meyn, S. P., 2000. "Multiplicative ergodicity and large deviations for an irreducible Markov chain," Stochastic Processes and their Applications, Elsevier, vol. 90(1), pages 123-144, November.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Ankush Agarwal & Stefano de Marco & Emmanuel Gobet & Gang Liu, 2017. "Rare event simulation related to financial risks: efficient estimation and sensitivity analysis," Working Papers hal-01219616, HAL.
    2. Renou, Ludovic & Tomala, Tristan, 2015. "Approximate implementation in Markovian environments," Journal of Economic Theory, Elsevier, vol. 159(PA), pages 401-442.
    3. Svetlana Ekisheva & Mark Borodovsky, 2011. "Uniform Accuracy of the Maximum Likelihood Estimates for Probabilistic Models of Biological Sequences," Methodology and Computing in Applied Probability, Springer, vol. 13(1), pages 105-120, March.
    4. Ahmad, I.A. & Amezziane, M., 2013. "Probability inequalities for bounded random vectors," Statistics & Probability Letters, Elsevier, vol. 83(4), pages 1136-1142.
    5. Sandrić, Nikola & Šebek, Stjepan, 2023. "Hoeffding’s inequality for non-irreducible Markov models," Statistics & Probability Letters, Elsevier, vol. 200(C).
    6. Penev, Spiridon & Peng, Hanxiang & Schick, Anton & Wefelmeyer, Wolfgang, 2004. "Efficient estimators for functionals of Markov chains with parametric marginals," Statistics & Probability Letters, Elsevier, vol. 66(3), pages 335-345, February.
    7. Choi, Michael C.H. & Li, Evelyn, 2019. "A Hoeffding’s inequality for uniformly ergodic diffusion process," Statistics & Probability Letters, Elsevier, vol. 150(C), pages 23-28.
    8. H. S. Chang, 2004. "Technical Note: On Ordinal Comparison of Policies in Markov Reward Processes," Journal of Optimization Theory and Applications, Springer, vol. 122(1), pages 207-217, July.
    9. Miasojedow, Błażej, 2014. "Hoeffding’s inequalities for geometrically ergodic Markov chains on general state space," Statistics & Probability Letters, Elsevier, vol. 87(C), pages 115-120.
    10. Liu, Jinpeng & Liu, Yuanyuan & Zhao, Yiqiang Q., 2022. "Augmented truncation approximations to the solution of Poisson’s equation for Markov chains," Applied Mathematics and Computation, Elsevier, vol. 414(C).
    11. Yongqiang Tang, 2007. "A Hoeffding-Type Inequality for Ergodic Time Series," Journal of Theoretical Probability, Springer, vol. 20(2), pages 167-176, June.
    12. Boucher, Thomas R., 2009. "A Hoeffding inequality for Markov chains using a generalized inverse," Statistics & Probability Letters, Elsevier, vol. 79(8), pages 1105-1107, April.
    13. Lember, Jüri & Matzinger, Heinrich & Sova, Joonas & Zucca, Fabio, 2018. "Lower bounds for moments of global scores of pairwise Markov chains," Stochastic Processes and their Applications, Elsevier, vol. 128(5), pages 1678-1710.
    14. Shie Mannor & John N. Tsitsiklis, 2005. "On the Empirical State-Action Frequencies in Markov Decision Processes Under General Policies," Mathematics of Operations Research, INFORMS, vol. 30(3), pages 545-561, August.
    15. Chang, Hyeong Soo, 2006. "On convergence rate of the Shannon entropy rate of ergodic Markov chains via sample-path simulation," Statistics & Probability Letters, Elsevier, vol. 76(12), pages 1261-1264, July.
    16. Hunt, F.Y., 2005. "Sample path optimality for a Markov optimization problem," Stochastic Processes and their Applications, Elsevier, vol. 115(5), pages 769-779, May.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Arnab Basu & Tirthankar Bhattacharyya & Vivek S. Borkar, 2008. "A Learning Algorithm for Risk-Sensitive Cost," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 880-898, November.
    2. Arapostathis, Ari & Biswas, Anup, 2018. "Infinite horizon risk-sensitive control of diffusions without any blanket stability assumptions," Stochastic Processes and their Applications, Elsevier, vol. 128(5), pages 1485-1524.
    3. Shie Mannor & John N. Tsitsiklis, 2005. "On the Empirical State-Action Frequencies in Markov Decision Processes Under General Policies," Mathematics of Operations Research, INFORMS, vol. 30(3), pages 545-561, August.
    4. Rolando Cavazos-Cadena, 2018. "Characterization of the Optimal Risk-Sensitive Average Cost in Denumerable Markov Decision Chains," Mathematics of Operations Research, INFORMS, vol. 43(3), pages 1025-1050, August.
    5. V. S. Borkar, 2002. "Q-Learning for Risk-Sensitive Control," Mathematics of Operations Research, INFORMS, vol. 27(2), pages 294-311, May.
    6. Kontoyiannis, I. & Meyn, S.P., 2017. "Approximating a diffusion by a finite-state hidden Markov model," Stochastic Processes and their Applications, Elsevier, vol. 127(8), pages 2482-2507.
    7. Ghosh, Mrinal K. & Golui, Subrata & Pal, Chandan & Pradhan, Somnath, 2023. "Discrete-time zero-sum games for Markov chains with risk-sensitive average cost criterion," Stochastic Processes and their Applications, Elsevier, vol. 158(C), pages 40-74.
    8. Lars Peter Hansen & Jose A. Scheinkman, 2012. "Recursive utility in a Markov environment with stochastic growth," Working Papers 1380, Princeton University, Department of Economics, Econometric Research Program..
    9. Kleptsyna, Marina & Le Breton, Alain & Ycart, Bernard, 2014. "Exponential transform of quadratic functional and multiplicative ergodicity of a Gauss–Markov process," Statistics & Probability Letters, Elsevier, vol. 87(C), pages 70-75.
    10. Qingda Wei & Xian Chen, 2021. "Nonzero-sum Risk-Sensitive Average Stochastic Games: The Case of Unbounded Costs," Dynamic Games and Applications, Springer, vol. 11(4), pages 835-862, December.
    11. Anna Ja'skiewicz, 2007. "Average optimality for risk-sensitive control with general state space," Papers 0704.0394, arXiv.org.
    12. Arnab Basu & Mrinal K. Ghosh, 2018. "Nonzero-Sum Risk-Sensitive Stochastic Games on a Countable State Space," Mathematics of Operations Research, INFORMS, vol. 43(2), pages 516-532, May.
    13. Lars Peter Hansen & Jose A. Scheinkman, 2012. "Recursive utility in a Markov environment with stochastic growth," Working Papers 1380, Princeton University, Department of Economics, Econometric Research Program..
    14. Rubén Blancas-Rivera & Rolando Cavazos-Cadena & Hugo Cruz-Suárez, 2020. "Discounted approximations in risk-sensitive average Markov cost chains with finite state space," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 91(2), pages 241-268, April.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:eee:stapro:v:56:y:2002:i:2:p:143-146. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Catherine Liu (email available below). General contact details of provider: http://www.elsevier.com/wps/find/journaldescription.cws_home/622892/description#description .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.