Robert Casella Independence Sampler Result

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), $$\|K(x,\cdot) -f\|_{TV} = 2 \sup_{A} |\int_{A} K(x,y) - f(y) dy|.$$ Where is this factor of 2 coming from? Ignoring the factor of 2 for a moment, the authors then obtain $$\|K(x,\cdot) -f\|_{TV} \leq 2 (1- 1/M),$$ 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.

You are correct that the factor $2$ does not make sense as written. It should be $$\|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$$ 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$$
• 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. – user2379888 Mar 24 '17 at 16:45
• 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. – Xi'an Mar 24 '17 at 18:07
• 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. – user2379888 Mar 24 '17 at 18:40