CS 122 Lab 3: Running and Analyzing Computational Simulations of Random WalksDr. Bruce Char & Dr. Frederick W. Chapman
Department of Computer Science
Drexel University(Last Revised on May 9, 2008)Your Name: Partner #1: Partner #2:

Click on the triangles in the left margin to open each of the worksheet sections below.Save your Maple worksheet often as you work through this lab!
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[0,153,153]">Directions & Requirements</Font></Text-field>The directions for this lab are different from any of the previous ones -- it will be impractical for you to do this lab without working in a group. Part of the reason is that we leave determination of larger portions of the Maple programming up to you to determine/complete, so you will probably benefit from talking to others about those steps to get through them. There are sections where the amount of computational work is non-trivial, so that it will be twice (or three times) faster to split up the work.
Be sure to type your name and the name(s) of your lab partner(s) in the spaces provided above. Although you may work together, you should each submit your own copy of the lab to Blackboard Vista. You must do this to receive credit for the lab!
Since the required material discussed in the tutorials and problems will be covered on Quiz 3, you are encouraged to complete Lab 3 as soon as possible. If you get stuck on any part of the lab, you can get help from a TA in office hours in the Cyber Learning Center (UC 147). Be sure to submit your lab on Blackboard Vista before the due date.This lab is divided into the following sections:Required Reading: Introduction & Overview, Tutorials 1-3, Wrap-UpRequired Problems: Problem 1, Parts (a) and (b); Problem 2, Parts (a) through (e)Optional Reading: None.Optional Problems: Problem 3.You will need to complete all 3 required tutorials and all 7 parts of the 2 required problems to prepare for the next quiz. The optional problem will not be covered on the quiz or the exam; the optional material is provided to deepen your knowledge, understanding, and mastery of Maple.
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[0,51,204]">Introduction & Overview</Font></Text-field>This lab is about investigating a process by building a model of it in the computer, running computational experiments, and trying to make sense of the the results through data analysis, mathematical analytics, and visualization. The "build, execute, analyze" approach is taken by many different kinds of projects in engineering research. Whether the process includes elements governed by randomness (as this one does) or is modeled deterministically by well-defined mathematical functions, computational simulation and analysis of the results is a useful and highly regarded activity in most engineering research.
The appeal of using systems like Maple, Mathematica or MATLAB for these kinds of problems is that they have far more power and are more convenient for doing the experiments than using a calculator or a "conventional" compiled language such as Java or C. Furthermore, their integration of symbolics, numerics, and graphics (for visualization) means that the analysis can be performed with the same tool that produced the results, so there is no additional learning curve to go through for another tool, nor the possibility of a data format mismatches or other unanticipated incompatibilities between tools. Furthermore, the worksheet interface allows convenient organization of the elements (programs, numbers, plots) in one place for subsequent viewing or reuse.
<Text-field style="Heading 2" layout="Heading 2"><Font foreground="[0,51,204]">What Is Computational Simulation?</Font></Text-field>We frequently apply engineering science to develop a detailed understanding of certain physical phenomena. This allows us to better meet our goals in engineering projects where these phenomena are in play. Examples are numerous:
How air flows around the body and wings of a particular airplane design.How well a particular collection of highway interchanges and stop lights handles traffic under different situations ("normal", "heavy flooding", "tractor trailer overturn", "multiple sporting events in the same location").Stress on weight-bearing beams in a multi-floor office building under a mixture of different kinds of tenants.Where groundwater flowing past a toxic waste buried in the ground carries the dissolved toxic chemicals, and how fast.How often a computer network switch will delay data beyond 2 milliseconds, under normal fluctuations in traffic load.
Back in the pre-computer "old days", engineers would build scale models or full-sized models and run tests by creating the situations they were interested in exploring and observing what happens. The model-building and result-collecting was tedious and could be somewhat expensive. While there is still much value to "reality based experimentation", as engineering science has gotten better at describing engineering phenomena mathematically, there has been general acknowledgment that there is a lot of value to building the model through more mathematical means in the computer, and running the experiments there. This is because (a) it's usually cheaper (because it's faster to get the results), and (b) it's a lot easier to change details in a computer model than a physical model, so many more "what if" scenarios can be explored.
<Text-field style="Heading 2" layout="Heading 2"><Font foreground="[0,51,204]">How Do We Gain Useful Information from a Computational Simulation?</Font></Text-field>Simulations usually describe what happens to various quantities of interest over time. Thus, it may be worthwhile just to run the program and have it dump out the quantities into an appropriate data structure (files, tables, lists, sequences). Then the computer is used again to do data analysis and visualization on the computed quantities, just as if the quantities were measurements taken in the lab or in the field. The results of the analysis are used to produce insight into the nature of the system being simulated -- whether the design performs well enough to meet behavior specifications (the airplane stays aloft, or meets its fuel economy budget), whether there are any hidden flaws, or how the design performs in "what if" situations that the designer is concerned about.
Sometimes the results indicate that the simulation is not being realistic -- that there are bugs or deficiencies in the programming or in the mathematics being used to describe the phenomenon. Then the computational engineer must do some reprogramming to improve the fidelity of the simulation.
<Text-field style="Heading 2" layout="Heading 2"><Font foreground="[0,51,204]">What Will I Be Asked to Do in This Lab?</Font></Text-field>In Tutorial 1, we return to the one-dimensional (1D) random walks we programmed last term in CS 121. The rest of the lab is work that allows you to answer the following question: What can we know about the location of the walker as a function of time (# of steps taken)? You will use versions of programs which model these walks to generate some data and to analyze the results. To help you do the analysis, you will be asked to do some plots on the data collected. This should provide clues that there is something systematic going on, and help you determine the nature of that behavior. You will then use Maple's symbolic math capabilities to help you find you a way to express the relationship mathematically.
As with the optimization problems we solved in an earlier lab, Maple can help you see or do things in this lab, but there are still parts where old-fashioned thinking is required. The execution of the program and the generation of the data will lead to the plots, but Maple can't tell you how to interpret the pictures. If you don't see any relationships, then it's time to consult with your team members to see what ideas they may have.
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[0,51,204]">Tutorial 1: Return of the Random Walk</Font></Text-field>
<Text-field style="Heading 2" layout="Heading 2"><Font foreground="[0,51,204]">Tutorial 1(a): What Experiments Are We Doing, and What Do We Hope to Discover?</Font></Text-field>Recall the "random walk" situations we were modeling in Lab 5 in CS 121 last term. There was a one-dimensional version and a two-dimensional version. In each one, an object moved through process controlled by chance. We wrote versions of programs to simulate these processes. Some versions were entertaining in that they provided a movie of the random movement -- but they also played a crucial role in convincing us that the behavior of the program was appropriate to what was being modeled. Others were more geared towards a specific computational goal -- just determining the final position after N steps of the walk.
Recall that the central question of our investigation: What can we know about the location of the walker as a function of the number of steps taken? There are some things that we can deduce from basic principles about random walks, and other things that are harder to determine just by thinking a little about it.
Since the simulation is driven largely by random processes, we won't get the same result each time we run the experiment. Each experiment will play out differently. We know from the animations from the last lab on random walks that repeated trials of the random walk had the figure ending up in a different position almost every time. So it doesn't seem like reality can be described by simple rules like "after 5 steps, the robot will always end up 3 feet away from the origin".
However, even in things like physics experiments where supposedly exact physical laws are in play, it's rare to have exact same result in repeated experiments. One typically can take averages and hope that one can make a statement about the behavior of averages.
To many readers, it will be obvious that since a step in one direction is just as likely as a step in any other, the average position over repeated experiments will be close to the origin. But how close? Just by watching a lot of random walks we might suspect that while the eventual result of taking a lot of steps would nearly cancel out, it isn't actually as common that they would cancel out exactly as they would cancel out only approximately.
Thus, it makes sense to measure the extent of the non-cancellation, and average that. For the one-dimensional case, this means carrying out the following steps:
Run an experiment of taking N steps, find the distance away from the origin at the end of the experiment.Average the distance over many repetitions of the experiment. This is "the average distance away from the origin after taking N steps".A clarification is in order at this point: We will use "root-mean-square" (RMS) averaging, which is a special way of measuring the average distance. It is closely related to the Euclidean measure of distance. This is explained in Tutorial 2.
<Text-field style="Heading 2" layout="Heading 2"><Font foreground="[51,0,255]">Tutorial 1(b): A Procedure to Simulate the One-Dimensional Random Walk</Font></Text-field>Here is the procedure developed for the one dimensional random walk. We've augmented the comments a bit to help remind you about what was going on.restart; #forget all previous assignments
aRandomWalk := proc(N, nextStep)
#Procedure parameters:
# N is the total number of steps to be taken
#nextStep is the random number generator that when called returns a 1 or a 2
local currentPosition, i, decision;
#local variables used only within the procedure, not related to
#variables of the same name that exist outside of the procedure body
currentPosition := 0; #initialize current Position to origin
for i from 1 to N do
decision := nextStep();
if decision = 1 then
currentPosition := currentPosition +1;
elif decision = 2 then
currentPosition := currentPosition -1;
end if;end do; return currentPosition;
end ;Note that to call it we have to create an appropriate random number generator and specify how many steps to take.flipper := rand(1..2);numSteps := 10;Now call the procedure with that many steps.aRandomWalk(numSteps, flipper); # output final position after that many stepsCall it a few times. We expect it to output a number between -numSteps and +numSteps each time (but varying).aRandomWalk(numSteps, flipper); aRandomWalk(numSteps, flipper); aRandomWalk(numSteps, flipper); aRandomWalk(numSteps, flipper);
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[51,0,204]">Tutorial 2: The Root-Mean-Square (RMS) Average</Font></Text-field>There are many different ways to describe data values through statistical measures. In basic statistics, for example, we have three different kinds of measures that claim to measure an "average": the mean (the sum of all the values divided by the number of values), the median (the middle value in a sorted list of values), and the mode (the value which occurs most frequently). In engineering, science, and mathematics, there is another kind of measure which is frequently used: the root-mean-square average or RMS average for short. In some technical applications, the RMS average is the best measure to use. The discussion below explains why.
<Text-field style="Heading 2" layout="Heading 2">Tutorial 2(a): Defining the RMS Average</Text-field>How is the RMS average defined? Moreover, how does it get its name? To understand how the root-mean-square average gets its name, it helps to remember how we define the mean. Suppose we have LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= data values LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiVRImlGJ0YyRjUvRjZRJ25vcm1hbEYnLyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGPQ== for LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYtLUkjbWlHRiQ2JVEiaUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj1GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1JI21uR0YkNiRRIjFGJ0Y5LUY2Ni1RIixGJ0Y5RjsvRj9GMUZARkJGREZGRkgvRktRJjAuMGVtRicvRk5RLDAuMzMzMzMzM2VtRictRlA2JFEiMkYnRjlGUy1GNjYtUSMuLkYnRjlGO0Y+RkBGQkZERkZGSC9GS1EsMC4yMjIyMjIyZW1GJy9GTkZYLUY2Ni1RIi5GJ0Y5RjtGPkZARkJGREZGRkhGV0Zdb0ZTLUYsNiVRIm5GJ0YvRjJGOQ==. The mean of the values LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiVRImlGJ0YyRjUvRjZRJ25vcm1hbEYnLyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGPQ== is usually denoted by LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2I1EhRictSSZtb3ZlckdGJDYlLUYjNiQtRiw2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GO1Enbm9ybWFsRictSSNtb0dGJDYuUSomT3ZlckJhcjtGJy8lLHBsYWNlaG9sZGVyR0Y5Rj0vJSZmZW5jZUdRJnVuc2V0RicvJSpzZXBhcmF0b3JHRkcvJSlzdHJldGNoeUdGOS8lKnN5bW1ldHJpY0dGRy8lKGxhcmdlb3BHRkcvJS5tb3ZhYmxlbGltaXRzR0ZHLyUnYWNjZW50R0Y5LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGVi8lJ2FjY2VudEdGOUY9 and is defined by the formulaLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2I1EhRictRiM2JUYrLUkmbW92ZXJHRiQ2JS1GIzYkLUYsNiVRImRGJy8lJ2l0YWxpY0dRJXRydWVGJy8lLG1hdGh2YXJpYW50R1EnaXRhbGljRicvRj1RJ25vcm1hbEYnLUkjbW9HRiQ2LlEqJk92ZXJCYXI7RicvJSxwbGFjZWhvbGRlckdGO0Y/LyUmZmVuY2VHUSZ1bnNldEYnLyUqc2VwYXJhdG9yR0ZJLyUpc3RyZXRjaHlHRjsvJSpzeW1tZXRyaWNHRkkvJShsYXJnZW9wR0ZJLyUubW92YWJsZWxpbWl0c0dGSS8lJ2FjY2VudEdGOy8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRlgvJSdhY2NlbnRHRjtGPy1GQjYtUSI9RidGPy9GSFEmZmFsc2VGJy9GS0Zbby9GTUZbby9GT0Zbby9GUUZbby9GU0Zbby9GVUZbby9GV1EsMC4yNzc3Nzc4ZW1GJy9GWkZjby1JJm1mcmFjR0YkNigtSSNtbkdGJDYkUSIxRidGPy1GIzYkLUYsNiVRIm5GJ0Y5RjxGPy8lLmxpbmV0aGlja25lc3NHUSIxRicvJStkZW5vbWFsaWduR1EnY2VudGVyRicvJSludW1hbGlnbkdGZnAvJSliZXZlbGxlZEdGW28tRkI2LVEnJnNkb3Q7RidGP0ZqbkZcb0Zdb0Zeb0Zfb0Zgb0Zhb0ZWRlktSSttdW5kZXJvdmVyR0YkNictRkI2LVEmJlN1bTtGJ0Y/RkdGSkZMRk4vRlFGOy9GU0Y7L0ZVRklGVi9GWlEsMC4xNjY2NjY3ZW1GJy1GIzYmLUYsNiVRImlGJ0Y5RjxGZ25GaG9GP0ZccC9GZm5GW28vJSxhY2NlbnR1bmRlckdGW28tSSVtc3ViR0YkNiVGNi1GIzYlLUZCNi1RIn5GJ0Y/RmpuRlxvRl1vRl5vRl9vRmBvRmFvRlZGWUZbckY/LyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGPw== .The root-mean-square average of the values LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiVRImlGJ0YyRjUvRjZRJ25vcm1hbEYnLyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGPQ== is usually denoted by LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiZRJHJtc0YnLyUnZmFtaWx5R1ErTW9ub3NwYWNlZEYnL0YzUSZmYWxzZUYnL0Y2USdub3JtYWxGJ0ZCLyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGQg== and is defined by the formulaLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYnLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiZRJHJtc0YnLyUnZmFtaWx5R1ErTW9ub3NwYWNlZEYnL0YzUSZmYWxzZUYnL0Y2USdub3JtYWxGJ0ZCLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYuUSJ+RidGPUZCLyUmZmVuY2VHRkEvJSpzZXBhcmF0b3JHRkEvJSlzdHJldGNoeUdGQS8lKnN5bW1ldHJpY0dGQS8lKGxhcmdlb3BHRkEvJS5tb3ZhYmxlbGltaXRzR0ZBLyUnYWNjZW50R0ZBLyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGZW4tRkg2LVEiPUYnRkJGS0ZNRk9GUUZTRlVGVy9GWlEsMC4yNzc3Nzc4ZW1GJy9GZ25GXG8tSSZtc3FydEdGJDYjLUYjNictSSZtZnJhY0dGJDYoLUkjbW5HRiQ2JFEiMUYnRkItRiM2JC1GLzYlUSJuRidGMkY1RkIvJS5saW5ldGhpY2tuZXNzR1EiMUYnLyUrZGVub21hbGlnbkdRJ2NlbnRlckYnLyUpbnVtYWxpZ25HRmRwLyUpYmV2ZWxsZWRHRkEtRkg2LVEnJnNkb3Q7RidGQkZLRk1GT0ZRRlNGVUZXRllGZm4tSSttdW5kZXJvdmVyR0YkNictRkg2LVEmJlN1bTtGJ0ZCL0ZMUSZ1bnNldEYnL0ZORmNxL0ZQRjQvRlJGY3EvRlRGNC9GVkY0L0ZYRmNxRlkvRmduUSwwLjE2NjY2NjdlbUYnLUYjNiYtRi82JVEiaUYnRjJGNUZobkZmb0ZCRmpvLyUnYWNjZW50R0ZBLyUsYWNjZW50dW5kZXJHRkEtSSVtc3VwR0YkNiUtSShtZmVuY2VkR0YkNiQtRiM2JC1GLDYlRi4tRiM2JEZeckZCRkRGQkZCLUYjNiQtRmdvNiRRIjJGJ0ZCRkIvJTFzdXBlcnNjcmlwdHNoaWZ0R0ZGRkJGQg== .If we compare the formula for the RMS average to the formula for the mean, we can see how the RMS average gets its name: To compute the RMS average, we first square the original data values, then take the mean of the squares, and finally take the square root of the mean. Thus, the root-mean-square average is just the root of the mean of the squares of the original data values!
<Text-field style="Heading 2" layout="Heading 2">Tutorial 2(b): Why Use the RMS Average Instead of the Mean?</Text-field>There are two main reasons for using the more complicated RMS average instead of the mean. Both reasons are consequences of the square terms which appear in the formula for the RMS average.The first reason for using the RMS average is that squaring the data prevents negative data values from canceling positive data values. Cancellation cannot occur in the sum since squaring makes all the terms greater than or equal to zero. As a result, the RMS average gives us information about the size of the data, while ignoring the sign of the data. In some situations, this is exactly what we want. For example, when we say that the voltage of the alternating current (AC) in a wall socket is 120 volts, this is really the RMS average of the voltage over one period of the AC waveform.The second reason for using the RMS average is that squaring the data makes it easier to compute the average of Euclidean distances. Suppose we have LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= data points LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkobWZlbmNlZEdGJDYkLUYjNictSSVtc3ViR0YkNiUtSSNtaUdGJDYlUSJ4RicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiQtRjQ2JVEiaUYnRjdGOi9GO1Enbm9ybWFsRicvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJy1JI21vR0YkNi1RIn5GJ0ZCLyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR0ZNLyUpc3RyZXRjaHlHRk0vJSpzeW1tZXRyaWNHRk0vJShsYXJnZW9wR0ZNLyUubW92YWJsZWxpbWl0c0dGTS8lJ2FjY2VudEdGTS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHRmZuLUZINi1RIixGJ0ZCRksvRk9GOUZQRlJGVEZWRlhGWi9GaG5RLDAuMzMzMzMzM2VtRictRjE2JS1GNDYlUSJ5RidGN0Y6Rj1GREZCRkJGQg== for LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYtLUkjbWlHRiQ2JVEiaUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIj1GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGTC1JI21uR0YkNiRRIjFGJ0Y5LUY2Ni1RIixGJ0Y5RjsvRj9GMUZARkJGREZGRkgvRktRJjAuMGVtRicvRk5RLDAuMzMzMzMzM2VtRictRlA2JFEiMkYnRjlGUy1GNjYtUSMuLkYnRjlGO0Y+RkBGQkZERkZGSC9GS1EsMC4yMjIyMjIyZW1GJy9GTkZYLUY2Ni1RIi5GJ0Y5RjtGPkZARkJGREZGRkhGV0Zdb0ZTLUYsNiVRIm5GJ0YvRjJGOQ==. Let LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiVRImlGJ0YyRjUvRjZRJ25vcm1hbEYnLyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGPQ== denote the Euclidean distance from the LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEiaUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic=-th point to the origin. Each LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiVRImlGJ0YyRjUvRjZRJ25vcm1hbEYnLyUvc3Vic2NyaXB0c2hpZnRHUSIwRidGPQ== is given by the formulaLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiVRImlGJ0YyRjUvRjZRJ25vcm1hbEYnLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYtUSI9RidGPS8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGSC8lKXN0cmV0Y2h5R0ZILyUqc3ltbWV0cmljR0ZILyUobGFyZ2VvcEdGSC8lLm1vdmFibGVsaW1pdHNHRkgvJSdhY2NlbnRHRkgvJSdsc3BhY2VHUSwwLjI3Nzc3NzhlbUYnLyUncnNwYWNlR0ZXLUkmbXNxcnRHRiQ2Iy1GIzYmLUklbXN1cEdGJDYlLUkobWZlbmNlZEdGJDYkLUYjNiQtRiw2JS1GLzYlUSJ4RidGMkY1RjhGP0Y9Rj0tRiM2JC1JI21uR0YkNiRRIjJGJ0Y9Rj0vJTFzdXBlcnNjcmlwdHNoaWZ0R0ZBLUZDNi1RIitGJ0Y9RkZGSUZLRk1GT0ZRRlMvRlZRLDAuMjIyMjIyMmVtRicvRllGYnAtRmpuNiUtRl1vNiQtRiM2JC1GLDYlLUYvNiVRInlGJ0YyRjVGOEY/Rj1GPUZmb0ZccEY9Rj0= .If we compute the mean of these LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= Euclidean distances, we get the somewhat nasty formulaLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYwLUkjbWlHRiQ2I1EhRictRiM2JkYrLUYjNiVGKy1JJm1vdmVyR0YkNiUtRiM2JC1GLDYlUSJkRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnL0Y/USdub3JtYWxGJy1JI21vR0YkNi5RKiZPdmVyQmFyO0YnLyUscGxhY2Vob2xkZXJHRj1GQS8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGSy8lKXN0cmV0Y2h5R0Y9LyUqc3ltbWV0cmljR0ZLLyUobGFyZ2VvcEdGSy8lLm1vdmFibGVsaW1pdHNHRksvJSdhY2NlbnRHRj0vJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZaLyUnYWNjZW50R0Y9RkFGK0ZBRistRkQ2LVEiPUYnRkFGSUZML0ZPRktGUEZSRlQvRldGSy9GWVEsMC4yNzc3Nzc4ZW1GJy9GZm5GX28tSSZtZnJhY0dGJDYoLUkjbW5HRiQ2JFEiMUYnRkEtRiM2JC1GLDYlUSJuRidGO0Y+RkEvJS5saW5ldGhpY2tuZXNzR1EiMUYnLyUrZGVub21hbGlnbkdRJ2NlbnRlckYnLyUpbnVtYWxpZ25HRmJwLyUpYmV2ZWxsZWRHRkstRkQ2LVEnJnNkb3Q7RidGQUZJRkxGXG9GUEZSRlRGXW9GWEZlbi1JK211bmRlcm92ZXJHRiQ2Jy1GRDYtUSYmU3VtO0YnRkEvRkpRJnVuc2V0RicvRk1GYXFGTi9GUUZhcS9GU0Y9L0ZVRj0vRldGYXFGWC9GZm5RLDAuMTY2NjY2N2VtRictRiM2Ji1GLDYlUSJpRidGO0Y+RmluRmRvRkFGaG8vRmhuRksvJSxhY2NlbnR1bmRlckdGSy1JJW1zdWJHRiQ2JUY4LUYjNiUtRkQ2LVEifkYnRkFGSUZMRlxvRlBGUkZURl1vRlhGZW5GW3JGQS8lL3N1YnNjcmlwdHNoaWZ0R1EiMEYnRmluRmFvRmdwRmpwLUkmbXNxcnRHRiQ2Iy1GIzYmLUklbXN1cEdGJDYlLUkobWZlbmNlZEdGJDYkLUYjNiQtRmJyNiUtRiw2JVEieEYnRjtGPi1GIzYkRltyRkFGaXJGQUZBLUYjNiQtRmVvNiRRIjJGJ0ZBRkEvJTFzdXBlcnNjcmlwdHNoaWZ0R0Zbcy1GRDYtUSIrRidGQUZJRkxGXG9GUEZSRlRGXW8vRllRLDAuMjIyMjIyMmVtRicvRmZuRlt1LUZiczYlLUZlczYkLUYjNiQtRmJyNiUtRiw2JVEieUYnRjtGPkZedEZpckZBRkFGYHRGZXRGQUZB .This formula is nasty because we must compute LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= square roots, one for each data point; however, if we square all of the Euclidean distances, we can get rid of the square root on each data point, like so:LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYoLUklbXN1cEdGJDYlLUkobWZlbmNlZEdGJDYkLUYjNiQtSSVtc3ViR0YkNiUtSSNtaUdGJDYlUSJkRicvJSdpdGFsaWNHUSV0cnVlRicvJSxtYXRodmFyaWFudEdRJ2l0YWxpY0YnLUYjNiQtRjc2JVEiaUYnRjpGPS9GPlEnbm9ybWFsRicvJS9zdWJzY3JpcHRzaGlmdEdRIjBGJ0ZFRkUtRiM2JC1JI21uR0YkNiRRIjJGJ0ZFRkUvJTFzdXBlcnNjcmlwdHNoaWZ0R0ZJLUkjbW9HRiQ2LVEiPUYnRkUvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRlgvJSlzdHJldGNoeUdGWC8lKnN5bW1ldHJpY0dGWC8lKGxhcmdlb3BHRlgvJS5tb3ZhYmxlbGltaXRzR0ZYLyUnYWNjZW50R0ZYLyUnbHNwYWNlR1EsMC4yNzc3Nzc4ZW1GJy8lJ3JzcGFjZUdGYW8tRiw2JS1GLzYkLUYjNiQtRjQ2JS1GNzYlUSJ4RidGOkY9RkBGR0ZFRkVGSkZQLUZTNi1RIitGJ0ZFRlZGWUZlbkZnbkZpbkZbb0Zdby9GYG9RLDAuMjIyMjIyMmVtRicvRmNvRmNwLUYsNiUtRi82JC1GIzYkLUY0NiUtRjc2JVEieUYnRjpGPUZARkdGRUZFRkpGUEZF .If we compute the RMS average of these LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEibkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= Euclidean distances, we get the much nicer formulaLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYpLUklbXN1YkdGJDYlLUkjbWlHRiQ2JVEiZEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1GIzYkLUYvNiZRJHJtc0YnLyUnZmFtaWx5R1ErTW9ub3NwYWNlZEYnL0YzUSZmYWxzZUYnL0Y2USdub3JtYWxGJ0ZCLyUvc3Vic2NyaXB0c2hpZnRHUSIwRictSSNtb0dGJDYuUSJ+RidGPUZCLyUmZmVuY2VHRkEvJSpzZXBhcmF0b3JHRkEvJSlzdHJldGNoeUdGQS8lKnN5bW1ldHJpY0dGQS8lKGxhcmdlb3BHRkEvJS5tb3ZhYmxlbGltaXRzR0ZBLyUnYWNjZW50R0ZBLyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGZW4tRkg2LVEiPUYnRkJGS0ZNRk9GUUZTRlVGVy9GWlEsMC4yNzc3Nzc4ZW1GJy9GZ25GXG8tSSZtc3FydEdGJDYjLUYjNictSSZtZnJhY0dGJDYoLUkjbW5HRiQ2JFEiMUYnRkItRiM2JC1GLzYlUSJuRidGMkY1RkIvJS5saW5ldGhpY2tuZXNzR1EiMUYnLyUrZGVub21hbGlnbkdRJ2NlbnRlckYnLyUpbnVtYWxpZ25HRmRwLyUpYmV2ZWxsZWRHRkEtRkg2LVEnJnNkb3Q7RidGQkZLRk1GT0ZRRlNGVUZXRllGZm4tSSttdW5kZXJvdmVyR0YkNictRkg2LVEmJlN1bTtGJ0ZCL0ZMUSZ1bnNldEYnL0ZORmNxL0ZQRjQvRlJGY3EvRlRGNC9GVkY0L0ZYRmNxRlkvRmduUSwwLjE2NjY2NjdlbUYnLUYjNiYtRi82JVEiaUYnRjJGNUZobkZmb0ZCRmpvLyUnYWNjZW50R0ZBLyUsYWNjZW50dW5kZXJHRkEtSSVtc3VwR0YkNiUtSShtZmVuY2VkR0YkNiQtRiM2JC1GLDYlRi4tRiM2JEZeckZCRkRGQkZCLUYjNiQtRmdvNiRRIjJGJ0ZCRkIvJTFzdXBlcnNjcmlwdHNoaWZ0R0ZGRkJGaG4tRl9vNiMtRiM2J0Zjb0ZpcEZccS1GaXI2JC1GIzYmLUZmcjYlLUZpcjYkLUYjNiQtRiw2JS1GLzYlUSJ4RidGMkY1Rl9zRkRGQkZCRmFzRmZzLUZINi1RIitGJ0ZCRktGTUZPRlFGU0ZVRlcvRlpRLDAuMjIyMjIyMmVtRicvRmduRl91LUZmcjYlLUZpcjYkLUYjNiQtRiw2JS1GLzYlUSJ5RidGMkY1Rl9zRkRGQkZCRmFzRmZzRkJGQkZCRkI= .This formula is nice because we must compute only one square root, no matter how many data points we have! This feature makes the RMS distance much easier to analyze mathematically than the mean distance. Since the square root function is expensive to compute in floating-point arithmetic, the RMS distance is also cheaper to evaluate numerically. These are the main reasons why the RMS average is the natural average to use when analyzing a data set consisting of Euclidean distances.
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[102,0,102]">Problem 1: Performing Many Trials of a One-Dimensional Random Walk</Font></Text-field>Here's an experiment we want to run with our simulation. It has three main steps:
Fix values for N and M; they should be positive integers, for example N = 10 and M = 40.Do the following M times: Run a single random walk with N steps and determine the final position of that random walk.After you have computed M final positions, compute their RMS average.First we should write a procedure to compute the RMS average.
<Text-field style="Heading 2" layout="Heading 2">Problem 1(a): Designing and Implementing a Maple Procedure "RMSAverage1"</Text-field>We aren't going to play "monkey see, monkey do" here. This is where your group needs to huddle and figure out how to define a Maple function to compute the RMS average of a list of numerical values, based on its mathematical definition given in Tutorial 2(a). You can also draw on your experience with the many, many examples of procedure definition given in previous labs. Here is a template you can use to write a procedure RMSAverage1 which accepts a list LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEiTEYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= of numerical values as input and returns the RMS average of those values as output.RMSAverage1 := proc(L::list)
local i; # use i for summing, but you may need other local variables, too.
# Complete the definition here -- it needs to be no more than a few lines.
end;Recall that Maple has three ways of defining a procedure: proc...end, the arrow operator, and unapply. This time, we chose to use proc...end because the definition naturally requires more than one line, which is proc...end is recommended. Also, if you need extra "local" variables to program the calculation, as it seems that we need here, you also don't get that with -> or unapply. Although we aren't providing you hints about how to write the procedure, we will provide some tests to see whether your procedure definition is working correctly.RMSAverage1([1,1,1]); #Result should be 1RMSAverage1([1,-1,1]); #Result should also be 1evalf(RMSAverage1([1,2,-3,2,62])); #Result should be approximately 27.79Checkpoint: When you reach this point, show your work to the TA.
<Text-field style="Heading 2" layout="Heading 2">Problem 1(b): Designing and Implementing a Maple Procedure "experiment1D"</Text-field>In this problem, you are to write a Maple procedure called experiment1D to compute the RMS average of the final positions resulting from M trials of a random walk with N steps.Here is an outline for a Maple procedure for running this experiment:experiment1D := proc(N, nextStep, M)
local i, results;
results := NULL;
#Step 1: run M trials of a random walk with N steps. Accumulate the final positions in the sequence "results".
#Step 2: compute the RMS average of the M trials. Return this as the result of the experiment1D function.
end;Given that we already have the procedure for doing one trial of a random walk with N steps, namely aRandomWalk, Step 1 can be done easily by writing a for loop that accumulates a sequence of results from aRandomWalk. Then you use the RMSAverage1 procedure that you just wrote. Get your posse together and put things together.We will now give you a few simple tests with small values of N and M. We turn on procedure tracing so that you can see what is going on inside. Note that the variable "results" should give you M position values, all of which should be between -N and N if the procedure is correct. The RMS average should also be between 0 and N if it is correct.trace(experiment1D); # givenflipper := rand(1..2); # givenDo 3 trials of a random walk of 5 steps:evalf(experiment1D(5,flipper,3)); # givenCorrectness checklist: answer "yes" or "no" to each question
a) Does the final value of "results" have M values?
Your answer:
b) Is each value in "results" between -N and N?
Your answer:
c) Is the RMSAverage calculated correctly? (You can always repeat the calculation manually?)
Your answer:
If the answer to any of these is "no", then your group should try to figure out what is wrong. This might be the time to get help from the TA if you really get stuck.Let's try it for a little larger problem.
evalf(experiment1D(10, flipper, 4)); # givenRepeat the checklist:
Correctness checklist: answer "yes" or "no" to each question
a) Does the final value of "results" have M values?
Your answer:
b) Is each value in "results" between -N and N?
Your answer:
c) Is the RMSAverage calculated correctly? (You can always repeat the calculation manually?)
Your answer:
If the answer to any of these is "no", then your group should try to figure out what is wrong. This might be the time to get help from the TA if you really get stuck.Checkpoint: When you reach this point, show your work to the TA.
If you get to this point, congratulations! You've just built the first experiment. Before we use it, turn off procedure tracing to disable "debugging" output.untrace(experiment1D); # given
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[0,51,204]">Tutorial 3: The Operator's Guide to Executing a "Long Running" Program</Font></Text-field>This lab is probably the first time that many of you have run anything on a computer where the result isn't produced instantaneously. With contemporary computational modeling, this is more the norm than the exception. As you've seen from labs so far, it's not atypical for problems to arise in a "shakedown cruise" even after you think the initial problems are overcome. As an experimenter, you want to minimize the amount of time you spend waiting around for results that turn out to have flaws in them. Thus, it's important to know the following about your programming before you start spending time on "big runs".
You should have tested your program on small inputs and checked for those easy cases that its output is correct.You should have some sense of how long a big run is going to take.You should have ways of checking even the big results for correctness, should you be challenged.Since our experience brings us so many computer programs that finish in a flash, it's easy for the naive user to think that everything is that way. Unfortunately, it's easy to write simple programs that take hours, centuries, or even more, to complete.
So how long does experiment1D(N, flipper, M) take to run? Using the Maple built-in time function, we can figure out how long a typical run might take:N := 100; M := 500; #Compute average of 500 random walks of 100 steps each.start_time := time();experiment1D(N, flipper, M);finish_time := time();elapsed_time100 := (finish_time - start_time) * seconds; # time in secondsLet's try a bigger run:N := 2000; M := 500; #Compute average of 500 random walks of 2000 steps each.start_time := time();experiment1D(N, flipper, M);finish_time := time();elapsed_time2000 := (finish_time - start_time) * seconds; # time in secondsNow let's try an even bigger run:N := 4000; M := 500; #Compute average of 500 random walks of 4000 steps each.start_time := time();experiment1D(N, flipper, M);finish_time := time();elapsed_time4000 := (finish_time - start_time) * seconds; # time in secondsIf this were an upper-level class on computer science, we could spend more time on this and get a formula relating the running time to N and M. For now, we have enough information to provide a rough estimate of how long it will take to do what we want.
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[102,0,102]">Problem 2: Gathering One-Dimensional Random Walk Data and Analyzing the Results</Font></Text-field>In this problem, you will first estimate the range of steps needed for a total computation time of three minutes. Then you will write a program to generate the desired computational results. After this you will run the program to actually generate these results, which you will then visualize with Maple's graphics. Finally, you will use Maple to determine a mathematical relationship which describes the results of your visualizations.
<Text-field style="Heading 2" layout="Heading 2">Problem 2(a): How Long to Collect the Results?</Text-field>Here's a "word problem" that your group should collectively solve. When you have an estimate that you agree on, show it to the TA for their approval.
Problem: We want to collect data on the RMS average of 500 random walks of N steps, where N=100, 200, 300, 400, 500, .....T. We would like the total computation time for the sum total of all the random walks to be about three minutes. How far out do you think you should go to collect three minutes' worth of data -- what do you think you should use for T? You may want to run experiment1D and time it for a few other values of N in order to come up with a stopping target T.
Place your work and your explanation of what you're using for T here.Value of T: Reasoning: Checkpoint: When you reach this point, show your work to the TA.
<Text-field style="Heading 2" layout="Heading 2">Problem 2(b): Writing a Program to Generate the Results</Text-field>Here's the next group task: Using experiment1D, write a procedure experimentSet1D that will conduct M trials of a random walk with N steps, as N varies in steps of 100 from a starting value low to an ending value high. Your procedure should return a sequence of pairs [Nvalue, RMSvalue], where Nvalue is the number of steps LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEiTkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= and RMSvalue is the RMS average computed from the M trials by experiment1D.#Fill in template below (may take a number of lines)
experimentSet1D := proc(M, nextStep, low, high)
local N, result;
result := NULL;
#for N from low to high by 100 do
#accumulate results from running experiment1D
return result;
end;We provide some tests to indicate what should be happening here.Procedure Testing (Short Version). Here is a test to check how well your procedure works.trace(experimentSet1D);untrace(experiment1D); #Turn on debugging for procedure you just wrote.evalf(experiment1D(100,flipper,500)); #Does experiment1D still work? Should produce a numberexperimentSet1D (500, flipper, 100, 200); #Should produce a sequence with data for N=100 and N=200.untrace(experimentSet); #Turn off debuggingProcedure Testing (Long Version). Here is a slightly longer test, just in case you still have doubts.trace(experimentSet);untrace(experiment1D); #Turn on debugging for procedure you just wrote.evalf(experiment1D(100,flipper,500)); #Does experiment1D still work? Should produce a numberexperimentSet1D (500, flipper, 100, 1000); #Should produce a sequence with data for N=100, 200, 300, up to 1000.Checkpoint: When you reach this point, show your work to the TA.untrace(experimentSet1D); #Turn off debugging
<Text-field style="Heading 2" layout="Heading 2">Problem 2(c): Generating the Results</Text-field>Okay, now you're clear to generate the list for N=100 up to N=T. At this point your team has two choices:
a) Pick one person and run it all. We outline the work for this below. But look at alternative b) below.
Let's keep track of how close your timing estimate is to what actually happens. Just execute the following script:
M := 500; # givenInsert your choice of T here:T := ????; # given (incomplete)# ... given ...start_time := time();results := experimentSet1D(M, flipper, 100, T);finish_time := time();elapsed_time := (finish_time - start_time) * seconds;b) Use multiple computers to collect the results. The experimentSet1D procedure is designed to allow you to run different portions of the result collection on different machines. For example, suppose you have picked T = 10000. Then on the first computer, you could do:
results1 := experimentSet1D(M, flipper, 100, 5000);
On the second
results2 := experimentSet1D(M, flipper, 5100, 8000);
and on the third
results3 := experimentSet1D(M, flipper, 8100, 10000);
(The reason why we don't split the results more evenly is that the bigger walks take longer, so we want the computers handling the short walks to do more proportionately.
Once the results have been computed, then collect them back onto one computer (email works fine), paste the individual results into the master worksheet, and do
results := results1, results2, results3;Checkpoint: When you reach this point, show your work to the TA.
<Text-field style="Heading 2" layout="Heading 2">Problem 2(d): Visualizing the Results</Text-field>First, let's plot the results. Load the plots package and then use the pointplot command to plot the sequence of points you stored in results. Save the plot to the variable resultplot for later use.Hint: Convert your sequence results into a list by enclosing it in the appropriate kind of brackets.There seems to be a rough relationship between the number of steps N and the RMS averages. It doesn't seem to be linear, but what else could it be? We can try a log-log plot. For those of you who haven't seen these in high school, instead of plotting (x,y), we will plot (log x, log y). If there are any power relationships between x and y (e.g. LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2JVEieUYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JKG1mZW5jZWRHRiQ2JC1GIzYkLUYsNiVRInhGJ0YvRjIvRjNRJ25vcm1hbEYnRj0tSSNtb0dGJDYtUSJ+RidGPS8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdGRS8lKXN0cmV0Y2h5R0ZFLyUqc3ltbWV0cmljR0ZFLyUobGFyZ2VvcEdGRS8lLm1vdmFibGVsaW1pdHNHRkUvJSdhY2NlbnRHRkUvJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR0ZULUZANi1RIj1GJ0Y9RkNGRkZIRkpGTEZORlAvRlNRLDAuMjc3Nzc3OGVtRicvRlZGZW5GPy1JJW1zdXBHRiQ2JUY6LUYjNiQtSSNtbkdGJDYkUSIyRidGPUY9LyUxc3VwZXJzY3JpcHRzaGlmdEdRIjBGJy1GLDYjUSFGJ0Y9) they show up on the log-log plot as a straight line. Maple does have a loglogplot command, so we'll demonstrate that for you now:loglogplot([results], style=point, labels=["log of N","log of RMS averages"]); # givenThat looks pretty linear! There seems to be some kind of power relationship between the number of steps N and the RMS average distance LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEickYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= from the origin after LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYkLUkjbWlHRiQ2JVEiTkYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy9GM1Enbm9ybWFsRic= steps.
<Text-field style="Heading 2" layout="Heading 2">Problem 2(e): Finding the Mathematical Relationship</Text-field>Here's the plan for finding the relationship:
a) from results, compute a new log-log sequence. Call it logresults. As an example, if results is LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkobWZlbmNlZEdGJDYmLUYjNiYtSSNtbkdGJDYkUSQxMDBGJy8lLG1hdGh2YXJpYW50R1Enbm9ybWFsRictSSNtb0dGJDYtUSIsRidGNC8lJmZlbmNlR1EmZmFsc2VGJy8lKnNlcGFyYXRvckdRJXRydWVGJy8lKXN0cmV0Y2h5R0Y9LyUqc3ltbWV0cmljR0Y9LyUobGFyZ2VvcEdGPS8lLm1vdmFibGVsaW1pdHNHRj0vJSdhY2NlbnRHRj0vJSdsc3BhY2VHUSYwLjBlbUYnLyUncnNwYWNlR1EsMC4zMzMzMzMzZW1GJy1GMTYkUSw5LjQ4MzAzNzQ4OEYnRjRGNEY0LyUlb3BlbkdRIltGJy8lJmNsb3NlR1EiXUYnRjctRiw2Ji1GIzYmLUYxNiRRJDIwMEYnRjRGNy1GMTYkUSwxMy41MzM5NTcyOUYnRjRGNEY0RlRGV0Y0 then logresults will be LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYvLUkobWZlbmNlZEdGJDYmLUYjNiYtSSNtbkdGJDYkUSw0LjYwNTE3MDE4NkYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy1JI21vR0YkNi1RIixGJ0Y0LyUmZmVuY2VHUSZmYWxzZUYnLyUqc2VwYXJhdG9yR1EldHJ1ZUYnLyUpc3RyZXRjaHlHRj0vJSpzeW1tZXRyaWNHRj0vJShsYXJnZW9wR0Y9LyUubW92YWJsZWxpbWl0c0dGPS8lJ2FjY2VudEdGPS8lJ2xzcGFjZUdRJjAuMGVtRicvJSdyc3BhY2VHUSwwLjMzMzMzMzNlbUYnLUYxNiRRLDIuMjQ5NTA0Njc1RidGNEY0RjQvJSVvcGVuR1EiW0YnLyUmY2xvc2VHUSJdRidGNy1GLDYmLUYjNiYtRjE2JFEsNS4yOTgzMTczNjdGJ0Y0RjctRjE2JFEsMi42MDUyMDE4ODJGJ0Y0RjRGNEZURlctRjg2LlEiLkYnLyUwZm9udF9zdHlsZV9uYW1lR1ElVGV4dEYnRjRGOy9GP0Y9RkFGQ0ZFRkdGSUZLL0ZPRk0tSSdtc3BhY2VHRiQ2Ji8lJ2hlaWdodEdRJjAuMGV4RicvJSZ3aWR0aEdRJjAuMGVtRicvJSZkZXB0aEdGW3AvJSpsaW5lYnJlYWtHUShuZXdsaW5lRictRjg2LlEifkYnRmFvRjRGO0Zkb0ZBRkNGRUZHRklGS0Zlb0Zmb0ZkcC1JI21pR0YkNiZRImJGJy8lJ2l0YWxpY0dGQEZhby9GNVEnaXRhbGljRictRjg2LlEiKUYnRmFvRjQvRjxGQEZkby9GQkZARkNGRUZHRkkvRkxRLDAuMTY2NjY2N2VtRicvRk9GZXFGZHBGZHBGNA==Do a least squares fit on the data in log results. Remember least squares? Use the LeastSquares command from the CurveFitting package to do this easily. The syntax isdependent_variable = LeastSquares ( [logresults] , independent_variable );This will give you a linear relationship between log(N) and log(r):LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYtLUkjbWlHRiQ2JVEkbG9nRicvJSdpdGFsaWNHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy1JKG1mZW5jZWRHRiQ2JC1GIzYkLUYsNiVRInJGJy9GMFEldHJ1ZUYnL0YzUSdpdGFsaWNGJ0YyRjItSSNtb0dGJDYtUSI9RidGMi8lJmZlbmNlR0YxLyUqc2VwYXJhdG9yR0YxLyUpc3RyZXRjaHlHRjEvJSpzeW1tZXRyaWNHRjEvJShsYXJnZW9wR0YxLyUubW92YWJsZWxpbWl0c0dGMS8lJ2FjY2VudEdGMS8lJ2xzcGFjZUdRLDAuMjc3Nzc3OGVtRicvJSdyc3BhY2VHRlUtRiw2JVEiQUYnRj1GPy1GQjYtUSIrRidGMkZFRkdGSUZLRk1GT0ZRL0ZUUSwwLjIyMjIyMjJlbUYnL0ZXRmluLUYsNiVRIkJGJ0Y9Rj8tRkI2LVEnJnNkb3Q7RidGMkZFRkdGSUZLRk1GT0ZRL0ZUUSYwLjBlbUYnL0ZXRmJvRistRjY2JC1GIzYkLUYsNiVRIk5GJ0Y9Rj9GMkYyLUYsNiNRIUYnRjI=.Hint: Use the variables logr and logN as temporary placeholders in your LeastSquares command, and then replace those variables with LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEkbG9nRicvJSdpdGFsaWNHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy1JKG1mZW5jZWRHRiQ2JC1GIzYkLUYsNiVRInJGJy9GMFEldHJ1ZUYnL0YzUSdpdGFsaWNGJ0YyRjJGMg== and LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYlLUkjbWlHRiQ2JVEkbG9nRicvJSdpdGFsaWNHUSZmYWxzZUYnLyUsbWF0aHZhcmlhbnRHUSdub3JtYWxGJy1JKG1mZW5jZWRHRiQ2JC1GIzYkLUYsNiVRIk5GJy9GMFEldHJ1ZUYnL0YzUSdpdGFsaWNGJ0YyRjJGMg== after you get a result.
c) Do the algebra (by Maple or in your head) to get the non-log power relationship between N and r -- the values of a and b such thatLUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYqLUkjbWlHRiQ2JVEickYnLyUnaXRhbGljR1EldHJ1ZUYnLyUsbWF0aHZhcmlhbnRHUSdpdGFsaWNGJy1JI21vR0YkNi1RIn5GJy9GM1Enbm9ybWFsRicvJSZmZW5jZUdRJmZhbHNlRicvJSpzZXBhcmF0b3JHRj0vJSlzdHJldGNoeUdGPS8lKnN5bW1ldHJpY0dGPS8lKGxhcmdlb3BHRj0vJS5tb3ZhYmxlbGltaXRzR0Y9LyUnYWNjZW50R0Y9LyUnbHNwYWNlR1EmMC4wZW1GJy8lJ3JzcGFjZUdGTC1GNjYtUSI9RidGOUY7Rj5GQEZCRkRGRkZIL0ZLUSwwLjI3Nzc3NzhlbUYnL0ZORlNGNS1GLDYlUSJhRidGL0YyLUY2Ni1RJyZzZG90O0YnRjlGO0Y+RkBGQkZERkZGSEZKRk0tSSVtc3VwR0YkNiUtRiw2JVEiTkYnRi9GMi1GIzYkLUYsNiVRImJGJ0YvRjJGOS8lMXN1cGVyc2NyaXB0c2hpZnRHUSIwRidGOQ==.d) Given that this is all experimental data, the relationship you've found is only an approximation of whatever underlying physical or mathematical laws are driving this phenomenon. What is your best guess about what the real relationship between N and r? Plot your best guess and your original results together to check your guess.Solution.a)b)c)d)Checkpoint: When you reach this point, show your work to the TA.
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[102,0,102]">Problem 3 (Optional): Studying the Behavior of Two-Dimensional Random Walks</Font></Text-field>Now it's time to turn our attention to two dimension. Here's the program to simulate a random walk in two dimensions based on what you did in the random walk lab from last term (CS 121 Lab 5). It outputs the final location.a2DRandomWalk := proc(N, directionSelector)
#N is the total number of steps in the walk
#directionSelector is a random number generator that calculates a number from 1 to 4
local j, newLocation, currentLocation,direction;
# initialize numSteps := N;
currentLocation := [0,0];
for j from 1 to N do
direction := directionSelector();
if direction= 1 then
newLocation := [currentLocation[1]+1,currentLocation[2]]; #take a step east
elif direction=2 then
newLocation := [currentLocation[1]-1, currentLocation[2]]; #take a step west
elif direction=3 then newLocation := [currentLocation[1], currentLocation[2]+1]; #take a step north elif direction=4 then newLocation := [currentLocation[1], currentLocation[2]-1]; #take a step south end if;
currentLocation := newLocation;
end do;
end:Let's test it a little to see that it is working okay.trace(a2DRandomWalk);dirProc := rand(1..4);a2DRandomWalk(5,dirProc);Check: Is the output a list of two numbers? Are the sum of the absolute value of the numbers less than or equal to N?
<Text-field style="Heading 2" layout="Heading 2">RMS Average for Two Dimensions</Text-field>Referring to the definition given in Tutorial 2(a), define the RMS average procedure for two dimensions. Define RMSAverage2 here.RMSAverage2 := proc(L)
end:Here are some tests.RMSAverage2( [ [0,0], [1,1] ]); #Should be 1RMSAverage2( [ [1,1], [1,1], [1,1] ]);#Should be sqrt(2)evalf(RMSAverage2([ [ 5,0], [0,1], [1,1] ])); #should be about 3.1The problem: for a 2 dimensional random walk, you want to determine the relationship between N the number of steps, and r, the RMS average of the distance from the origin after N steps. Use 500 trials to compute each average. Since this walk is a bit more computationally expensive, allocate five minutes of computation time (instead of three) for collection of the results.Suggested approach: have your group decide what is needed to convert the 1D work into 2D. Write a little summary of your conclusions and show it to the TA before you proceed.
Checkpoint: When you reach this point, show your work to the TA.experiment2D := proc(N, directionSelector, M)
end;A test for experiment2D.dirProc := rand(1..4);trace(experiment2D);evalf(experiment2D(5,dirProc,3)); #Average over 3 trials of five steps eachCheck: Do the intermediate results look like a step is being taken each move? Do you have 3 walks at the end? Does each result produce a list of two integers <= N? Is the final result <= N?experimentSet2D := proc(M,directionSelector,low, high)
end;Test for experimentSet2D.trace(experimentSet2D);untrace(experiment2D); untrace(a2DRandomWalk); #Turn on debugging for procedure you just wrote.evalf(experiment2D(100,flipper,500)); #Does experiment2D still work? Should produce a numberexperimentSet2D (500, flipper, 100, 200); #Should produce a sequence with data for N=100 and N=200.untrace(experimentSet2D); #Turn off debuggingHere is a slightly longer test, just in case you still have doubts.trace(experimentSet2D);untrace(experiment2D); #Turn on debugging for procedure you just wrote.evalf(experiment2D(100,flipper,500)); #Does experiment1D still work? Should produce a numberexperimentSet2D (500, flipper, 100, 1000); #Should produce a sequence with data for N=100, 200, 300, up to 1000.untrace(experimentSet2D); #Turn off debuggingEstimate run times.N := 100; M := 500; #Compute average of 500 random walks of 100 steps each.Let's try a bigger run:N := 2000; M := 500; #Compute average of 500 random walks of 2000 steps each.Here's an even bigger run:N := 4000; M := 500; #Compute average of 500 random walks of 4000 steps each.Estimate value of LUklbXJvd0c2Iy9JK21vZHVsZW5hbWVHNiJJLFR5cGVzZXR0aW5nR0koX3N5c2xpYkdGJzYmLUkjbWlHRiQ2J1EiVEYnLyUlYm9sZEdRJXRydWVGJy8lJ2l0YWxpY0dGMS8lLG1hdGh2YXJpYW50R1EsYm9sZC1pdGFsaWNGJy8lK2ZvbnR3ZWlnaHRHUSVib2xkRidGLy9GNUY5Rjc=.Run two-dimensional experiments to generate and collect results.M := 500;T := ????;Plot results of experiments.Convert results to log-log form.Do least-squares curve fitting to log-log data to derive mathematical relationship.Create plot of supposed relationship superimposed with data.Checkpoint: When you reach this point, show your work to the TA.
<Text-field style="Heading 1" layout="Heading 1"><Font foreground="[0,51,204]">Wrap-Up</Font></Text-field>To wrap up this lab, take a moment to reflect on what you've learned. Let's also identify what you'll need to know for the follow-up quiz.
<Text-field style="Heading 2" layout="Heading 2"><Font foreground="[0,0,153]">Summary and Conclusions</Font></Text-field>What you've just done. In this lab, we performed computational experiments through simulation, along with the analysis of the experimental data. The simulation we were using, of a random walk, obviously had a lot of random behavior built into it. While not everything is "totally random" as it was here, there are plenty of simulations tied to more concrete situations -- situations involving radioactive decay, rainfall, or arrival times of cars in a highway -- where randomness is present. Usually it's just a matter of how much and where, not if.
Because the things we were measuring (distance from the origin) were subject to random fluctuation, we needed to do a kind of averaging (RMS averaging) over measurements taken over many experiments. It took a bit of computer time, but eventually we found that the data made a compelling case for a relationship between the distance (on average) and the number of steps. Using Maple's ability to do curve fitting and to crunch formulas, we were able to complete the investigation in a few Maple commands once we have a firm notion of what kind of relationship we were looking for.
Getting to this discovery on the computer was a lot cheaper and faster compared to what we would have to do with physical modeling of the process -- hiring a person flipping a coin to move around, and taking measurements of the final position. Furthermore, with knowledge of programming we can more easily alter the program to model a slightly different situation. For example, we could ask the question: "What would the average distance be like if the probability of moving left were 2/3 and right only 1/3". We could investigate that by changing the programming a bit, but much of the activity could directed by the scripts we have already developed.
The appeal of computational simulation. We can collect and analyze the data on the same device. It is typically much cheaper and faster to develop the program than to build a physical model; it doesn't replace physical testing, but both need to be used in a cost-effective way. If the model and the programming are good then the results are believable. And it is much easier to explore "what if" engineering scenarios in a computer model than a physical model because of the low cost of changing the computer program. Of course, this presumes that someone knows enough about programming to do the changes!
"Professional" computational simulation. We are not suggesting that interactive systems such as "the 3Ms" (Maple, Mathematica, MATLAB) are the ultimate tool to use for computational simulation. There are performance limitations to all interactive systems. Typically experienced engineering investigators who want execution on giant sized versions of a problem (e.g. an experiment involving random walks of 100,000,000 steps) will first develop a version of the simulation on an interactive system to prove its value and correctness, because it is probably the fastest way of getting something working to the demonstration point. And, as you have seen, it usually works fast enough for making some useful discoveries.
If the performance on the interactive system is not enough, then the computational explorer would at least have an understanding of what they want out of the simulation, and have notions about how much extra performance they need. A professional would then use their programming expertise (which, if it is true expertise, works across multiple languages) and program the simulation in a language such as C, C++, or FORTRAN (sorry, Java doesn't cut it at the present state of the art). The C version would probably look very similar to the Maple (Mathematica, MATLAB, etc.) version. They would run such a program on a high performance computer that can crunch the simulation with the power of dozens, hundreds or even thousands of processors working on pieces in parallel -- a highly automated and expanded version of what your team did if it split up the work for this lab by running pieces of the experiment on different machines.
The software engineers who designed Maple realize that Maple does not exist on its own; it needs to relate to computations written in other languages. The Maple library has facilities for automatically translating Maple programs into computer languages such as C or FORTRAN (to read more about this, read the Maple help pages on ?CodeGeneration[C] or ?CodeGeneration[Fortran]) . Furthermore, Maple has ways of including a user's C, C++, or FORTRAN program in Maple itself (see the Maple help page on ?define_external). Thus you can use Maple's built-in features for "big math", quick scripting, and visualization with programs written in other languages.
<Text-field style="Heading 2" layout="Heading 2"><Font foreground="[0,0,153]">What Do I Need to Know for the Quiz?</Font></Text-field>Be able to read simple Maple procedures, understand what they are doing well enough to plan and implement modest changes in their behavior.Know the definition of the RMS average, be able to calculate RMS average distances in the one- and two-dimensional cases.In general, be able to write a Maple procedure to calculate a function given a simple mathematical formula for the definition.Do curve fitting from data for a power relationship through log-log transformations.Be able to articulate the typical steps in an investigation based on experiments involving a computer simulation.Be able to determine the amount of time the amount of computer time needed to perform a series of Maple calculations.Manipulate sequences and lists (create, combine, apply functions element-wise).CS 122 Lab 3 for Spring 2008