This module involves more doing than reading or listening. The assignments are more difficult than those in some other modules but the assignment is not due until late in the course. By presenting it early in the course, you have an opportunity to see what techniques from later modules might be useful and more time to work on it. The primary purpose is to introduce you to the very basic elements of simulation and construct a few simple spreadsheet simulations. Many students like this module as it is rather like solving puzzles. 

Simulation is an extremely broad topic and typically makes up an entire course or even a sequence of courses in an operations research, industrial engineering, or computer science curriculum. We are not going to get too serious with it, just learn a few new concepts, sharpen your spreadsheet skills, and have some fun. 

What is simulation?

Simulation in general is pretending that one deals with a real thing while really working with an imitation. In operations research the imitation is a computer model of the simulated reality. A flight simulator on a PC is a computer model simulation of some aspects of a flight: it shows on the screen, the controls, and what the "pilot" (the person who operates it) is supposed to see from the "cockpit" (his armchair). 

Why to use models?

To fly a simulator is safer and cheaper than the real airplane. For precisely this reason models are used in industry, commerce, and the military. It is very costly, dangerous, or often impossible to make experiments with real systems (nuclear explosions). Simulation may be an effective alternative provided that the models are adequate descriptions of reality, and experimenting with them can save money, suffering and even time. 

When to use simulations?

Systems which change with time such as a gas station where cars come and go (called dynamic systems) and involve randomness (nobody can guess at exactly which time the next car should arrive at the station) are good candidates to simulation. Modeling some complex dynamic systems mathematically may require too many simplifications and the emerging models may not be valid. Simulation of the system may not require that many simplifying assumptions, making it one of the few tools available.

Types of simulations:

Discrete event simulations. These attempt to describe systems that are assumed to change instantaneously in response to certain discrete occurrences. Arrivals and departures of cars at a toll booth is an example of discrete events. 

Continuous. In some systems the state changes all the time, not just at time of some discrete events. For example water level in a reservoir with a given inflow and outflow may change all the time. In such cases continuous simulation is more appropriate, although discrete event simulation can serve as an approximation. 

How simulations are performed?

Simulations may be performed manually. More often, however, the system model is written either as a computer code or as some kind of input into a simulator software. 

Software for simulation

Simulation may be carried out on a spreadsheet, by running a computer program written in some general language (such as C++), by running a computer program written in some special language for simulations, or by running specially built simulators with appropriate input. 

Simulation with spreadsheets is the most primitive form. Spreadsheets can be used for small simulations quite effectively. They are laborious and slow however. Their usefulness can be improved considerably by including macros and Visual Basic code. The use of macros will be introduced in this course. 

Simulation written in some general language. This is the most flexible method and according to some authors the most often chosen, too. This is probably the best method if the simulation is just one component of a larger system or when there is a considerable amount of data processing involved. The problem here is that writing a simulation from scratch may be a lengthy undertaking. However, with a good simulation library and a skeleton program the necessary investment can be reduced to minimal. 

Simulation written in some special language for simulations. There are many special languages for simulations. The disadvantage is that if the problem does not fall exactly in the category that these languages were designed for, it is very difficult, if not impossible, to write a suitable program. 

Special purpose simulators are the most inflexible programs: They work only for a narrow field and even there they cannot deal with all tasks, but only those for which they are destined.

In this course we will look at Monte Carlo simulation (this module) and discrete-events simulations in the Queuing Module using Excel.

Monte Carlo Method

The expression "Monte Carlo method" is actually very general. Monte Carlo (MC) methods are stochastic techniques--meaning they are based on the use of random numbers and probability statistics to investigate problems. You can find MC methods used in everything from economics to nuclear physics to regulating the flow of traffic. Of course the way they are applied varies widely from field to field, and there are dozens of subsets of MC even within a single field. But, strictly speaking, to call something a "Monte Carlo" experiment, all you need to do is use random numbers to examine some problem. 

The use of MC methods to model physical problems allows us to examine more complex systems than we could otherwise. Solving equations which describe the interactions between two atoms is fairly simple; solving the same equations for hundreds or thousands of atoms is impossible. With MC methods, a large system can be sampled in a number of random configurations, and that data can be used to describe the system as a whole. 

