Dimostrazione Disuguaglianza Di Bernstein
Salve a tutti, nell'articolo che sto leggendo per la mia tesi viene utilizzato il seguente risultato:
$P{ X_1 + X_2 + ... + X_n > a} \leq e^{-a^2 / n }$
dove $X_1, X_2, ..., X_n$ sono variabili aleatorie indipendenti tali che $P{X_i = 1} = P{X_i = -1} = 1/2$.
Nell'articolo la disuguaglianza viene chiamata Disugaglianza di Bernstein, ma cercando un po' su internet ho trovato che è un caso particolare. Comunque, aldilà dei nomi, il mio problema è che non riesco a dimostrarla.
L'idea della dimostrazione dovrebbe essere la seguente:
$P{ X_1 + X_2 + ... + X_n > a} = P{ e^(t(X_1 + X_2 + ... + X_n ))> e^(ta)}$ per t > 0
Utilizzando la disuguaglianza di Markov e il fatto che le $X_i$ sono indipendenti si ha che:
$P{ e^(t(X_1 + X_2 + ... + X_n ))> e^(ta)} leq (prod_(i = 1)^(n) E[e^(tX_i)])/e^(ta)$ per ogni t > 0.
a questo punto bisognerebbe trovare il t > 0 opportuno che massimizzi il secondo membro e la dimostrazione dovrebbe essere fatta. Il problema è che dopo conti su conti non trovo riesco a trovare il risultato che vorrei dimostrare.
Vi chiedo, quindi, un aiuto, sperando che qualcuno abbia qualche idea o conosca già la dimostrazione.
Ringrazio in anticipo chi vorrà aiutarmi.
RainbowInTheDark
$P{ X_1 + X_2 + ... + X_n > a} \leq e^{-a^2 / n }$
dove $X_1, X_2, ..., X_n$ sono variabili aleatorie indipendenti tali che $P{X_i = 1} = P{X_i = -1} = 1/2$.
Nell'articolo la disuguaglianza viene chiamata Disugaglianza di Bernstein, ma cercando un po' su internet ho trovato che è un caso particolare. Comunque, aldilà dei nomi, il mio problema è che non riesco a dimostrarla.
L'idea della dimostrazione dovrebbe essere la seguente:
$P{ X_1 + X_2 + ... + X_n > a} = P{ e^(t(X_1 + X_2 + ... + X_n ))> e^(ta)}$ per t > 0
Utilizzando la disuguaglianza di Markov e il fatto che le $X_i$ sono indipendenti si ha che:
$P{ e^(t(X_1 + X_2 + ... + X_n ))> e^(ta)} leq (prod_(i = 1)^(n) E[e^(tX_i)])/e^(ta)$ per ogni t > 0.
a questo punto bisognerebbe trovare il t > 0 opportuno che massimizzi il secondo membro e la dimostrazione dovrebbe essere fatta. Il problema è che dopo conti su conti non trovo riesco a trovare il risultato che vorrei dimostrare.
Vi chiedo, quindi, un aiuto, sperando che qualcuno abbia qualche idea o conosca già la dimostrazione.
Ringrazio in anticipo chi vorrà aiutarmi.
RainbowInTheDark
Risposte
Dopo giorni sono, incredibilmente sono riuscito a ottenre una dimostrazione !!!
Appena avrò un attimo di tempo ve la posterò per completezza
Appena avrò un attimo di tempo ve la posterò per completezza
Oppure se vuoi usare un po' di cannoni la tua disuguaglianza discende direttamente dalla disuguaglianza di Hoeffding 
http://en.wikipedia.org/wiki/Hoeffding%27s_inequality
http://www.stat.duke.edu/courses/Spring ... c/hoef.pdf
http://en.wikipedia.org/wiki/Hoeffding%27s_inequality
http://www.stat.duke.edu/courses/Spring ... c/hoef.pdf
Siano $X_1, X_2, X_3, \cdots, X_n$ variabili aleatorie indipendenti tali che $P\{X_i = 1\} = P\{X_i = -1\} = \frac{1}{2}$ per ogni $i = 1, 2, \cdots, n$. Allora:
$P\{|X_1+X_2+\cdots+X_n| \geq a\} \leq 2e^{-\frac{a^2}{2n}}$
con $a > 0$.
Notiamo che la distribuzione di $|X_1+X_2+\cdots+X_n|$ è simmetrica, quindi:
$P\{|X_1+X_2+\cdots+X_n| \geq a\} = 2P\{X_1+X_2+\cdots+X_n \geq a\}$
Dimostrare la disuguaglianza è equivalente a dimostrare:
$P\{X_1+X_2+\cdots+X_n \geq a\} \leq e^{-\frac{a^2}{n}}$
Fissiamo $\lambda > 0$. Allora la seconda disuguaglianza diventa:
$P\{e^{\lambda(X_1+X_2+\cdots+X_n)} \geq e^{\lambda a}\} \leq \frac{E[e^{\lambda(X_1+X_2+\cdots+X_n)}]}{e^{\lambda a}}= e^{-\lambda a}\prod_{i=1}^nE[e^{\lambda X_i}] =$
$= e^{-\lambda a}E[e^{\lambda X_1}]^n = e^{-\lambda a} {(\frac{e^\lambda + e^{-\lambda}}{2})^n }$
dove la prima disuguaglianza è la disuguaglianza di Markov, mentre nel secondo passaggio abbiamo utilizzato l'ipotesi d'indipendenza delle $X_i$.
Poichè la disuguaglianza vale per ogni $\lambda >0$, allora vale anche:
$P\{X_1+X_2+\cdots+X_n \geq a\} \leq \min_{\lambda > 0} e^{-\lambda a} (\frac{e^\lambda + e^{-\lambda}}{2})^n$
Bisogna trovare, dunque, il $\lambda^\star$ che minimizza il secondo membro della disequazione.
Ricordando lo sviluppo in serie della funzione esponenziale si ha che:
$e^\lambda + e^{-\lambda}= 1 + \lambda + \frac{\lambda^2}{2} + \sum_{k = 3}^{\infty} \frac{\lambda^k}{k!} + 1 - \lambda + \frac{\lambda^2}{2} + \sum_{k = 3}^{\infty} \frac{(-1)^k\lambda^k}{k!} = 2 \sum_{k = 0}^{\infty} \frac{\lambda^{2k}}{(2k)!} \leq \sum_{k = 0}^{\infty} \frac{(\frac{\lambda^2}{2})^k}{k!} = 2 e^\frac{t^2}{2}$
dove abbiamo utilizzato il fatto che $(2n)! \geq n!2^n$.
Allora:
$e^{-\lambda a} (\frac{e^\lambda + e^{-\lambda}}{2})^n \leq e^{-\lambda a}e^{\frac{n\lambda^2}{2}} = e^{\frac{n\lambda^2}{2}-\lambda a}$ per ogni $\lambda > 0$
Bisogna, quindi, trovare $\lambda^\star$ che minimizza la funzione $e^{\varphi(\lambda)}$, dove $\varphi$ è definita, per ogni $\lambda > 0$, da $\varphi(\lambda) = \frac{n\lambda^2}{2}-\lambda a$. Minimizzando quindi $\varphi(\lambda)$, otteniamo $\lambda^\star = \frac{a}{n}$, da cui si ha $\varphi(\lambda^\star) = -\frac{a^2}{2n}$. Infine si ha, quindi, che :
$P\{|X_1+X_2+\cdots+X_n| \geq a\} = 2P\{X_1+X_2+\cdots+X_n \geq a\} \leq 2e^{-\frac{a^2}{2n}}$
per ogni $a > 0$.
$P\{|X_1+X_2+\cdots+X_n| \geq a\} \leq 2e^{-\frac{a^2}{2n}}$
con $a > 0$.
Notiamo che la distribuzione di $|X_1+X_2+\cdots+X_n|$ è simmetrica, quindi:
$P\{|X_1+X_2+\cdots+X_n| \geq a\} = 2P\{X_1+X_2+\cdots+X_n \geq a\}$
Dimostrare la disuguaglianza è equivalente a dimostrare:
$P\{X_1+X_2+\cdots+X_n \geq a\} \leq e^{-\frac{a^2}{n}}$
Fissiamo $\lambda > 0$. Allora la seconda disuguaglianza diventa:
$P\{e^{\lambda(X_1+X_2+\cdots+X_n)} \geq e^{\lambda a}\} \leq \frac{E[e^{\lambda(X_1+X_2+\cdots+X_n)}]}{e^{\lambda a}}= e^{-\lambda a}\prod_{i=1}^nE[e^{\lambda X_i}] =$
$= e^{-\lambda a}E[e^{\lambda X_1}]^n = e^{-\lambda a} {(\frac{e^\lambda + e^{-\lambda}}{2})^n }$
dove la prima disuguaglianza è la disuguaglianza di Markov, mentre nel secondo passaggio abbiamo utilizzato l'ipotesi d'indipendenza delle $X_i$.
Poichè la disuguaglianza vale per ogni $\lambda >0$, allora vale anche:
$P\{X_1+X_2+\cdots+X_n \geq a\} \leq \min_{\lambda > 0} e^{-\lambda a} (\frac{e^\lambda + e^{-\lambda}}{2})^n$
Bisogna trovare, dunque, il $\lambda^\star$ che minimizza il secondo membro della disequazione.
Ricordando lo sviluppo in serie della funzione esponenziale si ha che:
$e^\lambda + e^{-\lambda}= 1 + \lambda + \frac{\lambda^2}{2} + \sum_{k = 3}^{\infty} \frac{\lambda^k}{k!} + 1 - \lambda + \frac{\lambda^2}{2} + \sum_{k = 3}^{\infty} \frac{(-1)^k\lambda^k}{k!} = 2 \sum_{k = 0}^{\infty} \frac{\lambda^{2k}}{(2k)!} \leq \sum_{k = 0}^{\infty} \frac{(\frac{\lambda^2}{2})^k}{k!} = 2 e^\frac{t^2}{2}$
dove abbiamo utilizzato il fatto che $(2n)! \geq n!2^n$.
Allora:
$e^{-\lambda a} (\frac{e^\lambda + e^{-\lambda}}{2})^n \leq e^{-\lambda a}e^{\frac{n\lambda^2}{2}} = e^{\frac{n\lambda^2}{2}-\lambda a}$ per ogni $\lambda > 0$
Bisogna, quindi, trovare $\lambda^\star$ che minimizza la funzione $e^{\varphi(\lambda)}$, dove $\varphi$ è definita, per ogni $\lambda > 0$, da $\varphi(\lambda) = \frac{n\lambda^2}{2}-\lambda a$. Minimizzando quindi $\varphi(\lambda)$, otteniamo $\lambda^\star = \frac{a}{n}$, da cui si ha $\varphi(\lambda^\star) = -\frac{a^2}{2n}$. Infine si ha, quindi, che :
$P\{|X_1+X_2+\cdots+X_n| \geq a\} = 2P\{X_1+X_2+\cdots+X_n \geq a\} \leq 2e^{-\frac{a^2}{2n}}$
per ogni $a > 0$.
Grazie di aver postato la tua soluzione in modo completo. 
non ho controllato tutto, ma sembra andare.
non ho controllato tutto, ma sembra andare.
"RainbowInTheDark":
Siano $X_1, X_2, X_3, \cdots, X_n$ variabili aleatorie indipendenti tali che $P\{X_i = 1\} = P\{X_i = -1\} = \frac{1}{2}$ per ogni $i = 1, 2, \cdots, n$. Allora:
$P\{|X_1+X_2+\cdots+X_n| \geq a\} \leq 2e^{-\frac{a^2}{n}}$
con $a > 0$.
Questa disuguaglianza e' falsa.
Infatti se prendi n=2 hai che $|X_1+X_2|$ e' una v.a. che vale 0 ed 2 con stessa probabilita' $1/2$.
Se $a = 1.9$ hai che $P(|X_1+X_2|>a)=P(|X_1+X_2|=2)=1/2$
ma $2 e^{-(a^2)/2}= 0.3289$.
Ciao DajeForte
questo non mi torna, come puoi affermare questa uguaglianza?
"DajeForte":
Se $a = 1.9$ hai che $P(|X_1+X_2|>a)=P(|X_1+X_2|=2)$
questo non mi torna, come puoi affermare questa uguaglianza?
Ciao hamming come va?
La variabile doppia $(X_1,X_2)$ assume i 4 valori (con stessa probabilita' $1/4$) (1,1) (-1,1) (1,-1) (-1,-1).
Su questi 4 la variabile $X_1+X_2$ assume i valori +2, 0, 0, -2 (rispettando l'ordine con cui ho elencato le realizzazione della doppia).
Dunque la variabile $|X_1+X_2|$ assume i valori 0 ( se e solo se $X_1+X_2$ e' 0) ed 2 (se e solo se $X_1+X_2$ e' 2 o -2).
Dunque l'evento "$|X_1+X_2|$ e' piu fgrande di 1.9" equivale a " $|X_1+X_2|$ e' uguale a 2".
La variabile doppia $(X_1,X_2)$ assume i 4 valori (con stessa probabilita' $1/4$) (1,1) (-1,1) (1,-1) (-1,-1).
Su questi 4 la variabile $X_1+X_2$ assume i valori +2, 0, 0, -2 (rispettando l'ordine con cui ho elencato le realizzazione della doppia).
Dunque la variabile $|X_1+X_2|$ assume i valori 0 ( se e solo se $X_1+X_2$ e' 0) ed 2 (se e solo se $X_1+X_2$ e' 2 o -2).
Dunque l'evento "$|X_1+X_2|$ e' piu fgrande di 1.9" equivale a " $|X_1+X_2|$ e' uguale a 2".
La variabile doppia $(X_1,X_2)$ assume i 4 valori (con stessa probabilita' $1/4$) (1,1) (-1,1) (1,-1) (-1,-1).
Su questi 4 la variabile $X_1+X_2$ assume i valori +2, 0, 0, -2 (rispettando l'ordine con cui ho elencato le realizzazione della doppia).
Dunque la variabile $|X_1+X_2|$ assume i valori 0 ( se e solo se $X_1+X_2$ e' 0) ed 2 (se e solo se $X_1+X_2$ e' 2 o -2).
Dunque l'evento "$|X_1+X_2|$ e' piu fgrande di 1.9" equivale a " $|X_1+X_2|$ e' uguale a 2".
ok c'hai ragione ed è pure logico
parliamo di v.a. discrete...."DajeForte":
Ciao hamming come va?
eeh è un periodo un po' laborioso
Hai perfettamente ragione infatti la disuguaglianza giusta è la seguente:
$P{|X_1+X_2+…+X_n| > a} ≤ 2e^{−a^2/(2n)}$
la dimostrazione che ho riportato è giusta, solo che ho dimenticato il 2 alla fine quando calcolo $\varphi(\lambda^\star)$ !
Ho modificato la dimsotrazione e l'enunciato ora dovrebbero essere a posto 
$P{|X_1+X_2+…+X_n| > a} ≤ 2e^{−a^2/(2n)}$
la dimostrazione che ho riportato è giusta, solo che ho dimenticato il 2 alla fine quando calcolo $\varphi(\lambda^\star)$ !
Ho modificato la dimsotrazione e l'enunciato ora dovrebbero essere a posto
Accedi a tutti gli appunti
Tutor AI: studia meglio e in meno tempo