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:

enter image description here

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)?

  • $\begingroup$ I believe you can obtain some good intuition by considering very poor PRNGs. Consider, for instance, a PRNG that repeats after every $2^k$ iterations with $k$ very small, such as $k=1$ or $k=2$. I don't think such an analysis is going to provide good insight, however. BTW, I don't believe your simulation: with a million steps, virtually all the walks should have returned to the origin. Here's a ten-second simulation of 1000 walks out to $10^5$ steps in R: n <- 1e5; N<- 1e3; x <- matrix(2*floor(runif(n*N, 0, 2)) - 1, nrow=n); y <- apply(x, 2, cumsum)[-1, ]; mean(colSums(y==0) > 0) $\endgroup$
    – whuber
    Jul 5 '16 at 1:24
  • $\begingroup$ The reason why they don't seem to is that the color-coding of the lines: I didn't explain the details, but I had set an artificial threshold, whereby the line was color in blue if the values stayed on whichever side of zero that the walk happened to be halfway down the $1e6$ steps. The idea was to give them a chance to "fight gravity", and to get a nice plot... $\endgroup$ Jul 5 '16 at 6:46

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.

  • $\begingroup$ Thank you. Are you OK with the very last line in your answer? $\endgroup$ Jul 6 '16 at 13:22
  • $\begingroup$ @AntoniParellada why shouldn't I..? Imagine a wheel of fortune with infinitely many categories, hitting any single one would appear with probability equal to $1/\infty = 0$ (stats.stackexchange.com/questions/60702/…) but every time someone spins it, he or she will hit some specific category. $\endgroup$
    – Tim
    Jul 6 '16 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.