# Proof of Approximate / Exact Bayesian Computation

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?

Thanks in advance to anyone that can offer some help!

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.
• Thanks Xi'an! If this was extended outside of the Bayesian context, so for arbitrary functions $f_{1}(x)$ and $f_{2}(x)$, does this work to find samples from $f \propto f_{1}f_{2}$? – user-2147482565 Dec 3 '18 at 16:04
• Yes, indeed!, this is actually the most rudimentary form of acceptance-rejection: simulate $X$ from $f_1$ and accept if the realisation of $Y\sim f_2$ is equal to the realisation of $X$. – Xi'an Dec 3 '18 at 18:28