Неравенство типа Чернова для случайной величины с 3 результатами

Предположим, у нас есть случайная переменная, которая принимает нечисловые значения a, b, c и хочет количественно определить, как эмпирическое распределение выборок этой переменной отличается от истинного распределения. В этом случае применяется следующее неравенство (от Cover & Thomas ).$n$

Теорема 12.4.1 (теорема Санова): Пусть - iid . Пусть - множество вероятностных распределений. Тогда где P ^ * = \ arg \ min_ {P \ in E} D (P || Q), является распределением в E , наиболее близким к Q по относительной энтропии.$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$

Это неравенство довольно слабое для малых $n$ . Для бинарных результатов $|\mathcal{X}|=2$ и граница Черноффа-Хеффдинга гораздо более жесткая.

Существует ли аналогичная строгая оценка для $|\mathcal{X}|=3$ ?

Вы можете получить довольно хорошие оценки, рассматривая случайную переменную которая равна 1, если и ноль в противном случае (для начиная с испытаний и учетом категорий). При любом фиксированном независимы и , следовательно могут быть проанализированы с использованием Черновым границ. Тогда сделайте объединение, связанное по .$Y_{ij}$$X_i = j$$1 \le i \le n$$1 \le j \le 3$$j$$Y_{ij}$$\sum_i Y_{ij}$$j$

Если вышесказанного недостаточно, советую взглянуть на модель шаров и урн, например, в учебнике Упфала и Митценмахера. Эта модель такая же, как у вас, за исключением того, что некоторые из ваших мусорных ведер могут иметь больше шаров, чем другие, не так ли? В этой модели есть несколько более изощренных методов, использующих приближения Пуассона, которые, вероятно, будут распространяться на ваши установки с неоднородными вероятностями бина.

Нет ничего о границах Черноффа Хоффдинга, которые бы относились к булевым переменным. Если$X_1,\ldots,X_n$ действительно ли случайные переменные имеют $0 \leq X_i \leq 1$Вы можете применить границу Черноффа. Хорошим справочником является «Концентрация меры для анализа рандомизированных алгоритмов» ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&rep=rep1&type=pdf ).