Desigualdade do tipo Chernoff para variável aleatória com 3 resultados

Suponha que tenhamos uma variável aleatória que aceite valores não numéricos a, b, ce queira quantificar como a distribuição empírica de $n$ amostras dessa variável se desvia da distribuição verdadeira. A seguinte desigualdade (da Cover & Thomas ) se aplica neste caso.

Teorema 12.4.1 (Teorema de Sanov): Seja iid ∼ Q ( x ) . Seja E ⊆ P um conjunto de distribuições de probabilidade. Então Q n ( E ) = Q n ( E ∩ P n ) ≤ ( n + 1 ) | X | 2 - n D ( P ∗ $X_1, X_2, \ldots, X_n$$\sim Q(x)$
$E \subseteq \mathscr{P}$ ondeP∗=arg min P ∈ E D(P||Q), é a distribuição emEmais próxima deQna entropia relativa.

$$Q^n(E) = Q^n(E \cap \mathscr{P}_n) \leq (n+1)^{|\mathcal{X}|}2^{-nD(P^*||Q)},$$ $$P^* = \arg\min_{P \in E} D(P||Q),$$ $E$$Q$

Essa desigualdade é bastante frouxa para pequenos . Para resultados binários, | X | = 2 , e o limite de Chernoff-Hoeffding é muito mais restrito.$n$$|\mathcal{X}|=2$

Existe um limite igualmente rígido para ?$|\mathcal{X}|=3$

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.

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)