Epónimos relacionados con las matemáticas

desigualdad de Hoeffding proporciona una cota superior a la probabilidad de que la suma de variables aleatorias se desvíe una cierta cantidad de su valor esperado. Las desigualdad de Hoeffding fue demostrada por Wassily Hoeffding en 1963.¹

Las desigualdad de Hoeffding es un caso particular de la desigualdad de Azuma-Hoeffding, aunque generaliza la desigualdad de Bernstein, demostrada por Sergei Bernstein en 1923. Ambas son casos especiales de la desigualdad de McDiarmid.

Caso particular de variables de Bernouilli

Las desigualdad de Hoeffding puede aplicarse al importante especial de variables de Bernouilli idénticamente distribuidas, y este es la manera en que la desigualdad se aplica frecuentemente en combinatoria y en informática.

Si se considera una moneda desequilibrada que muestra cara con probabilidad ${\displaystyle p}$ y cruz con probabilidad ${\displaystyle 1-p}$, y se consideran ${\displaystyle n}$ lanzamientos de esta moneda. El valor esperado del número de veces que se obtiene cara es ${\displaystyle p\cdot n}$. Más aún, la probabilidad de que se obtengan como mucho ${\displaystyle k}$ caras puede cuantificarse exactamente mediante la siguiente expresión:

${\displaystyle \Pr {\Big (}n{\text{ lanzamientos llevan como mucho a }}k{\text{ caras}}{\Big )}=\sum _{i=0}^{k}{\binom {n}{i}}p^{i}(1-p)^{n-i}\,.}$

En el caso de que ${\displaystyle k=(p-\epsilon )n}$ para algún ${\displaystyle \epsilon >0}$, la desigualdad de Hoeffding acota esta probabilidad mediante un término que disminuye exponencialmente en ${\displaystyle \epsilon ^{2}\cdot n}$:

${\displaystyle \Pr {\Big (}n{\text{ se obtinen como mucho}}(p-\epsilon )n{\text{ caras}}{\Big )}\leq \exp {\big (}-2\epsilon ^{2}n{\big )}\,.}$

De manera similar, en el caso de que ${\displaystyle k=(p+\epsilon )n}$ para algún ${\displaystyle \epsilon >0}$, la desigualdad de Hoeffding acota la probabilidad de que se obtengan al menos ${\displaystyle \epsilon n}$ un número de caras mayor que el valor esperado:

${\displaystyle \Pr {\Big (}n{\text{ se obtienen como poco}}(p+\epsilon )n{\text{ caras}}{\Big )}\leq \exp {\big (}-2\epsilon ^{2}n{\big )}\,.}$

En esas condiciones la desigualdad de Hoeffding implica que el número de caras que se obtienen se concentra alrededor de la media, con colas que decrecen exponencialmente.

${\displaystyle \Pr {\Big (}n{\text{ lanzamientos llevan a un número caras entre }}(p-\epsilon )n{\text{ y }}(p+\epsilon )n{\Big )}\geq 1-2\exp {\big (}-2\epsilon ^{2}n{\big )}\,.}$

Caso general

Sean ${\displaystyle X_{1},\dots ,X_{n}\!}$ n variables aleatorias independientes. Si se asume que las ${\displaystyle X_{i}}$ están acotadas casi con seguridad; es decir, si se asume para ${\displaystyle 1\leq i\leq n}$ que:

${\displaystyle \Pr(X_{i}\in [a_{i},b_{i}])=1.\!}$

Se define la media muestral de estas variables como:

${\displaystyle {\overline {X}}=(X_{1}+\cdots +X_{n})/n\,.}$

El segundo teorema en el artículo de Hoeffding prueba las siguientes desigualdades:

${\displaystyle \Pr({\overline {X}}-\mathrm {E} [{\overline {X}}]\geq t)\leq \exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\!}$

${\displaystyle \Pr(|{\overline {X}}-\mathrm {E} [{\overline {X}}]|\geq t)\leq 2\exp \left(-{\frac {2t^{2}n^{2}}{\sum _{i=1}^{n}(b_{i}-a_{i})^{2}}}\right),\!}$

que son válidas para valores positivos de t. Aquí ${\displaystyle \mathrm {E} [{\overline {X}}]}$ representa en alor esperado de ${\displaystyle {\overline {X}}}$.

Nótese que las desigualdades también son válidas cuando las ${\displaystyle X_{i}}$ han sido obtenidas usando muestreo sin reemplazo; en este caso las variables aleatorias no son de ninguna manera indendientes. Una demostración de esta afirmación puede encontrarse en el artículo de Hoeffding. Para cotas ligeramente mejores en el caso de muestreo sin reemplazo, puede consultarse el artículo de Serfling (1974).

desigualdad de la suma de Chebyshov, debe su nombre al matemático ruso Pafnuti Chebyshov.

Formulación

La desigualdad de la suma de Chebyshov establece que si:

${\displaystyle a_{1}\geq a_{2}\geq \cdots \geq a_{n}}$

y

${\displaystyle b_{1}\geq b_{2}\geq \cdots \geq b_{n},}$

