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

9

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 |X1 1,X2,...,XnQ(x)
EP ondeP=arg min P E D(P||Q), é a distribuição emEmais próxima deQna entropia relativa.

Qn(E)=Qn(EPn)(n+1 1)|X|2-nD(P||Q),
P=argminPED(P||Q),
EQ

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

Existe um limite igualmente rígido para ?|X|=3

Yaroslav Bulatov
fonte
Eu acredito que você pode mudar | X | para | X | -1, porque o "último tipo", nos métodos e tipos, é fornecido assim que você souber o resto.
Thomas Ahle

Respostas:

6

You can get fairly good bounds by considering the random variable YEuj which is 1 if XEu=j and zero otherwise (for 1 1Eun ranging over trials and 1 1j3 ranging over categories). For any fixed j the YEuj are independent and therefore EuYEuj 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.

Warren Schudy
fonte
3

There is nothing about Chernoff Hoeffding bounds that is specific to boolean variables. If X1 1,...,Xn are i.i.d. real valued random variables with 0 0XEu1 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)

Aaron Roth
fonte
I'm interested in categorical rather than real-valued variables, added a clarification
Yaroslav Bulatov