Show simple item record

dc.contributor.authorNorthshield, Sam
dc.contributor.authorPalacios, Jose Luis
dc.date.accessioned2018-04-09T18:36:33Z
dc.date.accessioned2020-06-22T14:35:28Z
dc.date.available2018-04-09T18:36:33Z
dc.date.available2020-06-22T14:35:28Z
dc.date.issued1995
dc.identifier.citationNorthshield, S. & Palacios, J.L. (1995). On the Commute Time of Random Walks on Graphs. Brazilian Journal of Probability and Statistics, 9(2).en_US
dc.identifier.urihttp://hdl.handle.net/20.500.12648/1108
dc.descriptionThis article has been published in the November 1995 issue of Brazilian Journal of Probability and Statistics.en_US
dc.description.abstractGiven 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]en_US
dc.languageen_USen_US
dc.language.isoen_USen_US
dc.publisherBrazilian Journal of Probability and Statisticsen_US
dc.subjectcommute timeen_US
dc.subjectcover timeen_US
dc.subjectescape probabilityen_US
dc.subjectlollipop graphen_US
dc.titleOn the Commute Time of Random Walks on Graphsen_US
dc.typeArticleen_US
refterms.dateFOA2020-06-22T14:35:28Z
dc.description.institutionSUNY Plattsburgh


Files in this item

Thumbnail
Name:
fulltext.pdf
Size:
9.157Mb
Format:
PDF
Description:
full-text

This item appears in the following Collection(s)

Show simple item record