On the Commute Time of Random Walks on Graphs
dc.contributor.author | Northshield, Sam | |
dc.contributor.author | Palacios, Jose Luis | |
dc.date.accessioned | 2018-04-09T18:36:33Z | |
dc.date.accessioned | 2020-06-22T14:35:28Z | |
dc.date.available | 2018-04-09T18:36:33Z | |
dc.date.available | 2020-06-22T14:35:28Z | |
dc.date.issued | 1995 | |
dc.identifier.citation | Northshield, 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.uri | http://hdl.handle.net/20.500.12648/1108 | |
dc.description | This article has been published in the November 1995 issue of Brazilian Journal of Probability and Statistics. | en_US |
dc.description.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] | en_US |
dc.language | en_US | en_US |
dc.language.iso | en_US | en_US |
dc.publisher | Brazilian Journal of Probability and Statistics | en_US |
dc.subject | commute time | en_US |
dc.subject | cover time | en_US |
dc.subject | escape probability | en_US |
dc.subject | lollipop graph | en_US |
dc.title | On the Commute Time of Random Walks on Graphs | en_US |
dc.type | Article | en_US |
refterms.dateFOA | 2020-06-22T14:35:28Z | |
dc.description.institution | SUNY Plattsburgh |