Hitting Times of Walks on Graphs through Voltages

We derive formulas for the expected hitting times of general random walks on graphs, in terms of voltages, with very elementary electric means. Under this new light we revise bounds and hitting times for birth-and-death Markov chains and for walks on graphs with cutpoints, and give some exact computations on the necklace graph. We also prove Tetali’s formula for hitting times without making use of the reciprocity principle. In fact this principle follows as a corollary of our argument that also yields as corollaries the triangular inequality for effective resistances and the reversibility of the sum of hitting times around a tour. 1. Introduction On a finite connected undirected graph with such that the edge between vertices and is given a resistance (or equivalently, a conductance ), we can define the random walk on as the Markov chain , , that jumps from its current vertex to the neighboring vertex with probability , where and means that is a neighbor of . There may be a conductance from a vertex to itself, giving rise to a transition probability from to itself, though the most studied case of these random walks on graphs, the simple random walk (SRW), excludes the loops and considers all ’s to be equal to 1. The hitting time of the vertex is the number of jumps that the walk takes until it lands on , and its expected value when the walk starts at is denoted by . The beginner’s handbook when studying random walks on graphs from the viewpoint of electric networks is the work of Doyle and Snell [1], which is both a mandatory reference in this area of research and a textbook suitable for undergraduate students. Notably absent from this remarkable monograph is the discussion of hitting times using electric tools. The first such description seems to be due to Chandra et al. [2], where they give the formula for the commute time of the SRW: where is the number of edges of the graph and is the effective resistance, as computed by means of Ohm’s law, between vertices and . The commute time has a nice compact electric formulation, but the one-sided hitting time is a bit more complicated and it was first given by Tetali [3] through a clever use of the superposition principle and the reciprocity theorem for electric networks, yielding the following formula (here we give the simpler version for SRW): where is the number of neighbors of . In this paper we want to depart from these expressions of expected hitting times in terms of effective resistances and give them instead in terms of voltages, using as tools the material in Doyle and Snell’s book, which relies on