Hostname: page-component-7b7567c8c-tnkh4 Total loading time: 0 Render date: 2026-11-17T07:52:01.982Z Has data issue: false hasContentIssue false

A large deviations heuristic made precise

Published online by Cambridge University Press:  01 May 2000

NEIL O'CONNELL
Affiliation:
BRIMS, Hewlett–Packard Laboratories, Bristol BS34 8QZ. e-mail: noc@hplb.hpl.hp.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

Sanov's Theorem states that the sequence of empirical measures associated with a sequence of i.d.d. 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 to establish LDPs for symmetric functions of many i.d.d. random variables under the condition that (i) a law of large numbers holds whatever the underlying distribution and (ii) the functions are uniformly Lipschitz. The 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.

Information

Type
Research Article
Copyright
The Cambridge Philosophical Society 2000