| Abstract: | Consider a graph G and a random walk on it. We want to stop the random walk at certain times (using an optimal stopping rule) to obtain independent samples from a given distribution ρ on the nodes. For an undirected graph, the expected time between consecutive samples is maximized by a distribution equally divided between two nodes, and so the worst expected time is 1/4 of the maximum commute time between two nodes. In the directed case, the expected time for this distribution is within a factor of 2 of the maximum. © 1998 John Wiley & Sons, Inc. J. Graph Theory 29: 57–62, 1998 |