entonces:

${\displaystyle {1 \over n}\sum _{k=1}^{n}a_{k}\cdot b_{k}\geq \left({1 \over n}\sum _{k=1}^{n}a_{k}\right)\left({1 \over n}\sum _{k=1}^{n}b_{k}\right).}$

Del mismo modo, si:

${\displaystyle a_{1}\leq a_{2}\leq \cdots \leq a_{n}}$

y

${\displaystyle b_{1}\geq b_{2}\geq \cdots \geq b_{n},}$

entonces:

${\displaystyle {1 \over n}\sum _{k=1}^{n}a_{k}b_{k}\leq \left({1 \over n}\sum _{k=1}^{n}a_{k}\right)\left({1 \over n}\sum _{k=1}^{n}b_{k}\right).}$¹

Demostración

Considérese la suma:

${\displaystyle S=\sum _{j=1}^{n}\sum _{k=1}^{n}(a_{j}-a_{k})(b_{j}-b_{k}).}$

Si las dos secuencias no se incrementan, entonces:

a_j − a_k y b_j − b_k

tienen el mismo signo para cualquier j, k. Por lo tanto S ≥ 0.

Resolviendo los paréntesis, se deduce que:

${\displaystyle 0\leq 2n\sum _{j=1}^{n}a_{j}b_{j}-2\sum _{j=1}^{n}a_{j}\,\sum _{k=1}^{n}b_{k},}$

donde:

${\displaystyle {\frac {1}{n}}\sum _{j=1}^{n}a_{j}b_{j}\geq \left({\frac {1}{n}}\sum _{j=1}^{n}a_{j}\right)\,\left({\frac {1}{n}}\sum _{j=1}^{n}b_{k}\right).}$

Una demostración alternativa se puede obtener con el procedimiento de reordenación de desigualdad.

Versión continua

También hay una versión continua de la desigualdad de la suma Chebyshov:

Si f y g son funciones de variable real integrables en el intervalo [0,1], pero no crecientes, o ambas no decrecientes, entonces:

${\displaystyle \int _{0}^{1}f(x)g(x)dx\geq \int _{0}^{1}f(x)dx\int _{0}^{1}g(x)dx,\,}$

con la desigualdad invertida si una función es no creciente y la otra es no decreciente.

desigualdad de Márkov proporciona una cota superior para la probabilidad de que una función no negativa de una variable aleatoria sea mayor o igual que una constante positiva. Su nombre le viene del matemático ruso Andréi Márkov.

La desigualdad de Márkov relaciona las probabilidades con la esperanza matemática y proporciona cotas útiles -aunque habitualmente poco ajustadas- para la función de distribución de una variable aleatoria.

Teorema

La desigualdad de Márkov afirma que:

Si X es una variable aleatoria y a > 0, entonces ${\displaystyle {\textrm {Pr}}(|X|\geq a)\leq {\frac {\mathbb {E} (|X|)}{a}}.}$ donde ${\displaystyle \mathbb {E} (\cdot )}$ denota el valor esperado.

Demostración

Para cualquier suceso A, sea I_A la variable aleatoria indicatriz de A, esto es, I_A = 1 si ocurre A y es 0 en el caso contrario. Entonces

${\displaystyle aI_{(|X|\geq a)}\leq |X|.\,}$

Por lo tanto

${\displaystyle \mathbb {E} (aI_{(|X|\geq a)})\leq \mathbb {E} (|X|).\,}$

Ahora, nótese que el lado izquierdo de esta desigualdad coincide con

${\displaystyle a\mathbb {E} (I_{(|X|\geq a)})=a\Pr(|X|\geq a).\,}$

Por lo tanto tenemos

${\displaystyle a\Pr(|X|\geq a)\leq \mathbb {E} (|X|)\,}$

y como a > 0, se pueden dividir ambos lados entre a.

Demostración alternativa

Una prueba más formal, relacionada con la teoría de la medida, es la siguiente:

${\displaystyle \Pr(|X|\geq a)=\int _{a}^{\infty }{f(x)dx}\leq \int _{a}^{\infty }{{\frac {|x|}{a}}f(x)dx}\leq {\frac {1}{a}}\int _{-\infty }^{\infty }{|x|f(x)dx}={\frac {\mathbb {E} (|X|)}{a}}}$

En la introducción de ${\displaystyle {\frac {|x|}{a}}}$, nótese que ya que estamos considerando la variable aleatoria sólo en sus valores iguales o mayores a ${\displaystyle a}$, ${\displaystyle |X|\geq a}$ y, por tanto,

${\displaystyle {\frac {|X|}{a}}\geq 1}$

con lo que al multiplicar ${\displaystyle f(x)dx}$ por algo mayor a uno será igual o mayor. La segunda desigualdad viene de añadir la suma

${\displaystyle \int _{-\infty }^{a}{|x|f(x)dx}}$

que siempre será positiva ya que se integra algo positivo como es el valor absoluto (por que ${\displaystyle \scriptstyle f(x)}$ es positiva).

• La desigualdad de Márkov se emplea para probar la desigualdad de Chebyshov.