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 X². 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.

1. Complete the definition of the AlleyWalker class, which is intended to simulate a one-dimensional walker. An AlleyWalker starts in position 0, and each call to the doStep method either increases or decreases its position by 1. To support the testing and debugging of your class, a unit testing class AlleyWalkerTest is also provided.

   
   

2. Define a class named AlleyWalkSimulator, which can be used to perform random alley walk simulations. When an AlleyWalkSimulator is constructed, the goal distance (i.e., number of steps to either exit) should be specified as a parameter. In addition, the following methods should be defined:

   
   
   
   

   /** * Simulates an alley walk, repeatedly stepping an AlleyWalker until it exits * the alley (i.e., reaches goal distance from starting position). */ int alleyWalk() { ... } /** * Conducts the specified number of alley walks and displays the average number * of steps required by the walks. The output includes the number of walks and * goal distance, as well as the average number of steps. * @param numWalks the number of alley walks to be simulated */ void displayAverage(int numWalks) { ... }

   This class will be similar in form to the VolleyBallSimulator class from the previous homework. In particular, the alleyWalk method should display the walker's position after every step when called directly, but not if called from displayAverage.

   
   
   

3. Using your 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 X² steps (on average). Are the averages more accurate as the number of walks increases? Should they be? Explain.

     
     
     
     
     
     
     
     
     
     
     
     

4. 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.

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

5. Modify your AlleyWalker and AlleyWalkSimulator classes to allow for dead-end walks to be simulated as well. Your approach should be similar to the modifications you made with the VolleyBallSimulator class to allow for two different scoring schemes. In particular, you should modify the AlleyWalker class so that it never moves into negative positions if there is a wall. Likewise, modify the AlleyWalkSimulator class so that the user can simulate either type of walk (with positions displayed), or perform repeated walks of each type and compare the step averages.

   
   

6. 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.

   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   
   

   ---