Simulation

1. Intro

A simulation is an attempt to mimic the real world using analytical methodology. They are ideal to forecast systems where the true relationship is too difficult to estimate or the system is easily modeled. Simulations are not necessarily alternatives to heuristic rules and statistical techniques but an alternative method for forecasting using those techniques.  To build a simulation model you may have to rely on either statistics and/or heuristics to build the core logic. Alternatively, you could use theoretical models as the core of your simulation. Simulations are powerful predictive tools as well as useful for running what-if scenarios. Example simulation models:

a) Supply and Demand

b) Queuing models, prisons, phone,…

c) Factory floor

2. Monte Carlo Simulations

Monte Carlo simulations are stochastic models. They simulate the real world by assuming it is a random or stochastic process.

a. Random Number Generators

Most of the time we do not have truly random numbers but pseudo-random numbers typically generated from the date and time the number was created. These random numbers are drawn from a uniform distribution.

One way to generate a random number drawn from a particular distribution is to calculate the probability density function (PDF) for the random variable then using a random number from a uniform distribution as the probability of that random number. In cases where we cannot easily use the PDF often times a simple algorithm will work.

b. Markov Chains

A Markov chain is a sequence of random numbers that are independent of one another. A classic example of a Markov chain is a random walk. A random walk, or drunkard s walk, is when, if walking each successive step is in a random direction. Studying Markov chains is not an excuse to hang out in bars more often; a real drunk has an intended direction but impaired capacity for executing their intension.

c. Example Model (Queuing)

1) Intro

Queuing models have one or more servers that process either people or items. If a server cannot instantaneously process people and if more then one person arrives a line forms behind the server.

2) Open Jackson Network Queuing

1. Arrival follows a Poisson process

2. Service time is independent and exponentially distributed

3. Probability of complete one node and going onto another is independent

4. Is open so can re-enter the system

5. Assume an infinite number of servers.

Note: Use an Erlang instead of Poisson distribution when you have a finite number of servers.

Simulation Example

This month we are going to take a stab at programming a simple queuing model in JavaScript.  First, why JavaScript and not R or SAS?  JavaScript is a good language to use for programming examples because nearly anyone with a computer and browser can play around with it. Another good reason is that while JavaScript is not JAVA it is very similar to JAVA and to other languages such as C++ and C#.  Learning JavaScript will help you in coding in those languages as well.

The model:

We are going to code a very simple queuing model. For this simulation we are going to assume a single server (where the people are processed), that people arrive following a Poisson distribution and the service time is a random number with an exponential distribution.

See the code running here: example simple queuing model.

<HTML>
<!–
Code was written by Ted Harris, Dec 2007 for Analyticalway.com
Questions and comments to: questionandcomments@analyticalway.com
–>
<HEAD>
<script type= text/javascript >

/*
First, we need to decide which distribution to use fro the arrival and service rates. Assuming a Poisson distribution for arrival times leads to an arrival rate generated from an exponential function. For service time we can also assume an exponential function.
Generating random number from an exponential functions is easy. We just need to solve: f(x) = -exp^alpha*x for x giving us: x = (-1/alpha) *log(f(x) ). Generate f(x) from a uniform distribution and you are done.
*/

function exponential(intAlpha)
{
var intR = Math.random();
var intX = (-1/intAlpha) * Math.log(intR);
return Math.round(intX);
}

/* Here is the core to the code that runs the simuation.*/
function runsim ()
{

/*First we declare dynamic arrays to hold our cases and results. */
var aryCases = new Array();
var aryResults = new Array();
var intTotCases= 100; /* The total number of cases you want to simulate.. */
var fltArrival = .5; /* This variables sets the average arrival rate. */
var fltWait = .5; /* This sets the average wait time, */
/* Next we populate the arrival and wait times for each case. */

for (i = 0; i < intTotCases; i++)
{
aryCases[aryCases.length] = new Array(i, exponential(fltArrival) ,exponential(fltWait) );
}

/*
Since we are assuming one server and one queue this is a relatively simple set up. That is dependant on the first case.
Now we can set the arrival and departure time for the first case. This on is simple:
Arrival = Exponential random number
Departure = Arrival + Exponential random number.
*/

aryResults[aryResults.length] = new Array(1, aryCases[0][1] , aryCases[0][1] + aryCases[0][2] ,aryCases[0][1] ,aryCases[0][2] );

/*
Now we set the arrival and departure times for the rest of the cases.
Arrival = Arrival time of previous queue member + Exponential random number
Departure = maxiumn value between Arrival + Exponential random number and exit time of previous queue memeber + Exponential random number .
*/

for (i = 1; i < aryCases.length; i++)
{
aryResults[aryResults.length] = new Array(i, aryResults[i-1][1]+ aryCases[i][1] , Math.max( (aryResults[i-1][1]+ aryCases[i][1]+ aryCases[i][2]) , (aryResults[i-1][2]+ aryCases[i][2]) ) );
}

/* Now write the results to the webpage.
writeresults(aryResults);
}

/* This function write the results. */
function writeresults( aryResults )
{

/*First, find the target object in the document (webpage) to over-write. */
var objParent= document.getElementById( results );
/* Create a new version of that object to be replaced.*/
var objNewParent = document.createElement( span );
/* Set the object ID to match that of the object we are replacing.*/
objNewParent.id = objParent.id;
/*Replace the object with our new object which has our new results writen to it. */
objParent.parentNode.replaceChild(objNewParent,objParent);
/*Now, clear out any child objects (content) associated with the old parent . */
while (objParent.firstChild)
{
objParent.removeChild(objParent.firstChild);
};

/* Write the header to the output.*/
objNewParent.innerHTML += <p> Arrives , Departs </p> ;
/*Now, loop through the results table and write the contents to the new span we ahev created, */
for (i = 0; i < aryResults.length; i++)
{
objNewParent.innerHTML += <p> + aryResults[i][1] + , + aryResults[i][2] + </p> ;
}
}
</script>

</HEAD>
</BODY>

<!– Create a button with an onclick event to run the code.–>
<button onclick = runsim(); > Run simulation </button>
<!– Add a break to make the code look a little better–>

<br>
<!– Create a span to write the output to. It is important to set the id for the span so JAVAScript can find it latter. –>
<span id = results >
</span >
<BODY>
</HTML>

Now you can play around with parameter and copy paste the output to Excel to do further research. In some version of Excel the columns will not be properly placed.  To correct for this copy paste the output to a text document then change the file extension to csv.  Excel should now open the file correctly. One fun thing to do is slowly increase the time to be served while keeping the arrival rate constant and watch how quickly the average wait time increases.

Further Reading:
http://members.aol.com/iandjmsmith/EXAMPLES.HTM
http://www.ciphersbyritter.com/JAVASCRP/NORMCHIK.HTM#Normal