Distribuição empírica

Definição (Distribuição empírica). Sejam \(X_1, \ldots, X_n\) observações i.i.d. com função de distribuição \(F\) em \(\mathbb{R}\). A distribuição empírica é definida por

\[\hat{F}_n(x) = \frac{1}{n}\sum_{i=1}^{n} \mathbb{I}(X_i \leq x), \qquad x \in \mathbb{R}.\]

Lema 1 (Média e variância). Para todo \(x \in \mathbb{R}\), \(n\hat{F}_n(x) \sim \text{Binomial}(n, F(x))\). Em particular,

\[\mathbb{E}[\hat{F}_n(x)] = F(x) \qquad \text{e} \qquad \mathbb{V}[\hat{F}_n(x)] = \frac{F(x)(1-F(x))}{n} \leq \frac{1}{4n}.\]

Prova. Como \(X_1, \ldots, X_n\) são i.i.d., \(\mathbb{I}(X_1 \leq x), \ldots, \mathbb{I}(X_n \leq x)\) são i.i.d. e \(\mathbb{I}(X_i \leq x) \sim \text{Bernoulli}(F(x))\), pois \(\mathbb{P}(X_i \leq x) = F(x)\). Portanto, \(n\hat{F}_n(x) = \sum_{i=1}^{n}\mathbb{I}(X_i \leq x) \sim \text{Binomial}(n, F(x))\) e

\[\mathbb{E}[\hat{F}_n(x)] = \frac{nF(x)}{n} = F(x) \qquad \text{e} \qquad \mathbb{V}[\hat{F}_n(x)] = \frac{nF(x)(1-F(x))}{n^2} = \frac{F(x)(1-F(x))}{n}.\]

A última desigualdade decorre de \(p(1-p) \leq 4^{-1}\), para todo \(p \in [0,1]\). \(\blacksquare\)

Observação. Como \(\hat{F}_n(x)\) é não-viesado, \(\text{MSE}(\hat{F}_n(x)) = \mathbb{V}[\hat{F}_n(x)] \leq (4n)^{-1}\), uniformemente em \(x\) e sem qualquer suposição sobre \(F\). Contraste com a Aula 1: estimar a densidade \(f\) exigiu suposições de suavidade e produziu \(\text{MSE} \asymp n^{-2/3}\), enquanto estimar \(F\) atinge a taxa paramétrica \(n^{-1}\) sem suposição alguma. A diferença é que \(F(x)\) é uma média de variáveis limitadas, ao passo que \(f(x)\) não é um funcional contínuo de \(F\).

Teorema 1 (Convergência pontual). Para todo \(x \in \mathbb{R}\), quase certamente,

\[\lim_{n \to \infty} \hat{F}_n(x) = F(x) \qquad \text{e} \qquad \lim_{n \to \infty} \hat{F}_n(x^-) = F(x^-),\]

em que \(\hat{F}_n(x^-) = n^{-1}\sum_{i=1}^{n}\mathbb{I}(X_i < x)\) e \(F(x^-) = \lim_{y \uparrow x} F(y)\).

Prova. Como visto na prova do Lema 1, \(\hat{F}_n(x)\) é a média de \(n\) variáveis i.i.d. e integráveis com esperança \(F(x)\). Decorre da Lei Forte dos Grandes Números que \(\hat{F}_n(x) \to F(x)\) quase certamente. Analogamente, \(\hat{F}_n(x^-)\) é a média de \(n\) variáveis i.i.d. com esperança \(\mathbb{P}(X_1 < x) = F(x^-)\), de modo que \(\hat{F}_n(x^-) \to F(x^-)\) quase certamente. \(\blacksquare\)

Definição (Erro máximo). O erro máximo da distribuição empírica é definido por

\[D_n = \sup_{x \in \mathbb{R}} \left|\hat{F}_n(x) - F(x)\right|.\]

Também é chamado de distância de Kolmogorov-Smirnov entre \(\hat{F}_n\) e \(F\).

