Real Mathematics – Life vs. Maths #5

Drunkard’s Way Back Home

Finally we are back with Steve the accountant. So far I’ve talked about one dimensional random walk in order to understand drunkard’s walk. Although we are all aware of the fact that right and left are not the only options when we take a walk.

That is why Steve’s walk should be thought in two dimensions.

There are four choices of movement in a two-dimensional plane: Right, left, up and down. They all have same probability (just like in one dimension). It is ¼. These four directions are familiar to us as we already learned about Cartesian coordinates. In the end Steve’s walk turned out to be a walk in Cartesian coordinates. Let me choose origin of the coordinate system as Steve’s starting point. For the first random step there will be these four options:

To facilitate Steve the accountant’s walk, one could use a 12-sided dice. When it is thrown:

Take your step upwards for 1-2-3,

take your step downwards for 4-5-6,

take your step to right for 7-8-9,

and take your step to left for 10-11-12.

IMG_6524

Q: How far from the starting point one would be after taking N random steps in a two-dimensional plane?

Answer to this question is same with one-dimensional random walk: After N random steps in two dimensions, one would be √N steps away from the starting point. That is same as imagining a circle that has its center at the origin (starting point) and has the radius √N. A two-dimensional random walk would likely end in this circle.

çember
After taking 20 steps, one would be in this area. (I took √20 as 5.)

Recall that for one-dimensional random walks we found three conclusions. Third one was saying that we are likely to be back to the starting point if N is large enough of a number. Same conclusion can be made for two-dimensional random walks too; the more steps we take, the most likely we would be close to the starting point.

“A drunkard will find his way home, but a drunken bird may get lost forever.”

Shizou Kakutani

This result shows that Steve the accountant will likely make circles and return to his starting point. But he will eventually reach his home.

Let me take this one step further: If Steve the accountant’s walk is long enough he would have visited all the streets in his neighborhood. This is why we say two-dimensional random walks are recurrent just like one-dimensional ones. But if we go into three dimensions, things change. A three-dimensional random walk is not recurrent which is why it is possible to get lost in 3-D.

güzergah
If Steve was taking his walk in this district, he would visit each and every street if his walk is long enough.

Biased Random Walk

We already know that in one-dimensional random walk there are two choices with equal probabilities: Right (1/2) and left (1/2).

Q: How can we find a one-dimensional random walk that is biased?

For such a random walk I can keep the probabilities of right or left unchanged. But I’ll arrange the number of steps taken. What I mean is that whenever we get a right; let’s take two steps instead of one but for a left we continue to take one step. Outcome used to be +1 or -1 for a step. Now it is either +2 or -1.

This is how a biased one-dimensional random walk can be created.

The reason this random walk is biased is that after taking N random steps, one will most likely be on the right side of the starting point. We can test that with a coin toss like we did in previous articles: Tails are +2, heads are -1.

After 10 coin tosses my path turned out to be as follows:

One wonders…

You make your own experiment with a coin and compare your results.

Ps. It is not over yet. To be continued…

M. Serkan Kalaycıoğlu

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.

indir (11)

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 ½.

IMG_6486

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.

IMG_6488

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.

IMG_6489

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:

image002-e1545564192978.png
Coming back to your starting point (which is zero) has the highest probability.

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.

502907-3-4-24aa2

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