Suppose that we start a lazy random walk on a connected graph. However, the starting node is picked from a distribution of $\mu$ and $||\mu-\pi||_{TV}<1/8$, where $\pi$ is the stationary distribution of the lazy random walk on the graph. Now I am interested to see if there is any result regarding the mixing time of this chain. For example, if we run the chain for $t$ steps rounds, what happens to the total variation distance of the chain from the stationary distribution.


1 Answer 1


For any vertex $v$, you can take $\mu$ to be $7/8 \pi + 1/8 v$, that is, the with probability $1/8$ pick $v$ and otherwise pick a random vertex according to $\pi$. Now the distance to stationarity at time $t$ will be $1/8$ of what it is when starting the chain at $v$. So it seems that there are really no new questions here to explore.

  • $\begingroup$ Thanks for the answer. What if we use other distance measure? Any idea? $\endgroup$
    – user86217
    Commented Jul 17, 2019 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.