Edit: he rellenado un poco más de detalles.
El Hoeffding obligado de expresar $Y-X$ como la suma de $n$ diferencias entre variables aleatorias de Bernoulli $B_q(i)-B_p(i)$ es
$$Prob(Y-X \ge 0) = Prob(Y-X + n(p-q) \ge n(p-q)) \le \exp\bigg(-\frac{2n^2 (p-q)^2}{4n}\bigg)$$
$$Prob(Y-X \ge 0) \le \exp\bigg(-\frac{(p-q)^2}{2}n\bigg)$$
Veo tres razones por las que usted puede estar satisfecho con esto.
- El Hoeffding obligado sólo no está afilada. Se basa en una de Markov, y que es por lo general muy afilados.
- El Hoeffding bound es aún peor que de costumbre en este tipo de variable aleatoria.
- La cantidad por la cual el Hoeffding obligado no es nítida es peor cuando $p$ $q$ son cerca de $0$ o $1$ que cuando están cerca de $\frac12$. El límite depende de $p-q$, pero no lo extremo de $p$ es.
Creo que se podría resolver algunas de estas yendo de nuevo a la prueba de Hoeffding presupuesto, o la de Bernstein desigualdades, para conseguir otra estimación que se ajusta a esta familia de variables mejor.
Por ejemplo, si $p=0.6$, $q=0.5$, o $p=0.9$, $q=0.8$, y quieres saber cuando la probabilidad es en la mayoría de las $10^{-6}$, la desigualdad de Hoeffding le dice que esto se logra con $n\ge 2764$.
Para la comparación, el mínimo de los valores de $n$ se $1123$$569$, respectivamente, por la fuerza bruta de la recapitulación.
Una versión de la Baya-Esseen teorema es que la Gaussiana aproximación a la función de distribución acumulativa es en la mayoría de los
$$0.71 \frac {\rho}{\sigma^3 \sqrt n}$$
donde $\rho/\sigma^3$ es fácil de calcular, en función de la distribución que no está lejos de 1 para las distribuciones de interés. Esto sólo gotas $n^{-1/2}$, que es demasiado lento para el propósito de obtener una aguda estimación de la cola. En $n=2764$, la estimación del error de Berry-Esseen sería de alrededor de $0.02$. Mientras que usted consigue eficaz de las estimaciones para la tasa de convergencia, esas estimaciones no son agudos cerca de las colas, por lo que la Baya-Esseen teorema da mucho peores estimaciones de la desigualdad de Hoeffding.
En lugar de intentar arreglar Hoeffding enlazado, otra alternativa sería la de expresar $Y-X$ como una suma de un (binomial) número aleatorio de $\pm1$s mirando el distinto de cero en términos de $\sum (B_q(i)-B_p(i))$. Usted no necesita una gran límite inferior en el número de distinto de cero términos y, a continuación, puede utilizar una mejor estimación en la cola de una distribución binomial.
La probabilidad de que $B_q(i)-B_p(i) \ne 0$$p(1-q) + q(1-p) = t$. Por simplicidad, supongamos por el momento que no se $nt$ cero términos y que esto es extraño. La probabilidad condicional de que
$B_q(i)-B_p(i) = +1$ $w=\frac{q(1-p)}{p(1-q)+q(1-p)}$.
El Chernoff obligado en la probabilidad de que la suma es positiva es $\exp(-2(w-\frac 12)^2tn)$.
$$ \exp(-2\bigg(\frac{q(1-p)}{p(1-q)+q(1-p)} - \frac 12\bigg)^2 \big(p(1-q) + q(1-p)\big) n)$$
no es riguroso, pero debemos ajustar las $n$ por un factor de $1+o(1)$, y podemos calcular el ajuste con otro Chernoff obligado.
Para $p=0.6, q=0.5$, obtenemos $n \ge 1382$. Para $p=0.9, q=0.8$, obtenemos $n \ge 719$.
El Chernoff obligado no es particularmente fuerte. Comparación con una serie geométrica con relación $\frac{w}{1-w}$ da que la probabilidad de que hay más $+1$s de $-1$s es en la mayoría de los
$${nt \choose nt/2} w^{nt/2} (1-w)^{nt/2} \frac {1-w}{1-2w}$$
Esto nos da nonrigorous límites de $nt \gt 564.4, n \ge 1129$ $p=0.6,q=0.5$ y
$nt\gt 145.97, n\ge 562$ $p=0.9,q=0.8$ . De nuevo, estos deben ser ajustados por un factor de $1+o(1)$ para obtener una rigurosa estimación (determinar $n$, de modo que hay, al menos, $565$ o $146$ cero términos, con alta probabilidad, respectivamente), así que no es una contradicción que el primer aceptable $n$$569$, mayor que la estimación de $562$.
Yo no he pasado por todos los detalles, pero esto demuestra que la técnica que se describe, usted obtiene mucho más cerca de los valores correctos de $n$ de la Hoeffding obligado.
