Bounded 3 values random walk

Question

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.

Answer 1

First look at some pattern:

$1$ step: $1\over 2$

$2$ steps: $1\over 2$ + $2$(${1\over 4}\times {1\over 4}$)

$3$ steps: $1\over 2$ + 2(${1\over 4}\times {1\over 4}$) + 2$({1\over 4}\times{1\over 2}\times {1\over 4})$

$4$ steps: $1\over 2$ + 2(${1\over 4}\times {1\over 4}$) + 2(${1\over 4}\times{1\over 2}\times {1\over 4}) + 2({1\over 4}\times{1\over 2}\times{1\over 2}\times {1\over 4} + {1\over 4}\times{1\over 4}\times{1\over 4}\times {1\over 4})$

We notice that each additional values for $n\geq 2$ steps consists of $2\times$ (${1\over 4}\times...\times{1\over 4}$) where $...$ consists of an even number of ${1\over 4}$ and any number of $1\over 2$ multiplying together. This is clearly true because once we go up a number with probability ${1\over 4}$ we need to go back first before reaching zero. And the negative side is completely symmetric to the positive side so hence the $2\times$. However we need to note that the order of appearances of $1\over 2$s and $1\over4$s actually matters so the problem becomes difficult to use generating functions to solve which I tried and failed to do so.

After $n$th step the additional value is

$$2({1\over4}\cdot{1\over 4})(\sum_{0\leq 2i \leq n-2}{n-2\choose 2i}({1\over 2})^{n-2i-2}({1\over 4})^{2i})$$

$$={1\over8}(\sum_{0\leq 2i \leq n-2}{n-2\choose 2i}({1\over 2})^{n+2i-2})$$

$$=({1\over2})^{n+1}(\sum_{0\leq 2i \leq n-2}{n-2\choose 2i}({1\over 2})^{2i})$$

Actually according to Wolfram-Alpha, the sum has a closed form solution (which I did not figure out initially)

$$=({1\over2})^{n+1}(({1\over2})^{n-1}(3^{n-2} +1)) =({1\over2})^{2n}(3^{n-2} +1) $$

To find the total probability after $n$ steps one needs to sum up all additional steps from $2$ to $n$ to end up and the initial $1\over 2$ with

$${1\over 2}+\sum_{j=2...n}({1\over2})^{2j}(3^{j-2} +1)$$

$$={1\over 2}+\sum_{j=0...n-2}({1\over2})^{2j+4}(3^{j} +1)$$

$$={1\over 2}+\sum_{j=0...n-2}({1\over16}({3\over4})^{j} +{1\over16}({1\over4})^{j})$$

$$={1\over 2}+{1\over16}({1-({3\over4})^{n-1}\over1-{3\over4}}) +{1\over16}({1-({1\over4})^{n-1}\over1-{1\over4}})$$

$$={1\over 2}+{1\over4}(1-({3\over4})^{n-1}) +{1\over12}(1-({1\over4})^{n-1})$$

Answer 2

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.