# Chernoff-type inequality for random variable with 3 outcomes

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$?

• I believe you can change |X| to |X|-1, because the "last type", in the methods og types, is given once you know the rest. – Thomas Ahle Jul 27 '17 at 10:25

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$.
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)