Lower bounds on partial sums of expected hitting times

Hyungkuk Yoon, Bara Kim, Jeongsim Kim

    Research output: Contribution to journalArticlepeer-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 languageEnglish
    Article number108715
    JournalStatistics and Probability Letters
    Volume160
    DOIs
    Publication statusPublished - 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

    Fingerprint

    Dive into the research topics of 'Lower bounds on partial sums of expected hitting times'. Together they form a unique fingerprint.

    Cite this