A Tale of Drunk Worms and Random Walks

Meet Larry the worm. Larry had a wonderful night drinking at a bar with his friends.

Alas, Larry got a bit too drunk, so when he and his friends finished drinking, he went to walk (err, crawl) home, drunk.

Larry and his friends live on a one dimensional road. As Larry is drunk, he walks home randomly. Each step, with probability 0.5 he will walk right and with probability 0.5 he will walk left instead. Additionally, each step is independent from the ones before and after it, and all steps are of a constant length

Oh by the way, Larry owns the bar and lives in it, he got so drunk he forgot the bar was his home… Anyway, the question remains, will Larry get home eventually?

Larry’s walk home is a classic example of a one dimensional random walk in probability, in one dimension. We can model Larry’s road as the whole numbers in a line, with the bar (and Larry’s home) being on the number zero. Each step with equal probability Larry walks right or left, and all the steps are independent from each other step. Walking right corresponds to adding 1 to Larry’s position, and left to subtracting 1

So will Larry get back home? It turns out that the answer is yes

A proof Larry will get home:

Suppose, without loss of generality, Larry walks right to 1 on his first step (the proof remains the same if he walks left). We now ask the question, what’s the probability Larry went to 2 before going back home (if at all)?

Well that is easy to answer, if he got to 0 first, he went left after 1, else he went right to 2. So the probability is equal to 0.5, as that is the probability of going left.

Now we ask a similar question, what is the probability of Larry getting back home before going to 4? Well, to go to 4 before going to 0, Larry has to pass 2, so he will need to get to 2 before 0. As explained before that has probability 0.5. After he gets to 2, the situation looks like this:

Now, what is the probability he will get from 2 to 4 before getting to 0. Notice that 0 and 4 are at equal distance from 2. Additionally, Larry’s walk gives no priority to either direction (left or right). Therefore, if we swap 0 and 4 it won’t affect the probabilities at all (for each way of getting to 4, there is a way with equal probability of getting to 0 and the opposite). So by symmetry, Larry has equal chances (0.5 each) of getting to 0 first and getting to 4 first.

Putting that together, for Larry to get to 4 before 0 he has to get to 2 before 0, and from 2 to 4 before 0. Each has probability 0.5, so since the steps are independent the probability of it happening is 0.5*0.5=0.25

We now repeat this process in induction. That is, we prove for each n that the probability of Larry getting to 2ⁿ before 0 is (0.5)ⁿ. Indeed, suppose we already proved this for n=k. We now want to prove for n=k+1. So as before, for Larry to get to 2^k+1 before 0, he has to get to 2^k before 0 first. That, by our assumption, has probability (0.5)^k

When he gets to 2^k, note that Larry is exactly in the middle between 0 and 2^k+1. So, as before, by symmetry the probability of Larry getting from here to 2^k+1 before getting to 0 is 0.5. Therefore, the probability of Larry getting to 2^k+1 before 0 is (0.5)^k+1. Thus we proved by induction (as we already covered the base case n=1).

For those unfamiliar with induction, think as this as a sort of domino effect. We proved the argument for n=1, and that if the argument holds for n=k, it holds for n=k+1. Therefore, it holding for n=1 implies it holds for n=2, n=2 for n=3, and so on for each n.

Now we note the following important fact we glossed over before. Larry will eventually escape any finite interval. That is, for each pair of integers m<k, if Larry is between m and k, he will eventually escape the interval between m and k, that is he will either get to the right of k or to the left of m.

Here is a sketch of how to prove this. When stuck in the interval, at each step Larry can take k-m steps to the right in the k-m following steps, with probability (0.5)^k-m. Since the length of the interval is k-m, this will take take Larry to the right of k, and thus out of the interval. The probability of this occurring is low but a non zero constant. Therefore, with enough time, Larry will take k-m steps to the right and get out of the interval (if he didn’t already).

Now we can finish the proof. Let’s look at the event of Larry never returning home (in the case of him taking a step to the right first, as stated before the other case is similar). As stated before, Larry will escape any finite interval, in particular the interval between 0 and 2ⁿ for any positive integer n. On the event where Larry doesn’t get home, he must escape this interval through 2ⁿ, as 0 is his home

But then he will get to 2ⁿ before getting to 0, and as we proved by induction that has probability (0.5)ⁿ. Therefore, the probability of Larry never getting home is less than (0.5)ⁿ, for each positive integer n. Letting n go to infinity, (0.5)ⁿ approaches zero, and so the probability of Larry never getting home must be less then zero, and thus zero. Therefore, Larry will get home with probability one, so almost surely he gets back home.

Q.E.D

Now here is a fun result from what we proved. Suppose Larry never stops the random walk, even if he gets back home . It turns out that this means Larry eventually reach any point in the line, infinitely many times, no matter where he started (almost surely)

