| 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: two-paris versus full houses
- Newton-Pepys dice problem (counting compliment, decision process)
|
B&H scan on Sakai
|
HW2 due; HW3 out
|
| 2/3 (Fri) |
6: Overcounting as a problem-solving 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: Bose-Einstein; Inclusion-Exclusion
|
- Bose-Einstein and when to use it
- inclusion-exclusion: unions of 2 and 3 sets
|
B&H scan on Sakai
|
HW3 due; HW4 out
|
| 2/10 (Fri) |
8: Inclusion-Exclusion
|
- discussion of quiz
- inclusion-exclusion 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 k-wise 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
- multi-step 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
- long-term behavior of chains: convergence, periodicity, or something else
- the steady state theorem
- application to google pagerank
|
C&D 6.3, 6.4
|
HW10 in
|