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 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 sea iid .
Sea un conjunto de distribuciones de probabilidad. Entonces
Esta desigualdad es bastante flexible para los pequeños . Para resultados binarios, , y el límite de Chernoff-Hoeffding es mucho más estricto.
¿Existe un límite similar para ?
pr.probability
chernoff-bound
Yaroslav Bulatov
fuente
fuente
Respuestas:
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 .Yij Xi=j 1≤i≤n 1≤j≤3 j Yij ∑iYij j
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.
fuente
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,…,Xn 0≤Xi≤1
fuente