O Teorema 1 garante que, para cada \(x\) fixo, o conjunto em que \(\hat{F}_n(x) \not\to F(x)\) tem probabilidade \(0\). Como há uma quantidade não-enumerável de valores de \(x\), disto não decorre diretamente que, quase certamente, a convergência ocorra simultaneamente para todo \(x\), isto é, que \(D_n \to 0\). O Lema a seguir contorna esta dificuldade, mostrando que \(D_n\) é controlado pelo erro máximo em um número finito de pontos.

Lema 2 (Discretização do supremo). Para cada \(k \in \mathbb{N}\) e \(1 \leq j \leq k-1\), defina \(x_j = \inf\{x \in \mathbb{R}: F(x) \geq jk^{-1}\}\), e também \(x_0 = -\infty\) e \(x_k = +\infty\), com as convenções \(F(x_0) = \hat{F}_n(x_0) = 0\) e \(F(x_k^-) = \hat{F}_n(x_k^-) = 1\). Se

\[\Delta_{n,k} = \max_{0 \leq j \leq k} \max\left\{\left|\hat{F}_n(x_j) - F(x_j)\right|, \left|\hat{F}_n(x_j^-) - F(x_j^-)\right|\right\},\]

então \(D_n \leq \Delta_{n,k} + k^{-1}\).

Prova. Como \(F\) é não-decrescente e contínua à direita, decorre da definição de \(x_j\) que \(F(x_j^-) \leq jk^{-1} \leq F(x_j)\), para \(0 \leq j \leq k\).

Seja \(x \in \mathbb{R}\). Como \(x_0 = -\infty\) e \(x_k = +\infty\), existe \(1 \leq j \leq k\) tal que \(x_{j-1} \leq x < x_j\). Como \(\hat{F}_n\) e \(F\) são não-decrescentes, \(\hat{F}_n(x) \leq \hat{F}_n(x_j^-)\) e \(F(x) \geq F(x_{j-1})\). Portanto,

\[\begin{align*} \hat{F}_n(x) - F(x) &\leq \hat{F}_n(x_j^-) - F(x_{j-1}) \\ &= \left[\hat{F}_n(x_j^-) - F(x_j^-)\right] + \left[F(x_j^-) - F(x_{j-1})\right] \\ &\leq \Delta_{n,k} + \frac{1}{k}, \end{align*}\]

pois \(F(x_j^-) \leq jk^{-1}\) e \(F(x_{j-1}) \geq (j-1)k^{-1}\). Analogamente, \(\hat{F}_n(x) \geq \hat{F}_n(x_{j-1})\) e \(F(x) \leq F(x_j^-)\), de modo que

\[\begin{align*} \hat{F}_n(x) - F(x) &\geq \hat{F}_n(x_{j-1}) - F(x_j^-) \\ &= \left[\hat{F}_n(x_{j-1}) - F(x_{j-1})\right] - \left[F(x_j^-) - F(x_{j-1})\right] \\ &\geq -\Delta_{n,k} - \frac{1}{k}. \end{align*}\]

Como as desigualdades acima valem para todo \(x \in \mathbb{R}\), \(D_n \leq \Delta_{n,k} + k^{-1}\). \(\blacksquare\)

Teorema 2 (Glivenko-Cantelli). Quase certamente, \(\lim_{n \to \infty} D_n = 0\).

Prova. Fixe \(\eps > 0\) e tome \(k\) tal que \(k^{-1} < .5\eps\). Decorre do Lema 2 que, \[\begin{align*} P(\limsup_{n \to \infty} D_n > \eps) &\leq P(\limsup_{n \to \infty} D_n > \eps) \\ &\leq P(\limsup_{n \to \infty} \Delta_{n,k} + k^{-1} > \eps) &\leq P(\limsup_{n \to \infty} \Delta_{n,k} > .5\eps) = 0, \end{align*}\] onde a última igualdade decorre do Teorema 1, já que cada uma das no máximo \(2(k+1)\) parcelas que definem \(\Delta_{n,k}\) converge a \(0\) quase certamente. Como a interseção de um número finito de eventos de probabilidade \(1\) tem probabilidade \(1\), \(\Delta_{n,k}\) converge quase-certamente a \(0\).

