# Independent Metropolis--Hastings without a proposal

Given a target $\pi(x)$ and a proposal $q(x)$, we can form a $\pi$-reversible Markov chain by implementing the following few steps.

Assume $X_k \sim \pi$ is a sample from $\pi$, then
1. Sample $X' \sim q(x)$
2. Set $X_{k+1} = X'$ with probability $\min\bigl(1, \frac{\pi(X')/q(X')}{\pi(X_k)/q(X_k)}\bigr)$, otherwise set $X_{k+1} = X_k$.

The resulting sample $X_{k+1}$ will be distributed according to $\pi$ too.

As you can see, in the above, we needed to have access to an _exact_ sample from $q$ to implement this.

**What if we don't have one?**

In this case, let's assume you have access to a $q$-reversible kernel $K$, i.e., a kernel such that $K(y \mid x) q(x) = K(x \mid y) q(y)$ for all pairs of points $x, y$.

We can now form the augmented target distribution
\begin{align}
\pi(x) K(y \mid x) = \frac{\pi(x)}{q(x)} K(x \mid y) q(y)
\end{align}
and perform the following operations: given $X_k, Y_k$,
1. Sample $Y_{k+1} \sim K(y \mid X_k)$
2. Sample $X' \sim K(x \mid Y_{k+1})$
3. Set $X_{k+1} = X'$ with probability $\min\bigl(1, \frac{\pi(X')/q(X')}{\pi(X_k)/q(X_k)}\bigr)$.

Then, provided $X_k \sim \pi$, then $X_{k+1}$ will be according to $\pi$ too.

**Why would I want to do this?**
Up to you really, I have a specific application coming up (soon?), but in general, it's indeed a bit silly.
I just thought the construction to be cute enough to share it ahead of time and independently of the actual problem I'm solving.