3
$\begingroup$

In the second edition of the Robert & Casella book (Monte Carlo Statistical Methods), the authors have a result, Theorem 7.8, on the independent Metropolis-Hastings sampler: Letting $f$ be the density of the target measure an $g$ the density of the proposal, if a minimization condition is satisfied $f(x)\leq M g(x)$ for all $x$ in the support of $f$, then the chain is uniformly ergodic and $$ \| K^n(x,\cdot) - f\|_{TV} \leq 2 (1-1/M)^n $$

The proof begins with an odd result (equation 7.9), \begin{equation} \|K(x,\cdot) -f\|_{TV} = 2 \sup_{A} |\int_{A} K(x,y) - f(y) dy|. \end{equation} Where is this factor of 2 coming from? Ignoring the factor of 2 for a moment, the authors then obtain \begin{equation} \|K(x,\cdot) -f\|_{TV} \leq 2 (1- 1/M), \end{equation} which I agree with, except, again, for the factor of 2. They then say that, by induction, one can obtain the result.

The best that I can obtain is $$ (2\|K^n(x, \cdot) - f\|_{TV})\leq (2\|K(x, \cdot) - f\|_{TV})^n \leq (2(1-1/M))^n, $$ which is based on a computation in Roberts & Rosenthal (2004) in Probability Surveys.

This calculation has been driving me nuts.

Improve this question
$\endgroup$
1
$\begingroup$

You are correct that the factor $2$ does not make sense as written. It should be \begin{equation} \|K(x,\cdot) -f\|_{TV} \stackrel{\text{def}}{=} \sup_{A} \left|\int_{A} K(x,y) - f(y) \text{d}y\right| = \dfrac{1}{2} \int_{A} |K(x,y) - f(y)| \text{d}y \end{equation} which only involves a $1/2$ for the L¹ distance (as recalled in the Wikipedia page about TV). In my current version of the book, there is actually no 2, so it is quite possible we have removed the 2 when realising it is a typo as written! Apologies about this typo.

For the proof of this inequality, the easiest approach is to use coupling: since $$K(x,y)\ge\frac{1}{M} f(y)$$ the kernel can be written as $$K(x,y)=\frac{1}{M} f(y)+\left(1-\frac{1}{M}\right)\frac{MK(x,y)-f(y)}{M-1}$$ Therefore, at each transition, the next generation is from $f$ with probability $1/M$, thus is not from $f$ with probability at most $$\left(1-\frac{1}{M}\right)\qquad\qquad(1)$$This means that the total variation distance between $f$ and $K(x,\cdot)$ is at most (1). Similarly, by a geometric argument, the generation at stage $n$ is not from $f$ with probability at most $$\left(1-\frac{1}{M}\right)^n$$

Improve this answer
$\endgroup$
4
  • 1
    $\begingroup$ That answers one matter, but shouldn't it be $\|K(x,\cdot)-f \| = \frac{1}{2}\int_{E} |K(x,y) - f(y)|dy$ with $E$ being the entire state space? While I then agree with (7.10)/(7.11), in the inductive step, don't you have, $\|K^{n+1}(x,\cdot) -f\| \leq \int_{E} |\int_A K^n(u,y) - f(y) dy| |K(x,u) - f(u)| du \leq 2(1-1/M)^n \int_{E}|K(x,u) - f(u)| du \leq 4(1-1/M)^{n+1}$? It looks like there's an amplification. $\endgroup$ – user2379888 Mar 24 '17 at 16:45
  • 2
    $\begingroup$ Also, the edition I am looking at is hardback, printed in the United States, and dated 2004. $\endgroup$ – user2379888 Mar 24 '17 at 16:46
  • $\begingroup$ Thanks! (0) You are correct, in the hardcover edition, the superfluous 2 is present. I was looking at my LaTeX file. (1) You are correct, it should be $1/2$ not too, as I now stand corrected. (2) You do not need the 2, see the addendum. $\endgroup$ – Xi'an Mar 24 '17 at 18:07
  • 2
    $\begingroup$ Ok, I am still confused. Let us agree that $\|K(x,\cdot) - f\| = \sup_{A} |\int_A K(x,y) - f(y) dy|$ is the definition of the TV norm. Suppose our goal is to obtain the published result, (7.8), that $\|K^n(x,\cdot) -f\|\leq 2 (1-1/M)^n$, and assume this holds up to $n$. Then in the inductive step, we still have to contend with $\|K^{n+1}(x,\cdot) - f\|\leq \int_{E} \sup_A|\int_A K^n(u,y) - f(y) dy| |K(x,u)-f(u)|du\leq 2 (1-1/M)^{n} 2 \|K(x,\cdot) -f(\cdot)\|\leq 4(1-1/M)^{n+1}$ from the use of the $L^1$ norm form of TV, and I am still stuck. $\endgroup$ – user2379888 Mar 24 '17 at 18:40

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.