Sanov's Theorem and Chernoff bound  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?
 A: 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.
A: 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. 
A: 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!
