Concentração do Máximo

Este post é uma continuação do post sobre concentração de medida, e vai ser necessário para um post futuro.

Naquele post eu falei sobre variáveis subgaussianas, para as quais a seguinte desigualdade vale:

\[ P(|X| > t) \leq e^{-\frac{t^2}{2\sigma^2}} \]

Agora suponha que você tem uma coleção de variáveis aleatórias, todas subgaussianas e não necessariamente independentes. Neste post, nós vamos cotar a probabilidade do máximo delas ser maior que um valor t.

Se você precisa de uma motivação pra isso, eu ofereço duas:

1. Nós frequentemente trabalhamos com estimadores que minimizam ou maximizam alguma função: mínimos quadrados, máxima verossimelhança. É natural que estes estimadores dependam do máximo de uma variável aleatória
2. Se você está trabalhando com algum processo aleatório, muitas vezes o máximo pode ser mortal: qual é o máximo que um ativo pode perder se a distribuição dos retornos é subgaussiana, por exemplo?

O próximo post vai ilustrar uma aplicação dessas desigualdades no caso 1. Para o problema em mãos, nós queremos:

\[ P\left(\max_{i=1,\ldots,n} |X| > t\right) \leq \text{?} \]

A primeira observação é que se o máximo de uma coleção é maior que \(t\), então pelo menos um dos elementos da coleção é maior que \(t\) (duhhh). Logo, o problema \(\max_{i=1,\ldots,n} |X| > t\) é equivalente ao problema “pelo menos um dos \(|X_i|\) é maior que t”. A gente vai escrever isso como \(\bigcup_{i=1,\ldots,n} |X_i| > t\).

Qual a vantagem disso? Bom, a seguinte desigualdade vale:

\[ P\left(\bigcup_{i=1,\ldots,n} |X_i| > t\right) \leq \sum_{i=1}^n P(|X_i| > t) \]

Eu não vou dar uma prova extremamente formal: se \(A\) e \(B\) são dijuntos - se \(A\) acontece, então \(B\) nunca acontece - então \(P(A \cup B) = P(A) + P(B)\). Isso pode ser estendido pra qualquer união finita de conjuntos. Suponha o caso mais geral, em que \(A\) e \(B\) não são dijuntos. Eu posso escrever:

\[ A \cup B = (A\cap B^c) \cup (A^c \cap B) \cup (A \cap B) \]

O superescrito \(c\) significa o evento complementar. Pelo resto do post, \(AB\) vai representar \(A \cap B\). Veja que \(A \cap B^c\) é dijunto de \(A^c \cap B\) e os dois são dijuntos de \(A \cap B\). Logo, eu escrevi a união de dois conjuntos como a união de dijuntos. Então:

\[ P(A \cup B) = P(AB^c) + P(A^cB) + P(AB) \]

Agora, nós podemos escrever \(A = AB^c \cup AB\) (A é a união de A interseção B e A interseção não B). Usando o único resultado que nós temos sobre probabilidade:

\[ P(A) = P(AB) + P(AB^c) \therefore P(AB^c) = P(A) - P(AB) \]

Eu posso fazer a mesma coisa com \(P(B)\), e nós temos:

\[ P(A \cup B) = P(AB^c) + P(A^cB) + P(AB) = P(A) - P(AB) + P(B) - P(AB) + P(AB) = P(A) + P(B) - P(AB) \]

Agora, probabilidades são sempre não negativas, então:

\[ P(A \cup B) = P(A) + P(B) - P(AB) \leq P(A) + P(B) \]

A nossa desigualdade é só é uma generalização para mais dois eventos.

De volta ao fio da meada, suponha que nós temos uma coleção \(x_1,\ldots,x_n\) de variáveis subgaussianas, todas com parâmetro \(\sigma\). Usando o meu argumento:

\[ P\left(\max_{j=1,\ldots,n} |X_j| > t\right) = P\left(\bigcup_{j=1}^n |X_j| > t\right) \leq \sum_{j=1}^n P(|X_j| > t) \]

Agora, use a cota para uma variável subgaussiana:

\[ P\left(\max_{j=1,\ldots,n} |X_j| > t\right) = P\left(\bigcup_{j=1}^n |X_j| > t\right) \leq \sum_{j=1}^n P(|X_j| > t) \leq \sum_{j=1}^ne^{-\frac{t^2}{2\sigma^2}} = ne^{-\frac{t^2}{2\sigma^2}} \]

Vamos deixar isso mais bonitinho: Faça \(t = \sigma(\sqrt{2\log(n)} + \delta)\). Então:

\[ t^2 = \sigma^2(\sqrt{2\log(n)} + \delta)^2 \]

Se \(a,b > 0\), então \((a+b)^2 \geq a^2 + b^2\). Considere os termos de t: \(\sqrt{2\log(n)}\) é positivo e \(\delta\) é sempre positivo, então:

\[ t^2 = \sigma^2(\sqrt{2\log(n)} + \delta)^2 \geq \sigma^2(2\log(n) + \delta^2) \]

Multiplicando por \(-1\) a gente inverte a desigualdade, logo:

\[ P \left(\max_{j=1,\ldots,n} |X_j| > \sigma(\sqrt{2\log(n)} + \delta) \right) \leq n\exp \left(-\frac{\delta^2}{2} - \frac{2\log(n)}{2}\right) = e^{-\frac{\delta^2}{2}} \]

Na última igualdade, eu usei que \(e^{-\log(n)} = \frac{1}{n}\)

O que essas contas todas dizem? Primeiro, mesmo se todas as variáveis tem média zero, o máximo delas não vai estar centrado em zero: a gente ganhou um termo \(\sigma\sqrt{2\log(n)}\). Esse termo é extremamente benevolente: ele cresce a raiz quadrada do log de n. Isso é bastante lento, como a figura abaixo mostra:

library(ggplot2)
library(latex2exp)
library(tidyr)

n <- 1:50
y <- sqrt(log(n))

df <- data.frame(n = n,y = y, id = n)
df <- pivot_longer(df,cols = c(y,id))

ggplot(df,aes(n,value,color = name)) + geom_abline() + geom_line()  + theme_light() + labs(x = "n", y = "", color = "") + scale_color_discrete(labels = c(id = expression(f(x)==x),y = expression(sqrt(log(n))))) 

A segunda observação é que as chances do valor do máximo ser muito maior que \(\sigma\sqrt{2\log(n)}\) é muito baixo: a cauda cai com a exponencial do quadrado, ou seja, a mesma velocidade da gaussiana.

Este post é estupidamente abstrato, mas ele vai ser necessário para um post no futuro que é um pouco menos abstrato.