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.

[学科分类] 统计和概率