¿Una desigualdad de Hoeffding máxima?

Question

Sea $X_1, \cdots, X_n$ sean variables aleatorias independientes de valor real que cumplan $|X_k|\le 1$ y $\mathbb EX_k=0$ . Desigualdad de Hoeffding nos dice que para cualquier $k=1,\cdots, n$ y $t>0$ , $$\mathbb P\Big( \Big | \frac{X_1+\cdots+ X_k}{\sqrt{k}} \Big | \ge t \Big) \le 2 e^{-t^2/2}.$$

Mi pregunta es si existe un límite similar para el máximo sobre $k$ . Más concretamente:

Pregunta: ¿Existen constantes absolutas $C>0$ y $A>0$ para que $$\mathbb P\Big( \max_{1\le k\le n} \Big | \frac{X_1+\cdots+ X_k}{\sqrt{k}} \Big | \ge t \Big) \le C e^{-t^2/A}$$ es válido para $t>0$ ? Si no, ¿qué podemos decir de la izquierda?

Answer 1

Las desigualdades de Hoeffding para los valores absolutos se obtienen determinando primero el límite del valor y luego duplicándolo para llegar al límite del valor absoluto. Pero en este caso se pide un límite relacionado con el máximo del valor absoluto, no con el valor absoluto del máximo, por lo que es necesario un examen directo del valor absoluto.
Para compactar la notación, definimos $S_k=\Big | X_1+\cdots+ X_k \Big |$ . Entonces estamos examinando

$$\mathbb P\Big( \max_{1\le k\le n} \Big | \frac{S_k}{\sqrt{k}} \Big | \ge t\Big) = \mathbb P\Big( \bigcup_k \Big\{ \Big|\frac{S_k}{\sqrt{k}} \Big | \ge t \Big\} \Big)$$

Denote $I_Z$ la función indicadora del acontecimiento $Z= \Big( \bigcup_k \Big\{ \Big|\frac{S_k}{\sqrt{k}} \Big |\ge t \Big\} \Big)$ y $I_1,..., I_n$ las funciones indicadoras de los acontecimientos, $\Big\{ \Big|\frac{S_1}{\sqrt{1}} \Big |\ge t \Big\},...\Big\{ \Big|\frac{S_n}{\sqrt{n}} \Big |\ge t \Big\} $ respectivamente. Entonces, por las propiedades de las funciones indicadoras $$I_Z=\max\Big \{I_1,...,I_n\Big \}$$ Ahora bien $I_Z =0$ significa que todos $I_i,\; i=1,...,n$ son cero. Si $I_Z=1$ significa que al menos una de estas funciones indicadoras individuales es la unidad, denótese $I_m$ y tenemos $$I_m =1 \Rightarrow \Big|\frac{S_m}{\sqrt{m}} \Big |\ge t $$ Sea $v = \text{argmax}_k \Big | \frac{S_k}{\sqrt{k}} \Big |$ y $\Big | \frac{S_v}{\sqrt{v}} \Big |$ la variable correspondiente. Entonces, en el caso en que $I_Z =1$ tenemos

$$\Big | \frac{S_v}{\sqrt{v}} \Big |\ge \Big|\frac{S_m}{\sqrt{m}} \Big |\ge t$$

Entonces, en todos los casos, ya sea cuando $I_Z=0$ o cuando $I_Z=1$ tenemos que, para algunos $h>0$ ,

$$I_Z \le \exp \left \{h\left (\Big | \frac{S_v}{\sqrt{v}} \Big |-t\right) \right \}$$

Por lo tanto,

$$\mathbb P\Big( \max_{1\le k\le n} \Big | \frac{S_k}{\sqrt{k}} \Big | \ge t\Big) = \mathbb P\Big( \bigcup_k \Big\{ \Big|\frac{S_k}{\sqrt{k}} \Big | \ge t \Big\} \Big) = EI_Z \le E\exp \left \{h\left (\Big | \frac{S_v}{\sqrt{v}} \Big |-t\right) \right \}$$

$$\Rightarrow \mathbb P\Big( \max_{1\le k\le n} \Big | \frac{S_k}{\sqrt{k}} \Big | \ge t\Big) \le e^{-ht} E\exp \left \{h \Big | \frac{S_v}{\sqrt{v}} \Big | \right \} \qquad [1] $$

Por el lema de Hoeffding, para una variable aleatoria $Y$ con $EY=0,\;a\le Y \le b$ tenemos, para cualquier $\lambda$ $$ E\left (e^{\lambda Y} \right) \le \exp \left(\frac{\lambda ^2 (b-a)^2}{8} \right) \qquad [2]$$ En nuestro caso, tenemos $$\Big | \frac{S_v}{\sqrt{v}} \Big | = \frac{1}{\sqrt{v}}\Big |X_1 +...+ X_v\Big | \le \frac{1}{\sqrt{v}}\Big (\Big |X_1 \Big | +...+ \Big | X_v\Big | \Big) \le \frac{1}{\sqrt{v}}v = \sqrt{v}$$

