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}\}$


\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*}

  • 1
    $\begingroup$ @Xi'an Machine Learning: A Probabilistic Perspective by Kevin Murphy. Page 818 under Rejection Sampling. Thanks! $\endgroup$
    – Tomislav
    Commented May 8, 2019 at 13:50

1 Answer 1


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<x_0}\overbrace{\mathbb{1}_{u\le \tilde p(x)/Mq(x)}}^\text{conditional on $x$}\text{d}u q(x)\text{d}x\\&=\int_{-\infty}^{x_0}\int_0^{\tilde p(x)/Mq(x)}\text{d}u q(x)\text{d}x\\&=\int_{-\infty}^{x_0}\frac{\tilde p(x)}{Mq(x)}q(x)\text{d}x\\&=\int_{-\infty}^{x_0} \frac{\tilde p(x)}{M}\text{d}x\end{align}


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.