Compreensão da prova de um lema usado na desigualdade de Hoeffding

Estou estudando as anotações de Larry Wasserman sobre estatística, que usam Casella e Berger como seu texto principal. Estou trabalhando nas anotações da aula, conjunto 2, e fiquei preso na derivação do lema usado na desigualdade de Hoeffding (pp.2-3). Estou reproduzindo a prova nas notas abaixo e depois da prova vou apontar onde estou preso.

Lema

Suponha que $\mathbb{E}(X) = 0$ e que $a \le X \le b$ . Em seguida, $\mathbb{E}(e^{tX}) \le e^{t^2 (b-a)^2/8}$ .

Prova

Como $a \le X \le b$ , podemos escrever $X$ como uma combinação convexa de $a$ e $b$ , nomeadamente $X = \alpha b + (1 - \alpha) a$ onde $\alpha = \frac{X-a}{b-a}$ . Pela convexidade da função $y \to e^{ty}$ temos

$e^{tX} \le \alpha e^{tb} + (1 - \alpha) e^{ta} = \frac{X-a}{b-a} e^{tb} + \frac{b-X}{b-a} e^{ta}$

Tome expectativas de ambos os lados e use o fato $\mathbb{E}(X) = 0$ para obter

$\mathbb{E}(e^{tX}) \le \frac{-a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} = e^{g(u)}$

