# Binomial Random Walk

For the random walk with step sizes: $S_i = \begin{cases} &+1 &\text{probability} &p, \\ &-2 &\text{probability} &q=1-p \end{cases}$

Let $T_n = \sum_{i=1}^mS_i$ be the displacement after a fixed, not random, number of steps $n$.

Find the probability distribution: $P(T_n=t)$

and the mean and variance of $T_n$ in terms of a general $n$ and $p$.

Note that $\frac{S_i+2}{3}$ is distributed as $B(1,p)$, giving that $\frac{T_n+2n}{3}$ is distributed as $B(n,p)$. Thus:

$$\mathbb{E}\left(\frac{T_n+2n}{3}\right)=np, \mathbb{V}\left(\frac{T_n+2n}{3}\right)=np(1-p)$$

from which you can derive:

$$\mathbb{E}(T_n)=n(3p-2), \mathbb{V}(T_n)=9np(1-p)$$

Furthermore, knowledge of the binomial distribution gives that:

$$\mathbb{P}\left(\frac{T_n+2n}{3}=k\right)=\binom{n}{k}p^k(1-p)^{n-k}$$

which can be manipulated to find the distribution of $T_n$ itself.

Let X_n be the random variable corresponding to the number of +1 steps in n turns. $X_n$ will follow Binomial Distribution with parameters $n$ and $p$. If $k$ is the number of +1 steps. Then, $n-k$ is the number of +2 steps. Then, $k+2(n-k) =t$. On solving, we get $k = 2n - t$.

Thus, $P(T_n = t) = P(X_n = 2n-t) = {n \choose 2n-t}p^{2n-t}(1-p)^{t-n}$.

Now, $E[S_i] = p + (1-p)*(-2) = 3p-2$ and, $Var[S_i] = E[S_i^2] -E[S_i]^2 = p + (1-p)(-2)^2 -(3p-2)^2 = 9p(1-p)$.

Using linearity of expectations and the fact that each step of the walk is independent and identically distributed, we get $E[T_n] = nE[S_i] =3np-2n$ and $Var[T_n] = nVar[S_i] =9np[1-p]$.

$P(T_n=t)=P(\sum_{i=1}^n S_i=t)$ so this is essentially the $n$-fold convolution of $S_1,S_2,...,S_n$. Not sure if a neat answer exists.

$E(T_n)=E(\sum_{i=1}^nS_i)=\sum_{i=1}^nE(S_i)=\sum_{i=1}^n[1\times p-2\times(1-p)]=n(3p-2)$

$Var(T_n)=Var(\sum_{i=1}^nS_i)=\sum_{i=1}^nVar(S_i)=nVar(S_1)$ due to iid $S_i$.

Find $Var(S_1)=E(S_1^2)-(E(S_1))^2$. Simplify.