# Proof of Rejection Sampling

I'm trying to go through the proof of rejection sampling and I found a paper ACCEPTANCE-REJECTION SAMPLING MADE EASY which provides several helpful explanations. For Lemma 2, the paper claims that if $Z$ has a uniform distribution $A$, and let $B \subset A$ and then the conditional distribution of $Z$ given $Z \in B$ is uniform in $B$. However, it does not provide proof. Can anyone help? Thanks.

• the paper is behind a paywall. It will be helpful for you to write the lemma in the post so that the post is fully self-contained. – Lucas Roberts Jan 22 '18 at 21:31
• @LucasRoberts I just changed the source so it should work now. – tzu Jan 22 '18 at 21:41
• Still, links break, and having to click through / click back-and-forth doesn't make it easy on your readers either. – jbowman Jan 22 '18 at 21:44
• As a thought experiment, imagine $x \sim \text{U}(0,1)$, and you find out that $x < 0.5$. What do you suppose the conditional distribution of $x : x\in(0, 0.5)$ is ? – jbowman Jan 22 '18 at 21:46
• @jbowman Correct me if I'm wrong. Is that just $x$ ~ U(0,0.5)? – tzu Jan 22 '18 at 23:47

I'll construct a proof of a simpler proposition which should make it clear how the more general one is done. Let $z \sim \text{U}(0,1)$. Then the density $p(z) = 1$ and the cumulative distribution $P(z) = z$. Now let us find the conditional distribution of $z | z < c$, i.e., $z \in (0,c)$.

Using the definition of conditional probability, $p(z|z<c)p(z<c) = p(z)$. In our case, $p(z<c) = c$ from the definition of the cumulative distribution and $p(z) = 1$ from the definition of the density. Rearranging terms gives:

$$p(z|z<c) = {p(z) \over p(z<c)} = {1 \over c}$$

Since $p(z|z<c)$ is constant for all $z$, the distribution is clearly Uniform over $(0,c)$. (The "constant for all $z$" part is why the distribution is called "Uniform", so this is really definitional.)

• Thanks! This is clear and helpful. I tried to think of it but it only works under the discrete case. – tzu Jan 24 '18 at 5:31
• Sorry, one more question. Isn't $p(z|z<c)p(z<c) = p(z,z<c)$? Why is $p(z,z<c)=p(z)$? To me, $p(z,z<c)$ should be equal to $p(z<c)$ since $z$ could be larger than $c$.Thanks! – tzu Jan 24 '18 at 5:37
• You can see that can't be the case because the multiplication won't work out. In order for your calculation to work, $p(z|z<c)$ would always have to equal 1, regardless of the probability distributions involved. The trick is that the range of $z$ changes, and I should have made that explicit with indicator functions. – jbowman Jan 24 '18 at 14:42
• Thanks for the probabilistic explanation that the integral of the probability should be 1. I am still trying to make an explanation based on the term of the intersection to explain that why $P(z,z<c)=P(z)$. So far my thought is that if $z\sim U(0,1)$ and the probability I randomly draw a $z$ and this $z$ is less than $c$ should just be $p(z)$, this is due to that I just draw one $z$ so which area this $z$ is should not affect the probability I draw it. Any suggestion? Thanks! – tzu Jan 24 '18 at 21:19
• Think of $p(z<c)$ as a normalizing constant. If we restrict $z < c$, it's clear that $p(z|z<c) = a*p(z)$, where $a$ is some constant independent of $z$, because we aren't changing the shape of $p(z)$ over the range $z<c$. We are now left with the following problem: $\int_{z<c}p(z)\text{d}z \neq 1$, so it's not a real probability distribution. How to make it one? If we set $a = 1/\int_{z<c}p(z)\text{d}z$, then clearly it WILL integrate to 1. And... $p(z<c) = \int_{z<c}p(z)\text{d}z$. So dividing $p(z)$ by $p(z<c)$ just normalizes it over the range $z<c$ so it will integrate to 1. – jbowman Jan 24 '18 at 21:24