Inégalité de type Chernoff pour variable aléatoire avec 3 résultats

Supposons que nous ayons une variable aléatoire qui prend des valeurs non numériques a, b, c et que nous voulons quantifier la façon dont la distribution empirique de échantillons de cette variable s'écarte de la vraie distribution. L'inégalité suivante (de Cover & Thomas ) s'applique dans ce cas.$n$

Théorème 12.4.1 (théorème de Sanov): Soit iid ∼ Q ( x ) . Soit E ⊆ P un ensemble de distributions de probabilité. Alors 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}$

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

Cette inégalité est assez lâche pour les petits . Pour les résultats binaires, , et la limite de Chernoff-Hoeffding est beaucoup plus serrée.$n$$|\mathcal{X}|=2$

Existe-t-il une limite similaire pour ?$|\mathcal{X}|=3$

Vous pouvez obtenir des bornes assez bonnes en considérant la variable aléatoire qui est 1 si et zéro sinon (pour s'étalant sur les essais et s'étalant sur les catégories). Pour tout fixe, les sont indépendants et donc peut être analysé en utilisant les bornes de Chernoff. Ensuite, effectuez une union liée sur .$Y_{ij}$$X_i = j$$1 \le i \le n$$1 \le j \le 3$$j$$Y_{ij}$$\sum_i Y_{ij}$$j$

Si ce qui précède ne suffit pas, je vous suggère de regarder le modèle des balles et des bacs, par exemple dans le manuel d'Upfal et de Mitzenmacher. Ce modèle est le même que le vôtre, sauf que certains de vos bacs peuvent être plus susceptibles que d'autres d'avoir des balles, n'est-ce pas? Il existe des techniques plus sophistiquées impliquant des approximations de Poisson dans ce modèle qui pourraient probablement être étendues à votre environnement avec des probabilités de bin non uniformes.

Il n'y a rien sur les bornes de Chernoff Hoeffding qui soit spécifique aux variables booléennes. Si sont des variables aléatoires à valeur réelle iid avec vous pouvez appliquer une borne Chernoff. Une bonne référence est "Concentration de mesure pour l'analyse d'algorithmes randomisés" ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&rep=rep1&type=pdf )$X_1,\ldots,X_n$$0 \leq X_i \leq 1$