<p>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$.</p>

<p>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.</p>

CC BY-SA 2.5
2010-10-13T17:35:27.013Z
2010-10-13T17:35:27.013Z
Warren Schudy
<p>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" (<a href="http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&amp;rep=rep1&amp;type=pdf" rel="nofollow">http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&amp;rep=rep1&amp;type=pdf</a>) </p>

CC BY-SA 2.5
2010-10-13T16:56:43.197Z
I'm interested in categorical rather than real-valued variables, added a clarification
Yaroslav Bulatov
CC BY-SA 2.5
2010-10-13T16:42:16.100Z
2010-10-13T16:42:16.100Z
Aaron Roth
<p>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 <a href="http://rads.stackoverflow.com/amzn/click/0471062596" rel="nofollow noreferrer">Cover &amp; Thomas</a>) applies in this case. </p>

<blockquote>
  <p>Theorem 12.4.1 (Sanov's theorem): Let $X_1, X_2, \ldots, X_n$ be i.i.d. $\sim Q(x)$.<br>
  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.</p>
</blockquote>

<p>This inequality is quite loose for small $n$. For binary outcomes, $|\mathcal{X}|=2$, and <a href="http://hunch.net/?p=1491" rel="nofollow noreferrer">Chernoff-Hoeffding</a> bound is much tighter. </p>

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

CC BY-SA 3.0
2017-07-27T10:25:20.737Z
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
<pr.probability><chernoff-bound>
Chernoff-type inequality for random variable with 3 outcomes
Yaroslav Bulatov
# Chernoff-type inequality for random variable with 3 outcomes

(Asked by: username_0 on 2010-10-13)

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](http://rads.stackoverflow.com/amzn/click/0471062596)) 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](http://hunch.net/?p=1491) bound is much tighter.

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

**Tags:** pr.probability, chernoff-bound
> **Comments:**
> **username_1**: 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.  

---

## 2 answers

### Answer by username_2 on 2010-10-13. Score: 6 | Accepted answer

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 by username_3 on 2010-10-13. Score: 3

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

> **Comments:**
> **username_0**: I'm interested in categorical rather than real-valued variables, added a clarification  

---

