Hitting times for random walks on vertex-transitive graphs

David Aldous

Mathematical Proceedings of the Cambridge Philosophical Society · 1989 · 51 citations · 15 references

Concepts

Abstract

Abstract For random walks on finite graphs, we record some equalities, inequalities and limit theorems (as the size of graph tends to infinity) which hold for vertex-transitive graphs but not for general regular graphs. The main result is a sharp condition for asymptotic exponentiality of the hitting time to a single vertex. Another result is a lower bound for the coefficient of variation of hitting times. Proofs exploit the complete monotonicity properties of the associated continuous-time walk.

References

15