5
$\begingroup$

I have a few related questions regarding the convergence of continuous-state Markov chains.

The theorems that I found claim that Markov chains converge in total variation if they are $\phi$-irreducible and aperiodic (e.g. http://arxiv.org/pdf/math/0404033.pdf, Theorem 4). I am confused by the fact that the way this result is phrased, it does not seem to depend on the choice of $\phi$ but $\phi$-irreducibility seems to always hold for the trivial measure. Maybe I misinterpreted the definition of $\phi$-irreducibility? Could somebody help me understand this important result?

The other question that I have is: Under which conditions do Markov chains converge in KL-divergence (ideally with respect to $D_\text{KL}[P^n(x, \cdot), Q]$)? Is this known? Pinsker's inequality tells me that convergence in either KL-divergence is stronger than convergence in total variation.

Thanks!

$\endgroup$
4
$\begingroup$

It is important to state the theorem correctly with all conditions. Theorem 4 in the paper by Roberts and Rosenthal states that the $n$-step transition probabilities $P^n(x, \cdot)$ converge in total variation to a probability measure $\pi$ for $\pi$-almost all $x$ if the chain is $\phi$-irreducible, aperiodic and has $\pi$ as invariant initial distribution, that is, if $$\pi(A) = \int P(x, A) \pi(\mathrm{d}x).$$ There is also a technical condition that the $\sigma$-algebra on the state space should be countably generated. We return to this below. It is quite important for the general application of the theorem that one knows upfront that there is an invariant $\pi$ -- otherwise the chain can be null recurrent. In the MCMC context on $\mathbb{R}^d$ of the cited paper the chains are constructed with a given target distribution as invariant distribution so in this context it is only the $\phi$-irreducibility and aperiodicity that we need to check.

The authoritative reference on these matters is Meyn and Tweedies book Markov Chains and Stochastic Stability, which is also cited heavily in the paper. However, as far as I can tell, there are minor differences in the results presented in the paper and the book, and the paper do have a proof of Theorem 4.

Returning to the question, the $\phi$-measure used to define $\phi$-irreducibility is by assumption non-zero, so the trivial measure is ruled out (this is actually missing in the Meyn and Tweedie book, but stated correctly in the paper on page 31. The Meyn and Tweedie book also lacks the assumption of $\sigma$-finiteness that Roberts and Rosenthal make. I cannot see that it is possible to give this up either.)

To return to the assumption on a countably generated $\sigma$-algebra on a general state space, this assumption ensures that $\phi$-irreducible chains have small sets, see Theorem 19 in the paper. If you can prove the existence of a small set by other means the assumption on the $\sigma$-algebra can be dropped.

Regarding the second question, I am afraid I can't be of much assistance. Why is this of interest? I have not encountered problems where KL-convergence was needed specifically.

$\endgroup$
  • $\begingroup$ Thank you for this thorough response. This cleared it up for me. The KL-divergence is part of an objective function frequently encountered in machine learning problems. Basically, I would like to show that this objective function can be minimized using MCMC. $\endgroup$ – Lucas Apr 13 '12 at 14:47
  • $\begingroup$ @Lucas, without knowing your specific problem I wonder whether you need KL-convergence of the transition kernels in the MCMC algorithm or whether the MCMC algorithm is run as part of the computation or optimization of the KL-divergence under consideration. $\endgroup$ – NRH Apr 13 '12 at 15:05
  • $\begingroup$ The MCMC algorithm would be part of the optimization. From Cover & Thomas (Chapter 4.4) I know that applying a transition operator makes the KL divergence smaller, $D_\text{KL}[P^{n + 1}(x, \cdot) || Q] \leq D_\text{KL}[P^n(x, \cdot) || Q]$, but it would be nice to know when it actually minimizes it. $\endgroup$ – Lucas Apr 13 '12 at 15:53
  • $\begingroup$ @NRH Is there a simpler proof of Theorem 4 available, if $P$ is the transition kernel from the Random Walk Metropolis-Hastings algorithm? $\endgroup$ – 0xbadf00d Dec 29 '18 at 10:12
  • $\begingroup$ @0xbadf00d I’m not aware of such a proof. $\endgroup$ – NRH Dec 29 '18 at 10:19

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.