# Rejection sampling

## Direct sampling

### Density estimation through direct sampling

I THINK THE STUFF HERE IS LIMITATIONS TO REJECTION SAMPLING??

DIRECT SAMPLING IS DOING PHYSICAL SAMPLES, MANUALLY PICKING BALLS FROM URL ETC?

There is distribution $$P(x)$$ which we want to know more about.

If the function was closed, we could estimate it by using values of $$x$$.

### Limitations of direct sampling

However if the function does not have such a form, we cannot do that.

We can’t plug in values, because the function is complex.

Sometimes we may know a function of the form:

$$f(x)=cP(x)$$

That is, a multiple of the function.

This can happen from Bayes’ theorem:

$$P(y|x)=\dfrac{P(x|y)P(y)}{P(x)}$$

We may be able to estimate $$P(x|y)$$ and $$P(y)$$, but not $$P(x)$$

This means be have

$$P(y|x)=cP(x|y)P(y)$$

## Acceptance-rejection sampling

### Introduction

Used to sample from propability distribution function.

Useful when can’t use direct sampling, because no closed form.

MORE GENERALLY FRAME THESE FIRST AS SAMPLING FROM PROBABILITY FUNCTION.

Generate pairs of $$(x, y)$$. If $$y<P(x)$$ then keep $$x$$.

Metropolis-Hastings and Gibb’s sampling are extensions of this.