# ANNOUNCEMENTS

• FINAL -- May 3 -- 5:30 p.m. - 8:30 p.m. in Wean 7500. Final covers only Chpts 20 - 23, plus Chpts 1-12.
• For the FINAL, you will again be allowed a single 3x5 index card as a "cheat sheet" for the exam. You can write anything you like on either side of the card.
• REVIEW Session for FINAL on Sunday, May 1 from 2 p.m. - 4 p.m. in Wean 7500.
• MIDTERM 2 -- April 6 -- 6:15 p.m. - 8:15 p.m. in Wean 7500.
• REVIEW Session for MIDTERM 2: April 4, from 8:30 p.m. - 10:30 p.m. in GHC 4307.
• For Midterm 2, you will again be allowed a single index 3x5 index card as a "cheat sheet" for the exam. You can write anything you like on either side of the card. Please note that we will provide you with several tail bounds for the exam. These will include: Markov, Reverse Markov, Chebyshev, Pretty Chernoff Binomial, Stronger Chernoff Binomial, Hoeffding. Please don't think that means you don't need to study.
• Midterm 2 will cover chapters 12, 13.1, 14 - 19, inclusive.
• Study your old homework solutions carefully. Solutions to old homeworks are always available in the bins outside Mor's office: GHC 7207.

# BOOK ERRORS/TYPOS

• p. 26 -- Axiom 3.4, part 2. Should say: forall i \neq j.
• p. 69 -- Eq (5.8) should say: E[S] = E[S | S \leq x] * P{S \leq x} + E[S | S > x] * P{S > x}
• p. 90 -- Extra "s" in the line describing the figure.
• p. 136 -- Defn 9.4 should say: for all x, y
• p. 139, in Defn 9.10 -- The last integral in the first equation should say "dy" instead of "dx."
• p. 218. *14.18 -- star should be parens
• p.241/242 -- The references should all be to Table 16.1, not 16.3.
• Exercise 21.6, Hint 2: s the fraction --> so the long-run fraction
• p. 319 -- "The irreducible chain might consist of" --> "A chain might consist of"
• p.396 -- N_center ~ min(N,20)

# HOMEWORKS

