Lower bounds on partial sums of expected hitting times

Hyungkuk Yoon; Bara Kim; Jeongsim Kim

doi:10.1016/j.spl.2020.108715

Lower bounds on partial sums of expected hitting times

Hyungkuk Yoon, Bara Kim, Jeongsim Kim

Department of Mathematics

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

Abstract

We consider a simple random walk on a connected undirected graph with N vertices. Palacios (2010) and Palacios and Renom (2012) investigated lower bounds on partial sums of expected hitting times of the random walk. In this paper, we show that Palacios’ (2010) lower bound is the best for all multigraphs. In addition, we show that the conjecture made by Palacios and Renom (2012) for simple graphs is true for N≤5, but it is not true for N≥6.

Original language	English
Article number	108715
Journal	Statistics and Probability Letters
Volume	160
DOIs	https://doi.org/10.1016/j.spl.2020.108715
Publication status	Published - 2020 May

Bibliographical note

Funding Information:
B. Kim’s research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) ( NRF-2017R1A2B4012676 ). J. Kim’s research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Korea ( 2017R1D1A1B03029542 ).

Publisher Copyright:
© 2020 Elsevier B.V.

Keywords

Hitting times
Random walks on graphs

ASJC Scopus subject areas

Statistics and Probability
Statistics, Probability and Uncertainty

Access to Document

10.1016/j.spl.2020.108715

Cite this

@article{2c5d65679f324f8f9c51e44621b48345,

title = "Lower bounds on partial sums of expected hitting times",

abstract = "We consider a simple random walk on a connected undirected graph with N vertices. Palacios (2010) and Palacios and Renom (2012) investigated lower bounds on partial sums of expected hitting times of the random walk. In this paper, we show that Palacios{\textquoteright} (2010) lower bound is the best for all multigraphs. In addition, we show that the conjecture made by Palacios and Renom (2012) for simple graphs is true for N≤5, but it is not true for N≥6.",

keywords = "Hitting times, Random walks on graphs",

author = "Hyungkuk Yoon and Bara Kim and Jeongsim Kim",

note = "Funding Information: B. Kim{\textquoteright}s research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) ( NRF-2017R1A2B4012676 ). J. Kim{\textquoteright}s research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Korea ( 2017R1D1A1B03029542 ). Publisher Copyright: {\textcopyright} 2020 Elsevier B.V.",

year = "2020",

month = may,

doi = "10.1016/j.spl.2020.108715",

language = "English",

volume = "160",

journal = "Statistics and Probability Letters",

issn = "0167-7152",

publisher = "Elsevier",

}

TY - JOUR

T1 - Lower bounds on partial sums of expected hitting times

AU - Yoon, Hyungkuk

AU - Kim, Bara

AU - Kim, Jeongsim

N1 - Funding Information: B. Kim’s research was supported by the National Research Foundation of Korea (NRF) grant funded by the Korea government (MSIP) ( NRF-2017R1A2B4012676 ). J. Kim’s research was supported by Basic Science Research Program through the National Research Foundation of Korea (NRF) funded by the Ministry of Education, Korea ( 2017R1D1A1B03029542 ). Publisher Copyright: © 2020 Elsevier B.V.

PY - 2020/5

Y1 - 2020/5

N2 - We consider a simple random walk on a connected undirected graph with N vertices. Palacios (2010) and Palacios and Renom (2012) investigated lower bounds on partial sums of expected hitting times of the random walk. In this paper, we show that Palacios’ (2010) lower bound is the best for all multigraphs. In addition, we show that the conjecture made by Palacios and Renom (2012) for simple graphs is true for N≤5, but it is not true for N≥6.

AB - We consider a simple random walk on a connected undirected graph with N vertices. Palacios (2010) and Palacios and Renom (2012) investigated lower bounds on partial sums of expected hitting times of the random walk. In this paper, we show that Palacios’ (2010) lower bound is the best for all multigraphs. In addition, we show that the conjecture made by Palacios and Renom (2012) for simple graphs is true for N≤5, but it is not true for N≥6.

KW - Hitting times

KW - Random walks on graphs

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

U2 - 10.1016/j.spl.2020.108715

DO - 10.1016/j.spl.2020.108715

M3 - Article

AN - SCOPUS:85078819982

SN - 0167-7152

VL - 160

JO - Statistics and Probability Letters

JF - Statistics and Probability Letters

M1 - 108715

ER -

Lower bounds on partial sums of expected hitting times

Abstract

Bibliographical note

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this