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.
Bibliographical noteFunding 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 ).
© 2020 Elsevier B.V.
- Hitting times
- Random walks on graphs
ASJC Scopus subject areas
- Statistics and Probability
- Statistics, Probability and Uncertainty