Editing Geometric distribution (section)

== Random variate generation ==
{{Further|Non-uniform random variate generation}}
The geometric distribution can be generated experimentally from [[i.i.d.]] [[Standard uniform distribution|standard uniform]] random variables by finding the first such random variable to be less than or equal to <math>p</math>. However, the number of random variables needed is also geometrically distributed and the algorithm slows as <math>p</math> decreases.<ref name=":6">{{Cite book |last=Devroye |first=Luc |url=http://link.springer.com/10.1007/978-1-4613-8643-8 |title=Non-Uniform Random Variate Generation |publisher=Springer New York |year=1986 |isbn=978-1-4613-8645-2 |location=New York, NY |language=en |doi=10.1007/978-1-4613-8643-8}}</ref>{{Rp|page=498}}

Random generation can be done in [[constant time]] by truncating [[exponential random numbers]]. An exponential random variable <math>E</math> can become geometrically distributed with parameter <math>p</math> through <math>\lceil -E/\log(1-p) \rceil</math>. In turn, <math>E</math> can be generated from a standard uniform random variable <math>U</math> altering the formula into <math>\lceil \log(U) / \log(1-p)\rceil</math>.<ref name=":6" />{{Rp|pages=499–500}}<ref>{{Cite book |last=Knuth |first=Donald Ervin |title=The Art of Computer Programming |publisher=[[Addison-Wesley]] |year=1997 |isbn=978-0-201-89683-1 |edition=3rd |volume=2 |location=Reading, Mass |pages=136 |language=en}}</ref>