Return to origin of a symmetric random walk and the zero-probability, infinitely deviating path

Question

In a symmetric random walk the probability of returning to the origin is $1$.

All paths in such a system are equally probable, in appearance following a branching system governed by $\frac{1}{2^{\mathbb N}}$. In comes measure theory to challenge this statement based on the uncountability of these infinite pathways, and dictating that the probability of return to the origin be constructed on events that have occurred (or not occurred) before a finite number of steps.

Regardless, the fact that the probability is $1$ does not mean that a path infinitely steering to the right (or to the left) cannot occur; it just means that its measured probability is zero.

I would like to imagine a computer so powerful that could run an infinite symmetric random walk endlessly until it found such a path always to the right or to the left of zero.

To illustrate, and thanks to the inspiration in one of Glen_b's phenomenal posts, I let the computer run overnight doing something silly like this with $1$ million steps for each iteration, and color-coding the paths that did not return to the origin after a certain number of steps in blue, and the ones that kept on crossing zero in red. Following the tails of some of the blue paths, the unavoidable drop to zero can easily be intuited:

OK, I paid tribute to Barcelona, FC and the Fourth of July at the same time. Now the question:

How would a computer pseudorandom number generation algorithm with unavoidable repeating sequences affect the expected time to return to origin of such an infinite simulation? And, possibly by extension, how would a generic pseudorandom algorithm impact the quest for that elusive path consistently to the left (or to the right)?

Answer 1

As you noticed, in a symmetric random walk the probability of returning to the origin is $1$ and probability of non-returning is $0$. Nevertheless, you want to imagine a case where infinite number of chains run for infinite time and among them you expect to find such that never returns to origin.

The problem is your stopping rule

I would like to imagine a computer so powerful that could run an infinite symmetric random walk endlessly until it found such a path always to the right or to the left of zero.

Actually this is achieved with probability $1$ by one-step chain. How long you would like it to run?

If it's infinitely long, then such chain has also infinite number of possibilities to return to origin. So you could have run $K-1$ chains that all returned to origin, but $K$-th chain does not for large number of steps, but in the end it gets to origin in $N$ steps. So you repeat your experiment $K+1$ time hoping the chain makes at least $N+1$ steps without going back to origin and it happens at $K+M$, next you'll have to wait for $N+2$, $N+3$, etc. reaching infinity, with the number of attempts growing all the way up to infinity... This would lead to infinitely many tries with infinitely long chains. That is why probability of observing it is zero.

As about your concern with pseudo random number generators, periodicity is not a problem for modern high-quality PRNG's because they have very long periods. For example, Mersenne-Twister used in R by default has period of $2^{19937} - 1$. You wouldn't be able to run your simulation long enough for it to affect you.

It's not that improbable things doesn't happen. There is nice little book The Improbability Principle by David J. Hand that describes lots of real-life "improbable" events that actually happen, but still, this doesn't make them improbable. If probability of something happening is equal to zero it doesn't mean that it is impossible.