Week 2, Problem 2: The sleepwalking student
[35 points; individual or pair] filename: hw2pr2.py

For this problem, you will write functions to simulate and investigate the behavior of a sleepwalking student (more formally known as a "random walk"). You should place these functions in a file named hw2pr2.py.

Part 1. First function (just to copy) rs()

Near the top of your file, be sure to have the following:

import random # this can go anywhere at the top of the file

def rs():

""" rs chooses a random step to make and returns it

notice that rs() requires parentheses, but takes

no inputs at all!

"""

return random.choice([-1,1])

You will thus be able to call on this rs() function whenever you want to obtain a new, random step. A big advantage of this is that it will be extremely easy to change what is meant by random step in the future. As long as all the rest of your code uses rs, you will be able to change the one line in rs in order to take much bigger or smaller random steps.

An alternative is to use the line

from random import *

If you use this line instead of the one above, you will not need to include the random. in front of calls to choice or other functions within the random module.

For this problem, string multiplication is very useful here. Here is an example to remind you how this works. The example with the 10 spaces shows how you can position text further to the right on the screen.

>>> 'spam'*3

spamspamspam

>>> 'start' + ' '*10 + 'end'

start end

Similar to this last example, you will want to multiply the string ' ' (consisting of one space) by different values for some of the functions below.

Part 2. Second function (to write) rwPos

Write a function named rwPos( start, nsteps ) which takes two inputs: an integer start, representing the starting position of our sleepwalker, and a nonnegative integer nsteps, representing the number of random steps to take from this starting position. The name, rwPos is meant to suggest that this function returns the position of a random walker. Be sure that your rwPos does return the position of the sleepwalker after nsteps random steps, where each step moves either plus 1 or minus 1 from the previous position.

Printing/debugging code to include:

As part of your rwPos function, include a line of debugging code that prints what s is each time the function is called. See the examples below for what this might look like.

Examples:

>>> rwPos( 40, 4 )

start is 40

start is 41

start is 42

start is 41

start is 42

42

>>> rwPos( 40, 4 ) # won't be the same each time...

start is 40

start is 39

start is 38

start is 37

start is 36

36

Even if you are comfortable using while or for loops, you should use recursion to implement rwPos for this problem. This is because this assignment ultimately exercises the functional and recursive style of computational problem-solving. There will be plenty of loops later in the term... .

Part 3. Third function to write rwSteps

Write rwSteps( start, low, hi ) which takes three inputs: an integer start, representing the starting position of our sleepwalker, an integer low, which will always be nonnegative, representing the smallest value our sleepwalker will be allowed to wander to, and an integer hi, representing the highest value our sleepwalker will be allowed to wander to. You may assume that hi ≥ start ≥ low . As soon as the sleepwalker reaches at or beyond the low or hi value, the random walk should stop. When it does stop, rwSteps should return the number of steps (hence the "Steps" in its name) that the sleepwalker took in order to finally reach the lower or upper bound.

Printing/debugging code:

As part of your rwSteps function, you should include a line of debugging code that prints a visual representation of your sleepwalker's position while wandering. Feel free to be more creative than the simple 'S' in the example below. For example, consider 0->-< (a true sleepwalker!)

Examples:

>>> rwSteps( 10, 5, 15 )

S

S

S

S

S

S

S

S

S

S

9 # here is the return value!

>>> rwSteps( 10, 7, 20 )

S

S

S

S

S

S

S

S

S

S

S

S

11

Again, you should use recursion to implement rwSteps for this problem. Hint: this problem is tricky because you are adding a random step and adding to the ongoing count of the total number of steps. One suggestion for the recursion is to use the call rwSteps( newstart, low, hi ) as the recursive call, with an appropriate assignment to newstart on the line above it... .

Need more time or space?

You can get more memory for recursion by adding this to the top of your file:

import sys

sys.setrecursionlimit(50000)

This provides 50000 function calls in the recursive stack. You can also slow down the simulation by adding this line to the top of your file:

import time

Then, in your rwSteps or rwPos functions, you can include the line

time.sleep(0.1)

which pauses for 0.1 second. Adjust as you see fit!

Part 4. Analysis of random walks

With these three functions working, you have the computational raw materials to start investigating these two (closely related) questions:

• What is the average final signed-displacement for a random walker after making N random steps? The "signed-displacement" is the signed (positive or negative) distance from the initial starting point. This is just the output of rwPos. Do not use abs.
• What is the average square of the final signed-displacement for a random walker after making N random steps, in terms of N? Be sure you square before you average the values.

You should adapt the random-walk functions you wrote to investigate these two questions. In particular, you should

• Write versions of rwPos and rwSteps that do not print any debugging or explanatory information. Rather, they should just return the final position or number of steps, respectively. Call these new versions rwPosPlain and rwStepsPlain . Be careful! the recursive calls will need to change, too... .
• Come up with a plan for how you will answer these questions. This plan should include writing at least one additional python function other than those written above. For example, you might consider writing a function that collects a lot of data and then presents a useful summary of that data -- perhaps using map or a list comprehension.
• Implement and test your additional function(s) to help your investigation.
• Report the answers you find from these computational tests. To do this, place your answers inside your python program file by either making them comments (using the # symbol) OR, even easier, including them in triple-quoted strings (since they can include newlines). For example,

"""

In order to compute the average signed displacement for a random walker after N random steps, I ...

(briefly explain what you did and your results)

(1-2 sentences for each question is OK)

"""

Thus, your file should include (1) answers to these two questions and how you approached them and (2) your python functions including whatever additional function(s) you wrote to help answer these questions. Make sure to include explanatory docstrings and comments for every function that you write!

Please include any references you might have used - you're welcome to read all about random walks online, if you like. However, you should also feel free not to bother - whether your answers are correct or not will have no effect on grading this problem. It will be graded on whether your functions work as they should, whether they would be helpful in answering those questions, and in the clarity and effectiveness of your write-up.

Submission

You should submit your hw2pr2.py file at Canvas .

Next

hw2pr3

Homework 2