# Negative Binomial

In this post I will show, using generating functions, that the sum of independent, identically distributed geometric random variables has a negative binomial distribution. More precisely, suppose ${X_k}$ is a sequence of independent random variables with ${X_k\sim\mathrm{Geo}(p)}$, i.e.

$\displaystyle \mathbb P(X_1=j)=(1-p)^jp, j=0,1,2,\ldots$

Then the generating function of ${X_k}$ is

\displaystyle \begin{aligned} \mathbb E[s^{X_k}] &= \sum_{j=0}^\infty (1-p)^jps^j\\ &= p\sum_{j=0}^\infty ((1-p)s)^j\\ &= \frac p{1 - (1-p)s}. \end{aligned}

For each positive integer ${r}$, let ${S_r = \sum_{k=1}^r X_k}$. Then the generating function of ${S_r}$ is

\displaystyle \begin{aligned} \mathbb E[s^{S_r}] &= \mathbb E[s^{\sum_{k=1}^r X_k}]\\ &= \prod_{k=1}^r \mathbb E[s^{X_k}]\\ &= \prod_{k=1}^r \frac p{1 - (1-p)s}\\ &= \left(\frac p{1 - (1-p)s} \right)^r. \end{aligned}

Now let ${Y\sim\mathrm{NegBin}(r,p)}$, i.e.

$\displaystyle \mathbb P(Y=j) = \binom {r+j-1}{j} p^r (1-p)^j, j=0,1,2,\ldots$

Then the generating function of ${Y}$ is

\displaystyle \begin{aligned} \mathbb E[s^Y] &= \sum_{j=0}^\infty \binom {r+j-1}{j} p^r (1-p)^j s^j\\ &= p^r \sum_{j=0}^\infty \binom {r+j-1}{j} ((1-p)s)^j. \end{aligned}

To compute this infinite series, let ${f(s) = (1-(1-p)s)^{-r}}$. We show that ${f^{(j)}(s) = \frac{(r+j-1)!}{(r-1)!}(1-p)^j(1-(1-p)s)^{-(r+j)}}$ and hence ${f^{(j)}(0) = \frac{(r+j-1)!}{(r-1)!}(1-p)^j}$ for each nonnegative integer ${j}$. For ${j=0}$, the claim is evident, as ${f(0) = 1 = \frac{(r-1)!}{(r-1)!}(1-p)^0}$. Assume the claim for some ${r\geqslant 0}$, then

\displaystyle \begin{aligned} f^{(j+1)}(s) &= \frac{\mathsf d}{\mathsf ds}[f^{(j)}(s)]\\ &= \frac{\mathsf d}{\mathsf ds}\left[\frac{(r+j-1)!}{(r-1)!}(1-p)^j(1-(1-p)s)^{-(r+j)} \right]\\ &= \frac{(r+j)(r+j-1)!}{(r-1)!}(1-p)^j(1-p)(1-(1-p)s)^{-(r+1+j)}\\ &= \frac{(r+j)!}{(r-1)!}(1-p)^{j+1}(1-(1-p)s)^{-(r+1+j)}. \end{aligned}

It follows that

$\displaystyle f^{(j+1)}(0) = \frac{(r+j)!}{(r-1)!}(1-p)^{j+1},$

thus proving the claim. Now, by Taylor’s theorem,

\displaystyle \begin{aligned} (1-(1-p)s)^{-r}=f(s) &= \sum_{j=0}^\infty \frac{f^{(j)}(0)}{j!}s^j\\ &= \sum_{j=0}^\infty \frac{\frac{(r+j-1)!}{(r-1)!}(1-p)^j}{j!}s^j\\ &= \sum_{j=0}^\infty \frac{(r+j-1)!}{j!(r-1)!}((1-p)s)^j\\ &= \sum_{j=0}^\infty \binom{r+j-1}{j}((1-p)s)^j, \end{aligned}

and hence

\displaystyle \begin{aligned} \mathbb E[s^Y] &= p^r(1-(1-p)s)^{-r} \\ &= \left(\frac p{1-(1-p)s} \right)^r\\ &= \mathbb E[s^{S_r}]. \end{aligned}

Since ${Y}$ and ${S_r}$ have the same generating function, we conclude that they have the same distribution.