# Sum of independent discrete random variables

Let $X_n$ be a sequence of independent random variables with distribution: $$P(X_i = -1)=q, \hspace{1cm} P(X_i = 0) = 1-2q = r, \hspace{1cm} P(X_i = 1) = q$$ for $i=1,..,n$ and $q \in (0,1/2)$.

I am investigating the distribution of $S_n = X_1 + X_2 + ... + X_n$.

What I have done for far:

let $p_n:= P(S_n = 0)$, then: \begin{equation} p_n = r^n + n(n-1)q^2 p_{n-2}. \end{equation}

Since all of the random variables $X_1, ..., X_n$ will be 0 or, the second possible option is that two of them will equal $1$ and $-1$ and the rest n-2 random variables will sum up to 0. Now we calculate $p_{n-2}$ the same way:

\begin{equation} p_{n-2} = r^{n-2} + (n-2)(n-3)q^2 p_{n-4}. \end{equation} (1) and (2) combined together give us: $$p_n = r^n + n(n-1)q^2 p_{n-2} =r^n + n(n-1)q^2 [ r^{n-2} + (n-2)(n-3)q^2 p_{n-4}] =$$ $$r^n + \frac{n!}{(n-2)!}q^2 r^{n-2} + \frac{n!}{(n-4)!}q^4 p_{n-4} = .... = r^n + \frac{n!}{(n-2)!}q^2 r^{n-2} + ... + \frac{n!}{(n-2k)!}q^{2k} r^{n-2k} + ... .$$

Analysing that we can deduce that:

$$p_n = P(S_n=0) = \left\{ \begin{array}{ll} \sum \limits_{k=0}^{n/2} \frac{n!}{(n-2k)!} q^{2k}r^{n-2k} & \textrm{when n is even},\\ \sum \limits_{k=0}^{\frac{n-1}{2}} \frac{n!}{(n-2k)!} q^{2k}r^{n-2k} & \textrm{when n is not even}.\\ \end{array} \right.$$

What seems to be accurate. I've checked for $n=1,2,3$ - so there is a chance that this calculation is correct.

Then I tried to calculate $P(S_n=i)$ as $$P(S_n=i) = \binom{n}{i} q^i P(S_{n-i} = 0)$$ for $i>0$, as we need to have at least i ones (and we have to pick which $X_i$ are equal 1) and the rest (n-i) together must sum up to 0, and $$P(S_n=i) = \binom{n}{-i} q^{-i} P(S_{n+i} = 0),$$ for $i<0$, but unfortunately this is incorrect.

I've checked in R that for $q=1/8$ and $n=3$: $$\sum \limits_{i=-n}^{i=n} P(S_n = i) = 1.011719 \neq 1$$

Please help me to find a mistake in my solution or help to calculate $P(S_n =i)$ in a different way.

• Your recursion formula of $p_n$ is overcounting. Note e.g. that it tells you that $p_4=r^4+12q^2p_2=r^4+12q^2(r^2+2q^2)=r^4+12q^2r^2+24q^4$. The term $24q^4$ corresponds with possibilities without any zero's. But there are only $6$ of them (not $24$). – drhab Apr 8 '17 at 15:26

## 2 Answers

On base of non-negative integers $u,v,w$ with $u+v+w=n$ you could start with:

$$\Pr(U_n=u\wedge W_n=w)=\frac{n!}{u!v!w!}q^{u+w}r^v=\frac{n!}{u!(n-u-v)!w!}q^{u+w}r^{n-u-w}$$ where $U_n$ stands for the number of times that $-1$ and $W_n$ for the number of times that $1$ shows up.

Then: $$\Pr(S_n=i)=\sum_{w-u=i}\Pr(U_n=u\wedge W_n=w)$$

addendum:

If $B_n^{(i)}$ are iid for $i=1,2$ with Bernouilli($p$) distribution where $p$ is a root of the equality: $$p(1-p)=q$$ then $X_n$ and $B_n^{(1)}-B_n^{(2)}$ have the same distribution.

Defining $T_n^{(i)}=B_1^{(i)}+\cdots+B_n^{(i)}$ for $i=1,2$ we find that $S_n$ and $T_n^{(1)}-T_n^{(2)}$ have equal distribution, while $T_n^{(i)}$ are iid and have binomial distribution with parameters $n$ and $p$.

This observation can help by for instance finding things like the variance or characteristic function of $S_n$.

• Thank you for your help! :) – Elizabeth_Banks Apr 8 '17 at 15:57
• You are welcome. I added something. – drhab Apr 9 '17 at 13:33
• Your help is much appreciated. – Elizabeth_Banks Apr 9 '17 at 14:24

I advise you to use generating functions. Let $Y_i=X_i+1$ (in order to work with positive valued random variables). In this way, because of independance, $S_n+n$ has generating function:

$$(q+rs+qs^2)^n=(s+q(1-s)^2)^n$$

It suffices to expand this expression in order to get the general term (don't forget to subtract $n$ at the end). In this way, one will find "trinomial coefficients" with some similarity with coefficients in the answer by @drhab.