When does the following hold?

$\sum_{(i_1,\ldots,i_k)\in E}
\frac{n!}{i_1! \ldots i_k!}
\le  \exp(n H^*)$

Where

$H^*=\max_{(i_1,\ldots,i_k)\in E} -(\frac{i_1}{n}\log \frac{i_1}{n}+\ldots +\frac{i_k}{n}\log \frac{i_k}{n})$ and E is some subset of {$ \{( i_1,\ldots,i_k):i_1+\ldots+i_k=n \}$}

Motivation: this is a generalization of Chernoff's bound to n tosses of fair k-sided dice where E represents the hypothesis we make about that sample. Another motivation is reconciling tight special-case <a href="http://en.wikipedia.org/wiki/Chernoff_bound#Theorem_for_additive_form_.28absolute_error.29">Chernoff bound</a> with looser but more general bound given by <a href="http://yaroslavvb.com/upload/sanovs.png">Sanov's theorem</a>

Examples: when k=2, it can be proven to hold for sets of coefficients where first component of the coefficient is less than n/2 (ie <a href="http://yaroslavvb.com/upload/binomial.png">here</a>).

When k=3, it seems (empirically) to hold for sets of coefficients where sum of first two components is &le;n/2. For instance, for n=10, highest entropy term gives upper bound of (2/3)^3 *10^5 whereas exact sum is 12585. Since k=3 multinomial coefficients lie in a 2-simplex, the 21 multinomial coefficients in this set can be visualized below. Top vertex represents coefficient (0,0,10)

<img src="http://yaroslavvb.com/upload/multinomials.png">

For higher k, we can look at similar sets, ie corners of the (k-1) simplex. I tried few values and it seems to hold for coefficients where sum of first k-1 components is below n/(k-1)

Here's how you'd check it in Mathematica
<pre>
getit[n_, k_, c_] := (
   all = Select[Tuples[Range[0, n], k], Total[#] == n &];
   e = Select[all, Total[Most[#]] &lt;= c &];
   hterm[x_] := If[0 &lt; x &lt; 1, x Log[x], 0];
   H[event_] := -Total[hterm /@ (event/n)];
   exact = Total[Multinomial @@@ e];
   upper = Exp[n Max[H /@ e]];
   exact &lt; upper
);
(* Check bound for k=3, n=10, with i1+i2&lt;=5 *)
getit[10, 3, 5]
</pre>

<b>Update 8/18</b>
Leandro gives a bound on a single multinomial coefficient which gives <a href="http://yaroslavvb.com/upload/sanovs.png">Sanov's theorem</a> if we consider that there's at most $(n+1)^k$ multinomial coefficients in any set E. It seems that to generalize the <a href="http://yaroslavvb.com/upload/binomial.png">proof</a> of the tighter binomial bound to, say, trinomial coefficients, one would need to prove the following inequality first

$$p_1 \log q_1 + p_2 \log q_2 + p_3 \log q_3 \ge q_1 \log q_1 + q_2 \log q_2 + q_3 \log q_3$$

Where p and q add up to 1. For each q, the set of p's for which the above bound holds also gives us the hypothesis for which we can give tight Chernoff-like bound. Empirically, this bound seems to hold for p's "bounded away" from the uniform distribution. Black circle below represents q, blue region is the set of distributions p where the bound above holds. My Mathematica <a href="http://yaroslavvb.com/research/qr/mo-multinomials/mo-multinomials.nb">notebook</a>

<img src="http://yaroslavvb.com/upload/cross-entropy-bound.png">

<b> Update 8/24</b>: the bound holds for sets of coefficients of the form $i_1 a_1 + \ldots + i_n a_n \le C$ where $a_1\ldots a_n$ are arbitrary non-negative numbers