Real Mathematics – Life vs. Maths #3

Drunkard’s Walk Back Home

Steve the accountant finished another working week. He usually spends his weekends in peace. But this specific weekend was different: He was supposed to meet his old college mates whom he hasn’t seen for ages. That night they talked about old days, laughed and drank until morning. Steve the accountant has never been a heavy drinker. At the end of the meeting even though he was barely standing he insisted that he can walk back to his home by himself.

Steve the accountant started walking in random directions: “This street looks familiar… Oh that building looks just like mine…”

Q: Can a drunkard make his way home using a random walk?

Random Walk in One Dimension

I have to talk about random walk in one dimension before I answer the fate of Steve the accountant. In one dimension walking path is something we are familiar since we are kids: The number line.

There are two directions on the number line: Right and left.

Rules:

• In one dimension one step to right means +1, one step to left means -1.
• Let’s assume that the probability of choosing right and left is same.
• Because of the previous assumption taking a step towards right or left has the probability of ½.

Now let’s draw a number line and choose zero as the starting point. First step can be taken towards +1 or -1. Their probabilities are equal: ½.

Taking two steps at once will be a little bit more complicated than taking one step. After taking only one step we concluded that there can be only two possibilities: +1 and -1. But when we try to take two steps at once, there will be four possibilities:

0 -> +1 -> +2

0 -> +1 -> 0

0 -> -1 -> -2

0 -> -1 -> 0.

In every possibility, probability will be equal: ¼.

After the second step, we may be standing on either one of +2, 0 or -2 with probabilities ¼, 2/4 and ¼ in order.

How about three steps?

We already know what the probabilities are after two steps. According to our findings third step can start either at +2, 0 or -2.

• If we take our step from +2, we can go to +3 or +1. Their probabilities will be half of the probability of +2. Hence it will be 1/8 each.
• If we take our step from -2, we can go to -3 or -1. Their probabilities will be half of the probability of -2. Hence it will be 1/8 each.
• If we take our step from 0, we can go to +1 or -1. Their probabilities will be half of the probability of 0. Hence it will be 2/8 each.

Our calculations show that after the third step we could stand on:

+3 with the probability of 1/8.

-3 with the probability of 1/8.

+1 with the probability of 1/8 + 2/8 = 3/8.

-1 with the probability of 1/8 + 2/8 = 3/8.

In case we continue using the same logic, fourth and fifth steps would look like the following:

After 100 steps, final position and its probability is shown as follows:

So far we can make these conclusions about a random walk in one dimension:

1. When we take even number of steps, we stop on an even number. When we take odd number of steps, we stop on an odd number.
2. As we increase the number of steps probability of stopping around the starting point gets higher.
3. Previous argument indicates that if we take more steps, probability of returning to the starting point will increase as well.

Game of Random Walk in One Dimension

So far we understood that a random walk in one dimension has two possible outcomes. In order to simulate a one dimensional random walk we can use coin toss since there are only two possible outcomes for a coin toss: Heads or tails.

If we have a fair coin, probability of getting heads or tails will be equal to each other: 1/2. Then let’s assign tails to -1 and heads to +1.

1. Toss a coin 10 times. Where did you finish your random walk?
2. Do the same thing for 30 times and compare your result with the previous one.

I could hear you saying: “What about Steve the accountant?”

A little bit of a patience. We’ll get there in the upcoming articles.

M. Serkan Kalaycıoğlu