ITEC 120 2008fall aaray, ejderrick, ibarland, jmdymacek

home—info—labs—hws—exams
textbook—java.lang docs—java.util docs—archive

lab12a
random walks
loops and arrays

This is a two-part lab.
ejderrick and ibarland sections: Hw09 will be: “complete all parts of lab12a”, due the Wednesday after the break (Dec.03).

Random walks

Consider a person who leaves a pub, and travels in the following manner:

• A third of the time they walk north a block.
• A third of the time they walk south a block.
• And the remaining third of the time they don't move at all.

If somebody takes a random walk of, say, WALK_LENGTH steps, where will end up? Sometimes they might be fully WALK_LENGTH moves north of the pub, but that's not very likely. Sometimes they'll be exactly back at the pub entrance (but that's still pretty lucky, if they went north exactly as many times as they went south). Most of the time they'll probably be somewhat near the pub, but not exactly where they started from.

So a natural question is, on average, where do they end up? If fifty such random walkers all leave the pub, how far will they get, on average? How much variation will there be---will these fifty people all be roughly the same distance away from the pub, or will some be very close to the pub while others are nearly a full WALK_LENGTH blocks away?

Aha, we are now in a position to experimentally find how far away they are! We will:

• Write a method which simulates one random walk.
• Collect data on many random walks, storing our results in an array.
• Calculate the average-distance-walked of all the numbers in the array.
• Calculate how far (on average) each walk tended to vary from the average.

TO DO First, write a function

/** See how far somebody gets, in a random walk.
 * @param numSteps The total number of steps taken.
 * @return The final position, after the walk:
 *    0 represents the starting point;
 *    the result can be positive or negative.
 */
int randWalk( int numSteps )

Initially, the walker starts 0 blocks north of the pub, and for the following numSteps times, it takes adds a random amount of -1, 0, or +1.

Test your function by first calling it with a small number of steps (say, a random walk of 5 steps, or even just 1 step). Repeat several times, so you get an idea of whether your method seems to be giving reasonable results. Then, try calling it with larger number of steps, like 150 or so.

Tip How to generate a random number in {-1,0,+1}: Create a random-number-generator (java.util.Random), as we saw last week. Create a number in {0,1,2} (by calling the Random's method nextInt(3)), and then subtract one from the result. This gives you a random number in the range you want. Try it in the code pad, a couple of times!

Analyzing Random Walks

TO DO Write a method to simulate many people, each taking their own random walk:

  /** Perform many random walks, recording the result.
   * @param numWalks How many random walks to simulate.
   * @param numSteps The length of each of those walks.
   * @return an array of length `numWalks`.
   */
  int[] takeManyWalks( int numWalks, int numSteps )

TO DO Write a driver method. For right now, it will just call our previous method, and print out the array of results. (We'll add more things to our driver later.)

But how do we print out an array? Alas, the built-in toString method is unhelpful, for arrays. There are several ways:

• Write a helper-method which loops through an array, printing each item.
• More flexibly, write a method which returns a String representing an array: loops through the array, each time tacking on the next number to a stringSoFar.
• You can use the improved toString method mentioned in the table comparing Lists and arrays.
• In BlueJ's Code Pad, you can inspect (double-click) on an array object.

Lab12, continued:

We are going to want to calculate the average of several different data sets (arrays). Rather than write the code-to-calculate-the-average-of-an-array repeatedly:
TO DO: let's just write a method avg which calculates the average of any array. What is its signature?

TO DO: Go back and modify your driver method, so that it prints out the average of all the random walks. (This average should be close to zero...on average. About half the walkers will end up north of the pub, about half will end up south of the pub, and these will roughly cancel each other out. But not always, of course -- occasionally a set-of-random-walks might include an unusual percentage of people who all end up (say) to the north, and the average of that set will be further away from 0.)

We might know the average distance of a random-walk, but how far away from the average is a typical walk? (That is, are walks tightly clustered around the average, or spread far away?)
TO DO: Modify your driver method to take the results of the random walks (which are both positive and negative), and modify that array so that each location stores how far each walker got (no negative numbers). That is, replace each item with is absolute value. (Use Math.abs to convert a number to its absolute value.)

TO DO: Now that the driver method has an array just of distances, calculate and print the average of this modified array. (Remember, from a previous step, you already have a method which will compute any array's average. Don't repeat that code; just call that method!) This gives an informative number: The average distance walked.

TO DO Write a method which takes in one array of numbers: first it calculates the average value of the array, and then it returns a whole new array whose elements are the distance from each original number was from the average.

  /** Given an array of data,
   * compute how far each element is from the average.
   * @param data The array of data.
   * @return an array containing the distance (non-negative)
   *  of each item from the average.
   *  For example: if `data` contains {18.0, 20.0, 22.0},
   *  this method would first compute the average (20.0),
   *  and return the array {2.0, 0.0, 2.0}.
   *     (since 18 is distance-two from the average,
   *     as is 22 -- we don't care about positive or negative).
   */
  double[] eachDistFromAvg( int[] data )

TO DO
At last, we can provide answers to the question of how tightly clustered random walks are — that is, how-far-from-average a walk tends to be (on average!). Have your driver print out the the average value of the distance-from-the-average.
Of course, getting this should be easy: calling eachDistFromAvg gives you an array of the differences, and then calling average will give us the result:

  double[] allDistances = eachDistFromAvg( data );
  double avgDistFromAvg = avg( allDistances );

Reflecting

From a coding standpoint, one thing to notice is that although there are several "TO DO" tasks, each one solves a nice, restricted problem, and is only about 3-4 lines of code. Moreover, by calling methods we have previously written, we leverage this code greatly -- we don't have the code for computing the average repeated four times; we only write it once³, and then later we can just call the method.

This approach is called a Monte Carlo simulation: rather than mathematically figuring out exactly what the average is, we do a whole bunch of simulations, and get an idea of what's going on.

Challenge: Run your program on walks with different lengths (say 100 steps, 1000 steps, 10,000 steps, 100,000 steps). Do you see a pattern, in

• The average distance walked? (Can you guess a formula for it?)
• The average-distance-from-the-average? (Can you guess a formula for it?)

home—info—labs—hws—exams
textbook—java.lang docs—java.util docs—archive

©2008, Ian Barland, Radford University Last modified 2008.Nov.20 (Thu)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu