Bounded 3 values random walk I have an array of size M, for each shift one random variable $X_i$ enter and one exit. The $X_i$ r.v. are iid and $X_i = \pm1$ with $p=\frac{1}{2}$.
Assuming that the sum of the $M$ $X_i$ random variables starts from $0$, what is the probability that after $n$ shifts has "revisited" $0$?
I've tried to solve this considering the random walk $\sum_{i}\varepsilon_i$ where $\varepsilon_i=\pm2$ with $p=\frac{1}{4}$ and $\varepsilon_i=0$ with $p=\frac{1}{2}$, could you please help me? As a start I can ignore that the array is bounded.
Any hint is well accepted (if there is a solution that uses the generating functions it's even better, as these are more familiar to me), thank you all.
 A: Solution for the large $M$ case only.
The OP models the the large $M$ case with a random walk with steps $\{-2, 0, +2\}$ with probabilities $\{{1\over 4}, {1\over 2}, {1\over 4}\}$.  This is unnecessarily complicated.
Instead, imagine each shift broken into 2 timesteps: First a value is shifted OUT of the array, then a value is shifted INTO the array.  Thus 2 timesteps = 1 shift.  This can be modeled as the (world's most) basic random walk with steps $\{-1, +1\}$ with probabilities $\{{1\over 2}, {1\over 2}\}$, by considering the sum inside the array.  I.e., shifting OUT a $\pm 1$ is equivalent to moving $\mp 1$, and shifting IN a $\pm 1$ is equivalent to moving $\pm 1$.
Clearly, with all the symmetry, the OP question becomes first-return-to-$0$ in the basic random walk.  Return-to-$0$ can only happen at even times $2k$, which is the same as $k$ shifts.  This problem has many references available.  I am not an expert but one reference I found was: https://www.stat.berkeley.edu/~arturof/Teaching/STAT150/Notes/I_First_Return_Probabilities.pdf
Quoting from above, prob of first return at time $2m$ (i.e. after $m$ shifts) is $f_{2m} = {1\over 2m-1} {2m \choose m} 2^{-2m}$.  This gives the PDF of first return time, and summing will give the CDF of first return time which the OP wants.  Other references might have an explicit formula for the CDF.  (Like I said, I am not an expert.)
Alas, this only works for large $M$.  For small $M$, once you shift out all the original content of the array, your future shift-outs are exactly equal to your shift-ins $M$ shifts ago, and you lose the independence property.  However, this approach will work up to the time you shift out all the old content.
