modified random walk problem

51 Views Asked by At

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]
  2. [1, 1, 1, -1]
  3. [1, 1, -1, 1]
  4. [1, 1, -1, -1]
  5. [1, -1, 1, 1]
  6. [1, -1, 1, -1]
  7. [1, -1, -1, 1]
  8. [1, -1, -1, -1]
  9. [-1, 1, 1, 1]
  10. [-1, 1, 1, -1]
  11. [-1, 1, -1, 1]
  12. [-1, 1, -1, -1]
  13. [-1, -1, 1, 1]
  14. [-1, -1, 1, -1]
  15. [-1, -1, -1, 1]
  16. [-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}$