Assignments 20% Midterm exam 20% October 18 Simulation Project 30% Final Exam 30%There will be no supplemental exam in this course.
The history of mankind (sic) is a history of model building. Rivett(1972)Building models is central to the way we understand the world around us. We give meaning to our perceptions of the world by fitting them into our mental model of the world. From time to time new experiences may force us to modify our models.
An interesting model of how living organisms respond to their environment is the theory of finite state machines, proposed by biologists in the 1950's. It models an organism as a set of states, stimuli from the environment cause the organism to change state according to a set of transition rules. These rules represent the organism's model of its world. Models upon models! In computer science, the theory of finite state machines is used to model digital electronic circuits and computer programs.
Four phases of modeling as used in simulation are:
If we now wish to experiment with a system, we have several choices:
Many distributions have been proposed for use in simulation, see Law [2]. The most frequently used are
Unfortunately for us, digital circuits are specifically designed to eliminate any random variation, they are completely deterministic. So, a lots of work has been done to produce pseudo-random number generators, deterministic procedures that produce a stream of numbers that look so haphazard that we are unable to predict what the next one will be, and pass statistical tests for randomness (chi-squared, auto- correlation). One popular method is to take two prime constants, A and B, and a seed number, then calculate
seed := A * seed + B
truncating to the number of bits the computer uses for integers, to simulate the ideal coin-flipping. Care and trial and error will lead to a good choice of constants.
Two principles to bear in mind with pseudo-random number streams:
f(t) = a exp(-at)
where a is the mean arrivals per unit time (arrival rate - usually written with the greek letter lambda). The average time between arrivals is 1/a. This is a consequence of the fact that the probability of an arrival in any time period of a given length is constant. Let g(t) be the probability that no arrival occurs in an interval of length t. then for an additional time-slice s:
g(t + s) = g(t) * g(s)
i.e. the probability that nothing arrived during interval t times the probability that no arrival occurs in the time-slice. This leads to a differential equation identical to that of radioactive decay or population growth, whose solution is
F(t) = 1 - g(t) = 1 - exp(-at)
the cdf (cumulative distribution function) which, when differentiated, gives the pdf above. It is the cdf which is used to get a neg-exponentially distributed random number from a uniform one.
An interesting property of the negative exponential distribution is that it is memoryless, that is, the pdf for the next arrival is the same after a period of waiting as it was right after the last arrival. For example, if down time for a computer network is neg-exp. distributed, the mean time until service is restored after a system crash is 1/a. If you walk in during the down time, the mean time of waiting is still 1/a. If after an hour the system is still down, the mean time to restoration is still 1/a! This explains why people find waiting for busses (and computers) so frustrating.
probability of n arrivals P(n,t) = [(at)**n / n!] exp (-at)
This is the Poisson distribution. It also characterizes the likelihood of random scratches on pieces of furniture.
exp(-x²)
With a few constants thrown in. It is characterized by 2 parameters, mean and standard deviation (sigma). It peaks at the mean, and is symmetrical, with width proportional to sigma. 67% of the samples lie within ± 1 sigma of the mean.
The term paradigm has come to be applied to programming styles (e.g. procedural, functional, declarative, and object oriented), and we use it to refer to modeling styles used for simulation, and the cultures and schools that have grown up around these.
In studies of population growth, obviously the population changes by discrete events. Animals are born, they die, or are eaten. However the large picture can be described in terms of birth and death rates, abstracting away from these individual events.
It is also very illustrative to provide an animation of the system with computer graphics (CSc 302!). Unfortunately, in one semester we cannot do everything, and programming animations can be very time consuming.
Examples:
A wide variety of systems can be studied using discrete methods. Most popular are
5 components of any discrete-event simulation are:
For more information, see:
Up to top of this document
Back to
Lin Jensen's home page.
Comments, etc, send to