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

9

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 P_{n}) \leq (n + 1)^{| X |} 2^{- n D (P^{*} | | Q)},$ $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),$ $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$ ?

pr.probability chernoff-bound

— Jarosław Bułatow
źródło

Wierzę, że możesz zmienić | X | na | X | -1, ponieważ „ostatni typ” w metodzie og typy jest podawany, gdy znasz resztę.

— Thomas Ahle,

6

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.

— Warren Schudy
źródło

3

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$

— Aaron Roth
źródło

Interesują mnie zmienne kategoryczne zamiast rzeczywistych, dodałem wyjaśnienie

— Jarosław Bułatow