Zrozumienie pomiaru nierówności koncentracji

W duchu tego pytania. Rozumiejąc dowód lematu stosowanego w nierówności Hoeffdinga , staram się zrozumieć kroki, które prowadzą do nierówności Hoeffdinga.

Najbardziej tajemnicą dla mnie jest część obliczania momentów wykładniczych dla sumy zmiennych iid, po których stosuje się nierówność Markowa.

Moim celem jest zrozumienie: Dlaczego ta technika powoduje ścisłą nierówność i czy jest ona najostrzejsza, jaką możemy osiągnąć? Typowe wyjaśnienie odnosi się do właściwości generujących moment wykładnika. Jednak uważam to za zbyt niejasne.

Post na blogu Tao, http://terrytao.wordpress.com/2010/01/03/254a-notes-1-concentration-of-measure/#hoeff , może zawierać kilka odpowiedzi.

Mając na uwadze ten cel, moje pytanie dotyczy trzech punktów w poście Tao, w których utknąłem i które, mam nadzieję, mogłyby dać wgląd w wyjaśnienie.

Tao wyprowadza następującą nierówność za pomocą k-tego momentu Jeśli jest to prawdą dla dowolnego k, kończy wykładniczą granicę. Tu się zgubiłem.
$P (| S_{n} | \geq λ \sqrt{n}) \leq 2 (\frac{\sqrt{e k / 2}}{λ})^{k} . (7)$ $\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq 2 (\frac{\sqrt{ek/2}}{\lambda})^k. \ \ \ \ \ (7)$ $P (| S_{n} | \geq λ \sqrt{n}) \leq C \exp (- c λ^{2}) (8)$ $\displaystyle {\bf P}( |S_n| \geq \lambda \sqrt{n} ) \leq C \exp( - c \lambda^2 ) \ \ \ \ \ (8)$
${X}$ ${[a,b]}$ ${t>0}$
$E e^{t X} \leq e^{t E X} (1 + O (t^{2} V a r (X) \exp (O (t (b - a)))) . (9)$ $\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} (1 + O( t^2 {\bf Var}(X) \exp( O( t (b-a) ) ) ). \ \ \ \ \ (9)$ $E e^{t X} \leq e^{t E X} \exp (O (t^{2} (b - a)^{2})) . (10)$ $\displaystyle {\bf E} e^{tX} \leq e^{t {\bf E} X} \exp( O( t^2 (b-a)^2 ) ). \ \ \ \ \ (10)$ $\displaystyle e^{tX} = 1 + tX + O( t^2 X^2 \exp( O(t) ) )$ .Dlaczego rozszerzenie może być ograniczone tym kwadratowym terminem? i jak przebiega równanie 10?
${O(t^2(b-a)^2)}$ ${t^2 (b-a)^2/8}$

Wszelkie dalsze intuicje \ wyjaśnienia dotyczące dowodu nierówności lub powodu, dla którego nie możemy ustalić ściślejszej granicy, są zdecydowanie mile widziane.

probability probability-inequalities Lew
źródło

Czy przeczytałeś oryginalny artykuł Hoeffdinga?

Alecos Papadopoulos

@AlecosPapadopoulos I tak naprawdę nie. Mam wrażenie, że wyprowadzenie składa się z kroków algebraicznych typowo nauczanych na kursach matematycznych, bez wyjaśnienia, którego szukam. Czy możesz powiedzieć inaczej?

Leo

Sugeruję, żebyś to przeczytał. Stabilny adres URL w jstor to jstor.org/stable/2282952 . To, co „ma dla ciebie największą tajemnicę”, to twierdzenia 1, 2 i 3 artykułu, których dowody znajdują się w części 4 artykułu (nie na końcu) i dla mnie wyglądają dość jasno. Nie wiem, czy szukasz jakiejś „niematematycznej” intuicji - jeśli tak, to nie zawsze istnieje.

Alecos Papadopoulos,

$\mathbb{E}e^X$ $\mathbb{E} X$ $X$ $\mathbb{E} e^X$ $\mathbb{E}X$ $\mathbb{E} e^X$ $\mathbb{E} e^X$ $e^{X}=1+X+\frac{X^2}{2}+\frac{X^3}{6}+\ldots$ $X$ $\mathbb{E}X$ $X$

gmravi2003
źródło

f

$f$

0

$0$

e^{X}

$e^X$

f (X)

$f(X)$

f

$f$

f (x) > 0

$f(x) >0$

X

$X$

e^{X}

$e^X$

Nie przyjrzałem się temu, ale podejrzewam, że wykładniczy ma pewne szczególne właściwości, w tym te, które wymieniasz, które są krytyczne: wszystkie współczynniki powinny być ściśle dodatnie i dobrze, że zbiega się absolutnie wszędzie. Sądzę jednak, że istnieją głębsze powody, dla których ta funkcja jest niezbędna, związana z właściwościami transformat Fouriera i Laplace'a. Rozsądne może być zbadanie pochodnych nierówności miar, aby zobaczyć, jakie właściwości wykładnicze są rzeczywiście używane! (+1)

whuber

P {x 1 + x 2 > 0} = E {1 [x 1 + x 2 > 0]} \leq E {e x p (t * x 1)} E {e x p (t * x 2)}

$P\{x1+x2>0\}=E\{1[x1+x2>0]\} \leq E\{exp(t*x1)\}E\{exp(t*x2)\}$

E {e x p (t * x 1)} < 1

$E\{exp(t*x1)\}<1$

Chciałbym Cię zainteresować pytaniem o szczelność tej granicy: stats.stackexchange.com/questions/77019/…

Leo

Zrozumienie pomiaru nierówności koncentracji

Odpowiedzi: