Son una cota más fina que las conocidas cotas basadas en el primer y segundo momento tales como la inecuación de Markov o la inecuación de Chebyshev, las cuales solo obtienen cotas de nivel exponencial cuando la distribución decrece.
Sean X1, ..., Xn variables aleatorias independientes que distribuyen Bernoulli, cada una con probabilidad p > 1/2 de ser igual a 1.
Podemos encontrar varias representaciones de las cotas de Chernoff: la original forma aditiva (la cual da una cota para el error absoluto) o la más práctica forma multiplicativa (la cual da una cota del error relativo para la esperanza).
Las cotas de Chernoff para una variable aleatoria X, la cual es la suma de n variables aleatorias independientes X1, ..., Xn, se obtienen al aplicar etX para algún t bien elegido.
Tomando a = nq en (1), obtenemos: Luego, conociendo que Pr(Xi = 1) = p, Pr(Xi = 0) = 1 − p, tenemos que Por lo tanto podemos computar fácilmente el ínfimo, usando cálculo: Igualando la ecuación a 0 y resolviéndola, tenemos entonces Por lo que, Como q = p + ε > p, vemos que t > 0, por lo cual nuestra cota se satisface para t. Luego de resolverlo para t, podemos sustituir en las ecuaciones anteriores para llegar a que Ahora tenemos el resultado deseado, que Para completar la demostración para el caso simétrico, simplemente definimos la variable aleatoria Yi = 1 − Xi, aplicamos la misma demostración, y sustituímos en nuestra cota.
En algunas ocasiones, la cota la cual es más fuerte para p < 1/8, es también usada.
De acuerdo a (1), La tercera línea abajo está dada porque
Este es idéntico al cálculo anterior en la demostración del teorema de la forma aditiva.
El mismo resultado puede obtenerse al reemplazar a en la ecuación para la cota de Chernoff con (1 + δ)μ.
Por lo tanto, Si simplemente hacemos t = log(1 + δ) tal que t > 0 para δ > 0, podemos sustituir y encontrar Esto prueba el resultado deseado.
Una estrategia similar de demostración puede ser usada para mostrar que La fórmula anterior en la práctica es usualmente torpe para computar,[3] por lo que las siguientes cotas más flojas pero más convenientes son usadas a menudo: Podemos obtener cotas más fuertes usando técnicas de demostración más simples para algunos casos especiales de variables aleatorias simétricas.
Típicamente mientras diseñamos un experimento estadístico, dadas las características de cada participante en el experimento, necesitamos conocer como dividir los participantes en dos conjuntos disjuntos tal que las características están tan balanceada como sea posible entre los dos grupos.
Rudolf Ahlswede y Andreas Winter introdujeron (Ahlswede y Winter, 2003) una cota de Chernoff para variables aleatorias con representación matricial.
Si M está distribuida acorde a cierta distribución sobre d × d matrices con esperanza 0, y si M1, ..., Mt son copias independientes de M entonces para todo ε > 0, donde
se cumple casi siempre y C > 0 es una constante.
Sea 0 < ε < 1 y M una matriz simétrica real aleatoria con
Asume que cada elemento en la base de 'M' tiene a lo sumo rango r. Evalúa Si
se cumple casi siempre, entonces donde M1, ..., Mt son copias de 'M' igualmente distribuidas.
La siguiente variante de las cotas de Chernoff puede ser usada para acotar la probabilidad de que una mayoría en una población se convierta en minoría en una muestra, o viceversa[6] Supón que hay una población general A y una sub-población B⊆A.
Entonces, para toda fracción d∈[0,1]: En particular, si B es una mayoría en A (r > 0.5) podemos acotar la probabilidad de que B se mantenga como una minoría en S (rS>0.5) tomando: d = 1 - 1 / (2 r):[7] Esta cota no es fina para nada.