Hitting times in Markov chains with restart and their application to network centrality

Konstantin Avrachenkov; Alexey Piunovskiy; Yi Zhang

doi:10.1007/s11009-017-9600-5

Hitting times in Markov chains with restart and their application to network centrality

Konstantin Avrachenkov^*, Alexey Piunovskiy, Yi Zhang

^*Corresponding author for this work

Mathematics

Research output: Contribution to journal › Article › peer-review

9 Citations (Scopus)

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.

Original language	English
Pages (from-to)	1173-1188
Number of pages	16
Journal	Methodology and Computing in Applied Probability
Volume	20
Issue number	4
DOIs	https://doi.org/10.1007/s11009-017-9600-5
Publication status	Published - 1 Dec 2018

Bibliographical note

Funding Information:
This work was partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672. Y.Zhang?s work was carried out with a financial grant from the Research Fund for Coal and Steel of the European Commission, within the INDUSE-2-SAFETY project (Grant No. RFSR-CT-2014-00025).

Funding Information:
Acknowledgments This work was partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672. Y.Zhang’s work was carried out with a financial grant from the Research Fund for Coal and Steel of the European Commission, within the INDUSE-2-SAFETY project (Grant No. RFSR-CT-2014-00025).

Publisher Copyright:
© 2017, Springer Science+Business Media, LLC.

Keywords

Discrete-time Markov process with restart
Expected hitting time
Network centrality

ASJC Scopus subject areas

Statistics and Probability
Mathematics(all)

Access to Document

10.1007/s11009-017-9600-5

Cite this

@article{1cc26230928945c5b6e7a6a44ca593e3,

title = "Hitting times in Markov chains with restart and their application to network centrality",

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",

author = "Konstantin Avrachenkov and Alexey Piunovskiy and Yi Zhang",

note = "Funding Information: This work was partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672. Y.Zhang?s work was carried out with a financial grant from the Research Fund for Coal and Steel of the European Commission, within the INDUSE-2-SAFETY project (Grant No. RFSR-CT-2014-00025). Funding Information: Acknowledgments This work was partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672. Y.Zhang{\textquoteright}s work was carried out with a financial grant from the Research Fund for Coal and Steel of the European Commission, within the INDUSE-2-SAFETY project (Grant No. RFSR-CT-2014-00025). Publisher Copyright: {\textcopyright} 2017, Springer Science+Business Media, LLC.",

year = "2018",

month = dec,

day = "1",

doi = "10.1007/s11009-017-9600-5",

language = "English",

volume = "20",

pages = "1173--1188",

journal = "Methodology and Computing in Applied Probability",

issn = "1387-5841",

publisher = "Springer",

number = "4",

}

TY - JOUR

T1 - Hitting times in Markov chains with restart and their application to network centrality

AU - Avrachenkov, Konstantin

AU - Piunovskiy, Alexey

AU - Zhang, Yi

N1 - Funding Information: This work was partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672. Y.Zhang?s work was carried out with a financial grant from the Research Fund for Coal and Steel of the European Commission, within the INDUSE-2-SAFETY project (Grant No. RFSR-CT-2014-00025). Funding Information: Acknowledgments This work was partially supported by the European Commission within the framework of the CONGAS project FP7-ICT-2011-8-317672. Y.Zhang’s work was carried out with a financial grant from the Research Fund for Coal and Steel of the European Commission, within the INDUSE-2-SAFETY project (Grant No. RFSR-CT-2014-00025). Publisher Copyright: © 2017, Springer Science+Business Media, LLC.

PY - 2018/12/1

Y1 - 2018/12/1

N2 - 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.

AB - 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.

KW - Discrete-time Markov process with restart

KW - Expected hitting time

KW - Network centrality

UR - http://www.scopus.com/inward/record.url?scp=85032979603&partnerID=8YFLogxK

U2 - 10.1007/s11009-017-9600-5

DO - 10.1007/s11009-017-9600-5

M3 - Article

AN - SCOPUS:85032979603

SN - 1387-5841

VL - 20

SP - 1173

EP - 1188

JO - Methodology and Computing in Applied Probability

JF - Methodology and Computing in Applied Probability

IS - 4

ER -

Hitting times in Markov chains with restart and their application to network centrality

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Fingerprint

Cite this