Sanov's Theorem (p.292, Thomas/Cover "Elements of Information Theory" (1991)) says that probability of a hypothesis $E$ according to distribution $Q$ is bounded above by

$$(n+1)^k \exp (-n D(P^* \|Q) )$$ where $D$ is KL-divergence, $k$ is the size of sample space and $P^*$ is an element of $E$ closest to $Q$ according $D(\cdot\|Q)$.

This bound is quite loose for small $n$ because when $k=2$ and $E$ is simply connected, Chernoff's bound tells us that the probability is at most the following

$$\exp (-n D(P^* \|Q) )$$

Is there a natural restriction of $E$ that makes the bound above generalize to $k>2$? Alternatively, is there a natural restriction of $E$ and a modification of Sanov's theorem that gives it a similar level of tightness to Chernoff's bound for small n?

  • $\begingroup$ I don't understand the question and I am sure your can improve the formulation. What is "the probability of a hypothesis" ? What do you mean by "When our hypothesis is of the form "sample mean is greater than..." ? E is a finite set of probabilities? You said "it seems that the sufficient condition for the bound to hold is that "... which bound are you talking about ? it seems it was a limit ? I guess the 5 people that found this question "usefull and clear" could also answer the comment :) $\endgroup$ – robin girard Aug 17 '10 at 13:21
  • $\begingroup$ I'm asking when the limit also serves as a bound. Hypothesis E is a set of events. Concrete example of E for which this holds is given by Chernoff's bound (additive form). For instance, if you toss a coin n times, your hypothesis may be that it landed heads less than n/2 times, for which the bound holds. I imagine it's easier to only look at finite E, but maybe not $\endgroup$ – Yaroslav Bulatov Aug 17 '10 at 16:37

There is a way to get the tighter bounds you mention.

Consider the following : Let $E\in\mathcal{X}^k$ be an arbitrary set and let $Q$ be some distribution on $\mathcal{X}$. Then, the following "non-typewise'' bound holds : $$Q^k(E) \leq \exp\left(-kD(P\Vert Q)\right)$$ where $P(a) := \sum_{x^k\in E}\frac{Q(x^k)}{Q(E)}P_{x^k}(a)$ for all $a\in\mathcal{X}$ (and of course $P_{x^k}(a)$ is the type of the sequence $x^k$). See Problem 7 in Chapter 2 of Csiszar & Korner's Book for a reference (and for a hint on proving this result).

So, it is not hard to see that if $E$ is a convex set of distributions, then the polynomial factor in front of the exponent can be dropped.


For convex sets E of probability measures, the bound you want (i.e., probability of empirical measure being in E is smaller than $e^{-nD(E\|Q)}$) is true in great generality, not just for finite alphabet settings. This is contained, for instance, in the spectacular 1984 paper of Csiszar titled "Sanov Property, Generalized $I$-Projection and a Conditional Limit Theorem": http://projecteuclid.org/DPubS?service=UI&version=1.0&verb=Display&handle=euclid.aop/1176993227 , which also contains (when you reduce it to its essence) a beautifully short and elegant proof.

  • 1
    $\begingroup$ Thanks for reference! I wonder why Shanon/Cover give the looser bound if polynomial term can be dropped $\endgroup$ – Yaroslav Bulatov Apr 27 '11 at 5:31

You don't need to restrict yourself to finite $E$ -- you get it for any set $E$ of distributions. In hypothesis testing people often take $E$ to be come convex set of distributions.

[added after comment]: I think the question is confusingly stated. The probability being calculated is not the probability of a hypothesis per se. Cover and Thomas simplify the notation a bit. let $X^n = (X_1, \ldots, X_n)$ be drawn i.i.d. according to $Q$ on a finite set $\mathcal{X}$. Let $E$ be any set of distributions. Let $T_{X^n}$ be the empirical distribution of $X_1, \ldots, X_n$. Sanov's Theorem says:

$\mathbb{P}( \{ X^n : T_{X^n} \in E \} ) \le (n+1)^{|\mathcal{X}|} \exp( -n \cdot \min_{P \in E} D(P \| Q) )$

This bound holds for any $n$, but is only optimal asymptotically as $n \to \infty$. That is, the exponent won't be better than this divergence. For smaller $n$ you can get better bounds, especially if you can get rid of that polynomial factor. The looseness in Sanov's theorem as stated is mostly in this polynomial factor -- if $E$ is a singleton, then if you inspect the proof you see that you don't need that factor.

To take an example from coin tossing, suppose $Q$ corresponds to a coin with bias $1/2$ (a fair coin) and let $E = \{ P : P(heads) \le 1/4 \}$. This is of the form "sample mean is less than 1/4" (if I understand your question). Your complaint would seem to be that as stated Sanov makes you account for coins with bias much less than 1/4, when in fact you can "get away" with only considering $P(heads) = 1/4$.

So if I understand your question now, the answer is : Sanov's theorem is loose because there is a union being taken over all distributions in $E$, but this looseness is mostly important for small $n$. The bound holds for all $n$ but for smaller $n$ you can get better bounds (e.g. Chernoff) by re-inspecting the proof of Sanov or through other methods. However, as $n \to \infty$ these bounds will not be better than Sanov's in terms of the exponent multiplying $-n$.

Hope that answers it!


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.