# 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.

• When you say "Assume the sum of the $M X_i$ r.v.s starts from $0$" -- is this meant to be interpreted as a conditional? Because if so, this makes the initial contents of the array non-independent (as they must sum to $0$). I imagine this will hugely complicate matters... E.g. suppose $M > n = 4$, the 4 values shifted out are slightly more likely to sum to $0$ than i.i.d. would predict (which is ${4 \choose 2} / 16$). If you dont want to deal with this dependence, you might need to not assume the initial sum is $0$, and instead ask for prob of returning to initial value. – antkam Feb 13 at 19:29
• @antkam No itsn't meant to be conditional, thank you for the clarification! – Luca Moroldo Feb 13 at 21:18
• OK, so is it equivalent to say that you are really looking for the event that sum of the $t$ shifted-out values = sum of the $t$ shifted-in values? If so, and if you're interested in exactly $t=n$, this has a simple solution I think. Whereas if you're interested in this happening for some $t \le n$, then I do agree it's equivalent to your random walk. Return-to-zero is a well studied topic although I'm not an expert. – antkam Feb 13 at 21:33
• @antkam For example, if M = 2 and the array is [-1,1], I'm looking for the probability that after n>0 shifts the array is again [-1,1], that can happen for any $t \leq n$ – Luca Moroldo Feb 13 at 23:09
• OK, just to avoid all possible misunderstandings. suppose you start with [-1, 1], and want the prob for $n=10$. as it happens, the array is [-1,1] after 2 shifts, and also after 7 shifts, but after 10 shifts the array is [1,1]. does this count as a success / part of your event? – antkam Feb 14 at 0:38

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})$$

• @Daniel Mathias What I worked on is the case where $M$ is not bounded. I haven't worked on $M$ bounded case though which will add additional constraint so that number of $1\over 4$ should be less than or equal to $M$. It looks like you are working on it so I will let you do that. But the solutions should match either way when $M\geq n$. – cr001 Feb 13 at 17:59
• @cr001 Thank you, but shouldn't the limit converge to 1 for $n \rightarrow \infty$? – Luca Moroldo Feb 14 at 11:02
• @Luca Moroldo The limit won't converge to $1$ because the steps does not follow a geometric distribution. After each step, the success rate decreases faster than that of the geometric distribution, as shown in the calculations. – cr001 Feb 14 at 13:38

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.