Let $\Omega$ be a finite state space, $(X_t)_{t\in\mathbb{N}}$ be a discrete-time Markov chain that converges to the uniform distribution, and $P$ be its transition matrix. I'm looking for different methods that estimates the distance in total variance to uniform at the $k$-step, that is $$\|P^k\cdot\pi-\left(\frac{1}{|\Omega|},\ldots,\frac{1}{|\Omega|}\right)\|_{TV}$$

for an initial distribution $\pi$. What heuristics are available that are broadly accepted?

So far, I tried an empirical approach that works as follows: Let $n:=|\Omega|$ and assume that after $k$-th steps of the Markov chain, you have observed $x_1,\ldots,x_m\in\Omega$, where you have seen sample $x_i$ exactly $s_i$ times (as a consequence $s_1+\ldots+s_m=k$). Then the distance to the uniform distribution in the $\|\cdot\|_1$ norm is precisely


In theory, this approach works. However, for giant samples spaces $\Omega$ (even if we possess a good approximation of $|\Omega|$), the evaluation of the sum is expensive in space and time since $m$ became huge during the computation.

  • $\begingroup$ can you explain the norm $||\cdot||_{TV}$? $\endgroup$
    – user75138
    Apr 25, 2016 at 21:10
  • $\begingroup$ Look at the eigenvalues of $P$. $\endgroup$
    – whuber
    Apr 25, 2016 at 21:15
  • $\begingroup$ Are you looking for a theoretical understanding of convergence, or more for convergence in practice? $\endgroup$ Apr 25, 2016 at 21:29
  • 1
    $\begingroup$ @Bey: Total Variation Distance. $\endgroup$
    – Alex R.
    Apr 25, 2016 at 22:22
  • $\begingroup$ @Greenparker: I'm looking for a convergence measurement in practice. $\endgroup$ Apr 26, 2016 at 4:39

1 Answer 1


You're interested in what's more generally called mixing time of a Markov chain which asks what the minimum $k$ is such that the total variation distance between your chain $P^k\pi$ and its stationary distribution is bounded by $\epsilon$. Even in finite state space, questions about mixing time can be highly nontrivial, and there exist many techniques for estimating them, for example as whuber mentions about looking at eigenvalues (particularly ratios of the largest$\neq 1$ over the smallest eigenvalues) of your chain. Perhaps your best bet is to take a look at one of the bibles on this topic: Markov Chains and Mixing Times by Levin, Peres and Wilmer, specifically chapter 4 and 12.

  • $\begingroup$ Thank you for your answer. I'm familiar with the theory of spectral gaps, mixing times, second largest eigenvalues, and the book of Levin et al. I'm looking more for a heuristic that to estimate the mixing time in practice. In my application, there is now way to get $P$ explicitely. $\endgroup$ Apr 26, 2016 at 4:44
  • $\begingroup$ @TobiasWindisch: it would really help if you specify what your $P$ is even if it's not possible to get explicitly. For example there are techniques for bounding TV by using a coupled markov chain which might be possible to find for your $P$. Otherwise the best you can say is something like $\|P^kx-\pi\|<Cr^k$ for some constants $C$ and $r\in(0,1)$. $\endgroup$
    – Alex R.
    Apr 26, 2016 at 17:25
  • $\begingroup$ Well, $P$ is the simple random walk on a $d$-regular graph $G$, that's all I can provide a priori. Unfortunately, $G$ can be any $d$-regular graph. Thats the reason why I hoped for a heuristic. $\endgroup$ Apr 26, 2016 at 17:58
  • $\begingroup$ @TobiasWindisch: that's a huge amount of information because you can use explicit conductance bounds and cheeger inequalities: cs.elte.hu/~lovasz/erdos.pdf $\endgroup$
    – Alex R.
    Apr 26, 2016 at 18:02
  • $\begingroup$ Please add that graph information to the body of your question. $\endgroup$
    – Alex R.
    Apr 26, 2016 at 18:31

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.