Generating Geometric Random Variables from Uniforms

1. Goal

Generate a random variable $X$ satisfying the geometric distribution with parameter $p$:

$$\begin{array}{r}P\{X=i\}=p{q}^{i-1},i\ge 1,\text{where }q=1-p.\end{array}$$

2. Derivation

由几何分布的含义, $X$ 可认为是 $n$ 次独立实验中首次成功的时间, 且每次实验的成功概率为 $p$, 故有:

$$\begin{array}{rl}\sum _{i=1}^{j-1}P\{X=i\}& =1-P\{X>j-1\}\\ & =1-P\{\text{first }j-1\text{ trials are all failures}\}\\ & =1-q^{j-1},j\ge 1.\end{array}$$

Thus generate a random number $U$ and let:

$$1-q^{j-1}\le U<1-q^j\Rightarrow q^j<1-U\le q^{j-1}.$$

Therefore:

$$X=\mathrm{Min}\left\{j:q^j<1-U\right\}.(\star )$$

Taking log on both sides:

$$\begin{array}{rl}X& =\mathrm{Min}\{j:j\log (q)<\log (1-U)\}\\ & =\mathrm{Min}\left\{j:j>\frac{\log (1-U)}{\log (q)}\right\}.\end{array}$$

If $\mathrm{Int}(x)$ means the largest integer not greater than $x$, then:

$$X=\mathrm{Int}\left(\frac{\log (1-U)}{\log (q)}\right)+1.$$

Equivalently:

$$\boxed{X\equiv \mathrm{Int}\left(\frac{\log (U)}{\log (q)}\right)+1}.$$

Related Notes

• Generating Discrete Random Variables
• Generating Exponential Random Variables from Uniforms