**January 16 (Tue), 2018**
Administrative information:
textbook, syllabus, grading policy. Roll called.
Examples of queueing systems (from ch.1 of Adan and Resing; see full
reference under "Some useful links" on the course website).
Kolmogorov's axioms of probability. Classical, limiting frequency,
and subjective (Bayesian) interpretations of probability. We show that
the classical interpretation is a model of the axioms.

**January 18 (Thu), 2018**
Q1.
We show that
the classical and subjective interpretations are models of the axioms.
Beginning of ch.3 ("Probability Review") [H] through Section 3.1.

**January 23 (Tue), 2018**
HW1 assigned: exercises 3.2, 3.3, 3.4, 3.5 [H],
due on Tuesday, January 30, 2018.
Chapter 3 [H] continued through most of section 3.4 [H] ("Independent
Events and Conditionally Independent Events").

**January 25 (Thu), 2018**
HW1 due date changed to Thursday, February 1, 2018.
Chapter 3 [H] continued through section 3.5 [H] {"Law of Total Probability")
with several examples.

**January 30 (Tue), 2018**
HW1 due date changed to Tuesday, February 6, 2018.
Chapter 3 [H] continued through section 3.6 [H] ("Bayes Law")
with several examples, including one with two independent tests and one with
different prior probabilities.

**February 1 (Thu), 2018**
HW1 is renamed HW2; its due date will be established later.
HW1 assigned: Exercises 3.19 and 3.20 due on Thursday, February 8.
Random variables (section 3.7 [H]) with several detailed examples.

**February 6 (Tue), 2018**
Q2.
Another example of use of Bayes' Rule with conditionally independent events,
completely described.
Definition 3.14 (pmf, cdf), illustrated with two detailed examples.
The Bernoulli(p) discrete distribution.

**February 8 (Thu), 2018**
The Bernoulli(p), Binomial(n,p), Geometric(p), Poisson(\) discrete
distributions with examples. Continuous distributions. Informal argument as
to why a continuous distribution has value zero for any particular argument.

**February 13 (Tue), 2018**
HW2 (reduced to exercises 3.2, 3.4, 3.5 [H]) is due on Thursday, February 15.
Exercise 3.20(c) corrected on the board in full detail.
Continuous random variables (3.8.2) through the uniform distribution.

**February 15 (Thu), 2018**
HW2 corrected in class, in detail.
Exponential distribution. Expectation of exponential distribution.

**February 20 (Tue), 2018**
HW3 assigned: exercise 3.3 [H] due on Tuesday, February 27.
Expectation, moments, variance (Section 3.9 [H]).

**February 22 (Thu), 2018**
Joint probability.
Independence of random variables.
Linearity of expectation.
Alternate formula for the computation of variance.

**February 27 (Tue), 2018**
Memoryless property of the exponential distribution.
The exponential distribution is unique continuous distribution that
has the memoryless property.
Reliability and instantaneous failure rate (hazard).

**March 1 (Thu), 2018**
Midterm exam.

**March 6 (Tue), 2018**
Midterm post-mortem in great detail.
Functions of random variables as a kind of function composition.
Theorem 2.3-1 from Higgins and Keller-McNulty, showing how one can
compute the expectation of a function of a random variable without first
computing its pdf.
Example with continuous variables: finding the pdf of X^2 (Trivedi, example
3.8).

**March 8 (Thu), 2018**
HW4 assigned: exercises 3.21, 3.22, and 3.23 [H], due March 22, 2018.
Examples from sections 3.12, 3.13, 3.15 [H]. Normal distribution
(section 3.14 [H]) done in part. Table of standard normal distribution
handed out.

**March 20 (Tue), 2018**
The normal distribution with examples. The normal distribution is an IFR
(Increasing Failure Rate) distribution. Some Q&A about HW4.

**March 22 (Thu), 2018**
HW4 (exercises 3.21, 3.22, and 3.23 [H]) due date changed to March 27, 2018.
Discussion of the exercises.
Expectation of a function of two random variables:
Disk seek example from Trivedi.
Generating Random Variables by Simulation (Ch. 4 [H]): the Inverse Transform
Method in the Discrete Case.

**March 27 (Tue), 2018**
HW4 corrected in class.
Generating Random Variables by Simulation (Ch. 4 [H]): the Inverse Transform
Method in the Discrete and Continuous Cases.

**March 29 (Thu), 2018**
HW5 assigned: exercises 4.1 and 4.2 [H], due on Thursday, April 5.
Please use the Accept-Reject
Method for Exercise 4.1 and the Inverse-Transform Method for Exercise 4.2.
The Accept-Reject Method in the discrete and continuous cases, with examples.
ch.1 [H] started. Design Example 1 (Doubling Arrival Rate) set as a
challenge.

**April 3 (Tue), 2018**
Examples of the Power of Queueing Theory from Ch.1 [H]. Queueing Theory
terminology (Ch.2 [H]) up to Device Utilization.

**April 5 (Thu), 2018**
HW6 assigned: Exercise 2.1 [H], due on Thursday, April 12, 2018: canceled on
April 10, 2018.
Correction of HW5.
Ch.2 [H]: open networks completed.

**April 10 (Tue), 2018**
HW6 canceled.
Ch.2 completed. Exercise 2.1 done in class. Since most students
have not taken linear algebra, and the exercise requires inverting a
matrix (for an efficient solution), I cancel HW6.

Here is an email from Dr. Harchol-Balter in which she explains
further the meaning of N (number of jobs or multiprogramming level) for
closed interactive and batch systems.

*****Email starts here**************************************************

I have a question that maybe is also a suggestion for a different way to
present the concept of multiprogramming level. I would like to have
some pointers to simple illustrations of the notion of multiprogramming level.

I recommend looking at my paper in NSDI 2006. This paper is on my website:
Bianca Schroeder, Adam Wierman, and Mor Harchol-Balter. "Closed versus Open
System Models: a Cautionary Tale." Proceedings of Networked Systems Design
and Implementation (NSDI 2006) . San Jose, CA, May 2006, pp. 239-252. pdf
The paper describes how most systems in computer science are actually closed
systems, while most modeling that is done is on open systems.

In the first paragraph of Section 2.6.1, you note that for interactive
(terminal-driven) systems the MPL is fixed and equal to the number of
terminals. Later in the same section, you mention two typical questions
asked by designers of terminal-driven systems: in the first question, you
do not assume that N is fixed. While this is not a contradiction, it is
odd to see the MPL described as an “exogenous” quantity at the beginning
of the section, and as something that can be changed later on to remain
within a fixed response time.

I understand what you're saying, and I'll try to make it clearer in the
next version.
I was trying to stress that in an interactive system, the system as a whole
is run with a fixed total number of users, N, while the central subsystem
may have a varying number of users. The fact is that the fixed number
of users, N, is chosen to be as high as possible without causing so much
congestion that response times get very high.
You should think of N as denoting the number of people who sit at terminals
entering data, which is then sent to some central subsystem for processing.

In Section 2.6.2 on batch systems, you similarly start with a fixed N
(“… there are always N jobs in the central subsystem”) and then relax
this constraint (“typically constrained by some maximum MPL (because only
so many jobs fit into memory or for some other reason”). Again, there is
no contradiction, but this kind of presentation makes it difficult to grasp
exactly what the multiprogramming level is.

Ah, what I mean here is that N is again fixed, but now that fixed value of N
is not determined based on some response time goal. Instead, N is based on
some artifact of the system, e.g., N is the maximum number of jobs that
can fit into memory. The point is that we want to run the batch system
with as high a value of N as possible, because our goal is to maximize
throughput (which means maximizing the business of the servers).
Unfortunately, there's typically a limit for how high N can be.
Note that I'm using N and MPL interchangeably. N is the
Multi-Programming-Level.

*************Email ends here**************************

**April 12 (Thu), 2018**
HW6 assigned: exercises 6.1 and 6.2 [H], due on Thursday, April 19.
Chapter 5 [H] concluded; Markov inequality (proved in different ways,
including one with indicator variables). Example (reliability with
exponentially distributed lifetime) in which the Markov inequality
gives a very poor bound. Chebychev's inequality, proved. Example
(exponentially distributed processing time) in which Chebychev's inequality
gives a non-informative bound (Probability less than or equal 1), but a
much stronger bound can be obtained using the distribution function directly.

**April 17 (Tue), 2018**
Q4.
HW6 delayed to Tuesday, April 24.
Bernoulli's Theorem (proved using Chebychev's inequality applied to
X~Binomial(n,p)). The Weak Law of Large Numbers, stated with comments (no
proof).
Chapter 6[H] ("Little's Law and Other Operational Laws") through
Section 6.5.
Notes by Professor Kishor Trivedi placed on the blackboard site for
the course, for the following topics: the memoryless property of the
exponential distribution and reliability; the normal distribution;
expectation (including the disk seek example); inequalities and
limit theorems.

**April 19 (Thu), 2018**
Q5.
Chapter 6[H] ("Little's Law and Other Operational Laws") through
Section 6.9.

**April 24 (Tue), 2018**
Q6.
Chapter 6[H] completed. Ch.7[H] ("Modification Analysis: 'What-If' for
Closed Systems" through the "Simple Example" of Section 7.4.

**April 26 (Tue), 2018**
Q7.
Exercise 6.2 [H] corrected in class.
Chapter 7 completed.
Chapted 8 [H] ("Discrete-Time Markov Chains") up to the statement of Theorem
8.6. The rest of chapter 8 is left for the students to study on their own.
Course evaluation.
The final exam will be in the classroom, at the time specified by
the university. It will be closed book and notes, except for one 5x7
handwritten card with definitions and theorems written on a single side.
The card will be collected at the end of the exam.