Desigualdad tipo Chernoff para variable aleatoria con 3 resultados

9

Supongamos que tenemos una variable aleatoria que toma valores no numéricos a, b, c y queremos cuantificar cómo la distribución empírica de n muestras de esta variable se desvía de la distribución verdadera. La siguiente desigualdad (de Cover & Thomas ) se aplica en este caso.

Teorema 12.4.1 (Teorema de Sanov): Sea X1,X2,,Xn sea ​​iid Q(x) .
Sea EP un conjunto de distribuciones de probabilidad. Entonces

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

Esta desigualdad es bastante flexible para los pequeños n . Para resultados binarios, |X|=2 , y el límite de Chernoff-Hoeffding es mucho más estricto.

¿Existe un límite similar para |X|=3 ?

Yaroslav Bulatov
fuente
Creo que puedes cambiar | X | a | X | -1, porque el "último tipo", en los métodos og types, se proporciona una vez que conoce el resto.
Thomas Ahle

Respuestas:

6

Puede obtener límites bastante buenos considerando la variable aleatoria que es 1 si y cero de lo contrario (para extiende sobre los ensayos y extiende sobre las categorías). Para cualquier fijo la son independientes y por lo tanto puede ser analizado usando límites Chernoff. Luego haga una unión ligada sobre .YijXi=j1in1j3jYijiYijj

Si lo anterior no es suficiente, sugiero que mire el modelo de bolas y contenedores, por ejemplo, en el libro de texto de Upfal y Mitzenmacher. Ese modelo es el mismo que el tuyo, excepto que algunos de tus contenedores pueden ser más propensos que otros a tener bolas en ellos, ¿verdad? Hay algunas técnicas más sofisticadas que involucran aproximaciones de Poisson en ese modelo que probablemente serían extensibles a su entorno con probabilidades de bin no uniformes.

Warren Schudy
fuente
3

No hay nada acerca de los límites de Chernoff Hoeffding que sea específico de las variables booleanas. Si son variables aleatorias con valores reales con , puede aplicar un límite de Chernoff. Una buena referencia es "Concentración de medida para el análisis de algoritmos aleatorios" ( http://citeseerx.ist.psu.edu/viewdoc/download?doi=10.1.1.120.2561&rep=rep1&type=pdf )X1,,Xn0Xi1

Aaron Roth
fuente
Estoy interesado en variables categóricas más que en valores reales, agregué una aclaración
Yaroslav Bulatov