Due Dates

Unless otherwise specified, Learning Group Assignments should be completed for the next lecture day.

Semester Calendar

,
Date Lecture Title Assignment(s) Lecture & Assignment Goals
Notes
Mon Dec 10 Final Exam

The final exam will be 3:15PM--5:15PM in the lecture hall.

Here is a list of learning goals covered by the final exam. The later portion of the course (since the midterm) may be weighted slightly more then the material beforehand.

Fri Dec 7

Thu Dec 6 Quiz #3 Returned, Grades and Assigned Work Individual Assignment:

Read section 8.3--8.4 of the text which discusses the batch means data grouping of steady state statistics as well as some formal definitions and the notion of transient statistics and simulation horizons.

Be able to distinguish between finite horizon and infinite horizon system statistics.

Be able to distinguish between transient and steady state system statistics.

How does autocorrelation affect the validity of calculating confidence intervals from batch means?

How is the mean of a particular steady state statistic affected by the choice of b and k?

Know the Batch Means Algorithm (8.4.1) and the definitions of variables b and k.

How does interval estimation of batch means statistics infringe upon the assumption of independence?

How does the choice of b and k affect autocorrelation in batch means?

In the context of batch means, how does bk=n relate to the terms replication and ensemble?

Must you decide on b and k before collecting (batch means) steady state statistics? Why or why not?

What is a replication and how is it related to an ensemble?

What is unrealistic about infinite horizon simulations?

Thu Dec 6

Classes end

Tue Dec 4 Quiz 3 Individual Assignment:

Read section 8.3--8.4 of the text which discusses the batch means data grouping of steady state statistics as well as some formal definitions and the notion of transient statistics and simulation horizons.

Be able to distinguish between finite horizon and infinite horizon system statistics.

Be able to distinguish between transient and steady state system statistics.

How does autocorrelation affect the validity of calculating confidence intervals from batch means?

How is the mean of a particular steady state statistic affected by the choice of b and k?

Know the Batch Means Algorithm (8.4.1) and the definitions of variables b and k.

How does interval estimation of batch means statistics infringe upon the assumption of independence?

How does the choice of b and k affect autocorrelation in batch means?

In the context of batch means, how does bk=n relate to the terms replication and ensemble?

Must you decide on b and k before collecting (batch means) steady state statistics? Why or why not?

What is a replication and how is it related to an ensemble?

What is unrealistic about infinite horizon simulations?

Here are the learning goals for the quiz.

Thu Nov 29 Quiz Prep 3 LG Assignment:

lga-quiz-prep-3

Individual Assignment:

ElevatorGaps (due December 6 2018 by 11:59PM). This is no longer a required assignment, if you have worked on it at all, then take a look at the write-up page on the wiki for earning credit for your efforts.

Note that the due date for an alternative submission is TONIGHT!

Know the inversion technique for non-stationary arrival times.

Understand the mechanics of algorithm 8.1.2 which minimizes the number of simulation runs for alpha confidence intervals.

Continuous random variables (variates) slides are here.

Tue Nov 27 Interval Estimation LG Assignment:

lga-interval-estimation

How do you create a confidence interval for a sample mean given the sample variance?

How is the central limit theorem important in the interpretation of simulation results?

What does a confidence interval mean? How would you explain it to your middle-school cousin?

What is a distribution's `idf()`?

Describe an algorithm that will not overrun a simulation for a given statistical result and confidence interval.

How does Monte Carlo estimation represent a special case of confidence interval estimation?

Understand the interprettation and connection between a statistical test with "α=0.05" and a 95% confidence interval.

Understand the mechanics of algorithm 8.1.2 which minimizes the number of simulation runs for alpha confidence intervals.

Appreciate the importance of independence between `Generate()` calls in algorithm 8.1.2. Otherwise all bets are off.

Know the standard meaning of the Central Limit Theorem, how is this connected to the validity of typical "means testing"?

