Nierówności prawdopodobieństwa

Szukam pewnych nierówności prawdopodobieństwa dla sum niezwiązanych zmiennych losowych. Byłbym bardzo wdzięczny, gdyby ktokolwiek mógł mi coś przekazać.

Moim problemem jest znalezienie wykładniczej górnej granicy ponad prawdopodobieństwem, że suma niezwiązanych zmiennych losowych iid, które są w rzeczywistości pomnożeniem dwóch iidów Gaussa, przekracza pewną określoną wartość, tj. $\mathrm{Pr}[ X \geq \epsilon\sigma^2 N] \leq \exp(?)$ , w którym $X = \sum_{i=1}^{N} w_iv_i$ , $w_i$ i $v_i$ są generowane IID z $\mathcal{N}(0, \sigma)$ .

Próbowałem użyć granicy Chernoffa za pomocą funkcji generowania momentu (MGF), granica pochodna jest dana przez:

$\begin{eqnarray} \mathrm{Pr}[ X \geq \epsilon\sigma^2 N] &\leq& \min\limits_s \exp(-s\epsilon\sigma^2 N)g_X(s) \\ &=& \exp\left(-\frac{N}{2}\left(\sqrt{1+4\epsilon^2} -1 + \log(\sqrt{1+4\epsilon^2}-1) - \log(2\epsilon^2)\right)\right) \end{eqnarray}$

gdzie jest MGF z . Ale granica nie jest tak ciasna. Głównym problemem w moim problemie jest to, że zmienne losowe są nieograniczone i niestety nie mogę użyć granicy nierówności Hoeffdinga. $g_X(s) = \left(\frac{1}{1-\sigma^4 s^2}\right)^{\frac{N}{2}}$ $X$

Będę szczęśliwy, jeśli pomożesz mi znaleźć ścisłą wykładniczą granicę.

— Farzad
źródło

Brzmi jak problem związany z wykrywaniem kompresji. Spójrz na uwagi R. Vershynina na temat nieasymptotycznej teorii losowej macierzy, a konkretnie na granice tego, co nazywa zmiennymi losowymi podwykładniczymi . To zaczniesz. Jeśli potrzebujesz więcej wskazówek, daj nam znać, a postaram się opublikować więcej informacji.

— kardynał

Na stronie math.SE znajduje się co najmniej kilka powiązanych pytań i odpowiedzi na ten temat (wyłączenie odpowiedzialności: w tym jedno, w którym uczestniczyłem).

— kardynał

Produkt ma dystrybucję „normalnego produktu”. Uważam, że średnia tego produktu wynosi zero, a wariancja to gdzie to wariancja i . Dla largeish, można użyć centralne twierdzenie graniczne, aby uzyskać przybliżoną norality z . Jeśli potrafisz obliczyć odchylenie normalnej dystrybucji produktu, uważam, że możesz zastosować twierdzenie Berry'ego-Esseena, aby ograniczyć tempo zbieżności CDF.

w_{i} v_{i}

$w_i v_i$

σ^{4}

$\sigma^4$

σ^{2}

$\sigma^2$

w_{i}

$w_i$

v_{i}

$v_i$

N

$N$

X

$X$

— shabbychef

@shabbychef, Berry-Esseen ma dość powolną konwergencję, ponieważ jest to jednolita związana nad klasą wszystkich funkcji rozkładu .

F

$F$

— kardynał

@DilipSarwate: Przepraszam, że widzę twój komentarz jakiś czas temu. Myślę, że może być zainteresowany w następującym trochę papieru, co mam związanego kilka razy na math.SE oraz: TK Phillips i R. Nelson (1995), moment związany jest mocniej niż na Chernoffa zobowiązany do pozytywnego ogona prawdopodobieństwa , The American Statistician , vol 42, no. 2., 175–178.

— kardynał

Odpowiedzi:

Używając granicy Chernoffa, którą zasugerowałeś dla niektórych które zostaną określone później, gdzie zachodzi druga nierówność dzięki dla dowolnego . Teraz weźmy i , prawa strona staje się który daje dla każdego . $s\le 1/(2\sigma^2)$

