Random Walk: Will the Drunk Man Fall Off the Cliff?
A drunk man standing on a cliff, takes steps randomly left and right. Each step he takes has a probability of going left and a probability of going right and the size of each step is same. If the drunk man is allowed to randomly step indefinitely, what will be the probability that he falls off the cliff?
Any guesses? Well, let’s again have a glimpse of this problem through “Random Walk”.
The Random Walk theory is based on the irregular motion of the individual pollen particles, studied by botanist, Mr. Robert Brown in 1828. In the process of researching on a random walk, scientists like Einstein and Smoluchowski studied similar subjects like random process, random noise, spectral analysis, and stochastic equations. The first simple model of Random Walk proposed was uncorrelated and unbiased.
- Uncorrelated means the direction of movement is completely independent of the previous directions taken.
- Unbiased means there is no preferred direction, the direction moved at each step is completely random.
“A random walk is a mathematical object, known as a stochastic or random process, that describes a path that consists of a succession of random steps on some mathematical space such as the integers.” (Source: Wikipedia)
It is a problem, which is closely related to Brownian motion.
Types of Random Walks
1. Correlated Random Walks (CRWs)
It involves a correlation between successive step orientations. This correlation is termed as Persistence. This produces a local directional bias, each step tends to point in the same direction as the previous one, although the influence of the initial direction of motion progressively diminishes over time and step, orientations are uniformly distributed in the long term. The nature of the motion of animals is similar, hence, CRWs have been constantly used to monitor motion paths of animals in various contexts.
2. Biased Random Walks (BRWs)
When the probability of traveling in a certain direction is greater, i.e. all directions are not equally likely, then such Random Walks are known as Biased Random walks.
Possible Factors of Bias :
- Fixed external environmental factors such, as a movement under gyrotaxis.
- Spatially varying factors, such as chemical gradients.
- Mean-reversion mechanisms, such as movement within a home range.
- Choice of direction by individuals at each step.
In BRWs, target direction and strength of bias vary with location and time.
3. General Random Walk & The Levy Walk
Generally, while considering the results from a random walk theory, we consider the step to be both fixed or variable. In variable lengths, those whose step lengths have fixed variance are considered.
Levy walk: Distribution of step lengths is heavy-tailed, i.e. has an infinite variance. In this case, the walk exhibits scale-invariant (i.e. fractal) characteristics. Many research papers suggest that the Levy model provides a suitable model for animal movements.
4. Simple Isotropic Random Walk
Let’s take a case where the walker is moving on an infinite one-dimensional uniform lattice. The motion is completely random. So the probability of moving either left or right is equal, i.e., ½. After one time step, the walker can either be at a distance 𝛿 to the left or to the right of the origin, with probability ½ each.
After the next time step, the walker will either be at a distance 2𝛿 to the left or right of the origin (with probability ¼ each) or will have returned to the origin (with probability ½). After an even (odd) number of steps, the walker can only be at an even (odd) distance away from the origin.
5. Analogy- Random Walker
A man starts from a point 0 and walks ‘x’ yards in a straight line. He then turns through any finite angle and walks another ‘x’ yards in a straight line. He repeats this process n times. We require the probability that after these n stretches he is at a distance between r and r + δr from his starting point 0.
The probability that a walker will be at a distance m to the right of the origin after n time steps (where m and n are even) is given by :
This is a form of the binomial distribution, with mean 0 and variance n. For large n, this converges to a normal (or Gaussian) distribution so, after a sufficiently large amount of time t = nτ, the location x = mδ of the walker is normally distributed with mean 0.
Random Walk in 1D
Let us assume that a walker can sit at regularly spaced positions along a line that is at distance ∆x apart so we can label the positions by the set of whole numbers m. We require the walker to be at position x=0 at time T=0.
The walker jumps to the right with probability p and to the left with probability q = 1 − p.
To find out the probability p(m, N) that the walker will be at position m after N steps.
For m < N there are many ways to start at 0 and go through N jumps to nearest neighbour sites and end up at m. But since all these possibilities are independent, we have to add up their probabilities. The walker must have made n1 jumps to the right (n1 = m + n2) and n2 jumps to the left, and since n1 + n2 = N, the walker must have made
Random Walk in 1-Dimension
The probability for making n1 jumps to the right and n2 jumps to the left is
The total number of distinguishable ways to have n1 steps to the right and n2 to the left therefore becomes
The probability of being at position m after N jumps is therefore given as
Properties of Random Walk in 1D
The probability of Random Walk is given by
If we sum all the probabilities then the cumulative sum is 1.
Expectation, aka, the expected value, is the summation or integration of all the possible values from a random variable and is given by
In the same manner, we can derive the Expectation for the second moment. Read more about moment states.
The variance of the variable n is defined by
The relative width of distribution goes to zero as N (number of steps) increases. This property is called self-averaging.
Position of the walker after N steps is given by
For the second moment, the position of the walker is
Variance of the displacement m is
Implementation
Now we have seen enough of theory and formulas, let’s checkout the fun part.
Random Walk in 1D
N = int(input()) # number of steps walked
P = float(input()) # probability to move right# initialize the starting position
start = 0
positions = [start]# create random points
random_points = np.random.random(N)
down_probability = random_points < Pfor m in down_probability:
if m:
positions.append(position[-1] - 1)
else:
positions.append(position[-1] + 1)
Special Case: For a large number of symmetric walkers with p = q = 0.5, the expressions of average displacement and mean square distance is as follows.
Random Walk for a large number of steps
We are interested in the behavior of the binomial distribution for Np → ∞ i.e., for a long time. Assuming N >> 1 we can use Stirling’s Approximation to approximate the factorials in the binomial distribution.
Stirling’s formula:
After a large number of steps, and with the help of Diffusion Coefficient D, the location of the walker can be given as
This is the fundamental solution for the Diffusion Equation. We can also see that this solution is Gaussian Distribution.
Random Walk for a long time follows Gaussian Distribution
Given the walker takes n1 steps to the right and n2 steps in the left direction and the probability to move in both directions is p and q respectively.
n1 + n2 = N (total number of steps)
n1 - n2 = m (steps displaced in right direction)
We have already seen that probability of walker at m distance after completing N steps is given by
# total number of steps
N = 10000p = 0.5 # probability to move right
q = 1 - p # probability to move left# path contains probability of having walker at n steps
path = []for m in range(N+1):
path.append((p ** (0.5*(N+m))) * (q ** (0.5(N-m))))
for m in range(N+1):
path[m] *= ncr(N, m)
As N increases ⇒ Binomial Distribution → Gaussian Distribution
Random Walk in 2D
In a 2D random walk, we consider independent random vectors instead of independent points. Let Xn be the trajectory of a random walk in two dimensions. Our discrete-time, simple random walk starts from the origin (0, 0) ∈ Z
Hence, for each step, there are four choices with respect to chosing of direction. All four directions have equal chances of being chosen.
Implementation
# number of steps
N = 10000x, y = numpy.zeros(N), numpy.zeros(N)for i in range(1, N):
rand = random.randint(1, 4)
if rand == 1:
x[i], y[i] = x[i-1]+1, y[i-1]
elif rand == 2:
x[i], y[i] = x[i-1]-1, y[i-1]
elif rand == 3:
x[i], y[i] = x[i-1], y[i-1]+1
else:
x[i], y[i] = x[i-1], y[i-1]-1
Applications of Random Walk
1. Bacteria finding food
Bacteria find their food using biased random walks. They can bias their walks based on the concentration gradient of a particular chemical. So even though each step is in a random direction, the length of the step is longer if the bacterium is moving towards a higher concentration compared to if it is moving towards a lower concentration.
Food for bacteria is usually a simple sugar, such as glucose. If sugar is floating around in solution, it usually exists in higher concentration areas. Bacteria use chemotaxis to wander towards the sugar source. It can also use this process to move to lower concentrations of poisons.
2. Quantum Cloud
Antony Gormley’s Quantum Cloud sculpture in London was designed by a computer using a random walk algorithm. The steel sections were arranged using a computer model with a random walk algorithm, starting from points on the surface of an enlarged figure based on Gormley’s body that forms a residual outline at the center of the sculpture.
3. Physics and Mathematics
In physics, random walks are used as simplified models of physical Brownian motion and diffusion such as the random movement of molecules in liquids and gases.
4. Population genetics
Random walk describes the statistical properties of genetic drift. Genetic drift is the change in the frequency of an existing gene variant in a population due to random sampling of organisms.
5. Psychology
Random walks explain the relation between the time needed to make a decision and the probability that a certain decision will be made.
6. Computer Science
In computer science, random walks are used to estimate the size of the Web. The Twitter website uses random walks to make suggestions of who to follow. In wireless networking, a random walk is used to model node movement.
References
- https://royalsocietypublishing.org/doi/pdf/10.1098/rsif.2008.0014
- https://en.wikipedia.org/wiki/Random_walk
- https://www.scribd.com/document/236400989/J-R-Soc-Interface-2008-Codling-813-34
- http://physics.gu.se/~frtbm/joomla/media/mydocs/LennartSjogren/kap2.pdf
- https://web.mit.edu/kardar/www/teaching/projects/chemotaxis(AndreaSchmidt)/finding_food.htm
- https://quizlet.com/353316895/genetic-drift-flash-cards/
If you’ve hung in this long… thanks! I hope there’s been valuable information for you. Drop me a note if you find it useful or have any follow-up questions.
Thanks for reading!
