Geometric distribution

Not to be confused with Hypergeometric distribution.

In probability theory and statistics, the geometric distribution is either one of two discrete probability distributions:

• The probability distribution of the number $X$ of Bernoulli trials needed to get one success, supported on $\mathbb {N} =\{1,2,3,\ldots \}$;
• The probability distribution of the number $Y=X-1$ of failures before the first success, supported on $\mathbb {N} _{0}=\{0,1,2,\ldots \}$.

Geometric

Probability mass function
Cumulative distribution function
Parameters	$0<p\leq 1$ success probability (real)	$0<p\leq 1$ success probability (real)
Support	k trials where $k\in \mathbb {N} =\{1,2,3,\dotsc \}$	k failures where $k\in \mathbb {N} _{0}=\{0,1,2,\dotsc \}$
PMF	$(1-p)^{k-1}p$	$(1-p)^{k}p$
CDF	$1-(1-p)^{\lfloor x\rfloor }$ for $x\geq 1$, $0$ for $x<1$	$1-(1-p)^{\lfloor x\rfloor +1}$ for $x\geq 0$, $0$ for $x<0$
Mean	${\frac {1}{p}}$	${\frac {1-p}{p}}$
Median	$\left\lceil {\frac {-1}{\log _{2}(1-p)}}\right\rceil$ (not unique if $-1/\log _{2}(1-p)$ is an integer)	$\left\lceil {\frac {-1}{\log _{2}(1-p)}}\right\rceil -1$ (not unique if $-1/\log _{2}(1-p)$ is an integer)
Mode	$1$	$0$
Variance	${\frac {1-p}{p^{2}}}$	${\frac {1-p}{p^{2}}}$
Skewness	${\frac {2-p}{\sqrt {1-p}}}$	${\frac {2-p}{\sqrt {1-p}}}$
Excess kurtosis	$6+{\frac {p^{2}}{1-p}}$	$6+{\frac {p^{2}}{1-p}}$
Entropy	${\tfrac {-(1-p)\log(1-p)-p\log p}{p}}$	${\tfrac {-(1-p)\log(1-p)-p\log p}{p}}$
MGF	${\frac {pe^{t}}{1-(1-p)e^{t}}},$ for $t<-\ln(1-p)$	${\frac {p}{1-(1-p)e^{t}}},$ for $t<-\ln(1-p)$
CF	${\frac {pe^{it}}{1-(1-p)e^{it}}}$	${\frac {p}{1-(1-p)e^{it}}}$
PGF	${\frac {pz}{1-(1-p)z}}$	${\frac {p}{1-(1-p)z}}$

These two different geometric distributions should not be confused with each other. Often, the name shifted geometric distribution is adopted for the former one (distribution of $X$); however, to avoid ambiguity, it is considered wise to indicate which is intended, by mentioning the support explicitly.

The geometric distribution gives the probability that the first occurrence of success requires $k$ independent trials, each with success probability $p$. If the probability of success on each trial is $p$, then the probability that the $k$-th trial is the first success is

$\Pr(X=k)=(1-p)^{k-1}p$

for $k=1,2,3,4,\dots$

The above form of the geometric distribution is used for modeling the number of trials up to and including the first success. By contrast, the following form of the geometric distribution is used for modeling the number of failures until the first success:

$\Pr(Y=k)=\Pr(X=k+1)=(1-p)^{k}p$

for $k=0,1,2,3,\dots$

The geometric distribution gets its name because its probabilities follow a geometric sequence. It is sometimes called the Furry distribution after Wendell H. Furry.

Definition

The geometric distribution is the discrete probability distribution that describes when the first success in an infinite sequence of independent and identically distributed Bernoulli trials occurs. Its probability mass function is$$P(X=k)=(1-p)^{k-1}p$$where $k=1,2,3,\dotsc$ is the number of trials and $p$ is the probability of success in each trial.

Alternatively, some texts define the distribution where $k=0,1,2,\dotsc$ and call the former the zero-truncated geometric distribution. This alters the probability mass function into:$$P(Y=k)=(1-p)^{k}p$$An example of a geometric distribution arises from rolling a six-sided die until a "1" appears. Each roll is independent with a $1/6$ chance of success. The number of rolls needed follows a geometric distribution with $p=1/6$.

Properties

Memorylessness

Main article: Memorylessness

