How to compute the sum of random variables of geometric distribution
Let $X_{i}$, $i=1,2,\dots, n$, be independent random variables of geometric distribution, that is, $P(X_{i}=m)=p(1-p)^{m-1}$. How to compute the PDF of their sum $\sum_{i=1}^{n}X_{i}$?
I know intuitively it's a negative binomial distribution $$P\left(\sum_{i=1}^{n}X_{i}=m\right)=\binom{m-1}{n-1}p^{n}(1-p)^{m-n}$$ but how to do this deduction?
$\endgroup$ 42 Answers
$\begingroup$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$:
$\endgroup$ 1 $\begingroup$$\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}$
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.
