HAL will be down for maintenance from Friday, June 10 at 4pm through Monday, June 13 at 9am. More information
Skip to Main content Skip to Navigation
Reports

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

Konstantin Avrachenkov 1 Alexey Piunovskiy 2 Yi Zhang 3
1 NEO - Network Engineering and Operations
CRISAM - Inria Sophia Antipolis - Méditerranée
3 imagine - Extraction de Caractéristiques et Identification
LIRIS - Laboratoire d'InfoRmatique en Image et Systèmes d'information
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.
Complete list of metadata

https://hal.inria.fr/hal-01055893
Contributor : Konstantin Avrachenkov Connect in order to contact the contributor
Submitted on : Thursday, March 9, 2017 - 7:33:57 PM
Last modification on : Friday, February 4, 2022 - 3:33:50 AM
Long-term archiving on: : Saturday, June 10, 2017 - 3:31:30 PM

Files

RR8581/RR-8581.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-01055893, version 3
  • ARXIV : 1503.08548

Citation

Konstantin Avrachenkov, Alexey Piunovskiy, Yi Zhang. Hitting Times in Markov Chains with Restart and their Application to Network Centrality. [Research Report] RR-8581, Inria. 2017, pp.15. ⟨hal-01055893v3⟩

Share

Metrics

Record views

2771

Files downloads

20174