Suma de variables aleatorias exponenciales independientes

¿Podemos probar un resultado de concentración aguda en la suma de variables aleatorias exponenciales independientes, es decir, Sea $X_1, \ldots X_r$ sean variables aleatorias independientes tales como $Pr(X_i < x) = 1 - e^{-x/\lambda_i}$ . Deje $Z = \sum X_i$ . ¿Podemos probar los límites de la forma $Pr(|Z-\mu_Z|>t) < e^{-t^2/\sum (\lambda_i)^2}$ . Esto se sigue directamente si usamos la forma de varianza de los límites de chernoff y, por lo tanto, creo que es cierto, pero los límites que leí requieren límites o tienen cierta dependencia de los límites de las variables. ¿Podría alguien señalarme una prueba de lo anterior?

pr.probability randomness chernoff-bound Rocín
fuente

simplemente siga la prueba de chernoff: es fácil vincular el momento exponencial de las variables aleatorias exponenciales.

Sasho Nikolov

He tratado de repetir la prueba de chernoff. Lo hice para el caso más simple cuando todo

λ_{i} = λ

$\lambda_i = \lambda$ . Puedo obtener el tipo de relación que estoy buscando en una condición leve de

t < n λ

$t < n\lambda$ . ¿Tal condición surge de forma natural o se debe a que mi solución no es tan buena?

NAg

Consulte Lemma 2.8 aquí eprint.iacr.org/2010/076.pdf

Sasho Nikolov

Sí, esto tiene sentido. Incluso en su lema que tienen una condición de

ser lo suficientemente pequeña. Bien, entonces mi solución parece correcta. Muchas gracias por los enlaces y la sugerencia.

t

$t$

NAg

Pr [X_{i} < x] = e^{- λ_{i} x}

$\Pr[X_i < x] = e^{-\lambda_i x}$

x

$x$

Pr [X_{i} < x] = 1 - e^{- λ_{i} x}

$\Pr[X_i < x] = 1-e^{-\lambda_i x}$

λ_{i}^{- 2}

$\lambda_i^{-2}$

Respuestas:

Para concreción, digamos que el pdf del rv es $X_i$

p (X_{i} = x) = \frac{1}{2} λ_{i} e^{- λ_{i} | x |} .

$p(X_i = x) = \frac{1}{2} \lambda_i e^{-\lambda_i|x|}.$

Esta es la distribución de Laplace, o la distribución doble exponencial. Su varianza es . El cdf es $\frac{2}{\lambda_i^2}$

Pr [X_{i} \leq x] = 1 - \frac{1}{2} e^{- λ_{i} x}

$\Pr[X_i \leq x] = 1 - \frac{1}{2}e^{-\lambda_i x}$ para .

x \geq 0

$x \geq 0$

El momento que genera la función de es $X_i$

E e^{u X_{i}} = \frac{1}{1 - u^{2} / λ_{i}^{2}},

$\mathbf{E}\ e^{uX_i} = \frac{1}{1 - u^2/\lambda_i^2},$ para . Usando este hecho y el método de momento exponencial que es estándar en la prueba de los límites de Chernoff, obtienes eso para y , la siguiente desigualdad es válida

| u | < λ_{i}

$|u| < \lambda_i$

X = \sum_{i} X_{i}

$X = \sum_i X_i$

σ^{2} = 2 \sum_{i} λ_{i}^{- 2}

$\sigma^2 = 2\sum_i \lambda_i^{-2}$

Pr [X > t σ] < e^{- t^{2} / 4},

$\Pr[X > t\sigma] < e^{-t^2/4},$ siempre que . Puede encontrar una derivación detallada en la prueba del Lema 2.8 de este documento .

t \leq 2 σ min_{i} λ_{i}

$t \leq 2\sigma \min_{i}{\lambda_i}$

Sasho Nikolov
fuente

Muchas gracias por la respuesta. Sin embargo, en mi aplicación no es necesariamente cierto que . Sin embargo, uno esperaría una concentración aún mayor en caso de que . Podemos obtener dicho resultado si no usamos la aproximación de que restringe el rango de en la prueba pero el análisis de eso se vuelve inmanejable en el caso de diferentes . ¿Alguna sugerencia en ese frente?

t \leq \sqrt{2} σ m i n_{i} λ_{i}

$t \leq \sqrt{2} \sigma min_i \lambda _i$

t > \sqrt{2} σ m i n_{i} λ_{i}

$t > \sqrt{2} \sigma min_i \lambda _i$

1 / (1 - x) \leq e^{c x}

$1/(1-x) \leq e^{cx}$

t

$t$

