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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s