8 votos

Desigualdades de Chernoff

Chernoff las desigualdades son las desigualdades que expresar la concentración en torno a la expectativa de una variable aleatoria $X=\sum_iX_i$ cuando la $X_i$ son yo.yo.d variables aleatorias

He estado encontrando estas desigualdades en bastantes contextos, y para varias distribuciones de las $X_i's$. Sin embargo, cada vez que trato de entender la prueba para él, a mí me parece que la prueba es sólo una secuencia de trucos y no puedo obtener ninguna pista.

  1. ¿Sabes de algún perspicaz, tal vez usando "matemática superior", camino a la vista de estas desigualdades?

  2. Para que las distribuciones de las $X_i's$ se puede esperar para obtener una chernoff obligado para $\sum_iX_i$?

13voto

Did Puntos 1

Estas pruebas no son definitivamente una secuencia de trucos. En su lugar se aplica una y otra vez una muy importante principio, que puede ser enunciada como:

Encontrar un buen pointwise la desigualdad entre variables aleatorias y se integran en ella.

Por ejemplo, la desigualdad de Markov es la versión integrada de la pointwise la desigualdad $$ t\,\mathbf 1_A\leqslant X,\quad\text{con}\quad A=[X\geqslant t], $$ que vale para todos los positivos $t$ y la variable aleatoria $X$ tal que $X\geqslant0$ casi seguramente.

Asimismo, Bienaymé-la desigualdad de Chebyshev es la versión integrada de la pointwise la desigualdad $$ t^2\,\mathbf 1_A\leqslant|X-\mathrm E(X)|^2,\quad\text{con}\quad A=[|X-\mathrm E(X)|\geqslant t], $$ que vale para todos los positivos $t$ y sin restricción en el signo de $X$.

Otro ejemplo es Chernoff obligado, que es la versión integrada de la desigualdad $$ \mathrm e^{xt}\,\mathbf 1_A\leqslant\mathrm e^{xS},\quad\text{con}\quad A=[S\geqslant t], $$ lo que es válido para cada variable aleatoria $S$ y cada número real $t$ pero sólo para $x\geqslant0$.

Los siguientes pasos son para elegir inteligentemente $t$$x$, y para ser capaces de estimar la $\mathrm E(\mathrm e^{xS})$. Por ejemplo, cuando se $S=X_1+\cdots+X_n$ es una suma de (i).yo.d. variables aleatorias $X_k$ distribuido como $X$, uno sabe que $\mathrm E(\mathrm e^{xS})=\left(\mathrm E(\mathrm e^{xX})\right)^n$ por lo tanto $$ \mathrm P(S\geqslant nt)\leqslant\mathrm e^{-nxt}\left(\mathrm E(\mathrm e^{xX})\right)^n=\mathrm e^{-n\Lambda(x,t)}, $$ con $$ \Lambda(x,t)=xt-\log\mathrm E(\mathrm e^{xX}), $$ y la pregunta crucial ahora es determinar si existe alguna $x\geqslant0$ tal que $\Lambda(x,t)\gt0$. Esto sólo puede suceder por $x\gt0$ desde $\Lambda(0,t)=0$ por lo tanto Chernoff límites sólo son relevantes cuando se $\mathrm E(\mathrm e^{xX})$ es finito para (al menos) algunos (pequeños) $x\gt0$.

2voto

JohnB Puntos 214

1) yo no considerar esto como una versión cuantitativa del teorema central del límite, sino más bien como una versión cuantitativa de la gran desviación teoremas (los dos están relacionados, por supuesto). Centrémonos en el resultado, y no en los métodos que utiliza para llegar a ellos. Deje $(X_i)$ ser una secuencia de yo.yo.d., $\mathbb{R}$con valores, centrado, delimitadas las variables aleatorias. Voy a denotar por $(S_n)$ la secuencia de sus sumas parciales. Una gran desviación principio indica que existe una tasa de función $I: \mathbb{R} \to \mathbb{R}_+$ tal que, para cualquier conjunto abierto $O$:

$$- \inf_O I \leq \liminf_{n \to + \infty} \frac{\ln \mathbb{P} (S_n/n \in O)}{n},$$

y para cualquier conjunto cerrado $F$:

$$\liminf_{n \to + \infty} \frac{\ln \mathbb{P} (S_n/n \in F)}{n} \leq - \inf_F I.$$

En otras palabras, la probabilidad de que la suma de $S_n$ es grande (por ejemplo, $S_n \geq \varepsilon n$ fijos $\varepsilon$) disminuye de manera exponencial en $n$, aproximadamente a la velocidad de la $e^{- I (\varepsilon)n}$.

Una característica notable de estos grandes de la desviación de los principios para el yo.yo.d. variable aleatoria es que la función de $I$, el cual regula la velocidad de la decadencia, es la Lapaplace-legendre de transformación de la función característica de a $X$. En otras palabras, exactamente lo que usted consigue con el Chernoff límites! Así que el Chernoff límites que le dan un cuantitativa, límite superior para la gran desviación de los principios de:

