# Probability of acceptance for Rejection Sampling

I wondered if someone could confirm if this is correct. The probability of accepting a sample from the proposal distribution $$q(z)$$ is given by the ratio $$\frac{\tilde {p}(z)}{kq(z)}$$ where $$\tilde {p}(z)$$ is the unnormalised true posterior and $$k$$ the scaling factor. This itself is not the acceptance probability (although I thought it was). It seems the acceptance probability is $$\frac{1}{k}$$ which is rationalised as follows:

$$\int \frac{\tilde {p}(z)}{kq(z)} q(z) dz = \frac{1}{k}$$ which seems that we take an expectation over this acceptance probability to get an average over all terms? Is this correct?

Both quantities are acceptance probabilities, assuming of course that the dominating inequality$$\sup_{z\in\mathfrak X}\dfrac{\tilde {p}(z)}{kq(z)}\le 1$$holds.
First, the quantity$$\dfrac{\tilde {p}(z)}{kq(z)}$$is the conditional probability of acceptance given that $$z$$ is the outcome of a (marginal) simulation from $$q(\cdot)$$. Defining the indicator random variable $$I=\mathbb I_{U\le {\tilde {p}(z)}/{kq(z)}}$$ when $$U\sim \mathfrak U(0,1)$$, $$I\in\{0,1\}$$ and is therefore a Bernoulli random variable. Conditionally on $$Z=z$$, when $$Z\sim q(z)$$, $$I$$ is a Bernoulli random variable$$\mathcal B(\tilde {p}(z)/{kq(z)})$$
Second, marginally, i.e., on its own, $$I$$ is a Bernoulli random variable with parameter $$p=\mathbb P(I=1) = \int_\mathfrak Z \dfrac{\tilde {p}(z)}{kq(z)} q(z)\text d z=\frac{1}{k}$$ (the last equality assuming both $$\tilde p(\cdot)$$ and $$q(\cdot)$$ are probability densities, i.e., are properly normalised). Therefore, $$1/k$$ is the average and marginal probability of acceptance in the accept-reject algorithm.
Note that, while $$Z$$ is marginally distributed from $$q(\cdot)$$, conditional on $$I$$, we have $$Z|I=1 \sim \tilde p(z) \quad\text{and}\quad Z|I=1 \sim \dfrac{kq(z)-\tilde p(z)}{k-1}$$
• Would you be able to edit your answer to show this formally? I do not see how $I$ is marginally bernoulli $B(\frac{1}{K})$ Mar 15, 2021 at 17:57