At the beginning of section 2 of the paper A Vanilla Rao-Blackwellization of Metropolis-Hastings Algorithms, the usual Metorpolis-Hastings estimator of $\int f$ given by the ergodic average $\frac1n\sum_{i=0}^{n-1}f(X_i)$ may equivalently be written as $\frac1n\sum_{i=0}^{n-1}\sum_{j=0}^i1_{\left\{\:X_i\:=\:Y_j\:\right\}}f(Y_j)$, where $(X_n)_{n\in\mathbb N_0}$ is the chain generated by the algorithm, $(Y_n)_{n\in\mathbb N}$ is the corresponding sequence of proposals and $Y_0:=X_0$.

However, while the idea behind this equivalent representation is clear to me, I don't understand why it holds. Couldn't it be the case that, for a particular outcome $\omega$, $X_i(\omega)=Y_j(\omega)=Y_k(\omega)$ and hence $f(Y_j(\omega))$ is mistakenly counted (at least) twice compared to the ergodic mean?

EDIT: Let's try to figure out if we can prove $$\operatorname P[\exists 1\le i<j\le k:Y_{n_i}=Y_{n_j}]=0\;\;\;\text{for all }k\in\mathbb N\text{ and }1\le n_1<\cdots<n_k\tag1$$ as suggested in Taylor's answer. It would be sufficient to show that, given $1\le m<n$, $$\operatorname P\left[Y_m=Y_n\right]=0\tag2.$$ In order for this to make sense, we technically need to assume that $\Delta:=\left\{(x,x):x\in E\right\}\in\mathcal E^{\otimes2}$, where $(E,\mathcal E)$ denotes the state space. We know that $$Z_k:=(X_{k-1},Y_k)\;\;\;\text{for }k\in\mathbb N$$ is a time-homogeneous Markov chain with transition kernel $$\kappa_{\text{aug}}((x,y),A\times B):=(1-\alpha(x,y))\delta_x(A)Q(x,B)+\delta_y(A)\alpha(x,y)Q(y,B)$$ for $x,y\in E$ and $A,B\in\mathcal E$, where $\alpha$ denotes the acceptance function of the algorithm.. Thus, $$(Z_m,Z_n)\sim\mathcal L(Z_m)\otimes\kappa_{\text{aug}}\tag3$$ and $$\mathcal L(Z_m)\sim\mathcal L(X_{m-1})\otimes Q\tag4,$$ where $Q$ denotes the proposal kernel. Assume $Q$ and the target distribution $\mu$ have a density $q$ and $p$ with respect to a common reference measure $\lambda$. For simplicity, let's focus on the case $n-m=1$. Then, \begin{equation}\begin{split}&\operatorname P\left[Y_{n-1}=Y_n\right]=\operatorname P\left[(Y_{n-1},Y_n)\in\Delta\right]\\&\;\;\;\;=\operatorname P\left[X_{m-1}\in{\rm d}x_1\right]\int Q(x_1,{\rm d}y_1)\int\kappa_{\text{aug}}((x_1,y_1),{\rm d}(x_2,y_2))1_\Delta((y_1,y_2))\end{split}\tag5\end{equation} and \begin{equation}\begin{split}&\int\kappa_{\text{aug}}((x_1,y_1),{\rm d}(x_2,y_2))1_\Delta((y_1,y_2))\\&\;\;\;\;=(1-\alpha(x_1,y_1))\int Q(x_1,{\rm d}y_2)1_\Delta((y_1,y_2))+\alpha(x_1,y_1)\int Q(y_1,{\rm d}y_2)1_\Delta((y_1,y_2))\end{split}\tag6\end{equation} for all $x_1,y_1\in E$.

