Share this:
Google+
< Previous | Contents | Next >
What is Random Walk?
Random walk is a process, a model or a rule to generate path sequence of random motion. Consider a particle motion in a straight line.
That particle can move 1 unit to the left or 1 unit to the right with a certain probability. For simplicity, let us assume symmetrical probability that the probability to the left is 50% and the probability to the right is 50%. We can do this random walk experiment. Every time step, we can toss a fair coin and decide to move the particle to the right if the coin turns head and to move the particle to the left if the coin turns tail. Starting at location \( x_0 = 0 \), we record the locations of the particle over time. We use notation \( x_t \) to indicate the location of the particle after taking \( t \) steps. A model to generate path sequence of the locations of a particle that moves based on random probability distribution is called random walk.
Random Walk Formula: $$ x_t = x_{t-1} + \Delta x $$
In this example, the value of \( \Delta x \) is either +1 or -1. An instance of such random walk sequence would be:
Time step |
Coin Face |
\( \Delta x \) |
\( x_t \) |
0 |
- |
- |
x(0) = 0 |
1 |
Head |
+1 |
x(1) = +1 |
2 |
Tail |
-1 |
x(2) = 0 |
3 |
Tail |
-1 |
x(3) = -1 |
4 |
Head |
+1 |
x(4) = 0 |
5 |
Tail |
-1 |
x(5) = -1 |
6 |
Head |
+1 |
x(6) = 0 |
7 |
Head |
+1 |
x(7) = +1 |
8 |
Head |
+1 |
x(8) = +2 |
And so on. Thus, the path sequence of random walk instance above is <0, 1, 0, -1, 0, -1, 0, 1, 2, …>
Random walk is sometimes called Brownian motion (after botanist Robert Brown in 1827 who discovered such motion of pollens in water under microscope). However, Brownian motion is actually a subset of random walk where the probability distribution in continuous over time.
Suppose the particle has taken \( N \) steps from the initial position. This means we have flipped the coins \( N \) times. Suppose we have \( n \) heads out of \( N \) flips. This also means we have \( N - n \) tails. Remember, head means we move the particle to the right and tail means we move the particle to the left. One natural question arise: what is the distance of the particle from the initial position? After taking \( N \) steps with \( n \) heads, the distance should be $$ d = n – (N – n) = 2n – N $$ to the right of its initial position.
We can reverse the formula above. If we know that at time \( N \), the particle is at position \( d \) from its initial position, assuming symmetrical probability between head and tail, how many heads did the coin flip? $$ n = 0.5 (d + N) $$
The often questions about random walk are:
- How far the particle can go away from the initial position after taking \( N \) steps?
- What is the probability that the particle will go back to the initial position after taking \( N \) steps?
- What is the probability that the particle will go to a given location in \( N \) steps?
- How long the particle can travel distance \( d \) from the starting point?
- Will the particle return to the initial position?
Random walk can be extended to higher dimension \( D \).
< Previous | Contents | Next >
Do you have question regarding this Stochastic Process tutorial? Ask your question here
These tutorial is copyrighted .
Preferable reference for this tutorial is
Teknomo, Kardi. (2019) Stochastic Process Tutorial .
http://people.revoledu.com/kardi/tutorial/StochasticProcess/