Proof of Approximate / Exact Bayesian Computation

Question

The ABC algorithm is given as

1. Draw $\theta \sim \pi(\theta)$
2. Simulate data $X \sim \pi(x | \theta)$
3. Accept $\theta$ if $\rho(X, D) < \varepsilon$

where $\pi(\theta)$ is the prior, $\pi(x | \theta)$ is the likelihood, $\rho(\cdot | \cdot)$ is some distance measure, $D$ is the observed data and $\varepsilon$ is the tolerance that represents a trade off between accuracy and computability.

Generally, in papers that I have seen on this, a proof is given where it states we actually sample from $\pi_{\varepsilon} = \pi(\theta | \rho(X, D) < \varepsilon)$ and then if $\varepsilon \to 0$, this converges to the true posterior $\pi(\theta | D)$.

If in Step 3, we had

3*. Accept $\theta$ if $X = D$

I was wondering if anyone knew how to prove that in this new algorithm, we sample from the true posterior? So there is no $\varepsilon \to 0$ argument?

Answer 1

This case is the original version of the algorithm, as in Rubin (1984) and Tavaré et al. (1997). Assuming that $$\mathbb{P}_\theta(X=D)>0$$ the values of $\theta$ that come out of the algorithm are distributed from a distribution with density proportional to $$\pi(\theta) \times \mathbb{P}_\theta(X=D)$$ since the algorithm generates the pair $(\theta,\mathbb{I}_{X=D})$ with joint distribution $$\pi(\theta) \times \mathbb{P}_\theta(X=D)^{\mathbb{I}_{X=D}} \times \mathbb{P}_\theta(X\ne D)^{\mathbb{I}_{X\ne D}}$$ Conditioning on $\mathbb{I}_{X=D}=1$ leads to $$\theta|\mathbb{I}_{X=D}=1 \sim \pi(\theta) \times \mathbb{P}_\theta(X=D)\Big/\int \pi(\theta) \times \mathbb{P}_\theta(X=D) \,\text{d}\theta$$ which is the posterior distribution.

On the side, I gave this very proof in class a few hours ago!