Lower bounds on partial sums of expected hitting times

초록

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. (C) 2020 Elsevier B.V. All rights reserved.

키워드