P [X > t] \leq \exp (- s t) \exp (- (N / 2) \log (1 - σ^{4} s^{2})) \leq \exp (- s t + σ^{4} s^{2} N)

$P[X>t] \le \exp(-st) \exp\Big(-(N/2) \log(1-\sigma^4s^2) \Big) \le \exp(-st + \sigma^4s^2 N)$

- \log (1 - x) \leq 2 x

$-\log(1-x)\le 2x$

x \in (0, 1 / 2)

$x\in(0,1/2)$

t = ϵ σ^{2} N

$t=\epsilon \sigma^2 N$

s = t / (2 σ^{4} N)

$s=t/(2\sigma^4N)$

\exp (- t^{2} / (4 σ^{4} N) = \exp (- ϵ^{2} N / 4)

$\exp(-t^2/(4\sigma^4N)=\exp(-\epsilon^2 N/4)$

P [X > ϵ σ^{2} N] \leq \exp (- ϵ^{2} N / 4) .

$P[X>\epsilon \sigma^2 N] \le \exp(-\epsilon^2 N/4).$

ϵ \in (0, 1)

$\epsilon\in(0,1)$

Inną drogą jest bezpośrednie zastosowanie nierówności koncentracji, takich jak nierówność Hansona-Wrighta lub nierówności koncentracji w przypadku chaosu gaussowskiego rzędu 2, który obejmuje zmienną losową, którą jesteś zainteresowany.

Prostsze podejście bez korzystania z funkcji generowania momentu

Wziąć dla uproszczenia (w przeciwnym razie mogą się przeskalowanie przez podzielenie ). $\sigma=1$ $\sigma^2$

Zapis i . Pytasz o górne granice na . $v=(v_1,...,v_n)^T$ $w=(w_1,...,w_n)^T$ $P(v^Tw>\epsilon N)$

Niech. Wtedy przez niezależność i jest niezależny od z z stopni swobody. $Z= w^T v/\|v\|$ $Z\sim N(0,1)$ $v,w$ $\|v\|^2$ $Z$ $\chi^2$ $n$

Według standardowych granic standardowych zmiennych normalnych i , Połączenie z związkiem daje górną granicę na postaci . $\chi^2$

P (| Z | > ϵ \sqrt{n / 2}) \leq 2 \exp (- ϵ^{2} n / 4), P (‖ v ‖ > \sqrt{2 n}) \leq \exp (- n (\sqrt{2} - 1)^{2} / 2) .

$P(|Z|>\epsilon\sqrt{n/2})\le 2\exp(-\epsilon^2 n/4), \qquad\qquad P(\|v\|>\sqrt{2n}) \le \exp(-n(\sqrt 2 -1)^2/2).$

P (v^{T} w > ϵ N)

$P(v^Tw>\epsilon N)$

2 \exp (- ϵ^{2} n / 4) + \exp (- n (\sqrt{2} - 1)^{2} / 2)

$2\exp(-\epsilon^2 n/4) + \exp(-n(\sqrt 2 -1)^2/2)$

— Jlewk
źródło

Ograniczenie, które otrzymujesz, jest rzędu jako . Nie sądzę, że możesz zrobić dużo lepiej dla generała . Ze strony Wikipedii dotyczącej Zmiennych produktu dystrybucja wynosi gdzie jest zmodyfikowaną funkcją Bessela. Z (10.25.3) w liście funkcji DLMF , tak, że dla wystarczająco duża który nie da ci granicy sub Gaussa. $e^{-\epsilon}$ $\epsilon \to \infty$ $\epsilon$ $w_i v_i$ $K_0(z)/\pi$ $K_0$ $K_0(t) \sim e^{-t}/\sqrt{t}$ $x$ $\mathbb{P}(w_i v_i > x) \sim \int_x^\infty e^{-t}/\sqrt{t} dt$

— BookYourLuck
źródło