Topics

- Sections: 3.3, 3.4, 4.3, 5.6
- Notes: Expectation, Variance, First-moment method, Second-moment method
- Homework Problems: HW2: 1-6, 8-9.
- Definitions and Theorems:
- Expectation
- Properties of Expectation
- Variance
- Higher Moments
- Markov's Inequality
- Chebyshev's Inequality
- First-moment method
- Second-moment method
- Covariance
- Correlation
- Indicator Random Variables
- Expectation and Variance of Counting Random Variables

- Sample Questions:
- Let p be a uniform [0,1] rv, then let X ~ Bin[n,p]. What is cov(X,p)?
- Let Omega be a disc around the orgin in the plane of area 1, and let P be the Lebesgue measure. Let X be the x-coordinate of an outcome, and R the distance from the origin. Are X and R independent? What is their covariance?
- Find a sharp threshold for the longest sequence of consecutive heads in n flips of a fair coin.
- Give an analogue of Chebyshev's Inequality if we know the expectation of Exp[ \lambda X].
- Find the asymptotics of the maximum of n independent normal RV's.
- Prove that whp a simple symmetric random walk will not cross 0 between steps n and n+n^{1/3}.
- Prove the Weak Law of Large Numbers.
- Should positive correlation between random variables lead to greater or lesser concentration of their sum? Why?
- Throw m balls into n bins at random. What is the covariance of the number of balls that land in bin 1 and bin 2? What is the expected number of empty bins? What is the variance of the number of emprty bins?