The geometric distribution is the only memoryless discrete probability distribution. It is the discrete version of the same property found in the exponential distribution. The property asserts that the number of previously failed trials does not affect the number of future trials needed for a success. Expressed in terms of conditional probability, $$\Pr(X>m+n\mid X>n)=\Pr(X>m)$$where $m$ and $n$ are natural numbers. The equality is still true when ≥ is substituted.

Moments and cumulants

The expected value and variance of a geometrically distributed random variable $X$ defined over $\mathbb {N}$ is$$\operatorname {E} (X)={\frac {1}{p}},\qquad \operatorname {var} (X)={\frac {1-p}{p^{2}}}.$$ When a geometrically distributed random variable $Y$ defined over $\mathbb {N} _{0}$, the expected value changes into$$\operatorname {E} (Y)={\frac {1-p}{p}},$$while the variance stays the same.

For example, when rolling a six-sided die until landing on a "1", the average number of rolls needed is ${\frac {1}{1/6}}=6$ and the average number of failures is ${\frac {1-1/6}{1/6}}=5$.

The moment generating function of the geometric distribution when defined over $\mathbb {N}$ and $\mathbb {N} _{0}$ respectively is$${\begin{aligned}M_{X}(t)&={\frac {pe^{t}}{1-(1-p)e^{t}}}\\M_{Y}(t)&={\frac {p}{1-(1-p)e^{t}}},t<-\ln(1-p)\end{aligned}}$$The moments for the number of failures before the first success are given by

${\begin{aligned}\mathrm {E} (Y^{n})&{}=\sum _{k=0}^{\infty }(1-p)^{k}p\cdot k^{n}\\&{}=p\operatorname {Li} _{-n}(1-p)&({\text{for }}n\neq 0)\end{aligned}}$

where $\operatorname {Li} _{-n}(1-p)$ is the polylogarithm function.

The cumulants $\kappa _{n}$ of the probability distribution of Y satisfy the recursion

$\kappa _{n+1}=\mu (\mu +1){\frac {d\kappa _{n}}{d\mu }}.$

where $\mu ={\frac {1-p}{p}}$, the expected value of a geometrically distributed random variable defined over $\mathbb {N} _{0}$.

Proof of expected value

Consider the expected value $\mathrm {E} (X)$ of X as above, i.e. the average number of trials until a success. On the first trial, we either succeed with probability $p$, or we fail with probability $1-p$. If we fail the remaining mean number of trials until a success is identical to the original mean. This follows from the fact that all trials are independent. From this we get the formula:

$\operatorname {E} (X)=p\cdot 1+(1-p)\cdot (1+\mathrm {E} (X)),$

which, if solved for $\mathrm {E} (X)$, gives:

$\operatorname {E} (X)={\frac {1}{p}}.$

The expected value of $Y$ can be found from the linearity of expectation, $\mathrm {E} (Y)=\mathrm {E} (X-1)=\mathrm {E} (X)-1={\frac {1}{p}}-1={\frac {1-p}{p}}$. It can also be shown in the following way:

${\begin{aligned}\operatorname {E} (Y)&{}=\sum _{k=0}^{\infty }(1-p)^{k}p\cdot k\\&{}=p\sum _{k=0}^{\infty }(1-p)^{k}k\\&{}=p(1-p)\sum _{k=0}^{\infty }(1-p)^{k-1}\cdot k\\&{}=p(1-p)\left[{\frac {d}{dp}}\left(-\sum _{k=0}^{\infty }(1-p)^{k}\right)\right]\\&{}=p(1-p){\frac {d}{dp}}\left(-{\frac {1}{p}}\right)={\frac {1-p}{p}}.\end{aligned}}$

The interchange of summation and differentiation is justified by the fact that convergent power series converge uniformly on compact subsets of the set of points where they converge.

Summary statistics

The mean of the geometric distribution is its expected value which is, as previously discussed in § Moments and cumulants, ${\frac {1}{p}}$ or ${\frac {1-p}{p}}$ when defined over $\mathbb {N}$ or $\mathbb {N} _{0}$ respectively.

The median of the geometric distribution is $\left\lfloor -{\frac {\log 2}{\log(1-p)}}\right\rfloor$ when defined over $\mathbb {N} _{0}$.

The mode of the geometric distribution is the first value in the support set. This is 1 when defined over $\mathbb {N}$ and 0 when defined over $\mathbb {N} _{0}$.

The skewness of the geometric distribution is ${\frac {2-p}{\sqrt {1-p}}}$.

The kurtosis of the geometric distribution is $9+{\frac {p^{2}}{1-p}}$. The excess kurtosis of a distribution is the difference between its kurtosis and the kurtosis of a normal distribution, $3$. Therefore, the excess kurtosis of the geometric distribution is $6+{\frac {p^{2}}{1-p}}$. Since ${\frac {p^{2}}{1-p}}\geq 0$, the excess kurtosis is always positive so the distribution is leptokurtic. In other words, the tail of a geometric distribution decays faster than a Gaussian.

General properties

• The probability generating functions of geometric random variables $X$ and $Y$ defined over $\mathbb {N}$ and $\mathbb {N} _{0}$ are, respectively,

${\begin{aligned}G_{X}(s)&={\frac {s\,p}{1-s\,(1-p)}},\\[10pt]G_{Y}(s)&={\frac {p}{1-s\,(1-p)}},\quad |s|<(1-p)^{-1}.\end{aligned}}$

• The characteristic function $\varphi (t)$ is equal to $G(e^{it})$ so the geometric distribution's characteristic function, when defined over $\mathbb {N}$ and $\mathbb {N} _{0}$ respectively, is$${\begin{aligned}\varphi _{X}(t)&={\frac {pe^{it}}{1-(1-p)e^{it}}},\\[10pt]\varphi _{Y}(t)&={\frac {p}{1-(1-p)e^{it}}}.\end{aligned}}$$
• The entropy of a geometric distribution with parameter $p$ is$$-{\frac {p\log _{2}p+(1-p)\log _{2}(1-p)}{p}}$$
• Given a mean, the geometric distribution is the maximum entropy probability distribution of all discrete probability distributions. The corresponding continuous distribution is the exponential distribution.
• The geometric distribution of the number Y of failures before the first success is infinitely divisible, i.e., for any positive integer n, there exist independent identically distributed random variables Y₁, ..., Y_n whose sum has the same distribution that Y has. These will not be geometrically distributed unless n = 1; they follow a negative binomial distribution.
• The decimal digits of the geometrically distributed random variable Y are a sequence of independent (and not identically distributed) random variables. For example, the hundreds digit D has this probability distribution:

$\Pr(D=d)={q^{100d} \over 1+q^{100}+q^{200}+\cdots +q^{900}},$

where q = 1 − p, and similarly for the other digits, and, more generally, similarly for numeral systems with other bases than 10. When the base is 2, this shows that a geometrically distributed random variable can be written as a sum of independent random variables whose probability distributions are indecomposable.

• Golomb coding is the optimal prefix code for the geometric discrete distribution.

Related distributions

• The sum of $r$ independent geometric random variables with parameter $p$ is a negative binomial random variable with parameters $r$ and $p$. The geometric distribution is a special case of the negative binomial distribution, with $r=1$.

• The geometric distribution is a special case of discrete compound Poisson distribution.
• The minimum of $n$ geometric random variables with parameters $p_{1},\dotsc ,p_{n}$ is also geometrically distributed with parameter $1-\prod _{i=1}^{n}(1-p_{i})$.

• Suppose 0 < r < 1, and for k = 1, 2, 3, ... the random variable X_k has a Poisson distribution with expected value r^k/k. Then

$\sum _{k=1}^{\infty }k\,X_{k}$

has a geometric distribution taking values in $\mathbb {N} _{0}$, with expected value r/(1 − r).

• The exponential distribution is the continuous analogue of the geometric distribution. Applying the floor function to the exponential distribution with parameter $\lambda$ creates a geometric distribution with parameter $p=1-e^{-\lambda }$ defined over $\mathbb {N} _{0}$. This can be used to generate geometrically distributed random numbers as detailed in § Random variate generation.

• If p = 1/n and X is geometrically distributed with parameter p, then the distribution of X/n approaches an exponential distribution with expected value 1 as n → ∞, since

${\begin{aligned}\Pr(X/n>a)=\Pr(X>na)&=(1-p)^{na}=\left(1-{\frac {1}{n}}\right)^{na}=\left[\left(1-{\frac {1}{n}}\right)^{n}\right]^{a}\\&\to [e^{-1}]^{a}=e^{-a}{\text{ as }}n\to \infty .\end{aligned}}$

More generally, if p = λらむだ/n, where λらむだ is a parameter, then as n→ ∞ the distribution of X/n approaches an exponential distribution with rate λらむだ:

$\Pr(X>nx)=\lim _{n\to \infty }(1-\lambda /n)^{nx}=e^{-\lambda x}$

therefore the distribution function of X/n converges to $1-e^{-\lambda x}$, which is that of an exponential random variable.

