I want to generate a negative binomial distribution from an uniform distribution. My attempt:
U follows $Unif(0,1)$.$X =\lfloor ln(U) \rfloor$.
$P(X=x)=P(\lfloor ln(U) \rfloor=x)$ =$P(x<=\lfloor ln(U) \rfloor<x+1)$=$e^{(x+1)}-e^{x}$
($x$ < $0$ is an integer)
There is still gap, and I wonder if this method is valid.
Could anyone give me some clues?
Let's start with the geometric distribution, which is a bit easier. One can easily derive random numbers satisfying a geometric distribution given uniformly distributed numbers by simply applying the geometric quantile function (or inverse cumulative distribution). Say $X\sim U([0,1])$ and we have
$$\mathbb{P}(G\leq k) = 1-(1-p)^k$$
where $p$ is the probability of success, $G$ is a geometric distributed random variable, and $k$ is an arbitrary number of trials. Then, we interpret our random number $X$ as the probability and invert the relation, i.e.
$$1-(1-p)^{k-1} \leq X < 1-(1-p)^{k}$$
or
$$ k-1 < \frac{\ln(1-X)}{\ln(1-p)}\leq k$$
Thus, we can define a random variable $K = \lceil\frac{\ln(1-X)}{\ln(1-p)}\rceil$, and that variable will have a geometric distribution. It's not important to have the $1-X$ in the numerator, we could equally define $K = \lceil\frac{\ln(U)}{\ln(1-p)}\rceil$ with $U\sim U([0,1])$, as $1-X$ is also uniformly distributed.
Now, one could try to generalize this approach to the negative binomial distribution, but here the cumulative distribution function is not so easy to invert. However, it turns out that a negative binomial distribution with parameters $p$ (probability of success) and $r$ (number of successes) can be seen as the sum of $r$ geometrically distributed random variables. Hence, all you need to do is generate $r$ geometrically distributed random variables and take the sum.
If this is not satisfactory, one could try rejection-sampling. The principle is to choose a distribution that is close to the negative binomial distribution but from which it is easier to generate a random variable. Then, an extra test is performed upon which the generated number is either accepted or rejected. This test is designed in such a way that the result satisfies the negative binomial distribution.