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

Konstantin Avrachenkov (), Alexey Piunovskiy () and Yi Zhang ()
Additional contact information
Konstantin Avrachenkov: Inria Sophia Antipolis
Alexey Piunovskiy: University of Liverpool
Yi Zhang: University of Liverpool

Methodology and Computing in Applied Probability, 2018, vol. 20, issue 4, 1173-1188

Abstract: 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.

Keywords: Discrete-time Markov process with restart; Expected hitting time; Network centrality; 60J05; 60J20 (search for similar items in EconPapers)
Date: 2018
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s11009-017-9600-5 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:metcap:v:20:y:2018:i:4:d:10.1007_s11009-017-9600-5

Ordering information: This journal article can be ordered from
https://www.springer.com/journal/11009

DOI: 10.1007/s11009-017-9600-5

Access Statistics for this article

Methodology and Computing in Applied Probability is currently edited by Joseph Glaz

More articles in Methodology and Computing in Applied Probability from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().