la última desigualdad por los supuestos iniciales. Dado que $v\le n$ tenemos $$0\le \Big | \frac{S_v}{\sqrt{v}} \Big | \le \sqrt{n} \Rightarrow -E\Big(\Big | \frac{S_v}{\sqrt{v}} \Big |\Big) \le \Big | \frac{S_v}{\sqrt{v}} \Big | - E\Big(\Big | \frac{S_v}{\sqrt{v}} \Big |\Big) \le \sqrt{n} -E\Big(\Big | \frac{S_v}{\sqrt{v}} \Big |\Big) $$ . Ahora tenemos una variable con valor esperado cero y acotada. La longitud del intervalo es $b-a = \sqrt{n} -E\Big(\Big | \frac{S_v}{\sqrt{v}} \Big |\Big) + E\Big(\Big | \frac{S_v}{\sqrt{v}} \Big |\Big) = \sqrt{n} $ y $\lambda = h $ . Insertando estos valores en el lema de Hoeffding y simplificando obtenemos

$$ E\exp \Big \{h\Big | \frac{S_v}{\sqrt{v}} \Big | - hE\Big(\Big | \frac{S_v}{\sqrt{v}} \Big |\Big)\Big \} \le \exp \left(\frac{nh^2}{8} \right) $$ $$\Rightarrow E\exp \Big \{h\Big | \frac{S_v}{\sqrt{v}} \Big | \Big \} \le \exp \left(\frac{nh^2}{8} \right)\exp\Big \{hE\Big(\Big | \frac{S_v}{\sqrt{v}} \Big |\Big)\Big \} \qquad [3]$$ Nótese que la exponencial que se ha desplazado a la derecha no contiene ninguna cantidad aleatoria, por eso ha desaparecido el valor esperado. De antes tenemos $$ \Big | \frac{S_v}{\sqrt{v}} \Big | \le \sqrt{n} \Rightarrow E\Big | \frac{S_v}{\sqrt{v}} \Big | \le \sqrt{n} \Rightarrow \exp\Big \{hE\Big(\Big | \frac{S_v}{\sqrt{v}} \Big |\Big)\Big \} \le \exp\Big \{h\sqrt{n}\Big \} \le \exp\Big \{h^2n\Big \} \; [4] $$

Insertar el lado derecho de $[4]$ en $[3]$ y de vuelta en $[1]$ obtenemos

$$ \mathbb P\Big( \max_{1\le k\le n} \Big | \frac{S_k}{\sqrt{k}} \Big |\Big )= \mathbb P\Big( \Big | \frac{S_v}{\sqrt{v}} \Big | \ge t\Big) \le \exp \left(-ht +\frac{9nh^2}{8} \right) \qquad [5]$$ Minimización de la RHS sobre $h$ obtenemos $h^* = \frac {4}{9n}t$ e insertando en $[5]$ obtenemos finalmente

$$ \mathbb P\Big( \max_{1\le k\le n} \Big | \frac{S_k}{\sqrt{k}} \Big |\Big )=\mathbb P\Big( \Big | \frac{S_v}{\sqrt{v}} \Big | \ge t\Big) \le \exp\Big \{-\frac{2}{9n}t^2\Big \} \qquad [6] $$

...que es un límite relacionado con el número de v.r. involucrados.

Answer 2

Tal como están las cosas, la desigualdad máxima no puede cumplirse ya que obtendríamos dejando que $n$ yendo al infinito que $$ \mathbb P\Big( \sup_{k\geqslant 1} \Big | \frac{X_1+\cdots+ X_k}{\sqrt{k}} \Big | \ge t \Big) \le C e^{-t^2/A}. $$ Sin embargo, por la ley de los logaritmos iterados, la variable aleatoria $\sup_{k\geqslant 1} \Big | \frac{X_1+\cdots+ X_k}{\sqrt{k}} \Big | $ es casi seguramente infinito, a menos que $X_i=0$ para cada $i$ .

Sin embargo, es posible demostrar que $$ \mathbb P\Big( \max_{1\le k\le n} \Big | \frac{X_1+\cdots+ X_k}{\sqrt{n}} \Big | \ge t \Big) \le C e^{-t^2/A}.$$ Para verlo, veamos $M_n:=\max_{1\leqslant k\leqslant n}\lvert X_1+\cdots+ X_k\rvert$ y $S_n=\lvert X_1+\cdots+ X_n\rvert$ . Por la desigualdad de Doob, $$ x\mathbb P\left(M_n>x\right)\leqslant \mathbb E\left[S_n\mathbf{1}_{\{M_n>x\}}\right]. $$ Escribe la última expectativa como una integral de la cola sobre la recta real positiva y trunca esta integral en $x/2$ para conseguir que $$ x\mathbb P\left(M_n>x\right)\leqslant 2\int_{x/2}^\infty \mathbb P\left(S_n>t\right)dt. $$ Entonces usa la desigualdad de Hoeffding.

Answer 3

Fíjate en el Lemma 1 de este documento: https://arxiv.org/pdf/1312.7308.pdf

Dado que está tomando un máximo, el límite es en realidad un poco diferente, y el exponente no es con $t^2$ pero $t^2/\log(t)$ . La idea de cómo demostrarlo es primero tomar un límite de unión ingenuo sobre una serie geométrica a $k=1,2,4,8,16$ (no necesariamente con 2 como base), entonces usa una desigualdad máxima que no involucre el denominador de $\sqrt{k}$ (véase, por ejemplo, Thm 20.20 aquí: http://www.math.wisc.edu/~roch/grad-prob/gradprob-notes20.pdf ) para delimitar el resto $k$ valores