Сумма независимых экспоненциальных случайных величин

Можем ли мы доказать точный результат концентрации на сумме независимых экспоненциальных случайных величин, т.е. пусть - независимые случайные величины, такие что . Пусть . Можем ли мы доказать оценки вида . Это следует непосредственно, если мы используем дисперсионную форму границ Чернова и, следовательно, я считаю, что это правда, но границы, которые я читаю, требуют ограниченности или имеют некоторую зависимость от ограниченности переменных. Может ли кто-нибудь указать мне на доказательство вышеизложенного? $X_1, \ldots X_r$ $Pr(X_i < x) = 1 - e^{-x/\lambda_i}$ $Z = \sum X_i$ $Pr(|Z-\mu_Z|>t) < e^{-t^2/\sum (\lambda_i)^2}$

pr.probability randomness chernoff-bound кляча
источник

просто следуйте доказательству Чернова: легко связать экспоненциальный момент экспоненциальных случайных величин.

Сашо Николов

Я попытался повторить доказательство Чернова. Я сделал это для более простого случая, когда все

λ_{i} = λ

$\lambda_i = \lambda$ . Я могу получить вид отношений, который я ищу, при мягком условии . Возникает ли такое состояние естественным образом или это связано с моим не очень хорошим решением?

t < n λ

$t < n\lambda$

NAg

Проверьте лемму 2.8 здесь eprint.iacr.org/2010/076.pdf

Сашо Николов

Да, это имеет смысл. Даже в их лемме они имеют условие на быть достаточно мал. Хорошо, тогда мое решение кажется правильным. Большое спасибо за ссылки и предложение.

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}$

Ответы:

Для конкретности, скажем , что ПДФ с.в. является $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|}.$

Это распределение Лапласа или двойное экспоненциальное распределение. Его дисперсия . Cdf является $\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}$ для .

x \geq 0

$x \geq 0$

Генерирующий момент функция является $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},$

для . Используя этот факт и метод экспоненциального момента, который является стандартным в доказательстве границ Чернова, вы получите, что для и выполняется следующее неравенство

| 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},$

пока . Вы можете найти подробный вывод в доказательстве леммы 2.8 этой статьи .

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

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

Сашо Николов
источник

Большое спасибо за ответ. Однако в моем приложении не обязательно верно, что . Однако можно ожидать еще большей концентрации в случае . Мы можем получить такой результат, если не будем использовать приближение которое ограничивает диапазон в доказательстве, но анализ этого становится неуправляемым в случае различных . Есть предложения на этот счет?

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

это будет энергичное размахивание руками, но я ожидаю, что такие большие значения наиболее вероятны, когда только небольшое число превышает медианумного. но двойные экспоненциальные переменные имеют более тяжелый хвост, чем гауссианы, и небольшое количество из них не может сосредоточиться так плотно

X

$X$

X_{i}

$X_i$

| X_{i} |

$|X_i|$

Сашо Николов

Я понимаю, что то, что я написал выше, не ясно: я ожидаю, что выход в хвосте выглядит как хвост другого rv который является суммой небольшого числа двойной экспоненциальной rv. Хвост такого не должен быть к югу от гауссовой.

X

$X$

X^{'}

$X'$

X^{'}

$X'$

Сашо Николов

Для распределения Лапласа, если вы используете границу Бернулли, вы можете написать

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},$ где . Тогда классический метод Черноффа дает

σ^{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}} .$

Обратите внимание, что эти границы справедливы для неограниченных значений и . Границы справа показывают два возможных режима. Для малых значений мы получаем «нормальную» концентрацию , в то время как для больших значений мы получаем , что также является CDF для одна переменная Лапласа. $t$ $\lambda_i$ $t$ $e^{-t^2/2}$ $t$ $\approx e^{-\sqrt{2}t}$

связаны позволяет интерполировать между этими двумя ситуациями, но я подозреваю , что почти во всех случаях один будет твердо в любом большом или малым лагеря. $1-\sqrt{1+2t^2}$ $t$ $t$

Для экспоненциального распределения те же методы дают нам где . Следовательно, Таким образом, вы по-прежнему выглядите слегка нормально, но с а не с как мы могли бы надеяться. Я не знаю, возможно ли получить границу с точки зрения дисперсии. Вы можете попытаться изучить , но с ним не так легко работать. $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}$

Томас Але
источник

У меня нет времени, чтобы проработать детали, но я на 99,9% уверен, что можно получить границу для экспоненциально распределенных случайных величин, которая зависит от дисперсии. Ваша ограниченная функция генерирования момента выглядит чрезмерно свободной.

Уоррен Шуди

@ Уоррен Шуди, какой у тебя подход?

Томас Але

Я вижу два очевидных подхода: 1. Вторая граница, перечисленная на en.wikipedia.org/wiki/…, выглядит так, как будто она должна работать. 2. Найти более плотную границу для функции, генерирующей момент.

Уоррен Шуди

@WarrenSchudy Граница Бернштейна дает , но только для . Я полагаю, это похоже на ответ Сашо.

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$

Томас Але

Это неизбежно, что границы в стиле Гаусса прекратятся в какой-то момент. Даже одна экспоненциально распределенная случайная величина в конечном итоге имеет более толстые хвосты, чем любая гауссовская.

Уоррен Шуди