Nierówność typu Chernoffa dla zmiennej losowej z 3 wynikami

Załóżmy, że mamy zmienną losową, która przyjmuje wartości nienumeryczne a, b, c i chce określić ilościowo, w jaki sposób rozkład empiryczny $n$próbki tej zmiennej odbiegają od rozkładu rzeczywistego. W tym przypadku obowiązuje następująca nierówność (z Cover & Thomas ).

Twierdzenie 12.4.1 (twierdzenie Sanowa): Niech $X_1, X_2, \ldots, X_n$ bądź tam $\sim Q(x)$.
Pozwolić$E \subseteq \mathscr{P}$być zbiorem rozkładów prawdopodobieństwa. Następnie

$$Q^n(E) = Q^n(E \cap \mathscr{P}_n) \leq (n+1)^{|\mathcal{X}|}2^{-nD(P^*||Q)},$$ gdzie $$P^* = \arg\min_{P \in E} D(P||Q),$$ jest rozkładem w $E$ najbliższym $Q$ w entropii względnej.

Ta nierówność jest dość luźna dla małych $n$ . W przypadku wyników binarnych $|\mathcal{X}|=2$ , a granica Chernoffa-Hoeffdinga jest znacznie ściślejsza.

Czy istnieje podobne ograniczenie dla $|\mathcal{X}|=3$ ?

Możesz uzyskać całkiem dobre granice, biorąc pod uwagę zmienną losową która wynosi 1, jeśli a zero w przeciwnym razie (dla obejmującego próby i obejmującego kategorie). Dla każdej ustalonej są niezależne, a więc mogą być analizowane przy użyciu granic Chernoffa. Następnie wykonaj związek związany przez .$Y_{ij}$$X_i = j$$1 \le i \le n$$1 \le j \le 3$$j$$Y_{ij}$$\sum_i Y_{ij}$$j$

Jeśli powyższe nie wystarczy, proponuję spojrzeć na model kulek i pojemników, np. W podręczniku Upfala i Mitzenmachera. Ten model jest taki sam jak twój, z tym wyjątkiem, że niektóre z twoich pojemników mogą być bardziej prawdopodobne niż inne, aby wylądowały w nich kule, prawda? Istnieje kilka bardziej wyrafinowanych technik wykorzystujących aproksymacje Poissona w tym modelu, które prawdopodobnie można rozszerzyć na twoje ustawienie z nierównomiernymi prawdopodobieństwami bin.

Nie ma nic w granicach Chernoffa Hoeffdinga, które są specyficzne dla zmiennych boolowskich. Jeśli są zmiennymi losowymi o wartości rzeczywistej o wartości , możesz zastosować ograniczenie Chernoffa. Dobrym odniesieniem jest „Stężenie miary do analizy algorytmów losowych” ( 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$