baccarat, random walks, solving an old problem, and the central limit theorem

The baccarat problem got me thinking about the random walk problem, because each of the three times in my game I reached the $200 betting limit my revenue became a random walk. At this point the problem was: which was going to come first, was I going to get into the black on $200 bets or was I going to burn through all of my cash? This is a random walk: my revenue bounces back and forth, an approximate 50% chance of each, and the game ends when I reach either of two targets: $200 above where I started (between $5000 and $6000) or $0.

Many years ago, I can't remember when, I encountered a problem in random walk probabilities which was: suppose a robot, starting at x = 0, steps either in the +1 direction or the -1 direction, at random, for infinite time. What is the probability he never returns to 0 after his first step? Wow -- this is a heady problem. It always seemed to me the probability was zero: surely in infinite time he has to eventually reach all points of finite x. But I could never prove this. Maybe the random walker, if it got far enough from zero, could just wander off to +infinity, never to return...

But now I can prove it. The expectation value of the change in x with every step is zero. So the expectation value of x for all time must be zero.

Consider the first step. He's either at +1 or -1. I don't care which. They're obviously the same problem. So I'll pick +1. What's the chance he never again reaches zero from +1? Well, I can propose a game in which the game ends if the robot reaches 0 (-1 relative to his present position) or if the robot reaches +X, which is X - 1 relative to his present position.

In the baccarat problem, I noted that nothing is going to beat the fact that the expectation value of the game is to slowly lose money. In the case of the robot, you can't change the fact that the expectation value of the deviation from the present position is going to be always zero. So the probability that the robot will reach X before it reaches 0, starting from x = 1, is 1 / X, leaving the chance the robot reaches zero first is 1 - 1 / X. You can check the math: (X - 1) (1 / X) - 1 (1 - 1 /X) = 0. So the expectation value is correctly always at x = 1.

But this doesn't exactly answer the original question. Fine, so it returns to zero before wandering off to infinity. But what if the robot never reaches neither X or 0? What if it spends all eternity bouncing back and forth between 1 and X - 1, inclusive?

Well, I think it's clear this is zero, because starting from any point within finite bounds, there is a finite calculable chance the robot will take a series of step directly towards and crossing either of the two boundaries. So if it wanders within those boundaries long enough, it will do this: eventually it will hit one of the two boundaries, something which has finite probability, given infinite time.

So that's it: because the robot has a zero expectation value for its motion, it's probability of reaching any finite point is greater than the probability of reaching any point of much larger magnitude, and therefore the probability is 100% it will eventually return to 0 after taking a first step to +1. And of course the same argument applies for a first step to -1.

It's good to finally have a clear grasp of this. The answer in retrospect is obvious. But obvious isn't good enough. In math you've got to prove it. And in trying to do that my previous thing was in get-ugly-fast recursive arguments. This is much better.

Moving ahead, I've been discussing the expectation value of position. What about the expectation value of the square of the position? This is intrinsically non-negative, and therefore cannot average zero, since the robot cannot remain on x=0. Well, given the robot is at position x, then with the next step the expectation value of the change in x² = 1/2 (x + 1)² + 1/2 (x − 1)² - x² = 1. So with each step the expectation value in x² increases by 1. It starts at zero at time 0, then obviously goes to 1 at step 1 (since x is either −1 or 1), then with step 2 it's now 2 (50% chance of 4 for x = 2 or x = −2, 50% chance of 0 for x = 0), etc. So by the central limit theorem the statistical distribution of the robot's position will converge onto a normal distribution (other than the fact it alternates between even and odd positions, which I can adjust for). So I calculate:

probability robot is on zero after N steps ≈
   0, N odd;
   2 / sqrt[ 2 π N ], N even.

So, for example, after one million steps, there's an approximate 1 in 1253 chance the robot will be on zero, with the rms (root-mean-squared) distance of the robot = 1000.

A quick test of this: I did a million random walks of 100 steps, so I'd expect a 1 in 125.3 chance of it ending on zero, or 79810 of the 1 million tries (σ= 790). So within 3 σ, I expect between 77130 and 82490 of the million results to finish at zero.

The result of my Perl simulation: 79417, so right on target.

Here's the statistical distribution of those million iterations of 100-step random walks. Note I'm plotting only even positions since odd positions are impossible after an even number of steps.

Even though 100 steps isn't many, on this scale the central limit theorem is working very nicely, and the normal distribution passes through all of the points.

I feel much better about random walks now. And when in Casino Royale (Fleming), when Bond took his initial 10 million francs and ran it up to 15 million francs before his encounter with Le Chiffre, he got lucky. He had an only 2/3 chance of doing this successfully.