Accept-Reject algorithm from binomial or other non-uniform distribution 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?
 A: Sufficient conditions for the accept-reject to work are that the target, proposal pdf's $f$, $g$ satisfy 


*

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

*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:


*

*Generate $X\sim g$, $U\sim\mbox{Unif}(0,1)$ independently.

*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$.
A: 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.
