View source for Accuracy paradox

In [[mathematics]] &mdash; specifically, in [[large deviations theory]] &mdash; a '''rate function''' is a function used to quantify the [[probability|probabilities]] of rare events. It is required to have several properties which assist in the formulation of the '''large deviation principle'''.{{clarify|reason=large deviation principle redirects here but has no explanation/definition|date=June 2012}} In some sense, the large deviation principle is an analogue of [[Convergence of measures|weak convergence of probability measures]], but one which takes account of how well the rare events behave.

A '''rate function''' is also called{{who|date=June 2012}} a '''Cramér function''', after the Swedish probabilist [[Harald Cramér]].

==Definitions==

An [[extended real number line|extended real-valued]] function ''I''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;[0,&nbsp;+∞] defined on a [[Hausdorff space|Hausdorff]] [[topological space]] ''X'' is said to be a '''rate function''' if it is not identically +∞ and is [[lower semi-continuous]], i.e. all the sub-level sets

:<math>\{ x \in X | I(x) \leq c \} \mbox{ for } c \geq 0</math>

are [[closed set|closed]] in ''X''. If, furthermore, they are [[compact space|compact]], then ''I'' is said to be a '''good rate function'''.

A family of [[probability measure]]s (''&mu;''<sub>''&delta;''</sub>)<sub>''&delta;''&gt;0</sub> on ''X'' is said to satisfy the '''large deviation principle''' with rate function ''I''&nbsp;:&nbsp;''X''&nbsp;→&nbsp;[0,&nbsp;+∞) (and rate 1&nbsp;⁄&nbsp;''&delta;'') if, for every closed set ''F''&nbsp;⊆&nbsp;''X'' and every [[open set]] ''G''&nbsp;⊆&nbsp;''X'', 

:<math>\limsup_{\delta \downarrow 0} \delta \log \mu_{\delta} (F) \leq - \inf_{x \in F} I(x), \quad \mbox{(U)}</math>
:<math>\liminf_{\delta \downarrow 0} \delta \log \mu_{\delta} (G) \geq - \inf_{x \in G} I(x). \quad \mbox{(L)}</math>

If the upper bound (U) holds only for compact (instead of closed) sets ''F'', then (''&mu;''<sub>''&delta;''</sub>)<sub>''&delta;''&gt;0</sub> is said to satisfy the '''weak large deviation principle''' (with rate 1&nbsp;⁄&nbsp;''&delta;'' and weak rate function ''I'').

===Remarks===

The role of the open and closed sets in the large deviation principle is similar to their role in the weak convergence of probability measures: recall that (''&mu;''<sub>''&delta;''</sub>)<sub>''&delta;''&gt;0</sub> is said to converge weakly to ''&mu;'' if, for every closed set ''F''&nbsp;⊆&nbsp;''X'' and every [[open set]] ''G''&nbsp;⊆&nbsp;''X'', 

:<math>\limsup_{\delta \downarrow 0} \mu_{\delta} (F) \leq \mu(F),</math>
:<math>\liminf_{\delta \downarrow 0} \mu_{\delta} (G) \geq \mu(G).</math>

There is some variation in the nomenclature used in the literature: for example, den Hollander (2000) uses simply "rate function" where this article &mdash; following Dembo & Zeitouni (1998) &mdash; uses "good rate function", and "weak rate function".  Fortunately, regardless of the nomenclature used for rate functions, examination of whether the upper bound inequality (U) is supposed to hold for closed or compact sets tells one whether the large deviation principle in use is strong or weak.

==Properties==

===Uniqueness===

A natural question to ask, given the somewhat abstract setting of the general framework above, is whether the rate function is unique.  This turns out to be the case: given a sequence of probability measures (''&mu;''<sub>''&delta;''</sub>)<sub>''&delta;''&gt;0</sub> on ''X'' satisfying the large deviation principle for two rate functions ''I'' and ''J'', it follows that ''I''(''x'')&nbsp;=&nbsp;''J''(''x'') for all ''x''&nbsp;∈&nbsp;''X''.

===Exponential tightness===

It is possible to convert a weak large deviation principle into a strong one if the measures converge sufficiently quickly.  If the upper bound holds for compact sets ''F'' and the sequence of measures (''&mu;''<sub>''&delta;''</sub>)<sub>''&delta;''&gt;0</sub> is [[Tightness of measures#Exponential tightness|exponentially tight]], then the upper bound also holds for closed sets ''F''.  In other words, exponential tightness enables one to convert a weak large deviation principle into a strong one.

===Continuity===

Naïvely, one might try to replace the two inequalities (U) and (L) by the single requirement that, for all Borel sets ''S''&nbsp;⊆&nbsp;''X'',

:<math>\lim_{\delta \downarrow 0} \delta \log \mu_{\delta} (S) = - \inf_{x \in S} I(x). \quad \mbox{(E)}</math>

Unfortunately, the equality (E) is far too restrictive, since many interesting examples satisfy (U) and (L) but not (E).  For example, the measure ''&mu;''<sub>''&delta;''</sub> might be [[Atom (measure theory)|non-atomic]] for all ''&delta;'', so the equality (E) could hold for ''S''&nbsp;=&nbsp;{''x''} only if ''I'' were identically +∞, which is not permitted in the definition.  However, the inequalities (U) and (L) do imply the equality (E) for so-called ''I'''''-continuous''' sets ''S''&nbsp;&sube;&nbsp;''X'', those for which

:<math>I \big( \stackrel{\circ}{S} \big) = I \big( \bar{S} \big),</math>

where <math>\stackrel{\circ}{S}</math> and <math>\bar{S}</math> denote the [[interior (topology)|interior]] and [[closure (topology)|closure]] of ''S'' in ''X'' respectively.  In many examples, many sets/events of interest are ''I''-continuous.  For example, if ''I'' is a [[continuous function]], then all sets ''S'' such that

:<math>S \subseteq \bar{\stackrel{\circ}{S}}</math>

are ''I''-continuous; all open sets, for example, satisfy this containment.

===Transformation of large deviation principles===

Given a large deviation principle on one space, it is often of interest to be able to construct a large deviation principle on another space.  There are several results in this area:

* the [[Contraction principle (large deviations theory)|contraction principle]] tells one how a large deviation principle on one space "[[push forward|pushes forward]]" to a large deviation principle on another space ''via'' a [[continuous function]];

* the [[Dawson-Gärtner theorem]] tells one how a sequence of large deviation principles on a sequence of spaces passes to the [[projective limit]].

* the [[tilted large deviation principle]] gives a large deviation principle for integrals of exponential [[functional (mathematics)|functional]]s.

* [[exponentially equivalent measures]] have the same large deviation principles.

==History and basic development==
The notion of a rate function began with the Swedish mathematician [[Harald Cramér]]'s study of a sequence of '''[[i.i.d.]]''' random variables (''Z''<sub>''i''</sub>)<sub>i∈ℕ</sub> at the time of the [[Great Depression]].  Namely, among some considerations of scaling, Cramér studied the behavior of the distribution of <math>X_n=\frac 1 n \sum_{i=1}^n Z_i</math> as ''n''→∞.<ref>{{cite journal|last=Cramér|first=Harald|title=Sur un nouveau théorème-limite de la théorie des probabilités|journal=Colloque consacré à la théorie des probabilités, Part 3, Actualités scientifiques et industrielles|volume=731|year=1938|pages=5–23|language=French}}</ref>  He found that the tails of the distribution of ''X''<sub>''n''</sub> decay exponentially as ''e''<sup>−''nλ''(''x'')</sup> where the factor ''λ''(''x'') in the exponent is the [[Legendre transform]] (a.k.a. the [[convex conjugate]]) of the [[cumulant]]-generating function <math>\Psi_Z(t)=\log \mathbb E e^{tZ}.</math>  For this reason this particular function ''λ''(''x'') is sometimes called the '''Cramér function'''.  The rate function defined above in this article is a broad generalization of this notion of Cramér's, defined more abstractly on a [[probability space]], rather than the [[state space]] of a random variable.

== See also ==
* [[Extreme value theory]]{{clarify|reason=how is this related per [[WP:SEEALSO]]|date=June 2012}}

{{more footnotes|date=June 2012}}

==References==
<references/>

* {{cite book
| last= Dembo
| first = Amir
| coauthors = Zeitouni, Ofer
| title = Large deviations techniques and applications
| series = Applications of Mathematics (New York) 38
| edition = Second edition
| publisher = Springer-Verlag
| location = New York
| year = 1998
| isbn = 0-387-98406-2
| nopp= true
| page = xvi+396
}} {{MathSciNet|id=1619036}}
* {{cite book
| last = den Hollander
| first = Frank
| title = Large deviations
| series = [[Fields Institute]] Monographs 14
| publisher = [[American Mathematical Society]]
| location = Providence, RI
| year = 2000
| isbn = 0-8218-1989-5
| page = x+143
}} {{MathSciNet|id=1739680}}

[[Category:Asymptotic analysis]]
[[Category:Large deviations theory]]