The first real use of a Monte Carlo calculation was probably during the Manhattan Project (if you don't know what that was, find out!), where very complex equations that could not be attacked with traditional methods had to be solved. The Monte Carlo technique is now used in virtually all areas of science and engineering where problems are too difficult or complex to be addressed with other methods. 

Some of the problems in the assignments will require the use of random numbers, hence, the Monte Carlo Method 

More information can be found at History of Monte Carlo Method and other similar sites on the net. 

So much for discussion - how do we do one.

Example 1

Let's simulate tossing a coin, specifically, a fair coin. 

For this example we will use the =rand function in Excel. If you type =rand() into a cell the computer will return a decimal between 0 and 1. The decimals go out to approximately 15 decimal places. Theoretically, each decimal is equally likely to occur, hence, random number.

Aside - In years past, the process of generating random numbers was a discipline unto itself. Many techniques were developed to generate truly random numbers, as were statistical techniques to "prove" their randomness. In reality, computer generated numbers may not be truly random and may be considered "pseudorandom". For our purposes, we will accept sequences of numbers generated by Excel as random.

We can use the =if statement to help count the results. In cell A1, type =if(rand()>.5,1,0). This function generates a random number. If the number is greater than .5, a "1" is put into the cell, otherwise a "0" is put into the cell. (Review the =if function in Excel Help if you need to.) Let 1 be a head and 0 be a tail. Copy A1 to A2:A1000. This will simulate 1000 tosses of a fair coin. The 1's and 0's make it easy to tabulate the results - simply put =sum(A1:A1000) into cell B1 and you will have the number of heads rolled in 1000 experiments readily available. 

A nice feature of Excel is the ability to control when it recalculates. Go to Tools-Options-Calculate tab and select the button for Manual. Now you have to press F9 to get any formula calculations. (This feature is especially handy when you are building large spreadsheets having many calculations.) Press F9 and watch the value in B1 change. With each press you are simulating tossing a coin 1000 time. It is not too difficult to include a few more formulas to keep a running total and a count of how many coin tosses you have made. You will actually find out how difficult or easy it is in your assignment for this module. 

As we build models there are some basic questions you should continually ask. 

The rest is just practice and fun.

Assignments:

All of these assignments can be completed using basic Excel formulas and functions. No macros, loops, etc. are necessary but their inclusion may make things easier. Creativity, ingenuity, and cleverness are the keys. I hope you look upon these as enjoyable puzzles and games and have fun trying to make the models. If it becomes too stressful, let me know. Be careful - some students become obsessed and neglect studies, work, home life, sleep, etc. If you want to use VBA, macros, or other advanced tools, feel free. Note: This is probably the most difficult module to get an A on. A good strategy is to complete the assignments up to the B level now then complete additional assignments for higher grades as you learn more Excel intricacies.

For a maximum grade of B-

1. Roll a pair of dice many times (you decide what "many" is). Construct a histogram that compares your results with the theoretical probabilities of how frequently each value (2 through 12) appears. A relative frequency histogram is appropriate. To "roll" one die, use the formula =int(rand()*6)+1. Do you see how this works?

2. Develop a spreadsheet(s) that accomplishes the counting and recordkeeping as shown in the workbook, counter.xls. Download the Excel file here.

For a maximum grade of B

1. Complete the B- grade assignment. 

2. Construct a simulation of the dice game called " Craps". Click on "Craps" for more instructions. For this grade level, turn in a basic, working model and compute the probability of winning in your model and compare it to the theoretical probability. This model can be troublesome. I will provide more hints after you struggle with it for a while. The counters you developed in the B- level assignment may be helpful.

For a higher grade, complete the B grade assignment then complete any one of the following for a maximum grade of B+, any two for a maximum grade of A-, and all three for a maximum grade of A

1. Use your Craps model to answer the following questions.

1. How many "turns" do you think is enough to gain "adequate" accuracy of the true probability? Defend your definition of "adequate".
2. What is your expected loss during a given session? (Assume 30 $2 bets per hour, and let a "session" be 12 hours of betting on a weekend.)
3. How variable is your cash flow? (Hint: Graph and compare cash flow for several weekends and/or conduct a statistical analysis of a series of weekends.)
4. How much of a bankroll would you need to be 90% certain that you would have enough stake to last a weekend?

2. A classic Monte Carlo simulation problem involves weapons delivery on a target. For this simulation you will study a cruise missile attack on an irregularly shaped factory complex . If a cruise missile impacts anywhere within the complex boundary, it is scored as a hit; otherwise, it is a miss. The missiles are aimed at the center of the complex and fly in directly from the south (bottom). The distribution of their impacts is normal with a standard deviation of 500 ft along the axis of attack and a standard deviation of 400 ft perpendicular to the axis of attack. Your assignment, should you accept it, is to conduct a simulation to determine the probability of any one missile hitting the factory.
Note 1: While the random number generator in Excel is ok, it is quite slow. A better way is to use =norminv(rand(),m,s). This will generate normally distributed random variables with mean m and standard deviation s. Take some time to understand how it works.
Note 2: We will be using the normal distribution in several other modules. You may have to dust off your old statistics text and review the associated concepts.

3. Construct and run a simulation for the John Conway's Game of Life. Click on the John Conway's Game of Life for rules. The game itself can be addictive - you can read more about it at theGame of Life Page. There is a nifty Java applet at Conway's Game of Life. Hint: Depending on your approach, your model may require several "game boards" and/or worksheets because of the order calculations must take place. Also, since the Game of Life rules specify that the state of all cells is determined simultaneously, you must provide for this in your simulation. Find a small Java simulation on the web and use it to compare yours to; this way you will know yours is working properly. There is a pretty good one here.

Oh, by the way, Good Luck!