Topics

- Sections: 5.11
- Notes: Poisson Convergence , Large Deviations
- Homework Problems: HW 5: 1,2,3,6
- Definitions and Theorems:
- Method of Moments for Poisson Distribution
- Chen-Stein Method with Dependency Graphs
- Total Variation Distance
- Large Deviation Rate Function
- Chernoff Bound (and proof)
- Exponential Markov Inequality

- Sample Questions:
- Prove a Chernoff bound for the sum of iid Uniform [0,1] RV's.
- Give an example of a RV that doesn't have a Normal-like Chernoff bound - i.e., the decay rate is not exponentially small.
- Show that the number of fixed points in a random permutation on n elements has a Poisson distribution in the limit as n-> infty.
- In a balls and bins model, find m=m(n) so that the number of bins with exactly one ball follows a Poisson distribution with mean 1, as n-> infty.
- Using a Chernoff bound find a good upper bound on the maximum pairwise dot product in a collection of m random vectors of length n, each of whose entries are +-1 with probability 1/2.
- Say there are 1000 car accidents per year on average in Atlanta. What would be a good rough guess for the probability that on a given day there are no accidents?