date 
lecture 
topics 
readings 
assignments 
1/19 (Tues) 
1: Introduction

 why we study probability
 set theory (review)
 class organization

C&D: preface


1/20 (Fri) 
2: Sample Spaces and Events

 finish set theory (cartesian products))
 sample spaces for experiments
 events and operations on events

C&D: 1.1

HW1 out

1/24 (Tues) 
3: Begin Counting

 multiplication principle
 tree diagrams
 sampling with and without replacement
 counting the compliment (the birthday problem)

C&D: 1.3 through 1.3.3

HW2 out

1/27 (Fri) 
4: Overcounting and Binomial Coefficients

 permutations, factorial notation
 overcounting and correcting for it (ex: arranging letters of a word with reptitions)
 binomial coefficients (combinations)
 poker hands and other applications

C&D: 1.3.4

Q1; HW1 due

1/31 (Tues) 
5: More Complex Counting

 poker hands, with decision processes and trees
 recognizing overcounting errors: twoparis versus full houses
 NewtonPepys dice problem (counting compliment, decision process)

B&H scan on Sakai

HW2 due; HW3 out

2/3 (Fri) 
6: Overcounting as a problemsolving tool

 breaking into groups (overcounting again)
 arrangement when some items repeat (arranging letters of a word)

B&H scan on Sakai

Q2

2/7 (Tues) 
7: BoseEinstein; InclusionExclusion

 BoseEinstein and when to use it
 inclusionexclusion: unions of 2 and 3 sets

B&H scan on Sakai

HW3 due; HW4 out

2/10 (Fri) 
8: InclusionExclusion

 discussion of quiz
 inclusionexclusion for many sets
 applications to several problems

B&H scan on Sakai

Q3

2/14 (Tues) 
9: Story Proofs and Midterm 1 review

 story proofs, with examples
 solved practice midterm

B&H scan on Sakai

HW4 due

2/17 (Fri) 
10: Midterm 1




2/21 (Tues) 
11: General probability

 axioms of probability
 consequences of the axioms, with proofs
 definition of conditional probability

C&D: 1.2, 1.4.1

HW5 out

2/24 (Fri) 
12: Conditional probability

 more on conditional probability intuition
 solving problems with conditional probability
 Bayes's theorem
 law of total probability (LOTP)

C&D: 1.4


2/28 (Tue) 
13: Monty Hall; Independence of events

 the Monty Hall problem
 definition of independent events

C&D: 1.5, 1.5.1

Q4, HW5 due

3/3 (Fri) 
14: Pairwise vs Mutual Independence

 definition of pairwise and kwise independent events
 definition of mutually independent events

C&D: 1.5.2

HW6 out

3/7 (Tues) 
15: Conditional Probability as
a Valid Probability; Conditional Independence

 how to use conditional probability to obtain a new valid probability
measure
 conditional independence

B&H scan 2 on Sakai


3/10 (Fri) 
16: Simpson's Paradox; Random Variables 
 Simpson's paradox and the example of university admissions
 definition of a random variable
 distribution of a random variable
 different random variables with the same distribution
 Bernoulli random variables

B&H scan 2 on Sakai for Simpson's;
C&D: 2.1, 2.2 up to 2.2.2

HW6 due

3/21 (Tues) 
17: Binomial and Hypergeometric distributions 
 review of random variable concepts, including support
 Bernoulli random variables
 Binomial distribution: story, parameters, intuition
 Binomial distribution: formula for pmf
 Hypergeometric distribution: story, parameters, intuition

C&D: 2.1, 2.2 up to 2.2.2, 2.4, 2.6.1 up to the proposition.
(we will cover 2.3 later)

HW7 out

3/24 (Fri) 
18: Functions of One or More Random Variables 
 functions h(X) of a r.v. like X, X^2, etc
 the distribution of h(X) versus X
 functions of two random variables ike X+Y
 distribution of X+Y versus X and Y

C&D does not cover these topics in one place 
Q5

3/28 (Tue) 
19: Independence of Random Variables; Expectation 
 joint distribution of r.v.s X and Y
 definition on independence of r.v.s
 definition expectation of a r.v.

C&D: 4.1.1, 2.3 
HW7 in; HW8 out

3/31 (Fri) 
20:
Shortcuts for computing expectation 
 LOTUS: easier formula for E(h(X))
 Linearity of expectation: E(X+Y) = E(X) + E(Y)
 Applications, including expectation of a binomial

C&D: 2.3.2 
HW8 in

4/4 (Tues) 
21:
Midterm 2 



4/4 (Tues) 
22:
Geometric and Negative Binomial 
 Story, support, and distribution of geometric
 Story, support, and distribution of negative binomial
 Expectation of geometric (calculus)
 Expectation of negative binomial (linearity)

C&D: 2.6.2


4/11 (Tues) 
23: Indicator Method

 indicator random variables
 the indicator method for computing expectation
 when to try indicators, tricks including symmetry and ignoring
dependence
 examples: empty hash table bins, HTH problem, birthday collisions

B&H scan 3 on Sakai

HW9 out

4/14 (Fri) 
24: Variance

 intuition for variance
 why average squared distance
 definition of variance (and standard deviation), variance of bernoulli
 alternative formula for variance
 properties: Var(X + Y) versus Var(X) + Var(Y), Var(cX), Var(c).

B&H scan 3 on Sakai.
C&D 2.3.3.


4/18 (Tue) 
25: Concentration Inequalities

 Markov's inequality (with proof)
 Chebyshev's inequality (with proof)
 Chernoff's inequality
 statement and how to apply each

lecture 25 notes (scan) on Sakai.


4/21 (Fri) 
26: Law of Large Numbers; Probabilistic Method

 statement, intuition, and proof of law of large numbers
 probabilistic method intuition and template

 probabilistic method examples: circle problem, committee problem,
exam problem

C&D 4.5.4;
B&H scan 4 on Sakai.

HW9 in; HW10 out

4/25 (Tue) 
27: Markov Chains

 intuition for Markov chains
 state space, state diagram, transition probabilities
 transition probabilities in a matrix
 multistep transitions probabilities and matrix multiplication

C&D 6.1, 6.2


4/28 (Fri) 
28: Regular Markov Chains and the Steady State Theorem

 initial distributions as vectors
 regular Markov chains
 longterm behavior of chains: convergence, periodicity, or something else
 the steady state theorem
 application to google pagerank

C&D 6.3, 6.4

HW10 in
