MIT OpenCourseWare http://ocw.mit.edu 6.00 Introduction to Computer Science and Programming, Fall 2008 Please use the following citation format: Eric Grimson and John Guttag, 6.00 Introduction to Computer Science and Programming, Fall 2008. (Massachusetts Institute of Technology: MIT OpenCourseWare). http://ocw.mit.edu (accessed MM DD, YYYY). License: Creative Commons Attribution-Noncommercial-Share Alike. Note: Please use the actual date you accessed this material in your citation. For more information about citing these materials or our Terms of Use, visit: http://ocw.mit.edu/termsMIT OpenCourseWare http://ocw.mit.edu 6.00 Introduction to Computer Science and Programming, Fall 2008 Transcript – Lecture 20 OPERATOR: The following content is provided under a Creative Commons license. Your support will help MIT OpenCourseWare continue to offer high quality educational resources for free. To make a donation, or view additional material from hundreds of MIT courses, visit MIT OpenCourseWare at ocw.mit.edu. PROFESSOR: All right, so today we're returning to simulations. And I'm going to do at first, a little bit more abstractly, and then come back to some details. So they're different ways to classify simulation models. The first is whether it's stochastic or deterministic. And the difference here is in a deterministic simulation, you should get the same result every time you run it. And there's a lot of uses we'll see for deterministic simulations. And then there's stochastic simulations, where the answer will differ from run to run because there's an element of randomness in it. So here if you run it again and again you get the same outcome every time, here you may not. So, for example, the problem set that's due today -- is that a stochastic or deterministic simulation? Somebody? Stochastic, exactly. And that's what we're going to focus on in this class, because one of the interesting questions we'll see about stochastic simulations is, how often do have to run them before you believe the answer? And that turns out to be a very important issue. You run it once, you get an answer, you can't take it to the bank. Because the next time you run it, you may get a completely different answer. So that will get us a little bit into the whole issue of statistical analysis. Another interesting dichotomy is static vs dynamic. We'll look at both, but will spend more time on dynamic models. So the issue -- it's not my phone. If it's your mother, you could feel free to take it, otherwise -- OK, no problem. Inevitable. In a dynamic situation, time plays a role. And you look at how things evolve over time. In a static simulation, there is no issue with time. We'll be looking at both, but most of the time we'll be focusing on dynamic ones. So an example of this kind of thing would be a queuing network model. This is one of the most popular and important kinds of dynamic simulations. Where you try and look at how queues, a fancy word for lines, evolve over time. So for example, people who are trying to decide how many lanes should be in a highway, or how far apart the exits should be, or what should the ratio of Fast Lane tolls to manually staffed tolls should be. All use queuing networks to try and answer that question. And we'll look at some examples of these later because they are very important. Particularly for things related to scheduling and planning. A third dichotomy is discrete vs continuous. Imagine, for example, trying to analyze the flow of traffic along the highway. One way to do it, is to try and have a simulation which models each vehicle. That would be a discrete simulation, because you've got different parts. Alternatively, you might decide to treat traffic as a flow, kind of like water flowing through things, where changes in the flow can be described by differential equations. That would lead to a continuous model. Another example is, a lot of effort has gone into analyzing the way blood flows through the human body. You can try and model it discretely, where you take each red blood cell, eachwhite blood cell, and look at how they move, or simulate how they move. Or you could treat it continuously and say, well, we're just going to treat blood as a fluid, not made up of discrete components, and write some equations to model how that fluid goes through and then simulate that. In this course, we're going to be focusing mostly on discrete simulations. Now if we think about the random walk we looked at, indeed it was stochastic, dynamic, and discrete. The random walk was an example of what's called a Monte Carlo simulation. This term was coined there. Anyone know what that is? Anyone want to guess? It's the casino, in Monaco, in Monte Carlo. It was at one time, before there was even a Las Vegas, the most famous casino in the world certainly. Still one of the more opulent ones as you can see. And unlike Las Vegas, it's real opulence, as opposed to faux opulence. And this term Monte Carlo simulation, was coined by Ulam and Metropolis, two mathematicians, back in 1949, in reference to the fact that at Monte Carlos, people bet on roulette wheels, and cards on a table, games of chance, where there was randomness, and things are discrete, in some sense. And they decided, well, this is just like gambling, and so they called them Monte Carlos simulations. What Is it that makes this approach work? And, in some sense, I won't go into a lot of the math, but I would like to get some concepts across. This is an application of what are called inferential statistics. You have some sample size, some number of points, and from that you try to infer something more general. We always depend upon one property when we do this. And that property is that, a randomly chosen sample tends to exhibit the same properties as the population from which it is drawn. So you take a population of anything, red balls and black balls, or students, or steps, and at random draw some sample, and you assume that that sample has properties similar to the entire population. So if I were to go around this room and choose some random sample of you guys and write down your hair color, we would be assuming that the fraction of you with blonde hair in that sample would be the same as the fraction of you with blonde hair in the whole class. That's kind of what this means. And the same would be true of black hair, auburn hair, etc. So consider, for example, flipping a coin. And if I were to flip it some number of times, say 100