1
$\begingroup$

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.

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

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.

| cite | improve this answer | |
$\endgroup$
  • $\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$ – Tobias Windisch Apr 26 '16 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 '16 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$ – Tobias Windisch Apr 26 '16 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 '16 at 18:02
  • $\begingroup$ Please add that graph information to the body of your question. $\endgroup$ – Alex R. Apr 26 '16 at 18:31

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.