In many situations, it is very useful to think of some sort of process that you wish to model as a succession of random steps. This can describe a wide variety of phenomena - the behavior of the stock market, models of population dynamics in ecosystems, the properties of polymers, the movement of molecules in liquids or gases, modeling neurons in the brain, or in building Google's PageRank search model. This type of modeling is known as a "random walk", and while the process being modeled can vary tremendously, the underlying process is simple. In this exercise, we are going to model such a random walk and learn about some of its behaviors!
Put the name of your group members here!
Imagine that you draw a line on the floor, with a mark every foot. You start at the middle of the line (the point you have decided is the "origin"). You then flip a "fair" coin N times ("fair" means that it has equal chances of coming up heads and tails). Every time the coin comes up heads, you take one step to the right. Every time it comes up tails, you take a step to the left.
Questions:
First: as a group, come up with a solution to this problem on your whiteboard. Use a flow chart, pseudo-code, diagrams, or anything else that you need to get started. Check with an instructor before you continue!
Then: In pairs, write a code in the space provided below to answer these questions!
In [ ]:
# put your code for Part 1 here. Add extra cells as necessary!
%matplotlib inline
import matplotlib.pyplot as plt
import random
import math
import numpy as np
n_trials = 1000 # number of trials (i.e., number of independent walks)
n_steps = 100 # number of steps taken during each trial
distances = [] # use this empty list to keep track of distance for each trial
this_trial = 0
# loop over trials
while this_trial < n_trials:
this_distance = 0 # distance gone in this trial - reset to zero each time
step=0 # what step this trial is on - reset to zero each time
# loop until we get to the right number of steps!
while(step < n_steps):
# random number is either 0 or 1 (heads or tails)
if random.randint(0,1) > 0:
this_distance += 1 # go right
else:
this_distance -= 1 # go left
step+=1
# keep track of distances (absolute value)
distances.append(abs(this_distance))
# keep track of number of trials
this_trial += 1
plt.hist(distances)
distances = np.array(distances) # convert to numpy array to make life easier
# in 1D, asymptotic solution for mean walk length is (n_steps*2/pi)**(1/2)
print("expected mean:", math.sqrt(n_steps*2.0/math.pi),
"\nactual mean:", distances.mean(), "\nmin:", distances.min(), "\nmax:", distances.max())
Now, we're going to do the same thing, but in two dimensions, x and y. This time, you will start at the origin, pick a random direction, and take a step one foot in that direction. You will then randomly pick a new direction, take a step, and so on, for a total of $N_{step}$ steps.
Questions:
First: As before, come up with a solution to this problem on your whiteboard as a group. Check with an instructor before you continue!
Then: In pairs, write a code in the space provided below to answer these questions!
In [ ]:
# put your code for Part 2 here. Add extra cells as necessary!
n_trials_2D = 1000 # number of trials (i.e., number of walks)
n_steps_2D = 100 # number of steps per trial
distances_2D = [] # to keep track of distances of each walk
this_trial = 0
# lists for x, y position of *each step* for the last trial.
# (This is just for visualization purposes - we want to make a plot.)
xpos=[]
ypos=[]
while this_trial < n_trials_2D:
x,y = 0.0,0.0
# keep track of walker position for last trial
if this_trial == n_trials_2D - 1:
xpos.append(x)
ypos.append(y)
step=0
# go until we reach the number of steps we want to take
while(step < n_steps_2D):
# pick a random angle between zero and 2*pi
theta = random.random()*2.0*math.pi
# step x and y in that direction
x += math.cos(theta)
y += math.sin(theta)
# if last trial, keep track of walker positions
if this_trial == n_trials_2D - 1:
xpos.append(x)
ypos.append(y)
step+=1
this_distance = (x**2 + y**2)**0.5
#print(this_trial, abs(this_distance))
distances_2D.append(abs(this_distance))
this_trial += 1
In [ ]:
plt.hist(distances_2D)
distances_2D = np.array(distances_2D)
# expect roughly sqrt(n_steps_2D) to be the right answer!
print("expected mean:", math.sqrt(n_steps_2D),
"\nactual mean:", distances_2D.mean(),
"\nmin:", distances_2D.min(),
"\nmax:", distances_2D.max())
In [ ]:
plt.plot(0.0,0.0,'ro',xpos,ypos,'b-')
#plt.xlim(-16,16)
#plt.ylim(-16,16)
If you have time, copy and paste your 1D random walk code in the cell below. This time, modify your code so that the coin toss is biased - that you are more likely to take a step in one direction than in the other (i.e., the probability of stepping to the right is $p_{step}$, of stepping to the left is $1-p_{step}$, and $p_{step} \neq 0.5$).
How does the distibution of distances gone, as well as the mean distance from the origin, change as $p_{step}$ varies from 0.5?
In [ ]:
# put your code for Part 3 here. Add extra cells as necessary!
n_trials = 100000
n_steps = 100
prob_right = 0.55
distances = []
this_trial = 0
while this_trial < n_trials:
this_distance = 0
step=0
while(step < n_steps):
if random.random() < prob_right:
this_distance += 1
else:
this_distance -= 1
step+=1
distances.append(this_distance)
this_trial += 1
plt.hist(distances)
distances = np.array(distances)
print("mean distance:", distances.mean(),
"\nabs mean distance:", np.abs(distances).mean())
For 100 steps, P = probability of stepping to the right. (I am only doing P >= 0.5 because the problem is symmetrical.)
| P | <dist> |
<abs_dist> |
|---|---|---|
| 0.5 | -0.01 | 8.03 |
| 0.55 | 9.96 | 11.62 |
| 0.6 | 19.94 | 20.01 |
| 0.8 | 60.06 | 60.06 |
| 1.0 | 100.0 | 100.0 |
Put your answers here!