Chernoff-type inequality for random variable with 3 outcomes

Question

Suppose we have a random variable which takes non-numeric values a,b,c and want to quantify how empirical distribution of $n$ samples of this variable deviates from true distribution. The following inequality (from Cover & Thomas) applies in this case.

Theorem 12.4.1 (Sanov's theorem): Let $X_1, X_2, \ldots, X_n$ be i.i.d. $\sim Q(x)$.
Let $E \subseteq \mathscr{P}$ be a set of probability distributions. Then $$Q^n(E) = Q^n(E \cap \mathscr{P}_n) \leq (n+1)^{|\mathcal{X}|}2^{-nD(P^*||Q)},$$ where $$P^* = \arg\min_{P \in E} D(P||Q),$$ is the distribution in $E$ that is closest to $Q$ in relative entropy.

This inequality is quite loose for small $n$. For binary outcomes, $|\mathcal{X}|=2$, and Chernoff-Hoeffding bound is much tighter.

Is there a similarly tight bound for for $|\mathcal{X}|=3$?

Answer 1

You can get fairly good bounds by considering the random variable $Y_{ij}$ which is 1 if $X_i = j$ and zero otherwise (for $1 \le i \le n$ ranging over trials and $1 \le j \le 3$ ranging over categories). For any fixed $j$ the $Y_{ij}$ are independent and therefore $\sum_i Y_{ij}$ can be analyzed using Chernoff bounds. Then do a union bound over $j$.

If the above isn't enough I suggest that you look at the balls and bins model e.g. in Upfal and Mitzenmacher's textbook. That model is the same as yours except that some of your bins may be more likely than others to have balls land in them, right? There are some more sophisticated techniques involving Poisson approximations in that model that would likely be extendable to your setting with non-uniform bin probabilities.

Answer 2

There is nothing about Chernoff Hoeffding bounds that is specific to boolean variables. If $X_1,\ldots,X_n$ are i.i.d. real valued random variables with $0 \leq X_i \leq 1$ you can apply a Chernoff bound. A good reference is "Concentration of Measure for the Analysis of Randomized Algorithms" (http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&rep=rep1&type=pdf)