# Why is $\frac1n\sum_{i=0}^{n-1}\sum_{j=0}^i1_{\{\:X_i\:=\:Y_j\:\}}f(Y_j)$ an equivalent representation for the usual Metropolis-Hastings estimator?

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 as suggested in Taylor's answer. It would be sufficient to show that, given $$1\le m, $$\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{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$$$$ and $$$$\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$$$$ for all $$x_1,y_1\in E$$.

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

• 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). – Taylor Nov 6 '19 at 20:11
• 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. – hejseb Nov 6 '19 at 20:32
• @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.) – 0xbadf00d Nov 7 '19 at 5:32
• @hejseb Intuitively, it should not be possible, but I'm asking how this can be proved formally. – 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.

## Edit:

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.

• 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)$. – 0xbadf00d Nov 6 '19 at 5:56
• $\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"? – 0xbadf00d Nov 6 '19 at 5:57
• @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]" – Taylor Nov 6 '19 at 13:41
• @0xbadf00d regarding the request for more formality, I can work on that – Taylor Nov 6 '19 at 13:42
• 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. – 0xbadf00d Nov 6 '19 at 15:59