Random Walks and the Regeneration Time

Consider a random walk on a graph $G$. We want to stop the random walk at certain times (using an optimal stopping rule) to obtain independent samples from a given distribution $\rho$ 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.