# Random Walk

**Thank you for voting on the poll question last week - I learn from your responses **

Imagine you are drunk … and walking !

The drunk walk, or, as we euphemistically call it - The Random Walk

So, every step you take forward is just as likely to be towards the left, as it is towards the right - that’s the assumption, and it is true when you are drunk, or for capturing true randomness

When you are starting at a point, your next step to the left is just as likely as your next step to the right, so, the probability (of you taking a step left) = 1/2, and the probability (of you taking a step right) is also 1/2

So, let’s say, you take three steps, and for the purpose of this conversation, let’s say it is +1 when you go right, and -1 when you go left

As you take one step forward : you can either be at +1 or -1

You need to evaluate your second step, based on your first step you just took. So, before you take the second step, you are either starting at +1 (if you went right in your first step) or -1 (if you went left in your first step)

**Let’s say, you went right in your first step, and hence you are at +1**

if you go right again in the second step, you are at +1 +1 = +2

if you go left in the second step, you are at +1 -1 = 0

**Let’s say, you went left in your first step, and hence you are at -1**

if you go right in the second step, you are at -1 +1 = 0

if you go left again in the second step, you are at -1 -1 = -2

Option 1 = +2

Option 2 = 0

Option 3 = 0

Option 4 = -2

So, you have four options : you can either be at +2, or 0, or 0 again, or at -2. But you could get to 0 in two of those four cases. You can either go right and then go left, or you could go left and then go right - and both of those lead to 0

On the contrary, notice that there is only one pathway to get to -2 and + 2

**Perfect … now what ?**

Let’s do one more step

So, at the end of the second step, you could either be at -2, 0 or +2

**If you go right (+1) in your third step, you have three options**

-2 +1 = -1

0 +1 = +1

+2 +1 = +3

**or, if you go left (-1) in your third step, you have three more options**

-2 -1 = -3

0 -1 = -1

+2 -1 = +1

So, now you have six options : you could be at any of these six points from your initial point : -1, +1, +3, -3, -1, +1

But, there is only one pathway to +3 and -3, where as, you have two pathways to reach +1 and -1

And if you repeat this statistical experiment infinite number of times, you will end up with a bell curve (technically, a binomial distribution, but at large sample sizes, binomial becomes a normal distribution, as in, a bell curve)

How mathematically elegant is that ?

but, more importantly, why do you end up with a bell curve?

You can see this yourself, if you drop a whole bunch of small beads through the pegs in the Galton board (below), it will beautifully form a normal distribution in front of your eyes

**What is the Statistical Intuition ?**

And the intuition makes sense, right ? to end up to the far left of the bell curve, you repeatedly have to take steps to the left all the time, and the likelihood of that happening is low (here is a great explanation)

Since your likelihood of going left is the same as going right, the combined likelihood of you going consistently left is very low - that’s why only one ball (in the picture above) ends up in the left most bin

Same goes to the far right

But as we talked about above, there are more pathways to the center, or, there or thereabouts near the center, and because of that - the probability of balls ending up somewhere in the middle is higher

That’s why more balls end up in the center and less balls end up in the edges - pretty much reflecting a bell curve

The Galton board experiment above is essentially simulating a drunk walk and presents the probability of where one might end up in the end, when compared to where that person started

**Machine Learning Applications**

Random Walk algorithms are used in image segmentation (computer vision) in Machine Learning. As a highly simplified example, if a cat sits on a roof, the algorithm helps segment between which pixels belong to the cat, as opposed to the roof (sources : Scikit Learn and IEEE)

A picture is essentially a collage of pixels. Initially, the user, labels some of the pixels as a cat or a roof. Then the machine learning algorithm takes an unlabeled pixel and releases a random walker from it

The intuition here is the same as above. If you release a drunk walker from an unlabeled pixel, then the walker, randomly walks and arrives at a labeled pixel (in this case, assume you initially labeled that pixel as a cat)

Based on the probability of arriving from the unlabeled pixel to the labeled pixel, you can classify the unlabeled pixel as either a cat or a roof. Identifying different objects this way has significant applications in autonomous vehicles as well

**Brownian Motion**

Einstein’s explanation of how gas molecules move as they are being bombarded by different invisible particles from all directions - is also based on random walk theory, and we call this Brownian Motion (MIT)

Sources : IEEE and Python Scikit Learn, MIT and Johnnie Walker