Jump to content

Sanov's theorem

From Wikipedia, the free encyclopedia

In mathematics and information theory, Sanov's theorem gives a bound on the probability of observing an atypical sequence of samples from a given probability distribution. In the language of large deviations theory, Sanov's theorem identifies the rate function for large deviations of the empirical measure of a sequence of i.i.d. random variables.

Let A be a set of probability distributions over an alphabet X, and let q be an arbitrary distribution over X (where q may or may not be in A). Suppose we draw n i.i.d. samples from q, represented by the vector xn=(x1,x2,
,xn). Then, we have the following bound on the probability that the empirical measure p̂xn of the samples falls within the set A:

qn(p̂xn∈A)≀(n+1)|X|2−nDKL(p∗||q),

where

  • qn is the joint probability distribution on Xn, and
  • p∗ is the information projection of q onto A.
  • DKL(P‖Q), the KL divergence, is given by: DKL(P‖Q)=∑x∈𝒳P(x)log⁥P(x)Q(x).

In words, the probability of drawing an atypical distribution is bounded by a function of the KL divergence from the true distribution to the atypical one; in the case that we consider a set of possible atypical distributions, there is a dominant atypical distribution, given by the information projection.

Furthermore, if A is a closed set, then

limn→∞1nlog⁥qn(p̂xn∈A)=−DKL(p∗||q).

Technical statement

[edit]

Define:

  • ÎŁ is a finite set with size ≄2. Understood as “alphabet”.
  • Δ(ÎŁ) is the simplex spanned by the alphabet. It is a subset of ℝΣ.
  • Ln is a random variable taking values in Δ(ÎŁ). Take n samples from the distribution ÎŒ, then Ln is the frequency probability vector for the sample.
  • ℒn is the space of values that Ln can take. In other words, it is

{(a1/n,
,a|Σ|/n):∑iai=n,ai∈ℕ}Then, Sanov's theorem states:[1]

  • For every measurable subset S∈Δ(ÎŁ),−infΜ∈int(S)D(Μ‖Ό)≀lim infn1nln⁥PÎŒ(Ln∈S)≀lim supn1nln⁥PÎŒ(Ln∈S)≀−infΜ∈cl(S)D(Μ‖Ό)
  • For every open subset U∈Δ(ÎŁ),−limnlimΜ∈U∩ℒnD(Μ‖Ό)=limn1nln⁥PÎŒ(Ln∈S)=−infΜ∈UD(Μ‖Ό)

Here, int(S) means the interior, and cl(S) means the closure.

References

[edit]
  1. ↑ Dembo, Amir; Zeitouni, Ofer (2010). "Large Deviations Techniques and Applications". Stochastic Modelling and Applied Probability. 38: 16–17. doi:10.1007/978-3-642-03311-7. ISBN 978-3-642-03310-0. ISSN 0172-4568.{{cite journal}}: CS1 maint: periodical has ISBN (link)

Further reading

[edit]
  • Sanov, I. N. (1957) "On the probability of large deviations of random variables". Mat. Sbornik 42(84), No. 1, 11–44.
  • ĐĄĐ°ĐœĐŸĐČ, И. Н. (1957) "О ĐČĐ”Ń€ĐŸŃŃ‚ĐœĐŸŃŃ‚Đž Đ±ĐŸĐ»ŃŒŃˆĐžŃ… ĐŸŃ‚ĐșĐ»ĐŸĐœĐ”ĐœĐžĐč ŃĐ»ŃƒŃ‡Đ°ĐčĐœŃ‹Ń… ĐČĐ”Đ»ĐžŃ‡ĐžĐœ". МАбЕМАбИЧЕСКИЙ СБОРНИК 42(84), No. 1, 11–44.