onde $u = t(b-a)$ , $g(u) = -\gamma u + \log(1-\gamma + \gamma e^{u})$ e $\gamma = -a /(b-a)$ . Observe que . Também $g(0) = g^{'}(0) = 0$ para todos. $g^{''}(u) \le 1/4$ $u > 0$

Pelo teorema de Taylor, existe um tal que $\varepsilon \in (0, u)$ $g(u) = g(0) + u g^{'}(0) + \frac{u^2}{2} g^{''}(\varepsilon) = \frac{u^2}{2} g^{''}(\varepsilon) \le \frac{u^2}{8} = \frac{t^2(b-a)^2}{8}$

Logo, . $\mathbb{E}(e^{tX}) \le e^{g(u)} \le e^{\frac{t^2(b-a)^2}{8}}$

Eu poderia seguir a prova até

mas eu sou incapaz de descobrir como derivar. $\mathbb{E}(e^{tX}) \le \frac{-a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} = e^{g(u)}$ $u, g(u), \gamma$

probability probability-inequalities Anand
fonte

É interessante que o máximo valor de

e, assim, o resultado é efectivamente

, que parece muito familiar a surgir por pura coincidência. Suspeito que possa haver outra maneira, possivelmente mais fácil, de obter o resultado por meio de um argumento probabilístico.

var (X)

$\text{var}(X)$

σ_{max}^{2} = (b - a)^{2} / 4

$\sigma_{\max}^2 = (b-a)^2/4$

E [e^{t X}] \leq e^{σ_{max}^{2} t^{2} / 2}

$E[e^{tX}] \leq e^{\sigma_{\max}^2t^2/2}$

Dilip Sarwate

@DilipSarwate Meu entendimento é que a variação máxima ocorre para uma variável aleatória uniforme

. A variância de

X \sim U (a, b)

$X \sim \mathcal{U}(a,b)$

X

$X$

. Você pode explicar como conseguiu

V a r (X) = \frac{(b - a)^{2}}{12}

$\mathsf{Var}(X) = \frac{(b-a)^2}{12}$

\frac{(b - a)^{2}}{4}

$\frac{(b-a)^2}{4}$

Anand

Concentrando a massa nos pontos finais ...

Elvis

@DilipSarwate Adicionei alguns comentários na prova, que podem esclarecer um pouco porque o pior caso é a variação máxima.

Elvis

@DilipSarwate - Veja o lema 1 e o exercício 1 aqui: terrytao.wordpress.com/2010/01/03/… . Parece que há uma derivação mais simples que depende da desigualdade de Jensen e da expansão de taylor. No entanto, os detalhes disso não são claros para mim. Talvez alguém possa entender isso. (derivação de (9) a (10) e exercício 1)

Leo

Não sei se entendi sua pergunta corretamente. Vou tentar responder: tente escrever em função de: isso é natural, pois você deseja um limite em

- \frac{a}{b - a} e^{t b} + \frac{b}{b - a} e^{t a}

$-\frac{a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta}$

u = t (b - a)

$u = t(b-a)$

e^{\frac{u^{2}}{8}}

$e^{u^2 \over 8}$

Ajudado pela experiência, você saberá que é melhor optar por escrevê-lo no formato . Então $e^{g(u)}$ leva a

e^{g (u)} = - \frac{a}{b - a} e^{t b} + \frac{b}{b - a} e^{t a}

$e^{g(u)} = -\frac{a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta}$

com

\begin{aligned} g (u) & = \log (- \frac{a}{b - a} e^{t b} + \frac{b}{b - a} e^{t a}) \\ = \log (e^{t a} (- \frac{a}{b - a} e^{t (b - a)} + \frac{b}{b - a})) \\ = t a + \log (γ e^{u} + (1 - γ)) \\ = - γ u + \log (γ e^{u} + (1 - γ)), \end{aligned}

$\begin{align*} g(u) &= \log\left( -\frac{a}{b-a} e^{tb} + \frac{b}{b-a} e^{ta} \right)\\ &= \log\left( e^{ta} \left( -\frac{a}{b-a} e^{t(b-a)} + \frac{b}{b-a} \right)\right)\\ &= ta + \log\left( \gamma e^u + (1-\gamma) \right)\\ &= -\gamma u + \log\left( \gamma e^u + (1-\gamma) \right),\\ \end{align*}$

γ = - \frac{a}{b - a}

$\gamma = - {a \over b-a}$

Esse é o tipo de coisa que você estava pedindo?

Edit: alguns comentários sobre a prova

O primeiro truque merece ser analisado com cuidado: se é uma função convexa e é uma variável aleatória centralizada, então $\phi$ $a\le X\le b$ $E (ϕ (X)) \leq - \frac{a}{b - a} ϕ (b) + \frac{b}{b - a} ϕ (a) = E (ϕ (X_{0})),$ $\mathbb{E}(\phi(X)) \le -{a\over b-a} \phi(b) + {b \over b-a} \phi(a) = \mathbb{E}(\phi(X_0)),$ $X_0$ $\begin{aligned} P (X_{0} = a) & = \frac{b}{b - a} \\ P (X_{0} = b) & = - \frac{a}{b - a} . \end{aligned}$ $\begin{align*} \mathbb P(X_0=a) &= {b \over b-a}\\ \mathbb P(X_0=b) &= -{a \over b-a}.\end{align*}$ $X_0$ $[a,b]$ $V a r (X) = E (X^{2}) \leq E (X_{0}^{2}) = \frac{b a^{2} - a b^{2}}{b - a} = - a b .$ $\mathsf{Var} (X) = \mathbb{E}(X^2) \le \mathbb{E}(X_0^2) = {ba^2 - ab^2 \over b-a } = - ab.$ $(b-a)$ $(b-a)^2\over 4$ $(b-a)^2 + 4ab \ge 0$ $a=-b$
$u = t(b-a)$ $X$ $\mathbb{E}\left( e^{tX} \right) \le s(t)$ $b-a=1$ $s( t(b-a) )$ $s(t)$

$\mathbb{E}(\phi(X))$ $\mathbb{E}(\phi(tX)) \le \mathbb{E}(\phi(tX_0))$ $u$ $\gamma$ $u = u_0 = t_0 (b_0 - a_0)$ $\gamma = \gamma_0 = - {a_0 \over b_0-a_0}$ $t, a, b$ $t = {t_0 \over \alpha}$ $a = \alpha a_0$ $b = \alpha a_0$
$- \frac{a}{b - a} ϕ (t b) + \frac{b}{b - a} ϕ (t a) = - \frac{a_{0}}{b_{0} - a_{0}} ϕ (t b_{0}) + \frac{b_{0}}{b_{0} - a_{0}} ϕ (a_{0}) .$ $-{a\over b-a} \phi(tb) + {b \over b-a} \phi(ta) = -{a_0\over b_0-a_0} \phi(tb_0) + {b_0 \over b_0-a_0} \phi(a_0).$ $u$
$g$ $u$ $\gamma$

$\gamma = -{a\over b-a}$ $1 -\gamma = {b\over b-a}$ $at = -\gamma u$ $bt = (1-\gamma)u$
$\begin{aligned} E (ϕ (t X)) \leq & - \frac{a}{b - a} ϕ (t b) + \frac{b}{b - a} ϕ (t a) \\ = & γ ϕ ((1 - γ) u) + (1 - γ) ϕ (- γ u) \end{aligned}$ $\begin{align*} \mathbb{E}(\phi(tX)) \le &-{a\over b-a} \phi(tb) + {b \over b-a} \phi(ta) \\ = & \gamma \phi((1-\gamma)u) + (1-\gamma) \phi(-\gamma u) \end{align*}$

$\phi=\exp$

Espero ter esclarecido um pouco.

Elvis
fonte

isso é exatamente o que eu estava procurando. Muito obrigado.

Anand

@ E eu sei que é difícil seguir os conselhos, mas acho que você não deve começar se concentrando em detalhes técnicos, mas sim tentar entender por que esse limite pode existir ... então a prova deve parecer mais fácil. Tentei mostrar o porquê na segunda parte, adicionada esta manhã (você precisa dormir em uma pergunta como esta - pelo menos eu preciso). Eu acho terrível como esse tipo de intuição não apareça na maioria dos livros didáticos ... mesmo se você receber a parte técnica, desde que não tenha as idéias, tudo parece mágico. Obrigado e CrossV por me dar a oportunidade de pensar nisso em detalhes!

Elvis

E [e^{t X}] \leq e^{E [t^{2} X^{2} / 2]} = e^{(t^{2} / 2) E [X^{2}]} = e^{(t^{2} / 2) var (X)} \leq e^{t^{2} σ_{max}^{2} / 2} ?

$E[e^{tX}] \leq e^{E[t^2X^2/2]} = e^{(t^2/2)E[X^2]} = e^{(t^2/2)\text{var}(X)} \leq e^{t^2\sigma_{\max}^2/2}?$

precisa saber é o seguinte

@ Elvis Obrigado pelo conselho e por reservar um tempo para escrever a parte intuitiva. Eu preciso gastar algum tempo para entender isso!

Anand

@ Elvis Levando em conta a intuição, quero esclarecer meu entendimento. Para obter limites mais nítidos, é preciso momentos mais altos. Markov usa o primeiro momento, Chebyshev o segundo momento e Hoeffding usa mgf. Isso está correto? Se alguém puder expandir e esclarecer esta parte, seria ótimo.

Anand

Compreensão da prova de um lema usado na desigualdade de Hoeffding

Respostas: