| ITEC 120 |
| 2009spring |
| ibarland nokie jmdymacek |
|
|
|
home—info—lects—labs—exams—hws
textbook—tutor/PIs—java.lang docs—java.util docs
Due Apr.22 (Wed).
Consider a person who leaves a their home, and travels in the following random manner:
If somebody takes a random walk of, say, 1000 such decisions, where will end up? Sometimes they might be fully 1000 steps north of their house, but that's not very likely. Sometimes they'll be exactly back at their house entrance (but that's still pretty unlikely, that they went north exactly as many times as they went south). Most of the time they'll probably be somewhat near their house, but not exactly where they started from.
So a natural question is, on average, how far away do they end up? If fifty such random walkers all leave their house, how far will they get, on average? And even more: how much variation will there be---will these fifty people all be roughly the same distance away from their house, or will some be very close to their house while others are nearly a full 1000 steps away?
Aha, we are now in a position to experimentally find how far away they are! We will:
How many steps should each walk be? 100 How many random walks do you want to simulate? 10000 On average, each person ended up 6.5485 steps from their home, and on average, each person was 3.951464599999985 steps away from the average |
public static void main( String[] args ) {
// m walks of n steps each:
int n = promptForInt( "How many steps should each walk be?" );
int m = promptForInt( "How many random walks do you want to simulate?" );
// For each walker, how far away from home do they end up?
double[] walks = takeManyWalks(m,n);
makeEachPositive(walks);
// For each walker, how far away from the average are they?
double avgDist = avg(walks);
subtractFromEach( avgDist, walks );
makeEachPositive( walks );
// What is the average distance-from-the-average?
double variation = avg( walks );
System.out.println( "On average, each person ended up " + avgDist
+ " steps from their home,\n"
+ "and on average, each person was " + variation
+ " steps away from the average.\n" );
}
|
First, write a function
/** See how far somebody gets, in a random walk. * @param numSteps The total number of decisions made, * in the random walk. * @return The final position, after the walk: * 0 represents the starting point; * the result can be positive or negative. */ static int takeOneWalk( int numSteps ) |
Initially, the walker starts 0 steps north of their house, 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've seen previously. 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!
Now, 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 number of decisions of each walks. * @return an array containing the result of `numWalks` random walks. */ static double[] takeManyWalks( int numWalks, int numSteps ) |
Before proceeding: Check whether the above method works. Myself, I (temporarily) had my main print out the array returned by takeManyWalks, and spent some time looking over the results, to see if the results were plausible.
But how do we print out an array? Alas, the built-in toString method is unhelpful, for arrays. There are several ways:
We already wrote avg(double[]) in class, to compute the average. You'll want it for this code. (Even if you don't remember it from class, you should be able to write that method from scratch rather easily.) It should be a static method, since its answer doesn't depend on which object you ask.
Note that as a sanity check, you can also have your main temporarily print out the average of the array returned by takeManyWalks; the average should be close to zero, even for huge walks: About half the walkers will end up north of their house, about half will end up south of their house, 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.)
Note that even though the final product won't include this average, I definitely did print it myself, to give me confidence that my code was giving reasonable answers.
We might know the average distance of a random-walk, but of course any individual walkers will be different from the exact average. Typically, are most walkers close to the average, or are some much bigger than the average and others much smaller than the average? (That is, are walks tightly clustered around the average, or is there big variation?)
To answer this, we'll start by modifying our data from being the ending-location (both positive and negative), to being just the distance-from-home (non-negative).
By the way, the average of this modified array is an informative number: The average distance-from-home. We can compute this immediately if we wanted, since we just call our previously-written method.
Our last method will be fairly general, but our main will happen to use it in a specific way. Write a method which takes in a number “diff” and also3 an array of numbers, and modifies the array by subtracting diff from each.
/** Subtract a number from each element of an array,
* modifying it.
* @param diff The amount to subtract from each element of `data`.
* @param data The array of data.
*
* For example: if `data` contains {18.0, 20.0, 22.0},
* and `diff` is 20.0,
* then this method would modify `data` to contain
* {-2.0, 0.0, 2.0}
*/
static void subtractFromEach( double diff, double[] data )
|
At last,
we can sit back and understand how that provided main works —
how it estimates
the variation among walks.
To ponder/discuss: Is this variation higher or lower than you might have expected?
My solution's main which was ten lines long (each line more or less corresponding to the points above). It had six other methods, but each of those was short: only two to five lines.
From a coding standpoint, one thing to notice is that although there are several sub-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 Question: 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
1 It is also sometimes referred to a “drunken walk”, in which case the starting point is usually called a pub. ↩
2 Why do we ask that this array hold doubles, even though conceptually it should hold ints?
3 The first version of this homework suggested using double[] eachDistFromAvg( double[] data ). That's fine too; we'll grant full credit for either approach that you get working. ↩
home—info—lects—labs—exams—hws
textbook—tutor/PIs—java.lang docs—java.util docs
| ©2009, Ian Barland, Radford University Last modified 2009.Apr.22 (Wed) |
Please mail any suggestions (incl. typos, broken links) to iba�rland  rad�ford.edu |
 |