TAOCP 3.4.1 Exercise 17
Let $X$ be a random variable representing the number of trials until the first success in a sequence of independent Bernoulli trials with success probability $p$, $0 < p \le 1$.
Section 3.4.1: Numerical Distributions
Exercise 17. ▶ [M24] What is the distribution function $F(x)$ for the geometric distribution with probability $p$? What is the generating function $G(z)$? What are the mean and standard deviation of this distribution?
Verified: yes
Solve time: 1m33s
Solution
Let $X$ be a random variable representing the number of trials until the first success in a sequence of independent Bernoulli trials with success probability $p$, $0 < p \le 1$. By definition, $X$ takes values in the set ${1, 2, 3, \ldots}$. The probability that the first success occurs on the $n$th trial is given by
$\Pr{X = n} = (1-p)^{n-1} p, \qquad n = 1, 2, 3, \ldots$
The distribution function $F(x)$ is the probability that $X \le x$ for a real number $x$. Since $X$ is integer-valued, for $x < 1$ we have $F(x) = 0$, and for $x \ge 1$, letting $\lfloor x \rfloor$ denote the greatest integer not exceeding $x$,
$$ F(x) = \Pr{X \le x} = \sum_{n=1}^{\lfloor x \rfloor} (1-p)^{n-1} p. $$
This is a geometric series with ratio $1-p$, summing to
$$ F(x) = p \frac{1 - (1-p)^{\lfloor x \rfloor}}{1 - (1-p)} = 1 - (1-p)^{\lfloor x \rfloor}, \qquad x \ge 1. $$
Thus the distribution function of the geometric distribution is
$$ \boxed{F(x) = 1 - (1-p)^{\lfloor x \rfloor}, \quad x \ge 1; \quad F(x) = 0, \quad x < 1.} $$
The generating function $G(z)$ is defined by
$$ G(z) = \sum_{n=1}^{\infty} \Pr{X = n} z^n = \sum_{n=1}^{\infty} (1-p)^{n-1} p, z^n = p z \sum_{n=0}^{\infty} [(1-p) z]^n. $$
This is a geometric series with ratio $(1-p)z$, which converges for $|z| < 1/(1-p)$. Summing the series yields
$$ G(z) = \frac{p z}{1 - (1-p) z}, \qquad |z| < \frac{1}{1-p}. $$
The mean of $X$ is
$$ \mathbb{E}[X] = \sum_{n=1}^{\infty} n \Pr{X = n} = \sum_{n=1}^{\infty} n (1-p)^{n-1} p. $$
Using the standard identity $\sum_{n=1}^{\infty} n r^{n-1} = 1/(1-r)^2$ for $|r|<1$ with $r = 1-p$, we obtain
$$ \mathbb{E}[X] = p \cdot \frac{1}{p^2} = \frac{1}{p}. $$
The variance of $X$ is
$$ \operatorname{Var}(X) = \mathbb{E}[X^2] - (\mathbb{E}[X])^2. $$
Compute $\mathbb{E}[X^2]$ using the identity $\sum_{n=1}^{\infty} n^2 r^{n-1} = \frac{1+r}{(1-r)^3}$:
$$ \mathbb{E}[X^2] = p \sum_{n=1}^{\infty} n^2 (1-p)^{n-1} = p \cdot \frac{2 - p}{p^3} = \frac{2 - p}{p^2}. $$
Thus
$$ \operatorname{Var}(X) = \frac{2 - p}{p^2} - \frac{1}{p^2} = \frac{1 - p}{p^2}. $$
The standard deviation is
$$ \sigma = \sqrt{\operatorname{Var}(X)} = \frac{\sqrt{1-p}}{p}. $$
$$ \boxed{\mathbb{E}[X] = \frac{1}{p}, \qquad \sigma = \frac{\sqrt{1-p}}{p}, \qquad G(z) = \frac{p z}{1 - (1-p) z}, \qquad F(x) = 1 - (1-p)^{\lfloor x \rfloor} \text{ for } x \ge 1.} $$
This completes the proof.
∎