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
$\begingroup$
$\endgroup$
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$ Commented Jul 17, 2019 at 11:53