1
$\begingroup$

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.

$\endgroup$
8
  • 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$ Jan 22, 2018 at 21:31
  • $\begingroup$ @LucasRoberts I just changed the source so it should work now. $\endgroup$
    – tzu
    Jan 22, 2018 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, 2018 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, 2018 at 21:46
  • $\begingroup$ @jbowman Correct me if I'm wrong. Is that just $x$ ~ U(0,0.5)? $\endgroup$
    – tzu
    Jan 22, 2018 at 23:47

1 Answer 1

3
$\begingroup$

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.)

$\endgroup$
5
  • $\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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 21:24

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.