Una cota superior exponencial sobre probabilidades de cola para sumas o agregados aleatorios obtenida aplicando la desigualdad de Markov a la función generadora de momentos (MGF) y optimizando la inclinación exponencial: para S suma, P(S ≥ t) ≤ inf_{s>0} e^{-s t} E[e^{s S}].

Principio

Se usa Markov en la transformación exponencial de la variable aleatoria (la MGF) y se elige el parámetro de inclinación que minimiza la cota; la independencia o el control subexponencial de los sumandos suele hacer que la cota sea exponencialmente pequeña en el tamaño de la muestra.

Demostración

Para ensayos de Bernoulli independientes con media p, las cotas de Chernoff dan P(S ≥ (1+δ)np) ≤ exp(−n D((1+δ)p || p)), donde D(·||·) es la entropía relativa, proporcionando probabilidades de cola que decrecen exponencialmente y que se usan en algoritmos aleatorizados y concentración combinatoria.

Aplicación incorrecta

Aplicar las fórmulas estándar de Chernoff a variables dependientes, a variables sin MGF finita en un entorno de cero, o ignorar la optimización del parámetro de inclinación; esto puede producir cotas vacías o engañosas.

Consecuencia

Proporciona cotas estrictas con decrecimiento exponencial que permiten garantías de alta probabilidad en algoritmos probabilísticos, teoría del aprendizaje y estimaciones de grandes desviaciones; se usa a menudo junto con cotas por unión para controlar muchos eventos simultáneamente.

Inversión

Reemplazar la técnica de Chernoff por desigualdades más débiles (p. ej., Chebyshev) produce decadencia polinómica o mucho más lenta de las probabilidades de cola; para distribuciones de cola pesada las cotas de Chernoff pueden no aplicarse o ser poco informativas.

Límite

Requiere existencia de una MGF en un entorno de cero o control de momentos exponenciales; las formas clásicas suponen independencia o dependencia limitada y colas acotadas/subexponenciales — fuera de estos regímenes se necesitan modificaciones u otras técnicas.

Tensión semántica

Compite con las desigualdades de Hoeffding, Bernstein y Bennett; Chernoff suele ser más ajustada para sumas de indicadores independientes o variables subgaussianas, pero puede ser inadecuada para datos con colas pesadas o fuerte dependencia.

Síntesis

Las cotas de Chernoff aplican Markov sobre MGFs y optimizan la inclinación exponencial para obtener cotas de cola exponenciales para sumas de variables adecuadas; potentes cuando existen MGFs y una (aproximada) independencia, pero limitadas por la existencia de momentos y la estructura de dependencia.