Name
Abstract | ||
|---|---|---|
Consider a graph G and a random walk on it. We want tostop the random walk at certain times (using an optimal stoppingrule) to obtain independent samples from a given distribution ρon the nodes. For an undirected graph, the expected time betweenconsecutive samples is maximized by a distribution equally dividedbetween two nodes, and so the worst expected time is 1-4 of themaximum commute time between two nodes. In the directed case, theexpected time for this distribution is within a factor of 2 of themaximum. © 1998 John Wiley & Sons, Inc. J. Graph Theory29: 5762, 1998 |
Year | DOI | Venue |
|---|---|---|
1998 | 10.1002/(SICI)1097-0118(199810)29:2<>1.0.CO;2-I | Journal of Graph Theory |
Keywords | Field | DocType |
random walk,inc. j. graph theory29,themaximum commute time,theexpected time,regeneration time,undirected graph,graph g,worst expected time,certain time,john wiley,expected time betweenconsecutive sample,optimal stopping | Graph theory,Random regular graph,Loop-erased random walk,Combinatorics,Random graph,Random walk,Random geometric graph,Stopping time,Heterogeneous random walk in one dimension,Mathematics | Journal |
Volume | Issue | ISSN |
29 | 2 | 0364-9024 |
Citations | PageRank | References |
2 | 0.51 | 1 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Andrew Beveridge | 1 | 55 | 8.21 |
| László Lovász | 2 | 791 | 152.09 |