My hope and plan is to open up the last programming assignment (ElevatorGaps) Wednesday evening, stay tuned.

Wed Nov 21 – Fri Nov 23

Thanksgiving Break (no lectures, campus open Wednesday)

Tue Nov 20 Lecture Continued Individual Assignment:

Begin perusing chapter 8, get ElevatorUp (due November 27 2018 by 11:59PM) up to snuff, and have a good break! (Recall there will be one more follow-on assignment to ElevatorUp!)

Know how the naive adaption of the stationary arrival time algorithm fails when substituting λ with λ(t).

Know the inversion technique for non-stationary arrival times.

Know the thinning technique for non-stationary arrival times (what is its downside?)

Understand the general steps taken in proving the general acceptance/rejection algorithm is correct.

Know the setup of f(x), c, and g(x) of the general acceptance/rejection algorithm, how can it be another variate generation technique?

This should wrap up our discussion of continuous random variables and variates.

Previous lecture topic continues.

Fri Nov 16

Last withdraw (all continuing students)

Thu Nov 15 CRV Applications LG Assignment:

lga-crv-applications

Know how to write Monte Carlo simulations for estimating a discrete data histogram of many events.

What is a distribution's `idf()`?

Know what constitutes a histogram and how it is connected to CDFs.

Know that exponential interarrival times yields arrival times that are uniformly distributed.

Know that uniform arrival times and uniform interarrivals are not the same thing.

Understand the general steps taken in proving the general acceptance/rejection algorithm is correct.

In the exponential interarrivals are uniform arrival times, the crux of the proof showed what distribution equations to be equivilant? The pdf, the cdf, or the idf?

Know how to maniuplate and derive CDFs and PDFs of variables that are functions of a Uniform(a,b) input.

Know the Exponential(mu) random variate and the interpretation of its parameter mu in the context of arrival times.

Know the F(x) inversion technique for constructing random variates. What is the requirement on F(x)?

Familiarize yourself with the Triangular CRV and its generation as a variate --- when might the TRV be used?

Know the setup of f(x), c, and g(x) of the general acceptance/rejection algorithm, how can it be another variate generation technique?

Know the two techniques for truncating pre-existing random variates.

Tue Nov 13 Continuous Random Variates LG Assignment:

lga-continuous-random-variates

Know the reservoir sampling algorithm for selecting n random elements from an unkown sized population.

Know the inversion technique for non-stationary arrival times.

Know the relationships between PMF/PDF and CDF for both discrete and continuous distributions.

Know the relationships between PMF/PDF, CDF, and InvDF. How do you derive one from another? Can this always be done?

Know how to maniuplate and derive CDFs and PDFs of variables that are functions of a Uniform(a,b) input.

Know what the construction technique means for random variates (of which summation is one example).

An approximate function for which of f(x), F(x), or the inverse of F(x) is useful in the approximation technique?

