The random walk $S_n=a+\sum_{i=1}^nX_i$

Question

Consider a variant of random walk defined as

$$S_n=a+\sum_{i=1}^nX_i,$$ where $X_i$ takes either value $2$ with prob= $p$ or value $-1$ with prob =$1-p$. What is $P(S_n=b)$?

Answer 1

First of all, you can assume WLOG that $a=0$.

Consider the easiest case, where $b=0$. Convince yourself that the sum of $X_i$ can only be zero if $n=3k$, where k is a nonnegative integer, and $S_n=0$ otherwise. Then, we are essentially looking for the probability that we select $X_2$ twice as often as we select $X_1$. Thus, we can model it as a binomial distribution, getting $k$ heads with probability $p$ out of $3k$ flips. Thus: $$ P(S_{3k}=0) = {3k \choose k}p^k(1-p)^{3k-k}\\ =\frac{(3k)!}{k!(2k)!}p^k(1-p)^{2k} $$

Other cases will involve looking at $b$ and determining what form $n$ must be to ensure $S_n$ is nonzero. For example, when $b=1$, we see that $n$ must be of the form $3k+2$, and we must get $k+1$ heads out of $3k+2$ flips.

For a specific $b$, look at getting the first $k$ out of $3k$ (to equal zero), and then the next $x$ out of $y$ to get $b$, to cover all nonzero $S_n$.

If you play around with it you can definitely extract a general formula for $x$,$y$ based on $b$.