so there is a problem of a machine which has a screen that can show integers. starting at $0$ at each time step the machine either increases the number by $1$ or decrease it by $1$ (the probability of these two actions are equal). if we know the machine have worked for T rounds, what is the probability of seeing $0$ at least one time on the screen during this time interval. for example for $T=4$ these streams can be produced by the machine:
- [1, 1, 1, 1]
- [1, 1, 1, -1]
- [1, 1, -1, 1]
- [1, 1, -1, -1]
- [1, -1, 1, 1]
- [1, -1, 1, -1]
- [1, -1, -1, 1]
- [1, -1, -1, -1]
- [-1, 1, 1, 1]
- [-1, 1, 1, -1]
- [-1, 1, -1, 1]
- [-1, 1, -1, -1]
- [-1, -1, 1, 1]
- [-1, -1, 1, -1]
- [-1, -1, -1, 1]
- [-1, -1, -1, -1]
the acceptable streams are:
[1, 1, -1, -1]
[1, -1, 1, 1]
[1, -1, 1, -1]
[1, -1, -1, 1]
[1, -1, -1, -1]
[-1, 1, 1, 1]
[-1, 1, 1, -1]
[-1, 1, -1, 1]
[-1, 1, -1, -1]
[-1, -1, 1, 1]
so the probability will be $\frac{10}{16}$