Convergence diagnostic of Markov chain that converge to uniform

Question

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

$$\sum_{i=1}^m\left|\frac{s_i}{k}-\frac{1}{n}\right|+\frac{n-m}{n}.$$

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.

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.