What Is Random Walk?

Consider the following situation. We have a drunkard who is clinging to a lamppost, and now he decides to start walking. He is in the middle of the street and the road runs from east to west. In his inebriated state, he is as likely to take a step towards the east as he is towards the west. It just means that there is a 50% chance that he will go in either direction. From each new position, he is again as likely to go east or west. Each of his steps are of the same length but in random direction. After having taken ‘n’ number of steps, he is to be found standing at some position on the street. This is what a random walk is. We can plot the position against the number of steps taken for any particular random walk. Now the question is, can we model his movement so that we can predict where he will be after taking ‘n’ steps?  

How does it work exactly?

Random movement is important for understanding complex behavior in everything from atoms and molecules in a gas to the motion of stars in a galaxy. We cannot know where all the moving bodies will be, but we can build a model and make an educated guess about the position. That’s because, despite electromagnetic interactions between molecules or gravitational effects between stars, the large-scale behavior of these objects appear to make them move randomly. But how do we describe the random motion of molecules in a gas? Molecules are a bit too small for us to see. So to help us better understand how the movement of molecules in a gas works, we need to build a model. Some of the most well known applications of random walk are in the fields of biochemistry, medicine, sub-atomic physics, semiconductors, etc. There are numerous applications of random walk, some of which are extremely critical to our day-to-day lives. Let’s start off with a simple example and see if we can add complexity to it so that we can develop a more complete model.

An example

We have an ant that starts moving along a straight line from the initial point ‘x’ and takes steps of equal length, say L. If it moves along this line extending away from the initial position in a particular direction, how far will it be from the initial point after ‘n’ steps? The answer is ‘nL’ units of distance. Though this seems to be a trivial example, it will allow us to work through one of the most basic problems in statistical science.

Now let’s add some spice to it. After taking each step, the direction of the step will be decided by flipping a coin. Let’s say ‘x’ is the current position of the ant. If the coin ends up heads, the ant steps right and ‘x’ increases by one i.e. ‘x+1’. If it’s tails, the ant steps left and x decreases by one i.e. ‘x−1’. A heads or tails is equally likely; therefore it is equally probable that the ant steps right or left. Your job is to compute the probability that the ant will be at position ‘y’ after taking ‘n’ steps. If you compute the probability at each point and plot the graph, you would have modeled the random walk of the ant according to the given constraints.

For you math buffs out there, we formulate this whole thing by treating simple random walk as a martingale. We then define an independent random variable for each point. The sum of this series gives us the distance traveled, and of course the expectation of this sum is 0. We can go into the mathematical details, but it will not be straightforward if you are not familiar with calculus. So if you really want to see the mathematical modeling, you can google “one-dimensional random walk” and you will find dozens of articles explaining the formulation. It’s actually really nice!

Where is it used?

The following are some of the more popular applications of random walk:

• In physics, random walks are used to model diffusion, and the random movement of molecules in liquids and gases
• In computer vision, random walks are used in image segmentation to separate different regions and find the labels for each pixel.
• In economics, the random walk is used to model share-prices and the related fluctuations.
• In computer science, random walks are used to estimate the size of the Web.
• In brain research, reinforced random walks are used to model cascades of neuron firing in the brain.
• In population genetics, random walk is used to infer the statistical properties of genetic drift.
• In psychology, random walks explain the relationship between the time needed to make a decision and the probability that a certain decision will be made.

————————————————————————————————-