How to compute the sum of random variables of geometric distribution

Solution 1:

Let $X_{1},X_{2},\ldots$ be independent rvs having the geometric distribution with parameter $p$, i.e. $P\left[X_{i}=m\right]=pq^{m-1}$ for $m=1,2.\ldots$ (here $p+q=1$).

Define $S_{n}:=X_{1}+\cdots+X_{n}$.

With induction on $n$ it can be shown that $S_{n}$ has a negative binomial distribution with parameters $p$ and $n$, i.e. $P\left\{ S_{n}=m\right\} =\binom{m-1}{n-1}p^{n}q^{m-n}$ for $m=n,n+1,\ldots$.

It is obvious that this is true for $n=1$ and for $S_{n+1}$ we find for $m=n+1,n+2,\ldots$:

$P\left[S_{n+1}=m\right]=\sum_{k=n}^{m-1}P\left[S_{n}=k\wedge X_{n+1}=m-k\right]=\sum_{k=n}^{m-1}P\left[S_{n}=k\right]\times P\left[X_{n+1}=m-k\right]$

Working this out leads to $P\left[S_{n+1}=m\right]=p^{n+1}q^{m-n-1}\sum_{k=n}^{m-1}\binom{k-1}{n-1}$ so it remains to be shown that $\sum_{k=n}^{m-1}\binom{k-1}{n-1}=\binom{m-1}{n}$.

This can be done with induction on $m$:

$\sum_{k=n}^{m}\binom{k-1}{n-1}=\sum_{k=n}^{m-1}\binom{k-1}{n-1}+\binom{m-1}{n-1}=\binom{m-1}{n}+\binom{m-1}{n-1}=\binom{m}{n}$

Solution 2:

Another way to do this is by using moment-generating functions. In particular, we use the theorem, a probability distribution is unique to a given MGF(moment-generating functions).
Calculation of MGF for negative binomial distribution:
$$X\sim NegBin(r,p),\ P(X=x) = p^rq^x\binom {x+r-1}{r-1}.$$ Then, using the definition of MGF: $$E(e^{tX})=\sum_{x=0}^{\infty}p^rq^x\binom {x+r-1}{r-1}*e^{tx} = p^r(1-qe^t)^{-r}=M(t)^r$$, where $M(t)$ denotes the moment generating function of a random variable $Y \sim Geo(p)$. As, $$E(e^{t(X_1+X_2+\dots+X_n)})=\prod_{i=1}^nE(e^{tX_i})$$(since they are independant), we are done.