Hitting Times in Markov Chains with Restart and their Application to Network Centrality - Archive ouverte HAL Access content directly
Journal Articles Methodology and Computing in Applied Probability Year : 2018

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

(1) , (2) , (2)
1
2

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.
Fichier principal
Vignette du fichier
HitWRestartAuthorVersion.pdf (313.75 Ko) Télécharger le fichier
Origin : Files produced by the author(s)
Loading...

Dates and versions

hal-01937983 , version 1 (28-11-2018)

Identifiers

Cite

Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang. Hitting Times in Markov Chains with Restart and their Application to Network Centrality. Methodology and Computing in Applied Probability, 2018, 20 (4), pp.1173 - 1188. ⟨10.1007/s11009-017-9600-5⟩. ⟨hal-01937983⟩
45 View
57 Download

Altmetric

Share

Gmail Facebook Twitter LinkedIn More