##  [Cota de Chernoff](/es/node/60610) 

 Definición

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

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

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

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

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

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

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

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

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.