Random walk

George Polya was a Hungarian mathematician who made contributions in many branches of mathematics, among which was probability theory. In this blog we will discuss the “Random Walk” problem in probability. What is interesting is that George Polya actually first theorized this problem by accident.

George Polya was at that time a professor at a university in Zurich, Switzerland. The beautiful landscape there helped him develop a habit: taking afternoon walks in local gardens. One day, when he took his afternoon walks, one strange thing happened: he met a young couple six times. Well, I don’t know how large the garden was and how many paths were there, but this coincidence did surprise our mathematician. He was wondering how could this be possible, considering that he was then taking a random walk. After he mentioned this to his wife, he decided to do some research on the probability regarding random walk. His research actually established a new topic in probability theory.

Now let’s begin our discussion about the random walk problem with the simplest case. Consider one object moving along a straight line. Our assumptions are that this object can only move leftward or rightward, and the distance it moves each time is just one unit. For each time, it has a 50% chance to move leftward and a 50% chance to move rightward. A random walk model is thus created. And now we can ask: if when the object return to the starting point, the movement will end, then what is the probability that the object could return to the starting point? Thanks to George Polya’s work, the answer is 100%. Although some people may think this is unlikely, that’s only because when we think about this problem, we have a pre-assumption that the time is limited, or finite, which is always true in our real life. However, this mathematical model sets the time as endless, so it means when there is enough time and the object keeps moving endlessly, at last it will almost always return to the starting point.

When combining this theoretical conclusion with real life experience, mathematicians created the so-called “Drunken Man Going Home” problem. Assume there is a drunken man. He comes out of a bar and walks randomly along the line connecting his home and the bar. Once he gets home he will stop. Then what is the probability that the drunken man could finally get home? The answer to this funny question is still 100%. The math model of this problem is equivalent to the previous one. Because when time approaches infinite, the different positions of fixed points on the line actually make no differences. In my own words, any finite number in front of infinite vanishes to zero. So in this case, we just move the ending point from the starting point in the first example, to a new fixed point which denotes the drunken man’s home in the second example. The result keeps unchanged.

But mathematical problems always go from simple cases to complex cases. In the original random walk along a straight line, if we change the condition from “along a straight line” to “in a two-dimensional plane”, the complexity of this problem will definitely increase. If we change the condition to “in a three-dimensional space”, the complexity of this problem will increase dramatically. And the answers to this problem also change. The law is that, when the dimension increases, the chances that the object could get back to its starting point decreases, with the assumption that other conditions keep unchanged. For example, for a three-dimensional space, the probability is 34%; for four-dimensional space, the probability is 19.3%; when the dimension reaches eight, the probability that the object can get back is only around 7.3%. This means that there is only a lucky “drunken man”, who could always find a way home; there is no lucky “bird”: in a three-dimensional space, if the bird flies randomly, its chance to get back to its nest is much smaller! (Even if it could fly endlessly.)

Some people may cannot help ask, what can the theorem on random walk be used for. Well, obviously it is not developed to help drunken men feel confident when they need find a way home. It does have very wide applications in various areas. I will broadly list its applications in three different areas.

In economics, the theorem on random walks generates a hypothesis called “random walk hypothesis”. With the help of this hypothesis, economists could construct math models to research factors affecting shares price and the change of shares prices. It is quite understandable because randomness is q characteristic of the stock market.

In physics, the famous Brownian motion can apply the theorem on random walk to achieve the purpose to simplify the system. Since molecules move randomly to every direction, if we make an assumption that the molecules will only move to a finite number N directions, then the problem can be converted to a random walk problem in finite dimensional space. We could estimate the case in real physical world through our approximation in theoretical random walk models.

In genetics, a random walk could be used to explain the change of genetic frequency — a phenomenon that finally leads to genetic drift. Because gene mutation is always random, when we view the original gene pool as a point in a multi-dimensional space, then each gene mutation will generate a new gene pool, which can be viewed as a new point that forms through the original point’s random walk. After countless random walks, we could use the computer to draw pictures that show the trajectory of these abstracted points. The trend and some important characteristics of a gene drift could be described by this.

Randomness is everywhere in nature. At first glance, randomness connotes lack of order, unpredictable and uncontrollable. However, after mathematician’s great job, we do gain many laws and theorems on randomness. Random walk now has very wide applications in various disciplines, and we must attribute this partially to the coincidence happened to George Polya.


  1. http://www.math.wichita.edu/history/men/polya.html
  2. http://www.guokr.com/article/53059/
  3. http://en.wikipedia.org/wiki/Random_walk