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.)