CSC 221: Computer Programming I
Fall 2006
HW5: Repetition and Simulation
In class, we considered the simulation of Dot races, where a single dot could move
a random distance along a track at each step. Dot races represent just one example
of a broad class of simulations known as random walks. In a random walk, the
walker starts at an initial position and is able to move in random (but possibly
constrained) steps. Random walks have been used in a variety of real-world
applications, including modeling the interactions of atomic particles, recreating
natural patterns such as river beds and mollusk shells markings, and drawing
realistic textures for 3-D graphics.
For this assignment, you will consider a form of random walk known as an alley
walk. In an alley walk, the walker is constrained to one-dimensional movement,
being able to move one unit to the right or left in a single step. As an analogy,
consider a person standing at the middle of a long, narrow alley. She can take a
step in either direction towards an exit. If the
direction is randomly chosen, it is possible that she may wander back and forth along
the alley before eventually stumbling out one end. The following diagram depicts a
situation where the person is 10 steps away from either exit.
As we have seen in past examples, random events such as dice rolls and coin flips
are predictable, but only in the long run. It is possible (although unlikely) for a
person to roll snake eyes on their first roll or flip heads four times in a row.
Similarly, a single random walk might produce unexpected results. An alley walk with
goal distance 10 could be completed in as few as 10 steps, or conversely might take
hundreds of steps. Given a large number of walks, however, you would expect such
anomalous walks to be rare and to balance out. It has been shown that, on average,
the number of steps required for an alley walk with goal distance X
is approximately X2. Thus, if a walker starts in the
center of an alley where each end is 10 steps away, it will take (on average)
approximately 100 steps to exit.
- Implement the AlleyWalker class, which is intended to
simulate a one-dimensional walker. An AlleyWalker should start in position 0, and
each call to the step method should either increase or decrease its position by
1. In addition, the stepToDistance method should repeatedly call the step
method until the specified goal distance is reached (i.e., the walker reaches either
end of the alley).
- While the AlleyWalker class allows you to perform individual alley walk
simulations, there can be considerable variation in individual walks. In order to
get a true estimate of the expected number of steps required, a large number of
alley walks must be simulated and the results averaged. The WalkStats class has been provided for you.
The constructor for this class takes a single parameter, the length of the alley, and
initializes an AlleyWalker object. The averageSteps method performs repeated
alley walk simulations and calculates the average number of steps over all the walks.
Using WalkStats and your AlleyWalker classes, perform
repeated simulations and enter the average number of
steps for the alley walks in the table below.
| SIMULATION 1 | SIMULATION 2 | SIMULATION 3
|
---|
1,000 alley walks, goal=10 | | |
|
10,000 alley walks, goal=10 | | |
|
100,000 alley walks, goal=10 | | |
|
1,000 alley walks, goal=20 | | |
|
10,000 alley walks, goal=20 | | |
|
100,000 alley walks, goal=20 | | |
|
- Does the consistency of the results improve when the number of walks
increases? That is, are the three averages obtained from 10,000 walks closer
together
than the three averages obtained from 1,000 walks? Likewise, are the averages
obtained from 100,000 walks closer together than those obtained from 10,000 walks?
Should
they be? Explain.
- Are the averages close to the expected results? Recall that an alley walk with goal
distance X should require approximately X2 steps (on average). Are the averages more accurate as
the number of walks increases? Should they be? Explain.
- Now consider a variation of the alley walk that takes place in a dead-end alley.
The person starts out at the wall, and can only exit at the other end. If he is
against the wall and takes a step in that direction, he merely bumps into the wall
and stays where he is. At any other place in the alley, however, he is free to move
in either direction as before.
Assuming the same goal distance, which do you think would require more steps (on
average) to complete: a random
alley walk in which the user can exit in either direction, or a random dead-end walk
in which the user can only exit in one direction but may repeatedly bump into the
wall. Note that bumps into the wall still counts as steps, even though the walker's
position does not change.
You must provide a plausible justification for your prediction.
EXTRA CREDIT
Modify your AlleyWalker class so that it can be used to simulate both
traditional alley walks (with two exits) and dead-end walks (with a wall and only
one exit). In order to do this, you must:
- Add a boolean parameter to the AlleyWalker constructor, which specifies
whether a wall is present. For example, in the statements below, the alley
object would be constructed with no wall, and so would perform traditional alley walks
as before. The dead object, however, would be constructed with a wall
at position 0, and so would perform dead-end walks.
AlleyWalker alley = new AlleyWalker(false);
AlleyWalker dead = new AlleyWalker(true);
- Modify the step method so that it limits the walker from moving into
a negative position if a wall is present. That is, if there is a wall, then any
attempt to move left from position 0 will result in no position change (although
the attempt should still count as a step).
- Finally, modify the constructor of the WalkStats class so that it
has a boolean parameter, identifying whether the walks to be simulated should have
a wall or not. This parameter should be used to construct the appropriate type of
walker for use in the simulations.
Using your modified classes, perform repeated simulations and enter the average
number of steps required for the dead-end walks in the table below.
| SIMULATION 1 | SIMULATION 2 | SIMULATION 3
|
---|
1,000 dead-end walks, goal=10 | | |
|
10,000 dead-end walks,
goal=10 | | |
|
100,000 dead-end walks,
goal=10 | | |
|
1,000 dead-end walks, goal=20 | | |
|
10,000 dead-end walks,
goal=20 | | |
|
100,000 dead-end walks,
goal=20 | | |
|
- Do these numbers support or refute your prediction as to the relative behavior
of alley walks and dead-end walks? Justify your answer.