Large Deviations and Poisson Convergence

MATH 6221

Spring 2013

Skiles 169

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


Will Perkins

Office: Skiles 017

  • 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?