HP Labs Technical Reports
Click here for full text:
A Large Deviations Heuristic Made Precise
Keyword(s): Sanov's theorem; Monge; Kantorovich; Ornstein; Azuma's inequality; extended contraction principle; bin- packing
Abstract: Sanov's theorem states that the sequence of empirical measures associated with a sequence of iid random variables satisfies the large deviation principle (LDP) in the weak topology with rate function given by a relative entropy. We present a derivative which allows one establish LDP's for symmetric functions of many iid random variables under the condition that (i) a law of large numbers holds whatever the underlying distribution and (ii) the functions are uniformly Lipschitz. This heuristic (of the title) is that the LDP follows from (i) provided the functions are "sufficiently smooth". As an application, we obtain large deviations results for the stochastic bin- packing problem.
Back to Index