January 10 (Tue), 2017 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 and subjective interpretations are models of the axioms.
January 12 (Thu), 2017 HW1 assigned: exercises 3.2, 3.3, 3.4, 3.5 [H], due on Thursday, January 19, 2017. Beginning of ch.3 ("Probability Review") [H] through Section 3.4.
January 17 (Tue), 2017 HW1 due date changed to January 24, 2017. Chapter 3[H] continued through Bayes's Law (section 3.6) and the definition of random variable (section 3.7[H]).
January 19 (Thu), 2017 HW2 assigned: Exercises 3.19 and 3.20 (parts (a) and (b) only) [H], due on Tuesday, January 24, 2017. HW2 due date changed to January 26, 2017. Random variables, with several examples.
January 24 (Tue), 2017 Examples of random variables, including a couple from the experiment of tossing a fair coin three times in sequence. Definition 3.14 (pmf, cdf). The Bernoulli(p) discrete distribution. Common discrete distributions: Bernoulli(p), Binomial(n,p), Geometric(p), Poisson(lambda).
January 26 (Thu), 2017 Q2. HW1 due date changed to February 2, 2017. Q2. Discussion of HW2, concentrating on the difference between P{A,B} and P{A}. Continuous distributions. Definition of probability density function and cumulative distribution function (pdf, cmf). Some common continuous distributions: Uniform(a,b), Exponential(lambda), Pareto (alpha). Expectation. Moments. Expectation of a function of a random variable. Variance defined. Variance of some common distributions.
January 31 (Tue), 2017 Linearity of expectation. Conditional pmf and pdf; independence of random variables. Computation of the expected value of the Geometric(p) r.v. using conditioning. Same for the Binomial(n,p) using indicator variables and the linearity of expectation. The Hats example (p.55-56 [H]).
February 2 (Thu), 2017 HW3 assigned: exercises 3.11, 3.15, 3.16, 3.24 (part a), due on Thursday, February 9, 2017. Expectation, with examples from Trivedi. Moments. Expectation of a function of a random variable. Variance defined. Variance of some common distributions. Joint probability and independence. An example from Trivedi (disk seek time),
February 7 (Tue), 2017 Discussion of HW3 with some hints given. The memoryless (Markov) property of the exponential distribution, using Trivedi's notes, which are available in the blackboard site for this course. Reliability (based on Trivedi's notes). The normal distribution (also based on Trivedi's notes.)
February 9 (Thu), 2017 HW4 assigned: exercise 3.8, 3.13(a), 3.14, 3.23 (all from [H]), due on Tuesday, 2017-02-21. The normal distribution and random deviates (from Trivedi's notes.)
February 14 (Tue), 2017 Midterm will be on Thursday, February 23, 2017. Ch.1 [H] ("Motivational Examples of the Power of Analytical Modeling") completed. HW3 corrected in class. This class was narrated over PowerPoint, because the instructor was absent; a graduate student proctored.
February 16 (Thu), 2017 Q3. Midterm will be on Thursday, February 23, 2017. Ch.2 [H] ("Queueing Theory Terminology") completed. This class was narrated over PowerPoint, because the instructor was absent; a graduate student proctored.
February 21 (Tue), 2017 Midterm will be on Thursday, February 23, 2017. It will be closed book and notes; no calculators. It will cover chapters 1-4 and the Trivedi sections on blackboard (except the one on inequalities and limit theorems). HW4 due date changed to Thursday, February 23, 2017. Please submit this homework using the departmental dropbox. Exercise 2.1 [H] done in class. Ch.4 [H] ("Generating Random Variables for Simulation") completed.
February 23 (Thu), 2017 Midterm (MT1).
February 28 (Tue), 2017 MT1 returned and discussed. Ch.5 ("Sample Paths, Convergence, and Averages"), except for 5.2 ("Strong and Weak Laws of Large Numbers").
March 2 (Thu), 2017 HW5 assigned: exercise 5.1 [H] due on Tuesday, March 21. (Note: if you base your answer on Trivedi's handout on Inequalities and Limit Theorems, which is on blackboard, you must quote it properly.) Partial solution to HW4: Exercises 3.8 and 3.13(a) (with discussion leading to a couple of proofs of Markov's inequality). Inequalities and Limit Theorems (Trivedi's section on blackboard), including the Weak Law of Large Numbers (Section 5.2 [H]).
March 14 (Tue), 2017 HW6 assigned: exercises 6.1 and 6.2 [H] due on Tuesday, March 21. Alternate proof of Markov's inequality. Chapter 6 ("Little's Law and Other Operational Laws") started. Statement of Little Law. Intuitions behind Little's Law. Little's Law up to the beginning of the second example in Section 6.7 [H].
March 16 (Thu), 2017 Chapter 6 ("Little's Law and Other Operational Laws") completed.
March 21 (Tue), 2017 HW7 assigned: Exercise 7.4 [H] due on Thursday, March 30. Problems with the projectors. Two support staff members, called, come and fix the problem. Exercises 6.1, 6.2, 6.3, 6.4, and 6.5 done on the whiteboard. I show the class 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************************** Ch.7 [H] ("Modification Analysis: 'What-If' for Closed Systems") started.
March 23 (Thu), 2017 Ch.7 [H] ("Modification Analysis: 'What-If' for Closed Systems") completed.
March 28 (Tue), 2017 Note on Ex.7.4: ignore the specified length of observation period: it is incorrect (less than the CPU busy time), but the error has no bearing on the exercise. Review of Ch.7 [H]; exercises 7.1, 7.2 (parts a and d only), and 7.3 on the board.
March 30 (Thu), 2017 Low attendance, likely due to near-flood conditions near Swearingen building. Correction of HW7. Ch.8 [H] ("Discrete-Time Markov Chains") started: definition, transition probability matrix, repair facility problem.
April 4 (Tue), 2017 Ch.8 [H] ("Discrete-Time Markov Chains") through the proof that the limiting distribution (if it exists) is equal to the stationary distribution (section 8.6).
April 6 (Thu), 2017 Chapter 8 [H] (Discrete-Time Markov Chains) completed. Using R, the matrixcalc package, and the matrix.power function in that package, we computed high powers of the transition matrix for several problems: forgetful professor, repair problem, and computer instruction problem. We noted that the high power matrices appeared to converge to stationary matrices, confirming some of theoretical results in the chapter.
April 11 (Tue), 2017 HW8 assigned: Exercise 8.7 [H] due 2017-04-18. Projector problems prevented the use of slides, etc. I used the whiteboard. Exercise 8.7 [H] discussed. Exercises 8.2, 8.3, 8.4, and parts of 8.5 done on the board.
April 13 (Thu), 2017 HW9 assigned: Exercise 9.3 [H] due 2017-04-20. Exercise 8.5 done on the board in detail. Ergodicity questions (9.1 [H]), Finite-State DTMCs (9.2 [H]), definitions of ergodicity (Definition 9.24 [H] and related footnote), Time-Reversibility Theorem and three types of equations (regular stationary, balance, and time-reversibility) (9.7 [H]).
April 18 (Tue), 2017 Selected topics on ergodicity from Ch.9 [H]. Exercise 9.2 in detail. Hints for Exercise 9.3 [H]. Section 9.2 [H]; Google's PageRank algorithm.
April 20 (Thu), 2017
The final exam will be closed book and notes, except for one handwritten side
of a letter-sized sheet with formulas and expressions, but no complete
examples. The final exam will include the topics covered since the midterm,
and in particular chapters 4-8 [H], chapter 9 [H] without proofs, sections
10.1 and 10.2 [H], sections 11.1 and 11.2 [H] (we actually covered this
material on the exponential distribution using Trivedi's notes), and section
13.1 [H] (the M/M/1 queue; without proofs).
The Aloha protocol (10.2 [H]) as a Markov chain.
Basics of M/M/1 queues; definition of Poisson process (definition 2 on p.215
[H]). Brief discussion of exercise 13.1 [H] ("Bathroom queue").
Student evaluation of course.
End of course.