λ_{i}^{'} s

$\lambda _i 's$

NAg

esto va a ser un movimiento de mano vigoroso, pero espero que valores tan grandes de sean más probables cuando solo un pequeño número de excede la mediana depor mucho pero las variables exponenciales dobles tienen una cola más pesada que las gaussianas, y un pequeño número de ellas no puede concentrarse tan fuertemente

X

$X$

X_{i}

$X_i$

| X_{i} |

$|X_i|$

Sasho Nikolov

Me estoy dando cuenta de que lo que escribí anteriormente no está claro: espero que esa salida en la cola parezca a la cola de otro rv que es la suma de un pequeño número de rv doble exponencial. La cola de tal no debería ser subgaussiano.

X

$X$

X^{'}

$X'$

X^{'}

$X'$

Sasho Nikolov

Para la distribución de Laplace, si usa el límite de Bernoulli puede escribir

E e^{u \sum_{i} X_{i}} = \prod_{i} \frac{1}{1 - u^{2} / λ_{i}^{2}} \leq \frac{1}{1 - u^{2} σ^{2} / 2},

$Ee^{u\sum_i X_i} = \prod_i \frac1{1-u^2/\lambda_i^2} \le \frac1{1-u^2\sigma^2/2},$ donde . Luego, el método clásico de Chernoff para dar

σ^{2} = 2 \sum_{i} λ_{i}^{- 2}

$\sigma^2=2\sum_i\lambda_i^{-2}$

Pr [\sum_{i} X_{i} \geq t σ] \leq \frac{1 + \sqrt{1 + 2 t^{2}}}{2} e^{1 - \sqrt{1 + 2 t^{2}}} \leq {\begin{cases} (e t / \sqrt{2} + 1) e^{- \sqrt{2} t} \\ e^{- t^{2} / 2 + t^{4} / 8} \end{cases} .

$\Pr[\sum_i X_i \ge t\sigma]\le \tfrac{1+\sqrt{1+2t^2}}{2} e^{1-\sqrt{1+2t^2}} \le\cases{ (et/\sqrt2+1) e^{-\sqrt{2}t} \\ e^{-t^2/2 + t^4/8}} .$

Tenga en cuenta que estos límites se mantienen para valores sin restricciones de y . Los límites a la derecha muestran los dos posibles regímenes. Para valores pequeños de obtenemos una concentración 'normal' , mientras que para valores grandes de obtenemos , que también es el CDF para una sola variable distribuida de Laplace. $t$ $\lambda_i$ $t$ $e^{-t^2/2}$ $t$ $\approx e^{-\sqrt{2}t}$

El límite permite interpolar entre las dos situaciones, pero sospecho que en casi todos los casos uno estará firmemente en el campo grande o pequeño . $1-\sqrt{1+2t^2}$ $t$ $t$

Para la distribución exponencial, las mismas técnicas nos dan donde . Por lo tanto, Así que todavía obtienes algo ligeramente normal, pero con lugar de como podríamos haber esperado. No sé si es posible obtener un límite en términos de la varianza. Podría intentar estudiar , pero no parece fácil trabajar con él. $Ee^{u\sum_iX_i}\le\frac{1}{1-u\mu}$ $\mu=\sum_i 1/\lambda_i$

Pr [(\sum_{i} X_{i}) - μ \geq t μ] \leq (t + 1) e^{- t} \leq e^{- t^{2} / 2 + t^{3} / 3} .

$\Pr[(\sum_i X_i)-\mu \ge t\mu]\le (t+1) e^{-t} \le e^{-t^2/2+t^3/3}.$

t μ

$t\mu$

t σ

$t\sigma$

E e^{u (\sum X_{i} - μ)^{2}}

$Ee^{u(\sum X_i-\mu)^2}$

Thomas Ahle
fuente

No tengo tiempo para resolver los detalles, pero estoy 99.9% seguro de que uno puede obtener un límite para variables aleatorias distribuidas exponencialmente que dependen de la varianza. Su límite en el momento que genera la función parece excesivamente suelto.

Warren Schudy

@Warren Schudy, ¿cuál sería tu enfoque?

Thomas Ahle

Veo dos enfoques obvios: 1. Parece que debería funcionar el segundo enlace enumerado en en.wikipedia.org/wiki/… . 2. Encuentre un límite más estricto en la función generadora de momentos.

Warren Schudy

@WarrenSchudy El límite de Bernstein da , pero solo para . Supongo que esto es similar a la respuesta de Sasho.

Pr [\sum_{i} X_{i} \geq t σ] \leq e^{- t^{2} / 2}

$\Pr[\sum_iX_i\ge t\sigma]\le e^{-t^2/2}$

t \leq σ min_{i} λ_{i} / 2

$t\le\sigma\min_i\lambda_i/2$

Thomas Ahle

Es inevitable que los límites de estilo gaussiano se detengan en algún momento. Incluso una sola variable aleatoria distribuida exponencialmente tiene colas más gruesas que cualquier gaussiana.

Warren Schudy