• Here is an OPTIONAL Latex Template template.tex . You are also free to hand-write your homeworks, provided you can keep your handwriting readable.
• HW 0: Prerequisites -- Due 1 p.m. 1/21.
• For the Taylor Series problem, follow the procedure in the chapter and assume that the Taylor series is centered at 0.
• HW 1: Probability on Events: 3.9, 3.10, 3.11, 3.16, 3.18, 3.22, 3.25, 4.4, 4.7 -- Due 1 p.m. 1/28.
• HW 2: Discrete Random Variables: 5.12, 5.13, 5.16, 5.17, 5.18, 5.21, 6.18, 6.25, 6.26 -- Due 1 p.m. 2/4.
• HW 3: Variance and z-Transforms: 6.21, 6.27b, 6.28, 7.2, 7.4, 7.6, 7.8, 7.9, 7.10 -- Due 1 p.m. 2/11.
• Note: Exercise 7.10 illustrates another important use of z-transforms: it allows us to solve recurrence relations. The recurrence in 7.10 can be solved without z-transforms, of course, by unravelling the recurrence (do that to check your solution). However some recurrences, like the Fibonacci recurrence, require z-transforms.
• Note: Exercise 7.11 is not assigned because it is a bit hard. However it illustrates another beautiful application of z-transforms. If you figure it out on your own, you can submit it for a bit of extra credit.
• HW 4: Continuous random variables: 8.4, 8.5, 8.9, 8.10, 9.7, 9.10, 9.12, 9.15, 9.16 -- Due 1 p.m. 2/18.
• HW 5 (very short): Normal and Pareto distributions: 9.3, 10.4, 11.1, 11.6 -- Due 1 p.m. 2/25.
• You do not need Mathematica for 11.6. Just do it by hand.
• HW 6 (bit short): Laplace transforms and Simulation: 12.4, 12.7, 12.8, 12.9, 12.11, 13.4, 13.6 -- Due 5 p.m. THURS 3/3.
• Optional fun problem from a real interview: 12.10.
• Problem 12.9: No, you do not have to do it without transforms. Transforms are key to making this kind of analysis easy.
• Problem 13.6: Remember to write out your explicit algorithm.
• HW 7: Tail Bounds: 14.3, 14.6, 14.7, 14.9, 14.10, 14.11, 14.12, 14.13, 14.15 (Note: if you want to get ahead, you can also do 14.17, which will be part of your next homework. -- Due 1 p.m. 3/18.
• In general, all the problems in Chpt 14 are relevant, so you may want to do additional problems to get more practice.
• Problem 14.6(d): For E[X], feel free to use the asymptotic mean that you computed in part (a).
• HW 8: Balls-n-Bins: 14.17, 14.18, 15.1, 15.3, 16.1, 16.2, 16.4. -- Due 1 p.m. 3/25. Optional Extra Credit: 14.19
• 14.18 (b) : You can use words. Just explain in words why each side implies the other.
• 16.4(a): Look for e^{-1} in your expression. Think about what Chpt 2 tells us about expressing e^{-1} as a limit.
• HW 9: Randomized Algorithms: 17.5, 17.6, 17.9, 17.12, 17.13, 18.1, 18.5, 18.6, 18.7, 18.11 -- Due 1 p.m. 4/1.
• Problem 17.6: Your final expression should be simple.
• Problem 17.9: To get E[X_{ij}], you only need to look at the most recent access to an element in the set S = {a_i, a_j}. If the most recent access to an element in S was to a_i, then you know that ...
• Problem 17.12(b)(iii): Let i be an arbitarily chosen node. You are simply trying to show that Pr{root-to-leaf path ending in node i has length >= 6g} <= 1/n^2. This is what you will need for part (c).
• Problem 18.6: This problem will be a lot easier if you (equivalently) define A_i to be the event that cut-set S_i is output. For part (b), using this equivalent definition, what do you know about the intersection of A_i and A_j?
• Problem 18.6(b): The probability of the union event is <= 1, because the probability of any event is <=1.
• HW 10: DTMCs: 20.2, 20.4, 20.5, 20.6, 20.7, 20.8, 20.10, 21.4, 21.6 -- Due 1 p.m. 4/15.
• Problem 20.4 -- Just find a single stationary distribution. You do not need to prove that it is the unique stationary distribution.
• Problem 20.8 -- To answer the question, use the stationary distribution.
• Problem 21.4 -- It will help simplify your result if you define rho = r/s. Now try to express pi_i as some function of \rho multiplied by pi_0.
• HW 11: Ergodicity: 21.1, 21.2, 21.5, 21.7, 21.11, 21.12, 21.13, 21.14, 21.15 -- Due 1 p.m. 4/22.
• Problem 21.11 Note that the graph is connected, as stated in the problem. In a connected graph, there is a *path* between any pair of vertices, i and j. If there is an edge connecting a particular pair of vertices, i and j, then w_{ij} > 0. If there is no edge connecting a particular pair of vertices, i and j, then w_{ij} = 0.
• HW 12: Infinite-state DTMCs + Queues: 22.2, 22.3, 22.4, 22.5, 22.8, 22.15, 22.18, 23.2, 23.4, 23.6 -- Due 1 p.m. 4/29. Optional Extra Credit: 22.21. You can skip writing up any ONE problem, but you need to clearly mark the problem that you're skipping (so we don't grade it), and you're still responsible for knowing how to solve all the problems.
• Problem 22.21: In this problem, we use the term "balance equations." These are very similar to stationary equations, but they equate the total rate of leaving a state to the total rate of entering the state. They end up being a touch simpler than stationary equations, but almost identical.