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?


1 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!

  • 1
    $\begingroup$ 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}$? $\endgroup$ Commented Dec 3, 2018 at 16:04
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Xi'an
    Commented Dec 3, 2018 at 18:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.