Teorema 3 (Desigualdade de Hoeffding, Hoeffding (1963)). Sejam \(Y_1, \ldots, Y_n\) independentes e tais que \(\mathbb{P}(Y_i \in [0,1]) = 1\). Se \(\bar{Y} = n^{-1}\sum_{i=1}^{n}Y_i\), então, para todo \(\varepsilon > 0\),

\[\mathbb{P}\left(\left|\bar{Y} - \mathbb{E}[\bar{Y}]\right| \geq \varepsilon\right) \leq 2\exp\left(-2n\varepsilon^2\right).\]

O Teorema 2 garante que \(D_n \to 0\), mas nada informa sobre a velocidade desta convergência. O Lema 2 e o Teorema 3 permitem obter uma primeira resposta.

Teorema 4 (Velocidade de convergência). Para todo \(\varepsilon \in (0,1]\),

\[\mathbb{P}(D_n \geq \varepsilon) \leq \frac{16}{\varepsilon}\exp\left(-\frac{n\varepsilon^2}{2}\right).\]

Prova. Fixe \(\varepsilon \in (0,1]\) e tome \(k = \lceil 2\varepsilon^{-1}\rceil\), de modo que \(k^{-1} \leq 2^{-1}\varepsilon\). Decorre do Lema 2 que \(D_n \leq \Delta_{n,k} + 2^{-1}\varepsilon\) e, portanto,

\[\{D_n \geq \varepsilon\} \subseteq \left\{\Delta_{n,k} \geq \frac{\varepsilon}{2}\right\}.\]

Para cada \(j\), \(\hat{F}_n(x_j)\) e \(\hat{F}_n(x_j^-)\) são médias de \(n\) variáveis i.i.d. em \([0,1]\) com esperanças \(F(x_j)\) e \(F(x_j^-)\). Decorre do Teorema 3 que cada uma das no máximo \(2(k+1)\) parcelas que definem \(\Delta_{n,k}\) excede \(2^{-1}\varepsilon\) com probabilidade no máximo \(2\exp(-2n(2^{-1}\varepsilon)^2) = 2\exp(-2^{-1}n\varepsilon^2)\). Assim, decorre da subaditividade que

\[\mathbb{P}(D_n \geq \varepsilon) \leq \mathbb{P}\left(\Delta_{n,k} \geq \frac{\varepsilon}{2}\right) \leq 4(k+1)\exp\left(-\frac{n\varepsilon^2}{2}\right).\]

Finalmente, como \(\varepsilon \leq 1\), \(k + 1 \leq 2\varepsilon^{-1} + 2 \leq 4\varepsilon^{-1}\). \(\blacksquare\)

Corolário 1. Quase certamente, \(D_n \leq 2\sqrt{n^{-1}\log n}\) para todo \(n\) suficientemente grande.

Prova. Seja \(\varepsilon_n = 2\sqrt{n^{-1}\log n}\). Para \(n\) suficientemente grande, \(\varepsilon_n \in (0,1]\) e, pelo Teorema 4,

\[\mathbb{P}(D_n \geq \varepsilon_n) \leq \frac{16}{\varepsilon_n}\exp\left(-2\log n\right) \leq \frac{16\sqrt{n}}{n^{2}} = 16n^{-3/2}.\]

Como \(\sum_n n^{-3/2} < \infty\), decorre do Lema de Borel-Cantelli que, quase certamente, \(D_n < \varepsilon_n\) para todo \(n\) suficientemente grande. \(\blacksquare\)

Teorema 5 (Dvoretzky-Kiefer-Wolfowitz, Dvoretzky, Kiefer, and Wolfowitz (1956); Massart (1990)). Para todo \(\varepsilon > 0\) e todo \(n \in \mathbb{N}\),

\[\mathbb{P}(D_n \geq \varepsilon) \leq 2\exp\left(-2n\varepsilon^2\right).\]

