(fill in your two names here)
Facilitator: (fill in name)
Spokesperson: (fill in name)
Process Analyst: (fill in name)
Quality Control: (fill in name)
If there are only three people in your team, have one person serve as both spokesperson and process analyst for the rest of this activity.
At the end of this Lesson, you will be asked to record how long each Model required for your team. The Facilitator should keep track of time for your team.
In the simulation of the random motion of many particles in a box, we did not care about their positions – all we needed to know was the number of particles on each side. Suppose that we want to characterize the motion of a dust particle in the atmosphere or a pollen grain suspended in water. We know that as a given dust particle collides with molecules in the atmosphere, it changes its direction frequently, and its motion appears to be random. A simple model for the trajectory of a dust particle in the atmosphere is based on the assumption that the particle moves in any direction with equal probability - this is a model is an example of a random walk.
Random walk has been used to build models for many scientific applications, including:
Consider an idealized/simplified example of a random walker that can move only along a line (in 1 dimension). Suppose that the walker begins at $x = 0$ and that each step is of equal length. At each time interval the walker has a probability $p$ of a step to the right and a probability $q = 1− p$ of a step to the left. The direction of each step is independent of the preceding one. The final position of the walker (or the displacement of the walker from the origin) after $N$ steps is:
$$x_N = \sum_{i=1}^{N}s_i$$
where $s_i=1$ for a step to the right and $s_i=-1$ for a step to the left.
For example, if $p=0.5$, a step to the right ($s = +1$) will occur $50%$ of the time. This does not mean, however, that the walker will move to the right every other step - each step is independent, like a coin flip. Overall, after many trials, we expect a step to the right to happen half the time and a step to the left ($s = -1$) the other half, but there is a finite possibility of moving right five times in a row (think about how you would calculate this probability given $p=0.5$).
In this lesson, we will develop a program to simulate a random walk. The walker will begin at position $0$. We will treat a step to the right as $+1$, and a step to the left as $-1$.
1. If the random walker takes steps of equal probability in random directions (left or right) after $N$ steps where do you predict the random walker will be? Explain your reasoning.
2. What is the range of possible values for the probability $p$ of a step to the right?
3. What are the possible positions for a 1D walker after one random step?
Make sure that as you work on these programming tasks, you are using your best pair programming technique (both driver and navigator) and switching drivers frequently.
Your code must have docstrings and comments for you to receive full credit.
We are using an Object Oriented Programming approach for this Lesson.
A. We will begin with a class that initializes ONE walker. Define a class called RandomWalk. The constructor should have one additional parameter besides the self parameter: the probability of a step to the right. (Do not set the parameter to a default value yet.) You will need to keep track of two instance variables: the probability and the position of this walker.
Make sure to test the constructor
In [ ]:
In [ ]:
## testing
B. Next add a get_position method that should return the position of the walker in relation to the original position.
Make sure to test get_position
In [ ]:
In [ ]:
## testing
C. Now add a run_simulation method that has the walker take one random step. Modify your __init__ method so it calls your run_simulation method. This method does not need to return anything.
Run your code several times to make sure it works.
In [ ]:
In [ ]:
## testing
D. Add a second parameter to the constructor: the total number of steps, $N$.
Also modify your run_simulation method so it has the walker take $N$ random steps.
Run your code several times to make sure it works.
In [ ]:
In [ ]:
## testing
E. Next, make probability an optional argument. Modify the constructor so the probability is set to $0.5$ if it is not given. Since all optional parameters must follow required parameters, you will need to reorder your arguments since the total number of steps is a required argument.
Run your code several times to make sure it works.
In [ ]:
In [ ]:
## testing
4. How does each of the following depend on the total number of steps? Your answers do not need to be an equation, but simply a general observation.
4a. The final position of your walker, after running the simulation once?
4b. The range of final possible positions, if the simulation was run multiple times (always starting at 0).
5. How does each of the following depend on the probability of a step to the right? Your answers do not need to be an equation, but simply a general observation.
5a. The final position of your walker, after running the simulation once?
5b. The range of final possible positions, if the simulation was run multiple times (always starting at 0).
Because of the many random choices of the walker, the final position varies each time the simulation is run. To obtain better statistics and visualization of the random walker, we will modify the RandomWalk class so that it simulates a large number of walkers and plots a histogram of the final positions. To do this, we will need to determine the maximum possible range of the final displacements, i.e., the value of the left-most and right-most possible positions for a single walker based on the simulation parameters.
6. If we are simulating a large number of walkers, will the final position for each walker be the same at the end of the simulation?
7. If we want to keep track of a large number of walkers, how should the instance variables in the RandomWalk class be modified?
8. What are the maximum values possible for the left-most and right-most possible positions, if:
8a. a walker takes 10 steps?
8b. a walker takes N steps?
9. After running the simulation of a large number of walkers, we would like to view a histogram showing the final positions of all the walkers. Describe the contents of the single list that we would have to send to pyplot.hist() and the two lists that must be sent to the pyplot.bar() function to create this histogram (note: you won't need to code both)
10. If we simulate 1000 walkers that each take 3 steps, how long are the above two lists?
11. Examine the instance variables in your RandomWalk class. Which instance variables are no longer necessary? What new instance variables do you need to introduce to the class to eventually create the above histogram?
12. What methods do you need to modify in your RandomWalk class, and what new methods are needed? Keeping the Walking Skeleton process in mind, list the order in which these methods should be modified, written and tested.
13. When you consider the expected output of your program, should the plot depend on the value of N? Why or why not? How would you generalize your output such that it is independent of N?
F. Follow the order you created in Question 12 above, modify your RandomWalk class so it runs the simulation for multiple walkers and creates a list that can be graphed. You should include a plot_positions method that creates a normalized histogram of the final position of all your walkers. (do it first with a regular histogram, then figure out how to normalize it (normalized means the heights of all the bars sum to 1) - there are several reasonable ways to accomplish this).
Run your code several times to make sure it works.
In [ ]:
In [ ]:
## testing
G. Modify your final code so that when you make an object, the output to the user is the normalized histogram. Make sure that your graph is well labeled.
Run your code a few times to make sure it works.
In [ ]:
In [ ]:
## testing
H. Modify your constructor so it only accepts valid values for the total number of steps, probability, and number of walkers. This information should also be in your docstring (2 of the values will have arbitrary maximums and that's ok). If arguments are invalid, then your code should print a helpful message.
Run your code several times to make sure it works.
In [ ]:
In [ ]:
## testing
14. Assume that the particle has an equal probability of going to the right or left with a step length of one. Run your simulation for different numbers of random walkers but keep the number of steps for each particle the same.
14a. Are some displacements more likely than others? Show some results and describe what you see.
In [ ]:
14b. On average, where does the walker end up after N steps? Explain your observations and provide more data as necessary.
16. It can be shown that if you average over sufficient number of walks of $N$ steps, then the average displacement, $\langle x \rangle$, can be calculated by:
$$\langle x \rangle = (p-q)N$$
How do the results of your previous simulations compare to the analytical result? Use data, code, and calculations to illustrate and fully explain your results.
How much time did it require for your team to complete each part?
Model 1:
Team Programming 1:
Model 2:
Team Programming 2:
Analysis Questions: