Hostname: page-component-cd9895bd7-p9bg8 Total loading time: 0 Render date: 2024-12-25T13:31:03.098Z Has data issue: false hasContentIssue false
  • English
  • Français

A large deviations heuristic made precise

Published online by Cambridge University Press:  01 May 2000

NEIL O'CONNELL
NEIL O'CONNELL
Affiliation:
BRIMS, Hewlett–Packard Laboratories, Bristol BS34 8QZ. e-mail: [email protected]
Get access Rights & Permissions [Opens in a new window]

Abstract

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.

Type
Research Article
Information
Mathematical Proceedings of the Cambridge Philosophical Society , Volume 128 , Issue 3 , May 2000 , pp. 561 - 569
Copyright
The Cambridge Philosophical Society 2000

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)