Observação. O Teorema 5 é mais forte que o Teorema 4 em três aspectos. Primeiro, o fator polinomial \(16\varepsilon^{-1}\), que decorre da união sobre os \(2(k+1)\) pontos do Lema 2, é substituído pela constante \(2\). Segundo, o expoente \(-2^{-1}n\varepsilon^2\), que decorre de aplicar o Teorema 3 com \(2^{-1}\varepsilon\) no lugar de \(\varepsilon\), é substituído por \(-2n\varepsilon^2\). Isto é, a cota do Teorema 5 para \(D_n\) é exatamente a que o Teorema 3 fornece para um único ponto: o supremo não custa nada. Terceiro, a constante \(2\) é a menor possível, isto é, o Teorema 5 não pode ser melhorado (Massart (1990)).

Observação. A diferença aparece na velocidade obtida. Como \(\mathbb{E}[D_n] = \int_0^{\infty}\mathbb{P}(D_n \geq \varepsilon) d\varepsilon\), decorre do Teorema 5 que

\[\mathbb{E}[D_n] \leq \int_0^{\infty} 2\exp(-2n\varepsilon^2)d\varepsilon = \sqrt{\frac{\pi}{2n}} = O\left(n^{-1/2}\right),\]

a taxa paramétrica. Já o Teorema 4 fornece apenas \(\mathbb{E}[D_n] = O(\sqrt{n^{-1}\log n})\) (Exercício 5), com um fator \(\sqrt{\log n}\) excedente, assim como o Corolário 1.

Classes de Glivenko-Cantelli

O Teorema 2 admite a seguinte generalização. Sejam \(P\) uma probabilidade em \((\mathcal{X}, \mathcal{A})\), \(X_1, \ldots, X_n\) i.i.d. com distribuição \(P\), e \(P_n = n^{-1}\sum_{i=1}^{n}\delta_{X_i}\) a medida empírica, isto é, \(P_n(A) = n^{-1}\sum_{i=1}^{n} \mathbb{I}(X_i \in A)\). Para \(g: \mathcal{X} \to \mathbb{R}\) mensurável, escreva \(P_ng = n^{-1}\sum_{i=1}^{n}g(X_i)\) e \(Pg = \mathbb{E}[g(X_1)]\).

Definição (Classe de Glivenko-Cantelli). Seja \(\mathcal{G}\) uma classe de funções mensuráveis e integráveis \(g: \mathcal{X} \to \mathbb{R}\). Dizemos que \(\mathcal{G}\) é uma classe de Glivenko-Cantelli para \(P\) se

\[\|P_n - P\|_{\mathcal{G}} := \sup_{g \in \mathcal{G}} \left|P_ng - Pg\right| \longrightarrow 0 \qquad \text{quase certamente}.\]

Se \(\mathcal{G}\) é uma classe de Glivenko-Cantelli para toda probabilidade \(P\), dizemos que \(\mathcal{G}\) é universal. Uma classe de conjuntos \(\mathcal{C} \subseteq \mathcal{A}\) é dita de Glivenko-Cantelli quando \(\{\mathbb{I}_C : C \in \mathcal{C}\}\) o é.

Observação. Nesta linguagem, o Teorema 2 afirma que \(\mathcal{C} = \{(-\infty, x] : x \in \mathbb{R}\}\) é uma classe de Glivenko-Cantelli universal, pois \(P_n\mathbb{I}_{(-\infty,x]} = \hat{F}_n(x)\) e \(P\mathbb{I}_{(-\infty,x]} = F(x)\). Note que a prova do Teorema 2 usa somente a Lei Forte dos Grandes Números e o fato de que \(\mathcal{C}\) pode ser aproximada por uma subclasse finita: é esta segunda propriedade que define, em geral, quais classes são de Glivenko-Cantelli.

Observação. Nem toda classe é de Glivenko-Cantelli. Se \(P\) é contínua e \(\mathcal{C}\) é a classe de todos os subconjuntos finitos de \(\mathbb{R}\), então, tomando \(C = \{X_1, \ldots, X_n\}\), \(P_n(C) = 1\) e \(P(C) = 0\). Logo, \(\|P_n - P\|_{\mathcal{C}} = 1\) para todo \(n\). Classes suficientemente ricas não podem ser estimadas uniformemente.

Observação. Na próxima seção estudaremos condições gerais para caracterizar classes de Glivenko-Cantelli.

Exercícios