# Large Deviations and Poisson Convergence

### Spring 2013

#### T / Th, 4:35 - 5:55 pm

Instructor

Will Perkins

wperkins3@math.gatech.edu

Office: Skiles 017

Topics
• Sections: 5.11
• Notes: Poisson Convergence , Large Deviations
• Homework Problems: HW 5: 1,2,3,6
• Definitions and Theorems:
1. Method of Moments for Poisson Distribution
2. Chen-Stein Method with Dependency Graphs
3. Total Variation Distance
4. Large Deviation Rate Function
5. Chernoff Bound (and proof)
6. Exponential Markov Inequality
• Sample Questions:
1. Prove a Chernoff bound for the sum of iid Uniform [0,1] RV's.
2. Give an example of a RV that doesn't have a Normal-like Chernoff bound - i.e., the decay rate is not exponentially small.
3. Show that the number of fixed points in a random permutation on n elements has a Poisson distribution in the limit as n-> infty.
4. 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.
5. 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.
6. 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?