Suma niezależnych wykładniczych zmiennych losowych

Czy możemy udowodnić ostry wynik koncentracji na sumie niezależnych wykładniczych zmiennych losowych, tj. Niech będą niezależnymi zmiennymi losowymi takimi, że . Niech . Czy możemy udowodnić granice postaci . Wynika to bezpośrednio, jeśli użyjemy formy wariancji granic chernoffa i dlatego uważam, że jest to prawda, ale granice, które czytam, wymagają ograniczenia lub zależą od ograniczeń zmiennych. Czy ktoś mógłby mi wskazać na dowód powyższego? $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 Gderać
źródło

wystarczy postępować zgodnie z dowodem chernoffa: łatwo jest wyznaczyć wykładniczy moment wykładniczych zmiennych losowych.

Sasho Nikolov

Próbowałem powtórzyć dowód Chernoffa. Zrobiłem to w prostszym przypadku, gdy wszystkie . Mogę uzyskać rodzaj relacji, której szukam, w łagodnym stanie . Czy taki stan powstaje naturalnie, czy może z powodu mojego niezbyt dobrego rozwiązania?

λ_{i} = λ

$\lambda_i = \lambda$

t < n λ

$t < n\lambda$

NAg

Sprawdź Lemma 2.8 tutaj eprint.iacr.org/2010/076.pdf

Sasho Nikolov

Tak, to ma sens. Nawet w ich lematu mają stan na jest wystarczająco małe. OK, więc moje rozwiązanie wydaje się prawidłowe. Wielkie dzięki za linki i sugestie.

t

$t$

NAg

@SureshVenkat gotowe. O, myślę, że w twoim pytaniu są literówki. Po pierwsze, to bardzo dziwny CDF dla dodatniego . Czy chodziło Ci o ? Jeśli tak, to wariancja ma postać a twoja granica chernoffa nie wygląda całkiem dobrze.

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

Sasho Nikolov

Odpowiedzi:

Dla konkretności, powiedz, że pdf rv to $X_i$

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

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

Jest to rozkład Laplace'a lub podwójny rozkład wykładniczy. Jego wariancja to . Plik cdf jest $\frac{2}{\lambda_i^2}$

Par [X_{ja} \leq x] = 1 - \frac{1}{2)} {mi}^{- λ_{ja} x}

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

x \geq 0

$x \geq 0$

Funkcja generowania momentu to $X_i$

mi {mi}^{u X_{ja}} = \frac{1}{1 - u^{2)} / λ_{ja}^{2)}},

$\mathbf{E}\ e^{uX_i} = \frac{1}{1 - u^2/\lambda_i^2},$ dla . Używając tego faktu i metody momentu wykładniczego, która jest standardowa w dowodzie granic Chernoffa, otrzymujesz to dla i , zachodzi następująca nierówność

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

Par [X > t σ] < {mi}^{- t^{2)} / 4},

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

o ile . Szczegółową pochodną można znaleźć w dowodzie lematu 2.8 tego artykułu .

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

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

Sasho Nikolov
źródło

Wielkie dzięki za odpowiedź. Jednak w mojej aplikacji niekoniecznie jest prawdą, że . jednak oczekiwać jeszcze silniejszej koncentracji w przypadku, gdy . Możemy uzyskać taki wynik, jeśli nie użyjemy aproksymacji która ogranicza zakres w dowodzie, ale jego analiza staje się niemożliwa do zarządzania w przypadku innej . Wszelkie sugestie dotyczące tego frontu?

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

będzie to energiczne machanie ręką, ale spodziewam się, że tak duże wartości najprawdopodobniej wystąpią, gdy tylko niewielka liczba przekroczy medianęprzez wiele. ale zmienne podwójnie wykładnicze mają cięższy ogon niż gaussowie, a niewielka ich liczba nie może się tak skoncentrować

X

$X$

X_{i}

$X_i$

| X_{i} |

$|X_i|$

Sasho Nikolov

Zdaję sobie sprawę, że to, co napisałem powyżej, nie jest jasne: spodziewam się, że wyjście z ogona

wygląda jak ogon innego rv

który jest sumą małej liczby podwójnych wykładniczych rv Ogon takiego

nie powinien być sub-gaussowski.

X

$X$

X^{'}

$X'$

X^{'}

$X'$

Sasho Nikolov

W przypadku rozkładu Laplace'a, jeśli używasz granicy Bernoulliego, możesz pisać

gdzie . Następnie klasyczna metoda Chernoffa daje

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

Par [\sum_{ja} X_{ja} \geq t σ] \leq \frac{1 + \sqrt{1 + 2) t^{2)}}}{2)} {mi}^{1 - \sqrt{1 + 2) t^{2)}}} \leq {\begin{cases} (mi t / \sqrt{2)} + 1) {mi}^{- \sqrt{2)} t} \\ {mi}^{- 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}} .$

Zauważ, że te granice przytrzymać przez nieograniczony wartości i . Granice po prawej stronie pokazują dwa możliwe reżimy. Dla małych wartości otrzymujemy `normalne” stężenie , natomiast dla dużych wartościach otrzymujemy $t$ $\lambda_i$ $t$ $e^{-t^2/2}$ $t$ , co jest również CDF dla pojedynczej zmiennej rozproszonej Laplace'a. $\approx e^{-\sqrt{2}t}$

związany pozwala interpolacji pomiędzy tymi dwoma sytuacjami, ale podejrzewam, że w prawie wszystkich przypadkach jeden będzie pewnie w każdym dużymlub małejobozie. $1-\sqrt{1+2t^2}$ $t$ $t$

W przypadku rozkładu wykładniczego te same techniki dają nam gdzie. Stąd Nadal masz coś nieco normalnie wyglądającego, ale zzamiast $Ee^{u\sum_iX_i}\le\frac{1}{1-u\mu}$ $\mu=\sum_i 1/\lambda_i$

Par [(\sum_{ja} X_{ja}) - μ \geq t μ] \leq (t + 1) {mi}^{- t} \leq {mi}^{- 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$

jak moglibyśmy się spodziewać. Nie wiem, czy można uzyskać granicę pod względem wariancji. Możesz spróbować studiować

, ale wydaje się, że nie jest to łatwe do pracy.

t σ

$t\sigma$

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

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

Thomas Ahle
źródło

Nie mam czasu na wypracowanie szczegółów, ale jestem na 99,9% pewien, że można uzyskać granicę wykładniczo zmiennych losowych zależnych od wariancji. Twoja funkcja generowania momentu wydaje się zbyt luźna.

Warren Schudy,

@Warren Schudy, jakie byłoby twoje podejście?

Thomas Ahle,

Widzę dwa oczywiste podejścia: 1. Wygląda na to, że druga granica wymieniona na en.wikipedia.org/wiki/… powinna działać. 2. Znajdź ściślej związany z funkcją generowania momentu.

Warren Schudy,

@WarrenSchudy Bernstein związany daje

, ale tylko dla

. Przypuszczam, że jest to podobne do odpowiedzi 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,

Nieuniknione jest, że granice w stylu gaussowskim w pewnym momencie się zatrzymają. Nawet pojedyncza zmienna losowa o rozkładzie wykładniczym ostatecznie ma grubsze ogony niż jakikolwiek gaussowski.

Warren Schudy,