# Proving the Accepted Samples from Rejection Sampling follows our Posterior Distribution

I get confused how Kevin Murphy gets to line $$(1)$$ in Machine Learning: A Probabilistic Perspective page 818 using the indicator functions. If someone can explain this to me or give me a hint that would be greatly appreciated. Thanks!

Define the following:
Let $$p(x)$$ be our posterior.
Let $$\tilde{p}(x)$$ be our unormalized posterior.
Let $$q(x)$$ be our proposal s.t $$Mq(x) \geq p(x)$$ for some constant $$M>0$$.
Let X be our sampled points.
Let $$S$$ = $$\{(x,u): u\leq\frac{\tilde{p}(x)}{Mq(x)}\}$$
Let $$S_{0}$$ = $$\{(x,u): u\leq\frac{\tilde{p}(x)}{Mq(x)}, x \leq x_{0}\}$$

Proof:

\begin{align*} P(X \leq x_{0} | X \text{ accepted})&= \frac{P(X \leq x_{0 }, X\text{ accepted})}{P(X\text{ accepted})} \\ &= \frac{\int\int\mathbb{1}((x,u)\in S_{0})q(x)dudx}{\int\int\mathbb{1}((x,u)\in S)q(x)dudx} \text{ (1)} \\ &= \frac{\int_{-\infty}^{x_{0}}\tilde{p}(x)dx }{\int_{-\infty}^{\infty}\tilde{p}(x)dx} \\ &= \text{CDF of p(x)} \end{align*}

• @Xi'an Machine Learning: A Probabilistic Perspective by Kevin Murphy. Page 818 under Rejection Sampling. Thanks! – Tomislav May 8 '19 at 13:50

First, the constant $$M$$ should be related to the unnormalised version $$\tilde p(\cdot)$$ and not to the normalised version $$p(\cdot)$$. Second, \begin{align}\int_\mathcal S q(x)\text{d}u\text{d}x &= \int_{-\infty}^\infty\int_0^1 \overbrace{\mathbb{1}_{u\le \tilde p(x)/Mq(x)}}^\text{conditional on x}\text{d}u q(x)\text{d}x\\&=\int_{-\infty}^\infty\int_0^{\tilde p(x)/Mq(x)}\text{d}u q(x)\text{d}x\\&=\int_{-\infty}^\infty \frac{\tilde p(x)}{Mq(x)}q(x)\text{d}x\\&=\int_{-\infty}^\infty \frac{\tilde p(x)}{M}\text{d}x\end{align} and \begin{align}\int_{\mathcal S_0} q(x)\text{d}u\text{d}x &= \int_{-\infty}^\infty\int_0^1 \mathbb{1}_{x