Loading...
Journal Title
Readers/Advisors
Journal Title
Term and Year
Publication Date
1995
Book Title
Publication Volume
Publication Issue
Publication Begin
Publication End
Number of pages
Collections
Files
Loading...
full-text
Adobe PDF, 9.16 MB
Research Projects
Organizational Units
Journal Issue
Abstract
Given a simple random walk on an undirected connected graph, the commute time of the vertices x and y is defined as C(x,y) = ExTy+EyTx. We give a new proof, based on the optional sampling theorem for martingales, of the formula C(x,y) = 1/(Π(y)e(y,x)) in terms of the escape probability e(y,x ) (the probability that once the random walk leaves x, it hits y before it returns to x) and the stationary distribution Π(·). We use this formula for C(x,y) to show that the maximum commute time among all barbell-type graphs in N vertices is attained for the lollipop graph and its value is O[(4N3)/27]
Citation
Northshield, S. & Palacios, J.L. (1995). On the Commute Time of Random Walks on Graphs. Brazilian Journal of Probability and Statistics, 9(2).
DOI
Description
This article has been published in the November 1995 issue of Brazilian Journal of Probability and Statistics.