IDEAS home Printed from https://ideas.repec.org/a/spr/metcap/v20y2018i4d10.1007_s11009-017-9600-5.html
   My bibliography  Save this article

Hitting Times in Markov Chains with Restart and their Application to Network Centrality

Author

Listed:
  • Konstantin Avrachenkov

    (Inria Sophia Antipolis)

  • Alexey Piunovskiy

    (University of Liverpool)

  • Yi Zhang

    (University of Liverpool)

Abstract

Motivated by applications in telecommunications, computer science and physics, we consider a discrete-time Markov process with restart. At each step the process either with a positive probability restarts from a given distribution, or with the complementary probability continues according to a Markov transition kernel. The main contribution of the present work is that we obtain an explicit expression for the expectation of the hitting time (to a given target set) of the process with restart. The formula is convenient when considering the problem of optimization of the expected hitting time with respect to the restart probability. We illustrate our results with two examples in uncountable and countable state spaces and with an application to network centrality.

Suggested Citation

  • Konstantin Avrachenkov & Alexey Piunovskiy & Yi Zhang, 2018. "Hitting Times in Markov Chains with Restart and their Application to Network Centrality," Methodology and Computing in Applied Probability, Springer, vol. 20(4), pages 1173-1188, December.
    • Handle: RePEc:spr:metcap:v:20:y:2018:i:4:d:10.1007_s11009-017-9600-5
    DOI: 10.1007/s11009-017-9600-5
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s11009-017-9600-5
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s11009-017-9600-5?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    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. Maurer, Sebastian M. & Huberman, Bernardo A., 2001. "Restart strategies and Internet congestion," Journal of Economic Dynamics and Control, Elsevier, vol. 25(3-4), pages 641-654, March.
    2. Miquel Montero & Axel Masó-Puigdellosas & Javier Villarroel, 2017. "Continuous-time random walks with reset events," The European Physical Journal B: Condensed Matter and Complex Systems, Springer;EDP Sciences, vol. 90(9), pages 1-10, September.
    3. Nummelin, Esa & Tuominen, Pekka, 1982. "Geometric ergodicity of Harris recurrent Marcov chains with applications to renewal theory," Stochastic Processes and their Applications, Elsevier, vol. 12(2), pages 187-202, March.
    4. Søren Asmussen & Pierre Fiorini & Lester Lipsky & Tomasz Rolski & Robert Sheahan, 2008. "Asymptotic Behavior of Total Times for Jobs That Must Start Over if a Failure Occurs," Mathematics of Operations Research, INFORMS, vol. 33(4), pages 932-944, 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. Dmitrii Silvestrov & Sergei Silvestrov & Benard Abola & Pitos Seleka Biganda & Christopher Engström & John Magero Mango & Godwin Kakuba, 2021. "Perturbed Markov Chains with Damping Component," Methodology and Computing in Applied Probability, Springer, vol. 23(1), pages 369-397, March.

    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. Tesfatsion, Leigh, 2001. "Introduction to the special issue on agent-based computational economics," Journal of Economic Dynamics and Control, Elsevier, vol. 25(3-4), pages 281-293, March.
    2. Beare, Brendan K & Toda, Alexis Akira, 2020. "On the emergence of a power law in the distribution of COVID-19 cases," University of California at San Diego, Economics Working Paper Series qt9k5027d0, Department of Economics, UC San Diego.
    3. Leblanc, Frédérique, 1996. "Wavelet linear density estimator for a discrete-time stochastic process: Lp-losses," Statistics & Probability Letters, Elsevier, vol. 27(1), pages 71-84, March.
    4. Søren Asmussen & Peter W. Glynn, 2017. "On preemptive-repeat LIFO queues," Queueing Systems: Theory and Applications, Springer, vol. 87(1), pages 1-22, October.
    5. Djellout, H. & Guillin, A., 2001. "Moderate deviations for Markov chains with atom," Stochastic Processes and their Applications, Elsevier, vol. 95(2), pages 203-217, October.
    6. Duffie, Darrell & Singleton, Kenneth J, 1993. "Simulated Moments Estimation of Markov Models of Asset Prices," Econometrica, Econometric Society, vol. 61(4), pages 929-952, July.
    7. Achim Wübker, 2013. "Asymptotic Optimality of Isoperimetric Constants," Journal of Theoretical Probability, Springer, vol. 26(1), pages 198-221, March.
    8. Richard C. Bradley, 2021. "On some basic features of strictly stationary, reversible Markov chains," Journal of Time Series Analysis, Wiley Blackwell, vol. 42(5-6), pages 499-533, September.
    9. Allam, Abdelazziz & Mourid, Tahar, 2002. "Geometric absolute regularity of Banach space-valued autoregressive processes," Statistics & Probability Letters, Elsevier, vol. 60(3), pages 241-252, December.
    10. Predrag R. Jelenković & Jian Tan, 2010. "Modulated Branching Processes, Origins of Power Laws, and Queueing Duality," Mathematics of Operations Research, INFORMS, vol. 35(4), pages 807-829, November.
    11. Kevei, Péter, 2018. "Ergodic properties of generalized Ornstein–Uhlenbeck processes," Stochastic Processes and their Applications, Elsevier, vol. 128(1), pages 156-181.

    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:spr:metcap:v:20:y:2018:i:4:d:10.1007_s11009-017-9600-5. 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: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    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.