Semester Calendar

,
Date Lecture Title Assignment(s) Lecture & Assignment Goals
Notes
Wed Dec 13 Final Exam

The final exam will be 1-3PM in the lecture hall.

DSA Students: you may not know whether you plan on doing the final project or sitting for the written exam --- but be smart and make a reservation with the testing center now! These are easy to cancel but very hard to make at the last minute!

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 than the material beforehand.

Wed Dec 6

Classes End

Tue Dec 5 Quiz 3

Here are the learning goals for the quiz.

Thu Nov 30 Quiz Prep 3 LG Assignment:

lga-quiz-prep-3

"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?

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?

Lecture slides for variance reduction using pRNG streams.

Lecture slides for new and modern pRNGs.

Tue Nov 28 Lehmer Generators LG Assignment:

lga-lehmer-generators

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

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

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?

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 is a full period multiplier and why is it important to Lehmer pRNGs?

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

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

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?

Lecture notes for Lehmer PMMLCG slides.

Lecture slides for variance reduction using pRNG streams.

Thu Nov 23 – Fri Nov 24

Thanksgiving Holiday - Campus closed

Wed Nov 22

Thanksgiving Holiday - No-Class Day, campus open

Tue Nov 21 Non-Stationary Arrivals 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 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?)

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

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

Be able to use Von-Neumann's accept-reject algorithm as a variate technique for difficult to invert F(x)s

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 three techniques for truncating pre-existing random variates.

Von-Neumann's accept-reject algorithm is another variate generation technique.

Lecture slides for generating non-stationary arrivals.

Q#3 of lga-crv-applications is an incredibly important question for your group to internalize --- unfortunately it's a bit long in the tooth. So have a couple people tackle it (collaboratively would be ideal, I think) and get one really good solution for the group to review together in your next LGT. Hint the essential math is very similar to question #3 of lga-continuous-random-variates.

Thu Nov 16 Quiz 2

Here are the learning goals for the quiz.

Tue Nov 14 Quiz Prep 2 LG Assignment:

lga-quiz-prep-2

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

Be able to use Von-Neumann's accept-reject algorithm as a variate technique for difficult to invert F(x)s

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

Reservoir sampling proof.

Von-Neumann's accept-reject algorithm is another variate generation technique.

Thu Nov 9 Continuous Random Variables LG Assignment:

lga-continuous-random-variates

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

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?

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.

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

As promised, my plots. Note that I've also included plots for having shuffled the deck before each experiment --- which I don't believe the problem statement say should be done.

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

Tue Nov 7 Sampling Algorithms LG Assignment:

lga-sampling-algorithms

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 (6.5.6) for selecting n random elements from an unkown sized population.

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.

Know how to identify and create truncated probability distributions using an accept-reject technique.

Be able to recognize and apply the formulas of variate truncation by CDF modification.

Know the constrained inversion technique for truncated random variates.

Know three techniques for truncating pre-existing random variates.

Here are the Shuffling and Sampling Slides from lecture.

Fisher-Yates shuffling proof.

Tue Nov 7

Last Day to Withdrawal from Courses (No Refund)

Thu Nov 2 Discrete Random Variates LG Assignment:

lga-discrete-random-variates


CrosswalkSim.

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 how to identify and create truncated probability distributions using an accept-reject technique.

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?

Be able to recognize and apply the formulas of variate truncation by CDF modification.

Know the constrained inversion technique for truncated random variates.

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

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

Know three 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, their truncation by F(x) modification.

Tue Oct 31 Event List (continued)

lga-meta-events measures to check your own solutions: SSQ Result Ranges and the same for SiS.

Thu Oct 26 NES Event "Lists" LG Assignment:

lga-meta-events

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

What are the most critical operations performed on an NES event list (E)?

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

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.

How are Event Management schemes (data structures) judged and evaluated?

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

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

