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.

  • 1
    $\begingroup$ 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. $\endgroup$ – Lucas Roberts Jan 22 '18 at 21:31
  • $\begingroup$ @LucasRoberts I just changed the source so it should work now. $\endgroup$ – tzu Jan 22 '18 at 21:41
  • $\begingroup$ Still, links break, and having to click through / click back-and-forth doesn't make it easy on your readers either. $\endgroup$ – jbowman Jan 22 '18 at 21:44
  • $\begingroup$ 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 ? $\endgroup$ – jbowman Jan 22 '18 at 21:46
  • $\begingroup$ @jbowman Correct me if I'm wrong. Is that just $x$ ~ U(0,0.5)? $\endgroup$ – 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.)

  • $\begingroup$ Thanks! This is clear and helpful. I tried to think of it but it only works under the discrete case. $\endgroup$ – tzu Jan 24 '18 at 5:31
  • $\begingroup$ 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! $\endgroup$ – tzu Jan 24 '18 at 5:37
  • $\begingroup$ 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. $\endgroup$ – jbowman Jan 24 '18 at 14:42
  • $\begingroup$ 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! $\endgroup$ – tzu Jan 24 '18 at 21:19
  • $\begingroup$ 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. $\endgroup$ – jbowman Jan 24 '18 at 21:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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