Be familiar with the numerical approach (Newton's Method) to random variate generation through the u=F(x).

Familiarize yourself with the Triangular CRV and its generation as a variate --- when might the TRV be used?

Know about the approximation technique for creating random variates --- what is a requirement of the approximating function?

Know the criteria by which variates are judged: portability, efficiency, clarity, syncronicity, ...

Know the difference between a random number and a random variate.

For those of you interested in the CRV relations graph, take a look at the first author... Lecture slides from CRVs...

Thu Nov 8 Sampling Algorithms LG Assignment:

lga-sampling-algorithms

Individual Assignment:

ElevatorUp (due November 27 2018 by 11:59PM).

Know Fisher-Yates shuffling algorithm, be able to apply it to sampling tasks in simulations.

Know Fisher-Yates shuffling algorithm, be able to present a convincing argument of its correctness.

Know the reservoir sampling algorithm for selecting n random elements from an unkown sized population.

Recall casino thieves, be able to write an algorithm that deals deterministic n-player 5-card poker hands

Know the several different properties and attributes of sampling and shuffling algorithms presented in the text.

Know how to write Monte Carlo simulations for estimating a discrete data histogram of many events.

Know how to write Monte Carlo simulations for estimating the Pr(A) of an event A.

Be able to implement a non-trivial DES using next event software architecture.

How is the simulation clock different than the wall clock or an accelerated, virtual clock?

Know the basic algorithm for executing a DES using next event methodology.

Know the two techniques for truncating pre-existing random variates.

Here are the Shuffling and Sampling Slides from lecture.

Tue Nov 6 Discrete Random Variables LG Assignment:

lga-discrete-random-variates

Know how to write Monte Carlo simulations for estimating a discrete data histogram of many events.

Know how to write Monte Carlo simulations for estimating the Pr(A) of an event A.

What are replications in the context of Monte Carlo simulations?

Know the CDF search technique for creating discrete random variates.

Know the F(x) inversion technique for constructing random variates. What is the requirement on F(x)?

Know the three techniques for constructing a discrete random variate.

Know what the construction technique means for random variates (of which summation is one example).

What does the parameter u in random variates represent? Computationally, how do we get a value for u in code?

Know the criteria by which variates are judged: portability, efficiency, clarity, syncronicity, ...

Know the difference between a random number and a random variate.

Know the two techniques for truncating pre-existing random variates.

Know the Geometric(p) random variate, it's parameter p, and it's connection to Exponential(mu)

Slides for discrete random variates.

Thu Nov 1 Quiz 2 Individual Assignment:

Assignment for Tuesday Nov 6: correct any flaws to your lga-nes-better-eventlists code (students stop thinking at 60 minutes (sorry `:(`). Come to lecture with your 120m N.

Here are the learning goals for the quiz.

Tue Oct 30 Quiz Prep 2 LG Assignment:

lga-quiz-prep-2

If the full tree is stored in an array (heap), Henriksen's algorithm can make lowest priority ENQUEUE O(1), how?

A Henriksen's tree-list hybrid structure uses what property of NES to improve DEQUEUE O(n) ?

What are the O(n) of ENQUEUE, DEQUEUE, SEARCH, DELETE of priority queue structures (heaps) and balanced trees?

Lecture slides for "better" event list management.

Thu Oct 25 NES Better Event Lists LG Assignment:

lga-nes-better-eventlists

Appreciate the performance increase that advance Event List data structures provide.

Cite pros and cons for at least two "pure" event list data structures commonly used for event list management.

Cite pros and cons for at least two hybrid data structures commonly used for event list management.

If the full tree is stored in an array (heap), Henriksen's algorithm can make lowest priority ENQUEUE O(1), how?

A Henriksen's tree-list hybrid structure uses what property of NES to improve DEQUEUE O(n) ?

What are the O(n) of ENQUEUE, DEQUEUE, SEARCH, DELETE of priority queue structures (heaps) and balanced trees?

See how to use a C++ STL `priority_queue` as an Event List in NES.

Lecture slides for "better" event list management.

Tue Oct 23 NES Event "Lists" LG Assignment:

lga-nes-eventlists

Understand the basic steps in augmenting a pre-existing NES with additional system and meta events.

What is the difference between system events and meta events?

Cite pros and cons for at least two "pure" event list data structures commonly used for event list management.

Cite pros and cons for at least two hybrid data structures commonly used for event list management.

Practice understanding a pre-existing NES simulation, and making changes to it.

If the full tree is stored in an array (heap), Henriksen's algorithm can make lowest priority ENQUEUE O(1), how?

A Henriksen's tree-list hybrid structure uses what property of NES to improve DEQUEUE O(n) ?

What are the O(n) of ENQUEUE, DEQUEUE, SEARCH, DELETE of priority queue structures (heaps) and balanced trees?

Given Welford's discrete and integral mean and variance equations (Thms 4.1.2, 4.1.4), be able to apply them to a set of data.

DES people don't need integrals and anti-differentiation when integrating. Why not?

Lecture slides for "better" event list management.

Thu Oct 18 Midterm Exam

Here are the learning goals for the exam.

Mon Oct 15 – Tue Oct 16

Fall Break (no lectures)

Thu Oct 11 NES Software Architecture LG Assignment:

lga-nes (checked on Oct 23)

Describe S, the system state. What does "system" refer to?

How is the simulation clock different than the wall clock or an accelerated, virtual clock?

Name four data elements or data collections that go into a next event simulation (this list may not be exhaustive).

What constraint(s) are placed on events being inserted into the event list?

What is the difference between system events and meta events?

How does serial correlation affect estimated mean and standard deviation?

What is the difference between serial and paired correlation?

What is autocorrelation and autocorrelation lag? Why is autocorrelation important in DES?

What is positive (and negative) serial correlation? Cite a positive serial correlation example from the SSQ model.

What is a mean-square orthogonal-distance (MSOD) linear regression line?

Why are MSOD regression lines more suitable for DES?

Why don't we use standard statistical linear regression lines for DES results?

Given Welford's covariance equations (Thm 4.4.3), be able to apply them to a set of paired data (u,v).

Know that valid computer simulations do not produce outliers. End of discussion.

Intro to NES lecture slides.

Lecture slides on linear correlation.

Tue Oct 9 Simulation Statistics LG Assignment:

lga-sim-statistics

Individual Assignment:

Students are encouraged to browse through chapter 4 of the textbook. A good chunk of it will hopefully review. Some of the LGA questions have specific reading responsibilities, you should return to your group with a mastery of the knowledge required to answer the question --- not a mastery of the complete reading.

If there some "more important" sections of chapter 4 to read through they are 4.1.3 Examples which discusses the problems created by non-independent samples and 4.4.2 Serial Correlation. I suggest this reading because they are probably topics not dealt with (or not discussed enough) in introductory statistics courses.

Complete the SAN Critical Path assignment (due October 23 2018 by 11:59PM). You may partner up if you like.

What is special about outliers in the context of computer simulation results?

What are empirical CDFs? How are they better than histograms for assesing a data distribution?

Know the general form of the integral equations for CRVs (average and deviation calculations).

Know what constitutes a histogram and how it is connected to CDFs.

How is the height of a continuous histogram bin calculated?

Know the general approach to binning continuous data, about how many bins are needed for a sample of `n`?

How is the mean and standard deviation of a continuous data histogram differ than the underlying dataset?

Why would we ever need to calculate mean and std dev from histogram data?

How is the approach of MSOD regression lines different than the approach taken for conventional "least squares" regression lines?

What is a mean-square orthogonal-distance (MSOD) linear regression line?

Given Welford's discrete and integral mean and variance equations (Thms 4.1.2, 4.1.4), be able to apply them to a set of data.

Implement Welford's Equations for mean and variance in your preferred language for future course projects.

Know that Welford's Equations exist, why they are superior to the "one-pass" algorithm common in statistical texts.

Know which of the two (non Welford) standard equations for calculating s2 or s is flawed.

DES people don't need integrals and anti-differentiation when integrating. Why not?

Know that valid computer simulations do not produce outliers. End of discussion.

Lecture slides for Welford's Equations.

Lecture slides on histograms

Thu Oct 4 Uniform Arrivals and Sync'd Random Sequences
Tue Oct 2 Exponential and Geometric Variates LG Assignment:

lga-uniform-arrivals

Individual Assignment:

Complete the SAN Critical Path assignment (due October 23 2018 by 11:59PM). You may partner up if you like.

Understand that skewed results are obtained from SIS simulations (w/ delivery delays) with syncronized demand and delay random sequences.

Understand that skewed results are obtained from SSQ simulations with syncronized interarrival and service times.

Know that uniform arrival times and uniform interarrivals are not the same thing.

Understand the steps in going from uniform arrival times to exponential interarrival times.

Know the Exponential(mu) random variate and the interpretation of its parameter mu in the context of arrival times.

Know the Geometric(p) random variate, it's parameter p, and it's connection to Exponential(mu)

Previous lecture topic continues.

Thu Sep 27 Monte Carlo Simulations LG Assignment:

lga-random-points

Know how to use accept/reject techniques for uniformly random (geometric) point generation.

Know the pitfalls associated with common (naive) methods of random point generation.

What unique characteristic of a system or simulation makes it Monte Carlo?

Know the tell-tale feature(s) of spatial plots produced by faulty point generation algorithms.

When randomizing points in a circle without accept/reject, how should the radi r be chosen using Random()?

Why is it important to use multiple seeds and many replications in Monte Carlo simulations.

Know the Equilikely(a,b) random variate: the meaning of its parameters, pmf, and CDF.

Know the F(x) inversion technique for constructing random variates. What is the requirement on F(x)?

Know the Uniform(a,b) random variate: the meaning of its parameters, pdf, and CDF.

Understand the problems with the often used and always flawed `RandomInteger() mod SIZE` programming pattern.

What does the parameter u in random variates represent? Computationally, how do we get a value for u in code?

Know the difference between a random number and a random variate.

Lecture slides for Monte Carlo simulations.

Tue Sep 25 Quiz 1 Individual Assignment:

You may want to read some or all of section 2.4.4 (stochastic area networks) from the text (optional).

Understand the submission and I/O requirements of simuation projects for the course.

Review or learn about Makefiles and the course provided Makefile Project.mak templates.

Review the use of command line arguments in your preferred language.

Understand what a stochastic activity network is and how it relates to one of your first simulation projects.

Here are the learning goals for the first learning group quiz.

Thu Sep 20 New and Modern pRNGs LG Assignment:

lga-quiz-prep-1

"Good" pRNGs requiring k bits to hold values of their state space S have a period approximately how large?

Why is breaking up a modern, large period pRNG into streams avoided?

How are k values in a mod 2 number system (aka bits) turned into a fractional value in the interval (0,1).

How does the Lehmer pRNG (from the book) differ in theory from modern pRNGs?

Lecture slides for new and modern pRNGs.

Tue Sep 18 pRNG Streams LG Assignment:

lga-monte-carlo-probs

Know how to write Monte Carlo simulations for estimating the Pr(A) of an event A.

What are replications in the context of discrete event simulations?

How do you apply pRNG streams to achieve variance reduction in simulation experiements?

How is a (sub)stream of a Lehmer pRNG created?

What is the geometric interpretation of multiple Lehmer pRNG streams?

Know the Equilikely(a,b) random variate: the meaning of its parameters, pmf, and CDF.

Know the Uniform(a,b) random variate: the meaning of its parameters, pdf, and CDF.

What does the parameter u in random variates represent? Computationally, how do we get a value for u in code?

Lecture slides for variance reduction using pRNG streams. Substreams of pRNGs are not covered by the text until chapter 3 --- I prefer to cover them now. If you want to see what the book has to say about them, the reading is section 3.2 (chapter 3, section2).

Thu Sep 13 Lehmer pRNGs LG Assignment:

lga-lehmer-generators

Explain the values a, m, g() and x0 in a (Lehmer) PMMLCG; how is the next Uniform(0,1) random value calculated?

Given a and m (a a full period multiplier), find the smallest and largest floating point values between 0 and 1 that can be generated.

How is an xi+1 value converted from an integer to a real number in the interval (0,1)?

What does the pRNG API routine Random() provide to a simulation writer?

What is a full period multiplier and why is it important to Lehmer pRNGs?

Explain what "random numbers fall mainly in the planes" means.

What is the geometric interpretation of multiple Lehmer pRNG streams?

What is modulus compatibility mean for a in the context of Lehmer pRNGs? Why is this important to the implementation?

How did zero delivery lag manifest itself in the SiS conceptual, specification, and computational models?

Lecture notes for Lehmer PMMLCG slides.

Tue Sep 11 No Lecture (Career Day!)
Thu Sep 6 pRNG properties and Lehmer LG Assignment:

lga-coding-sis (now the problems!)

Wed Sep 5

Tue Sep 4 Simple Inventory System (SIS) LG Assignment:

What (arithmetic) pRNG properties did the thieves take advantage of in electronic poker games?

Speculate how the electronic poker games dealt predictable valid 2-player poker hands (including draws) from pRNG values.

Speculate why time syncronization and hitting "PLAY" at the precise moment was critical to the thieves' strategy.

Explain the values a, m, g() and x0 in a (Lehmer) PMMLCG; how is the next Uniform(0,1) random value calculated?

What does the pRNG API routine Random() provide to a simulation writer?

What is a full period multiplier and why is it important to Lehmer pRNGs?

Explain what "random numbers fall mainly in the planes" means.

How did back-ordering inventory manifest itself in the SiS conceptual, specification, and computational models?

How did flow-balanced inventory manifest itself in the SiS conceptual, specification, and computational models?

How did zero delivery lag manifest itself in the SiS conceptual, specification, and computational models?

In the SiS case study, what were s and S (note the case) and how did the simulation experiment vary one or both of them?

What SiS assumption about demand over an inventory review period simplified the specification model?

Here is the Code base for LGA on SIS. Lecture slides for simple inventory systems.

Mon Sep 3

Labor Day (no lectures)

Thu Aug 30 Coding SSQs and Inventory Systems LG Assignment:

lga-coding-ssqs

Understand how a FIFO SSQ simulation can be written in a simple while loop and how a_i and s_i can be manipulated for simple experiments.

How were arrival times and service times "modeled" in the Sven & Larry case study?

Know how to use an appropriate indicator function in the proof of Little's Theorem.

Which variable was altered Sven & Larry ice cream parlor simulation experiment? How was it altered? Was the measure of traffic intensity affected?

Here is the tarball with the provided ssq programs. Lecture slides for Little's Equations and Traffic Intensity.

Tue Aug 28 Introduction to SSQs LG Assignment:

lga-intro-to-ssqs

Know the rules for presenting discrete and continuous data relationships (scatter plots vs connected dots).

Know how to calculate traffic intensity and its connection to service rate.

Understand the canonical SSQ and appreciate its broad application to computer simulation.

Be familar with the job averaged statistics and time averaged statistics of an SSQ.

Know the algebraic form of Little's equations connecting the two types of statistics.

Which of the SSQ time measures (there are 5) are timestamps and which are time intervals?

show-simple-machine-shop.pdf

SSQ Slides

Fri Aug 24

Thu Aug 23 Simulation Design LG Assignment:

lga-engineering-a-simulation

Learn about several different simulation approaches, topics, and uses.

What are consistency checks? How can they be used in V&V?

What are the authors' five phases of simulation development?

What is simulation validation?

What is simulation verification?

What is the computational model of a simulation?

What is the conceptual model of a simulation?

What is the specification model of a simulation?

Name two acceptable ways to validate a simulation.

When can a particular phase (concept, specification, computational, v&v) of simulation development be skipped?

Intro to Simulation Design slides.

Tue Aug 21 This is merely a simulation Individual Assignment:

Review the course syllabus, Learning Groups with participation points, and the use of bounties in the course.

You may also want to look through the assignment submission guidelines so you know what you're getting into.

From this zip, read one paper (choose the one of most interest to you), and be prepared to discuss it in the next lecture.

Learn of several different simulations reported in the literature, compare and constrast their pros and cons.

You do not (yet) need a login for course website, when the time comes you will authenticate using your `mymail` Mines Email address (through `google`).

This course will not use Blackboard.

Mon Aug 20

Classes begin