Henriksen's algorithm can make lowest priority ENQUEUE O(1), how?

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 sample paths. Why not?

lga-nes measures to check your own solutions: SSQ Result Distributions and the same for SiS. There were concerns after lecture today about SiS orderCount, I double checked my SIM and cannot find an error - if your SiS numbers don't agree see the second slide and confirm the Exponential(3/4), Exponential(7) and Geometric(2/3) values being generated in your SIM match mine. I seem to recall Geometric() being a common issue in previous semesters. You may need to refresh your browser's cached PDF.

Discussion questions about event ordering details in NES

Lecture slides for "better" event list management.

Tue Oct 24 NES Software Architecture LG Assignment:

lga-nes

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?

Know the basic algorithm for executing a DES using next event methodology. (hint: probably not more than 5-8 items, depending on wording, and one loop)

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

What is the difference between system events and meta events?

NES Design Slides

Thu Oct 19 Continued Lecture

How does serial correlation affect estimated mean and confidence interval widths?

What is the difference between serial and paired correlation?

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

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.

When j lagged serial correlation rj values from n data points are uncorrelated what percent will fall within ±2/√n?

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?

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

Get War-and-Trash finished!

Lecture slides on linear correlation.

Mon Oct 16 – Tue Oct 17

Fall Break - No-Class Day, Campus open

Thu Oct 12 Simulation Correlations LG Assignment:

lga-sim-correlations

Know the square root rule, by increasing the replication size 9x, how much smaller will our confidence intervals be?

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

How does serial correlation affect estimated mean and confidence interval widths?

What is the difference between serial and paired correlation?

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

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.

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?

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?

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

Lecture slides on histograms

Lecture slides for the square root rule.

Lecture slides on linear correlation.

Tue Oct 10 Midterm Exam

Here are the learning goals for the exam.

Thu Oct 5 Uniform Arrivals or Uniform Interarrivals

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

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

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?

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.

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

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

LGA discussion slides for uniform arrivals vs uniform interarrivals.

Lecture slides on histograms

Lecture slides for Welford's Equations, and the derivation of Welford's discrete forms of the average and ivi. Derivations for continuous forms follow the same pattern, with only a couple more curves in the road :)

Tue Oct 3 Simulation Stats LG Assignment:

lga-sim-statistics


Students are encouraged to browse through chapter 4 of the textbook. A good chunk of it will be hopefully review. Some of the LGA assignments or questions will have specific reading responsibilities. Use the associated learning goals to guide your reading!

The more important sections of chapter 4 to read through are 4.1.3 Examples which discusses the problems created by non-independent samples and 4.4.2 Serial Correlation. This reading is needed because the topics were (likely) not dealt with (or not discussed enough) in introductory statistics courses.

Know how derivations between the CDF (F(x)) and the PDF (f(x)) of continuous valued distributions are performed.

Know how to calculate the Pr(Event) for both discrete and continuous valued distributions.

Know how to calculate the mean and standard deviation of discrete data.

Understand why the traditional one-pass variance equation is flawed for use in computer simulation.

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

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

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?

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 sample paths. Why not?

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

Lecture slides for Welford's Equations, and the derivation of Welford's discrete forms of the average and ivi. Derivations for continuous forms follow the same pattern, with only a couple more curves in the road :)

Lecture slides on histograms

Thu Sep 28 Uniform Arrivals LG Assignment:

lga-uniform-arrivals

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 F(x) inversion technique for constructing random variates. What is the requirement on F(x)?

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

Exponential and Geometric distributions and variates

Tue Sep 26 Quiz 1 LG Assignment:

After the quiz is graded, you will be assigned to your second round learning groups.


Check your Blaster Card access to CTLM B60! You will want this just in case when projects roll around (soon)!

Read about project requirements for the course; we'll review these (briefly) next lecture.

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

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

Thu Sep 21 Monte Carlo Wrap-up & War-n-Trash LG Assignment:

lga-quiz-prep-1


War-and-Trash

Tue Sep 19 Random Points LG Assignment:

lga-random-points


Check your Blaster Card access to CTLM B60! You will want this just in case when projects roll around (soon)!

Read about project requirements for the course; we'll review these (briefly) next lecture.

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.

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

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. Some of you may be missing §2.3 in your text, this might help.

Thu Sep 14 Probability Primer & Monte Carlo Simulations LG Assignment:

lga-monte-carlo-probs

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

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

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

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.

What are replications in the context of Monte Carlo simulations?

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

What is a seed for a pRNG, how is it related to the sequence of valued generated by Random()?

What is ρ (rho) for pRNGs? When does the sequence of values from Random() repeat?

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.

chl_cycle-vs-random-results.pdf

pRNG primer slides and f(x), F(x) reminder slides.

Lecture slides for Monte Carlo simulations. Some of you may be missing §2.3 in your text, this might help.

Tue Sep 12 No Lecture (In-person Career Day!)
Tue Sep 12 – Wed Sep 13

Career Day - dates subject to change (NO-ASSESSMENT)

Thu Sep 7 Simple Inventory System (SIS) LG Assignment:

lga-coding-sis

Understand the Simple Inventory System (SIS), it's assumptions and simplifications.

Understand the experimental design of the Simple Inventory System case study; how was an optimal s determined?

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?

Lecture slides for simple inventory systems.

Here is the Code base for LGA on SIS.

Considering q-bar in questions 1.2.2 and 1.2.8 group question.

Wed Sep 6

Last day to DROP

Tue Sep 5 SSQs Continued LG Assignment:

There will most likely not be an LGA for Thursday. But don't get used to the idea of "no LGA days"; these will be few and far between.

Know how the expected behavior or performance of an SSQ changes with varying levels of traffic intensity.

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.

What properties must an SSQ have in order to apply Little's Equations to its statistical measures.

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

Is the relationship between traffic intensity and average queue length linear or non-linear?

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

Know the "pattern of the proof" using indicator functions to show Little's equations for SSQs.

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

Considering q-bar in questions 1.2.2 and 1.2.8 group question.

Lecture slides for Little's Equations and Traffic Intensity.

Mon Sep 4

Labor Day Holiday - Campus Closed

Thu Aug 31 Coding SSQs LG Assignment:

lga-coding-ssqs

Know how the expected behavior or performance of an SSQ changes with varying levels of traffic intensity.

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

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

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.

What properties must an SSQ have in order to apply Little's Equations to its statistical measures.

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

Is the relationship between traffic intensity and average queue length linear or non-linear?

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

Know the "pattern of the proof" using indicator functions to show Little's equations for SSQs.

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

Lecture slides for Little's Equations and Traffic Intensity.

Here is the tarball with the provided ssq programs.

Tue Aug 29 Introduction to SSQs LG Assignment:

lga-intro-to-ssqs

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

What is simulation validation?

What is simulation verification?

Name two acceptable ways to validate a simulation.

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.

Know the four different types of queuing disciplines that might be used in an SSQ simulation.

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

LGA discussion slides

Simple Machine Shop slides

Considering V&V group question.

SSQ Slides

Thu Aug 24 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.

Some resources you'll need during lecture: show_article_discussion.pdf, new-learning-group-0-todo.txt.

Tue Aug 22 This is merely a simulation

Review the course syllabus and read how Learning Groups with participation points will be used in the course.

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

Intro slides

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.

Understand how the course participation grade will be factored into your course grade.

Understand how your course grade will be calculated.

Students on Monday requested to see an example of what a SIM project write-up looks like. Here are two that I'm pretty sure we won't be doing this semester:

You do not (yet) need a login for the course website, when the time comes you will authenticate through Mine's SSO or individualized logins (TBD).

This course will not use Canvas or Blackboard.

Mon Aug 21

Classes begin