Supongamos que tenemos variables aleatorias IID $X_1,\dots,X_n$$\mathrm{Ber}(\theta)$. Vamos a observar una muestra de la $X_i$'s de la siguiente manera: vamos a $Y_1,\dots,Y_n$ ser independientes $\mathrm{Ber}(1/2)$ variables aleatorias, supongamos que todas las $X_i$'s y $Y_i$'s son independientes, y definir el tamaño de la muestra $N=\sum_{i=1}^n Y_i$. El $Y_i$'s para indicar cuál de las $X_i$'s son en la muestra, y queremos estudiar la fracción de éxitos en la muestra definida por $$ Z = \begin{cases} \frac{1}{N}\sum_{i=1}^n X_i Y_i & \text{if}\quad N > 0\, , \\ 0 & \text{if} \quad N = 0 \, . \end{casos} $$ Para $\epsilon>0$, queremos encontrar una cota superior para $\mathrm{Pr}\!\left(Z \geq \theta + \epsilon\right)$ que decae exponencialmente con la $n$. Hoeffding la desigualdad no se aplica de inmediato debido a las dependencias entre las variables.
Respuestas
¿Demasiados anuncios?
Podemos trazar una conexión a Hoeffding la desigualdad de una manera bastante directa.
Tenga en cuenta que tenemos $$ \{ Z > \theta + \epsilon\} = \big\{\sum_i X_i Y_i > (\theta + \epsilon)\sum_i Y_i \big\} = \big\{ \sum_i (X_i - \theta \epsilon) Y_i > 0 \} \>. $$
Set$Z_i = (X_i - \theta - \epsilon)Y_i + \epsilon/2$, de modo que el $Z_i$ son iid, $\mathbb E Z_i = 0$ y $$ \mathbb P( Z > \theta + \epsilon ) = \mathbb P\big(\sum_i Z_i > n \epsilon/2\big) \leq e^{-n \epsilon^2/2}\>, $$ por una sencilla aplicación de Hoeffding la desigualdad (ya que el $Z_i \in [-\theta-\epsilon/2,1-\theta-\epsilon/2]$ y así tomar valores en un intervalo de tamaño de uno).
Hay una rica y fascinante de la literatura relacionada con la que se ha construido a lo largo de los últimos años, en particular, sobre temas relacionados con la matriz de la teoría con diversas aplicaciones prácticas. Si usted está interesado en este tipo de cosas, te recomiendo:
R. Vershynin, Introducción a la no-análisis asintótico de azar matrices, Capítulo 5, del Comprimido Detección, Teoría y Aplicaciones. Editado por Y. Eldar y G. Kutyniok. Cambridge University Press, 2012.
Creo que la exposición es clara y ofrece una muy buena forma de llegar rápidamente aclimatadas a la literatura.
Detalles de la $N=0$ de los casos. $$ \begin{align} \{Z\geq\theta+\epsilon\} &= \left(\{Z\geq\theta+\epsilon\} \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\ &= \left(\{0\geq\theta+\epsilon\} \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\ &= \left(\emptyset \cap \{N=0\}\right) \cup \left(\{Z\geq\theta+\epsilon\} \cap \{N>0\}\right) \\ &= \left\{\sum_{i=1}^n X_iY_i\geq(\theta+\epsilon)\sum_{i=1}^n Y_i\right\} \cap \{N>0\} \\ &\subset \left\{\sum_{i=1}^n X_iY_i\geq(\theta+\epsilon)\sum_{i=1}^n Y_i\right\} \\ &= \left\{\sum_{i=1}^n (X_i-\theta-\epsilon)Y_i\geq 0\right\} \\ &= \left\{\sum_{i=1}^n \left((X_i-\theta-\epsilon)Y_i+\epsilon/2\right)\geq n\epsilon/2\right\} \, . \end{align} $$
Para Alecos. $$ \begin{align} \mathrm{E}\!\left[\sum_{i=1} ^n W_i\right]&=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i=0\}}\sum_{i=1} ^n W_i\right] + \mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\sum_{i=1} ^n W_i\right] \\ &=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\frac{\sum_{i=1} ^n Y_i}{\sum_{i=1}^n Y_i}\right]=\mathrm{E}\!\left[I_{\{\sum_{i=1}^n Y_i>0\}}\right]=1-1/2^n \, . \end{align} $$
Esta respuesta se mantiene la mutación. La versión actual no se refiere a la discusión que tuve con @cardenal en los comentarios (a pesar de que fue a través de esta discusión que me afortunadamente se dio cuenta de que el condicionamiento enfoque parece que no llevan a ninguna parte).
Para este intento, voy a utilizar otra parte de Hoeffding original de 1963 papel, a saber, la sección 5 "es la suma de los Dependientes de las Variables Aleatorias".
Set $$W_i \equiv \frac {Y_i}{\sum_{i=1}^nY_i}, \qquad \sum_{i=1}^nY_i \neq 0, \qquad \sum_{i=1}^nW_i=1, \qquad n\geq 2$$
mientras establecemos $W_i =0$ si $\sum_{i=1}^nY_i = 0$.
Luego tenemos la variable
$$Z_n= \sum_{i=1}^nW_iX_i, \qquad E(Z_n) \equiv \mu_n$$
Estamos interesados en la probabilidad de
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon), \qquad \epsilon < 1-\mu_n$$
Como para muchas otras desigualdades, Hoeffding comienza su razonamiento señalando que $$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) = E\left[\mathbf 1_{\{Z_n-\mu_n -\epsilon \geq 0\}}\right]$$ y que
$$\mathbf 1_{\{Z_n-\mu_n -\epsilon\geq 0\}} \leq \exp\Big\{h(Z_n-\mu_n -\epsilon)\Big\}, \qquad h>0$$
Para el dependiente de variables del caso, como Hoeffding utilizamos el hecho de que $\sum_{i=1}^nW_i=1$ e invocar la desigualdad de Jensen para la (convexo) función exponencial, a escribir
$$e^{hZ_n} = \exp\left\{h\left(\sum_{i=1}^nW_iX_i\right)\right\} \leq \sum_{i=1}^nW_ie^{hX_i}$$
y la vinculación de los resultados para llegar a
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) \leq e^{-h(\mu_n+\epsilon)}E\left[\sum_{i=1}^nW_ie^{hX_i}\right]$$
Centrándonos en nuestro caso, ya que los $W_i$ $X_i$ son independientes, valores esperados pueden ser separados,
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) \leq e^{-h(\mu_n+\epsilon)}\sum_{i=1}^nE(W_i)E\left(e^{hX_i}\right)$$
En nuestro caso, el $X_i$ son yo.yo.d Bernoullis con el parámetro $\theta$, e $E[e^{hX_i}]$ es su momento común de generación de función en $h$, $E[e^{hX_i}] = 1-\theta +\theta e^h$. Así
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) \leq e^{-h(\mu_n+\epsilon)}(1-\theta +\theta e^h)\sum_{i=1}^nE(W_i)$$
Minimizar el lado derecho con respecto a $h$, obtenemos
$$e^{h^*} = \frac {(1-\theta)(\mu_n+\epsilon)}{\theta(1-\mu_n-\epsilon)}$$
Conectarlo a la desigualdad y la manipulación de la que obtenemos
$$\mathrm{Pr}(Z_n\geq \mu_n +\epsilon) \leq \left(\frac {\theta}{\mu_n+\epsilon}\right)^{\mu_n+\epsilon}\cdot \left(\frac {1-\theta}{1-\mu_n-\epsilon}\right)^{1-\mu_n-\epsilon}\sum_{i=1}^nE(W_i)$$
mientras
$$\mathrm{Pr}(Z_n\geq \theta +\epsilon) \leq \left(\frac {\theta}{\theta+\epsilon}\right)^{\theta+\epsilon}\cdot \left(\frac {1-\theta}{1-\theta-\epsilon}\right)^{1-\theta-\epsilon}\sum_{i=1}^nE(W_i)$$
Hoeffding muestra que
$$\left(\frac {\theta}{\theta+\epsilon}\right)^{\theta+\epsilon}\cdot \left(\frac {1-\theta}{1-\theta-\epsilon}\right)^{1-\theta-\epsilon} \leq e^{-2\epsilon^2}$$
Cortesía de la OP (gracias, me estaba volviendo un poco agotada...) $$\sum_{i=1}^n E(W_i) =1-1/2^n$$
Así que, finalmente, las "variables dependientes enfoque" nos da $$\mathrm{Pr}(Z_n\geq \theta +\epsilon) \leq (1-\frac 1{2^n})e^{-2\epsilon^2} \equiv B_D$$
Vamos a comparar esto con el Cardenal enlazado, que se basa en una "independencia" de la transformación, $B_I$. Para nuestra obligado a ser más fuerte, lo necesitamos
$$B_D=(1-\frac 1{2^n})e^{-2\epsilon^2} \leq e^{-n\epsilon^2/2}=B_I$$
$$\Rightarrow \frac {2^n-1}{2^n} \leq \exp\left\{\left(\frac {4-n}{2}\right)\epsilon^2\right\}$$
Así, por $n\leq 4$ tenemos $B_D \leq B_I$. Para $n \geq 5$, bastante rápidamente, $B_I$ se convierte en más de lo $B_D$ pero por muy pequeño $\epsilon$, mientras que incluso esta pequeña "ventana" rápidamente converge a cero. Por ejemplo, para $n=12$ si $\epsilon \geq 0.008$, $B_I$ es más rigurosa. Así, el Cardenal seguramente es más útil.
COMENTARIO
Para evitar la confusión impresiones acerca de Hoeffding del original en papel, tengo que mencionar que Hoeffding se estudia el caso de un determinista combinación convexa de dependiente de variables aleatorias. En concreto, su $W_i$'s son números, no de variables aleatorias, mientras que cada una de las $X_i$ es una suma de variables aleatorias independientes, mientras que la dependencia puede existir entre el $X_i$'s. Entonces él considera diversos de la "U" estadísticas de que puede ser representada de esta forma.