Statistical inference

The true parameter $p$ of an unknown geometric distribution can be inferred through estimators and conjugate distributions.

Method of moments

Provided they exist, the first $l$ moments of a probability distribution can be estimated from a sample $x_{1},\dotsc ,x_{n}$ using the formula$$m_{i}={\frac {1}{n}}\sum _{j=1}^{n}x_{j}^{i}$$where $m_{i}$ is the $i$th sample moment and $1\leq i\leq l$. Estimating $\mathrm {E} (X)$ with $m_{1}$ gives the sample mean, denoted ${\bar {x}}$. Substituting this estimate in the formula for the expected value of a geometric distribution and solving for $p$ gives the estimators ${\hat {p}}={\frac {1}{\bar {x}}}$ and ${\hat {p}}={\frac {1}{{\bar {x}}+1}}$ when supported on $\mathbb {N}$ and $\mathbb {N} _{0}$ respectively. These estimators are biased since $\mathrm {E} \left({\frac {1}{\bar {x}}}\right)>{\frac {1}{\mathrm {E} ({\bar {x}})}}=p$ as a result of Jensen's inequality.

Maximum likelihood estimation

The maximum likelihood estimator of $p$ is the value that maximizes the likelihood function given a sample. By finding the zero of the derivative of the log-likelihood function when the distribution is defined over $\mathbb {N}$, the maximum likelihood estimator can be found to be ${\hat {p}}={\frac {1}{\bar {x}}}$, where ${\bar {x}}$ is the sample mean. If the domain is $\mathbb {N} _{0}$, then the estimator shifts to ${\hat {p}}={\frac {1}{{\bar {x}}+1}}$. As previously discussed in § Method of moments, these estimators are biased.

Regardless of the domain, the bias is equal to

$b\equiv \operatorname {E} {\bigg [}\;({\hat {p}}_{\mathrm {mle} }-p)\;{\bigg ]}={\frac {p\,(1-p)}{n}}$

which yields the bias-corrected maximum likelihood estimator,

${\hat {p\,}}_{\text{mle}}^{*}={\hat {p\,}}_{\text{mle}}-{\hat {b\,}}$

Bayesian inference

In Bayesian inference, the parameter $p$ is a random variable from a prior distribution with a posterior distribution calculated using Bayes' theorem after observing samples. If a beta distribution is chosen as the prior distribution, then the posterior will also be a beta distribution and it is called the conjugate distribution. In particular, if a $\mathrm {Beta} (\alpha ,\beta )$ prior is selected, then the posterior, after observing samples $k_{1},\dotsc ,k_{n}\in \mathbb {N}$, is$$p\sim \mathrm {Beta} \left(\alpha +n,\ \beta +\sum _{i=1}^{n}(k_{i}-1)\right).\!$$Alternatively, if the samples are in $\mathbb {N} _{0}$, the posterior distribution is$$p\sim \mathrm {Beta} \left(\alpha +n,\beta +\sum _{i=1}^{n}k_{i}\right).$$The posterior mean approaches its maximum likelihood estimate ${\widehat {p}}$ as $\alpha$ and $\beta$ approach zero, regardless of the support.

Unbiased estimator

An unbiased estimator of $p$ will, on average, equal the true parameter. Expressed in terms of expectation, the unbiased estimator $T(x)$ satisfies $\mathrm {E} (T(x))=p$. For the geometric distribution, the unbiased estimator would need to satisfy:$$\sum _{x=1}^{\infty }T(x)p(1-p)^{x-1}=p$$The only solution to this equation is,$$T(x)={\begin{cases}1&x=1\\0&x\geq 2\end{cases}}$$This estimator is not useful when $p$ is not close to 0 or 1.

Random variate generation

Further information: Non-uniform random variate generation

The geometric distribution can be generated experimentally from i.i.d. standard uniform random variables by finding the first such random variable to be less than or equal to $p$. However, the number of random variables needed is also geometrically distributed and the algorithm slows as $p$ decreases.

Random generation can be done in constant time by truncating exponential random numbers. An exponential random variable $E$ can become geometrically distributed with parameter $p$ through $\lceil -E/\log(1-p)\rceil$. In turn, $E$ can be generated from a standard uniform random variable $U$ altering the formula into $\lceil \log(U)/\log(1-p)\rceil$.

See also

• Hypergeometric distribution
• Coupon collector's problem
• Compound Poisson distribution
• Negative binomial distribution

External links

• Geometric distribution on MathWorld.