$$\mathbb{P} (S_n/n \geq \varepsilon) \leq e^{- I(\varepsilon) n},$$

o, equivalentemente,

$$\frac{\mathbb{P} (S_n/n \geq \varepsilon)}{n} \leq - I(\varepsilon).$$

En un contexto más general de la configuración, la función de velocidad de $I$ está relacionado con la entropía de un sistema (se obtiene un gran entropía [que es pequeño para un físico, a menudo hay un cambio de signo] cuando la suma de $S_n$ está lejos de su estado típico).

==========

Hay un punto que es digno de nota, pero no se ha planteado todavía. Usted puede demostrar que momento los límites son más fuertes que la exponencial límites. Usted sabe que, para cualquier $p \geq 0$ y cualquier $t > 0$:

$$\mathbb{P} (|X| \geq t) \leq \frac{\mathbb{E} (|X|^p)}{t^p}.$$

Estos límites son más fuertes que el Chernoff límites: si conoce a cada uno de los momentos de $X$, entonces, el momento de los límites permiten obtener mejores límites en $\mathbb{P} (|X| \geq t)$ de Chernoff límites. Sin embargo, se comportan muy mal cuando usted mira sumas de yo.yo.d. variables aleatorias (debido a los momentos de cambio no trivial de la forma), mientras que la exponencial límites son muy fáciles de manejar:

$$\mathbb{E} (e^{\lambda S_n}) = \mathbb{E} (e^{\lambda X})^n.$$

==========

2) Obviamente, Chernoff límites de existir tan pronto como la función característica $\mathbb{E} (e^{\lambda X})$ está definido en un barrio de $0$, por lo que sólo necesita exponencial de colas para $X$ (y no del acotamiento). Por otra parte, si usted desea conseguir un enlace en una dirección (es decir, en $\mathbb{P} (S_n/n \geq \varepsilon)$ o $\mathbb{P} (S_n/n \leq -\varepsilon)$, no en $\mathbb{P} (|S_n/n| \geq \varepsilon)$), sólo se necesita exponencial de las colas en la dirección correspondiente.

Si usted asume la hipótesis más fuerte en las colas de $X$, usted puede conseguir más fuerte Chernoff límites. Acotamiento o sub-gaussianidad de $X$ son típicos supuestos.

Usted puede obtener similar límites (concentración de las desigualdades), no sólo para el aprtial sumas de yo.yo.d. variables aleatorias, sino también por algunos martingales (ver Collin McQuillan de la respuesta), y mucho, mucho más grandes clases de procesos. Esta página de la Wikipedia, le dará un sabor de la misma, así como algunas palabras clave, si usted está interesado.

1voto

Brian Duff Puntos 121
  1. Es una versión cuantitativa del teorema del límite central, además de algunos límites en la cola de probabilidades de la distribución normal. Se puede ver que la distribución normal decae rápidamente a partir de la función de densidad de probabilidad $\frac{1}{\sqrt{2\pi}}e^{-x^2/2}$. Esto deja a la pregunta de una explicación intuitiva para el teorema del límite central. Si algo así como el CLT fuera cierto, sería de esperar que la distribución de probabilidad de $\frac{1}{\sqrt{n}}(X_1+\dots,X_n)$ (donde $X_1,\dots,X_n$ son yo.yo.d.r.v, con una media de cero y acotado, dicen) converge a una distribución de probabilidad, cuyo momento de generación de la función satisface $M_X^n(t/\sqrt{n})=M_X(t)$, el cual debe ser de la forma $\log M_X(t)=Ct^2$, y por lo tanto debe ser una distribución normal.

  2. Basta con que las variables son independientes y acotada. Una importante generalización es la Azuma la desigualdad.

0voto

dtldarek Puntos 23441

La forma en que los veo, ellos son una especie de generalización de la desigualdad de Markov:

$$ P(|X| \geq t ) \leq \frac{E|X|}{t}. $$

Observar, que aquí se utiliza un solo momento, es decir, el valor esperado. Para obtener una mayor enlazado, se pueden utilizar dos momentos, es decir, la desigualdad de Chebyshev:

$$ P(|X-EX| \geq t) \leq \frac{D^2X}{t^2}. $$

Esto se puede generalizar a los momentos de orden superior, cuarta, sexta, y así sucesivamente. Chernoff obligado utiliza logarítmica del número de momentos, esto es posible porque ha $n$ i.yo.d. variables aleatorias, por lo que su suma es muy concentrados alrededor de su media. Por favor, tenga en cuenta que esta es sólo mi intuición (que podría ser muy malo), lo siento, no puede proporcionar ninguna evidencia.

Espero que ayude :-)

i-Ciencias.com

I-Ciencias es una comunidad de estudiantes y amantes de la ciencia en la que puedes resolver tus problemas y dudas.
Puedes consultar las preguntas de otros usuarios, hacer tus propias preguntas o resolver las de los demás.

Powered by:

X