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.