To see why, note that after Larry returns to 0 the first time, he essintially restarts his walk. Since the steps are independent, the way he returned to 0 has no effect on the future of his walk. So, after returning to 0 for the first time, he will restart his walk, and thus almost surely return to 0 again. Similarly, he will after that almost surely again return to 0, and again, and again, and again and so on. Therefore, almost surely he will be in 0 in infinitely many steps.

Now, let k be an integer on the number line. Starting from 0, if Larry takes |k| steps left or |k| steps right (depending on the sign of k), he will reach k. This has a constant probability of (0.5)^|k| of happening. This can be very low, but it is still positive. So since Larry visits 0 infinitely many times, in one of these visits he will eventually do those |k| steps and reach k. Q.E.D

(in a similar way as before, we can prove Larry will return to k infinitely many times)

Case 2: Drunk Worms on a Tank

By the way, the reason Larry and is friends can go to a bar, and talk to each other and all of that, is because they are superintelligent mutant worms. And now they are coming for blood.

In the great human-worm war of 2059, Larry and his friends are part of a worm tank battalion, attacking multiple locations in the Gobi desert. As tradition, Larry and his friends have fun and drink together. Unfortunately, they also drink and drive (a tank).

They drunkenly drive their tank out of the base, and proceed in a two dimensional random walk. At each step, with equal probability they drive either forward, backwards, left, or right, each with an equal probability of 0.25, and each step if of the same length (also the Gobi desert is an infinite plain and is completely desreted for some reason).

Mathematically speaking, we can model this using the lattice Z^2 (the integers squared). That is, the Lattice of coordinates (x,y), where x and y are whole numbers. The random walk starts at (0,0) (Larry’s millitary base) and at each step either:

• The x coordinate increases by 1
• The x coordinate decreases by 1
• The y coordinate increases by 1
• The y coordinate decreases by 1

And each of these happen with probability 0.25, with each step independent from the rest of them.

We now ask the same question as before. Will Larry and his friends get back to the base eventually?

Well, we can perhaps used what we already proved for one dimensional random walks. If we look only at the x coordinate, then at each step it either increases by 1 with probability 0.25, decreases by 1 with probability 0.25, or doesn’t change (as the tank moved in the y axis) with probability 0.5, and of course all steps are independent. This is kind of similar to the one dimensional random walk from before, except that there is a chance of staying in place at each steps. Nevertheless, it is not hard to see the same result from before holds, that is the x coordinate will return to 0 eventually.

Similarly, we can show that the y coordinate will return to 0 evantually. In fact, due to what we showed for one dimensional random walks, this means the x coordinate will be 0 infinitely many times, same for the y coordinate.

Sadly, we are now stuck. Although the x coordinate and y coordinate each will be 0 infinitely many times, this does not mean they will eventually both be 0 at the same time, meaning a return to (0,0)

So maybe because that attempt failed, Larry will unfortunately not always return to his base. After all, in a sense the two dimensional plain is ‘larger’ than the line before it, so it will be easier to get lost there. It turns out however, that indeed Larry and his crew will return to (0,0). The proof is a bit dense to include here, so I will include a proof for it at the end of this post.

Case 3: Drunk Worms…. in Space!

So Larry and his worm companions successfully managed to conquer the earth and eradicate humanity. Now they are ready to leave earth, explore outer space, and become a space civilization.

Larry and his buddies are chosen to be the first worms to explore space. Unfortunately, they got drunk again. As before, Larry’s journey is a random walk (err, space travel). At each step, with an equal probability of 1/6, their spaceship moved either upwards, downwards, right, left, forward, or backwards (if you look at outer space as a 3D space with a clear notion of what these directions mean)

We again can model this mathematically as a 3D random walk. Each position of the spaceship is a vector (x,y,z) in the Lattice Z^3, where x,y and z are whole. The spaceship starts at (0,0,0), and at each step, with equal probability the spaceship travels one of the cardinal directions.

The question remains as before. Will Larry’s spaceship get back to earth eventually? A possible approach is again to try to use what we know already about one and two dimensional random walks. But as before, this attempt sadly doesn’t result in anything. But it seems, that as before, he will return back to earth, right?

It turns out that the answer is surprisingly no. With a positive probability, Larry’s spaceship will never return to earth, and its distance from earth will approach infinity, and Larry will wander space forever.

The proof, again, is a bit too dense to include here so I included a link to it for those interested below. Perhaps unsurprisingly, in random walks in higher dimension than 3 also with a positive probability the walk will not return to the origin.

For me personally, this example is one of the things that really got me into probability. Intuitively, it seems that the two dimensional walk will sometimes not return to the origin, but surprisingly it does return with probability one. Then after seeing that the two dimensional walk returns to the origin, your intuition tells you that it also holds in the three dimensional case. But again the intuition is false and it turns out three and higher dimensional walks may not return to the origin. This was astounding to me when I saw it in the first lesson of my first probability class.

I will end this post with a question for you. Returning to the one dimensional random walk, we know that it almost surely will return to the origin. But how many steps will that take on average?

Proof that the 2D random walk returns to the origin while the 3D walk doesn’t