HP Labs Technical Reports

A Large Deviations Heuristic Made Precise

O'Connell, Neil

HPL-BRIMS-98-10

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.

10 Pages

Back to Index