Mathematical Proceedings of the Cambridge Philosophical Society · 1989 · 51 citations · 15 references
Natural SciencesMathematicsCombinatoricsProbability TheoryStochastic ProcessesDirected Acyclic GraphsGraph TheoryMarkov ChainsMarkov ProcessesProbabilistic CombinatoricsRandom WalksAsymptotic PropertiesHitting TimesMonotonicity ConditionsRandom GraphsRandom Walk Hitting TimesRandom Walk Limit TheoremsRandom Walk LimitsRandom Walks On Graphs
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.
15
Applied Probability and Queues.
Upendra Dave, Søren Asmussen · Journal of the Operational Research Society · 1987 · 2.8K citations
Random walks, universal traversal sequences, and the complexity of maze problems
Romas Aleliunas, Richard M. Karp, Richard J. Lipton et al. · 1979 · 705 citations
F. Göbel, A. A. Jagers · Stochastic Processes and their Applications · 1974 · 251 citations · Full text
Applied Probability and Queues
Upendra Dave · Journal of the Operational Research Society · 1987 · 167 citations