Suponga que se dan $n$ i.yo.d muestras $X_1, ..., X_n$ procedentes de una distribución discreta $p = (p_1, ..., p_k)$. Nos gustaría estimación $p$ utilizando el estimador empírico \begin{equation} \hat{p}_i = \frac{1}{n} \sum_{j=1}^{n}\mathbb{1}_{\{X_j =i\}}. \end{equation} Utilizando clásico Chernoff tipo de concentración de las desigualdades, fácilmente podemos deducir la siguiente apretado obligado \begin{equation} \mathbb{P}\left(|\hat{p}_i - p_i| \geq \alpha \right) \leq 2 e^{-n\alpha^2/4}, \end{equation} para cualquier $i \in \{1, ..., k\}$. Podemos hacer uso de la desigualdad anterior para demostrar apretado límites superiores en la $l_1$ $l_\infty$ errores? Precisamente, nos gustaría encontrar apretado límites superiores en la \begin{equation} \mathbb{P}\left(\sum_{i=1}^{k} |\hat{p}_i - p_i| \geq \alpha \right), \end{equation} y \begin{equation} \mathbb{P}\left(\max_{i \in \{1, ..., k\}}|\hat{p}_i - p_i| \geq \alpha \right). \end{equation} Observe que el $|\hat{p}_i - p_i|$'s están correlacionados. También, observe que el vector de la cuenta $(Y_1, ..., Y_k)$, donde \begin{equation} Y_i = \sum_{j=1}^{n}\mathbb{1}_{\{X_j =i\}}, \end{equation} se distribuye de acuerdo a una Multinomial$(n, p_1, ..., p_k)$ distribución. Por lo tanto, el problema es equivalente a encontrar apretado límites superiores en la \begin{equation} \mathbb{P}\left(\sum_{i =1}^{k} |Y_i - \mathbb{E}[Y_i]| \geq n\alpha \right), \end{equation} y \begin{equation} \mathbb{P}\left( \max_{i \in \{1, ..., k\}}|Y_i - \mathbb{E}[Y_i]| \geq n\alpha \right), \end{equation} donde $(Y_1, ..., Y_k) \sim$ Multinomial$(n, p_1, ..., p_k)$. Nosotros, posiblemente, puede utilizar el límite provisto en el Lema 3 de este documento, pero sólo vale para un gran $n$. Además, no está claro si o no, que se une es apretado.
Respuesta
¿Demasiados anuncios?
Desde su alfabeto es finito (tiene el tamaño de k), puede utilizar el método de los tipos; estimación de densidad de kernel (es decir, tratar con un continuo alfabeto) es mucho más difícil.
El método de tipos (Véase, por ejemplo, Dembo y Zeitouni Grandes desviaciones Técnicas y Aplicaciones 2e, sección 2.1, o el capítulo 11 de la Cubierta y Thomas Elementos de la teoría de la Información 2e) nos dice que: $P(||\hat{p} - p|| \geq \alpha) \leq \sum_{x : ||x-p|| \geq \alpha} e^{-n D(x,p)} \leq (n+1)^k e^{-n D(p^*,p)}$ donde $p^* = \arg \min_{\{x : ||x-p|| \geq \alpha\}} D(x,p)$ $D(p,q)$ es el de Kullback-Leilber divergencia. Este límite ajustado (Sanov del teorema) en el exponente.
Pinsker la desigualdad dice que $D(p,q) \geq \frac{1}{2} ||p-q||_1^2$ $D(p,q) \geq 2 TV(p,q)^2 \geq 2 ||p-q||_\infty^2$ (tomando singleton establece en la definición de la variación total), y ambos son apretados. Conectar estos límites en el límite en $P(||\hat{p} - p|| \geq \alpha)$ da $\frac{\log P(||\hat{p} - p|| \geq \alpha) }{n}$ se comporta como $-\alpha^2/2$ $1$- norm caso, y $-2 \alpha^2$ en el sup-norm caso (y estos son ajustados).
Ahora, tenga en cuenta que $||\hat{p}-p||$ tiene delimitadas las diferencias de la propiedad: si se cambia una $X_i$, y es el 1-norma, cambios en la mayoría de las $2/n$. Si es el sup-norma, cambios en la mayoría de las $1/n$. El uso de la delimitadas las diferencias de desigualdad va a dar un salto, a continuación, que coincide con el exponente dado por Sanov del teorema + Pinsker ( $2 e^{- n \alpha^2/2}$ $2 e^{- 2 n \alpha^2}$ , respectivamente). Por lo tanto, estos son ajustados hasta sub-exponencial de los factores.
