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.
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.
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.
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
kmatematikatolyesi.com 