How can we show that $(5)$ (or maybe already $(6)$) vanishes?

  • $\begingroup$ the time index thing is confusing me here still. I'll need to agree with that before I agree with how you've written down $\kappa_{\text{aug}}$. I think it might even be more than that though-- when you write $Q(y,B)$, you are saying that the proposal is being generated from previous proposal (which isn't the case for the Metropolis-Hastings algorithm). $\endgroup$ – Taylor Nov 6 '19 at 20:11
  • $\begingroup$ Why would it ever be the case that two proposals (from a continuous family of distributions) would be equal? I have a hard time understanding why you would even question this to begin with. $\endgroup$ – hejseb Nov 6 '19 at 20:32
  • $\begingroup$ @Taylor $\kappa_{\text{aug}}$ is the transition kernel of the joint chain. See, for example, section 3.1 here: arxiv.org/pdf/1805.07174.pdf. ($Q$ is called $P$ therein.) $\endgroup$ – 0xbadf00d Nov 7 '19 at 5:32
  • $\begingroup$ @hejseb Intuitively, it should not be possible, but I'm asking how this can be proved formally. $\endgroup$ – 0xbadf00d Nov 7 '19 at 5:32

As you say, it is sufficient to show that, with probability $1$, all proposed points $Y_t$ are distinct. Note that the fact that the $X_t$ come from a Markov chain is inessential to showing that the $Y_t$ are distinct.

More precisely, assume that we are working in $\mathbf R^d$, and that the proposal kernel has a density (e.g. a Gaussian random walk proposal). It is then simpler to show the following:

Let $X_1, \ldots, X_N$ be arbitrary points in $\mathbf R^d$. For $i = 1, \ldots, N$, independently draw $Y_i \sim q ( X_i \to Y_i ) $. Then, with probability $1$, $Y_1, \ldots, Y_N$ are all distinct.

The argument of @Taylor then works here: the probability that $Y_i = Y_j$ for any pair $(i, j)$ is $0$, since the proposals have a density, and then by a union bound, one deduces that all of the $Y_i$ are distinct.


The proposals are coming from a density, so they should all be different with probability one.

It might make it clearer if you write out a sample path from the algorithm. Think of the chain on the extended space $$ (X_t, Y_t) | (X_{t-1}, Y_{t-1}) \sim q(y_t \mid x_{t-1}) p(x_t \mid y_t, x_{t-1}) $$ where $p(x_t \mid y_t, x_{t-1})$ is the binary distribution on the support $\{x_{t-1}, y_t\}$. Say we started the chain at $1.2$ (or written in this way, it would be $(1.2,1.2)$):

Xi      | 1.2 | 5.0| 5.0 | 7.3
Yj      | 1.2 | 5.0| 6.2 | 7.3
 action | NA  | Ac | Fa  | Ac

So the first proposal you accept, the second you reject, and then the third you accept. Notice that the inner sum goes from $0$ to $i$. This counts the preceding proposal in the case of a rejection, and it counts the contemporaneous accepted proposal in the case of an acceptance. In either event, you won't double-count anything because $q(y_t | x_{t-1})$ doesn't have any mass on anywhere.


I'm going to suppose $j < i$ to keep more in line with the notation above.

\begin{align*} P[\exists 1\le j < i\le k:Y_{n_i}=Y_{n_j}] &\le \sum_{1\le j< i\le k} P[Y_{n_i} = Y_{n_j}] \end{align*}

Each summand is an integral over a set of measure $0$. If $n_i$ and $n_j$ are next to each other, for instance, the measure is $\mu_{n_j} \otimes Q$ which has mass on a horizontal slab, but if you integrate over a diagonal sliver, you should be good. Note that $\mu_{n_j}$ is just the marginal distribution, which may or may not be the stationary distribution, but yes, it does have mass on the starting point.

  • $\begingroup$ Thank you for your answer. I have some problems to follow your explanations. First of all, I guess our indices are off by $1$: Given $X_{n-1}$, I sample $Y_n$ from $Q(X_n,\;\cdot\;)$. Now I guess you're assuming the chain is stationary. Then $X_n\sim\mu$ and $Z_n:=(X_{n-1},Y_n)\sim\mu\otimes Q$. Now I don't see how you obtain your formula for the condition distribution. We should have $(Z_n,Z_{n+1})\sim\mathcal L(Z_n)\otimes\kappa$, where $\kappa((x,y),A\times B)=(1-\alpha(x,y))\delta_x(A)Q(x,B)+\delta_y(A)\alpha(x,y)Q(y,B)$. So, $\text P[Z_{n+1}\in A\times B\mid Z_n]=\kappa(Z_n,A\times B)$. $\endgroup$ – 0xbadf00d Nov 6 '19 at 5:56
  • $\begingroup$ $\alpha$ is denoting the acceptance function of the algorithm. (b) In order to show that all proposals are different with probability $1$, we would need to show that for all $k\in\mathbb N$ and $n_1<\cdots<n_k$, $$\operatorname P[\exists 1\le i<j\le k:Y_{n_i}=Y_{n_j}]=0.$$ I don't see how this follows. Can you formalize your argument that it follows from the fact that "the proposals are coming from a density"? $\endgroup$ – 0xbadf00d Nov 6 '19 at 5:57
  • $\begingroup$ @0xbadf00d first, I don't get pinged for comments unless you "@" me. Second, I think my indices are okay. You propose values for the next iteration of the chain, given the current state: "Given $X_{n-1}$, I sample $Y_n$ from $Q(X_{n-1}, \cdot)$ [sic]" $\endgroup$ – Taylor Nov 6 '19 at 13:41
  • $\begingroup$ @0xbadf00d regarding the request for more formality, I can work on that $\endgroup$ – Taylor Nov 6 '19 at 13:42
  • $\begingroup$ I cannot "@" you in a comment below a post of you. You should automatically get notified about any such comment. I'll check your edit soon. $\endgroup$ – 0xbadf00d Nov 6 '19 at 15:59

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.