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.


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
    Jul 17 '19 at 11:53

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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