1

I'm currently researching monte carlo simulations and the different methods. What I'm finding is that methods such as accept-reject typically sample from a uniform distribution and then compare that to someone criteria that meets a target distribution.

My question is, does this go the other way? Say you were sampling from a binomial distribution and you wanted uniform discrete.

I believe you'd need to do something like f(x)/pdf(x) to balance out the samples of the proposal or else you'd just end up with the same target.

Is this possible? Are there any examples?

Seve Martinez
  • 35
  • 4
  • For a rejection sampler, your proposal distribution should have heavier tails than the target distribution. This ensures that you actually sample the extreme values of the distribution. The uniform(0,1) will be heavier tailed than most beta(a,b) distributions. This means that a U(0,1) would be a reasonable proposal to form a rejection sampler for beta(a,b). I could alternatively use a beta(a,b) as a proposal for uniform(0,1) this would likely be very inefficient. The main consideration is that the targets support must be a subset of the proposal support. – jcken Jun 10 '20 at 18:45
  • If you really want a uniform sample of $\{0,1,2,\ldots, n-1\}$ using a Binomial random number generator, sample from a Binomial$(n^2,1/2)$ distribution and reduce the results modulo $n.$ It will be *remarkably* uniform. (It that's not sufficiently accurate, you can follow it with a rejection step--but most of the time you won't reject anything.) This was inspired by method 8 of https://stats.stackexchange.com/a/117711/919. – whuber Dec 31 '21 at 17:15

2 Answers2

1

Sufficient conditions for the accept-reject to work are that the target, proposal pdf's $f$, $g$ satisfy

  1. $f(x)/g(x) \le M$ (some $M<\infty$) over the support of $g$, and

  2. the support of $g$ contains the support of $f$.

As mentioned, the efficiency will be affected by how small you can take $M$ to be, but any $f,g$ with $M<\infty$ can be used in principle.

If $g$ is Binom($n$,$p$) ($p\ne 0, 1$) and $f$ is uniform over $\{0,1,...,n\}$, then this works with $M=1/[(n+1) \min\{g(0), g(n)\}]$ since $g$ is unimodal. In fact, you'll be able to find $M$ for any $f$, $g$ with the same finite support, since you can just take $M=\max_x f(x)/g(x)<\infty$.

Then accept-reject works as usual:

  1. Generate $X\sim g$, $U\sim\mbox{Unif}(0,1)$ independently.
  2. Accept $X$ if $f(X)/g(X)\ge UM$. Otherwise, return to step 1.

In your case you can simplify things, e.g., the test in step 2 can be written $g(X)\le \min\{g(0), g(n)\}/U$.

Dedekind Cuts
  • 66
  • 5
1

The only constraint in the finite case is that both distributions have the same support. Meaning that $U_{0\le k\le n}(\{0,1,\ldots,n\})$ can indeed be simulated from a Binomial $B(n,p)$ for any $0<p<1$ once the upper bound $$M(p)=\max_{0\le k\le n} \dfrac{1/(n+1)}{{n \choose k}p^k(1-p)^{n-k}}= \dfrac{1/(n+1)}{\min_{0\le k\le n}{n \choose k}p^k(1-p)^{n-k}}$$ is found.

Xi'an
  • 90,397
  • 9
  • 157
  • 575