8

The way to generate geometrically distributed random numbers is the following

$$\lfloor{\ln(u)/\ln(1-p)}\rfloor$$

where $u$ is uniformly distributed in $[0,1]$ and $p$ is the parameter in the geometric distribution.

But can anybody help provide a rigorous proof? I only see that $\ln(u)/\ln(1-p)$ is exponentially distributed, but how to get the geometric distribution?

Qiang Li
  • 4,097
  • Hint: what is the cdf of a geometric distribution? – Macavity Sep 06 '13 at 04:21
  • It is $F(X\le{k})=1-(1-p)^k$, but still I am not seeing how this can help to provide a rigorous proof if possible. – Qiang Li Sep 06 '13 at 04:34
  • Here's how - $\displaystyle P(\lfloor{\ln(u)/\ln(1-p)}\rfloor \le k) = \int_{\ln(u)/\ln(1-p) < k+1} du = \int_{(1-p)^{k+1}}^{1} du = 1 - (1-p)^{k+1}$ which is the cdf of geometric distribution. The method is quite general to take cdf and use a uniform random number to simulate a distribution. – Macavity Sep 06 '13 at 12:21

1 Answers1

7

Let us, as is customary, use capital letters for random variables, and consider $$ N=\lfloor{\ln(U)/\ln(1-p)}\rfloor, $$ where $U$ is uniform on $(0,1)$. Then $N$ is a random nonnegative integer and, for every $n\geqslant0$, the event $A_n=\{N=n\}$ is $$ A_n=\{(n+1)\ln(1-p)\lt\ln U\leqslant n\ln(1-p)\}. $$
(Note that $\ln(1-p)$ is negative.) Thus, $$ A_n=\{(1-p)^{n+1}\lt U\leqslant(1-p)^n\}. $$ For every $u\lt v$ in $(0,1)$, $P[u\lt U\leqslant v]=v-u$ hence $$ P[N=n]=P[A_n]=(1-p)^n-(1-p)^{n+1}=p(1-p)^n. $$ This proves that the distribution of $N$ is geometric (with parameter $p$ or $1-p$, depending on the convention used).

Did
  • 279,727
  • Unless Mauricio G Tec can fix his solution, I believe yours is correct, but not as general as his. – Qiang Li Sep 06 '13 at 06:21
  • Re generality, note that the inverse $F^{-1}$ of the CDF $F$ of a discrete random variable never exists. – Did Sep 06 '13 at 06:31