Sanov's Theorem and Chernoff bound

Question

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?

Answer 1

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": Link , which also contains (when you reduce it to its essence) a beautifully short and elegant proof.

Answer 2

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!

Answer 3

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.