# DMMR: Study guide for Chapter 7 of the textbook by K. Rosen

## STUDY ALL SECTIONS OF THIS CHAPTER

#### Key concepts. (This is not a complete list of all the content.)

• Section 7.1: this section gives an introduction to discrete probability via Laplace's restricted model where all outcomes in the sample space are always equally likely; it should be read for building intuition, but we started directly on the general notion of a sample space and probability distribution, as described starting in section 7.2;
• Section 7.2: Discrete Probability: finite or countable sample spaces; probability distribution on a sample space; Events (subsets of sample spaces) and their probability; Probabilities of complements and (finite or countable) unions of events; conditional probability; Independence of two events; pairwise and mutual independence of more than 2 events; Bernoulli trials and the binomial distribution; Random variables; Examples: the birthday problem, the probabilistic method and Ramsey numbers;
• Section 7.3: Bayes' Theorem, and Generalized Bayes' Theorem; Applications of Bayes' Theorem and Generalized Bayes' Theorem: computing conditional probabilities; Examples of applications (rudimentary spam filters)
• Section 7.4: Random variables, Expectation, and Variance: the expected value of a random variable; expectations for random variables with key distributions, like binomially distributed random variables and geometrically distributed random variables; Linearity of Expectation, and its applications; (we skipped the discussion of average-case computational complexity); The geometric distribution; Independent random variables and their basic properties; Variance and Standard Deviation of a random variable; Chebyshev's Inequality and Markov's inequality (Markov's inequality was covered in class, but is only an exercise in the book); in class we very brief covered (without proof) more advanced deviation inequalities called Chernoff bounds;
Various Examples of problems in probability, including the birthday paradox, and examples of using of the probabilistic method for showing existence of combinatorial objects (lower bounds on Ramsey numbers);

#### Parts of Chapter 7 that were NOT covered in this course

Basically nothing. All of the chapter was covered and should be read. (We didn't really start, like the book does in section 7.1, by treating separately first the Laplace model of only equally likely outcomes. We just went straight to the more general model of a discrete (finite or countable) sample space and an arbitrary discrete probability distribution on it.)

 Informatics Forum, 10 Crichton Street, Edinburgh, EH8 9AB, Scotland, UK Tel: +44 131 651 5661, Fax: +44 131 651 1426, E-mail: school-office@inf.ed.ac.uk Please contact our webadmin with any comments or corrections. Logging and Cookies Unless explicitly stated otherwise, all material is copyright © The University of Edinburgh