Probabilidad de que una variable binomial sea mayor que otra.

Question

Necesito calcular (o atados) la probabilidad de que una variable binomial es mayor que la de otros. Específicamente, si $x \leftarrow B(n,p)$$y \leftarrow B(n,q)$, ¿cuál es la probabilidad de que $y \geq x$? De manera informal, voy a voltear dos doblada monedas con los conocidos sesgos $n$ veces cada uno, y me gustaría una conveniente expresión/obligado en la probabilidad de que uno gana el otro. Si importa, me gustaría específicamente superior límites en $Pr(y \geq x)$ al $q < p$.

He intentado siguientes estrategias:

• Considere la posibilidad de $z=y-x$ a ser una variable. Enlazado $Pr(z\geq 0)$ el uso de Hoeffding la desigualdad. Esto funciona, pero parece dar muy débil límites.
• Aproximado de $B(n,p)$ $B(n,q)$ con distribuciones normales. Llamar a estos $P(x)$$Q(y)$. Luego de hacer la integral de la $\int_{x=0}^n \int_{y=x}^n Q(y) P(x) dy dx$. Esto se pone feo bastante rápido y, aunque fue un éxito, no darle un apretado obligado, pero sólo una aproximación.

Parece que sería una bien estudiada problema, pero la búsqueda no desvelar mucho. Agradezco cualquier ayuda!

Answer 1

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.

Answer 2

Creo que no has entendido el punto un poco. Hoeffding la desigualdad ser bueno o malo no está vinculado a la desigualdad de Markov. Se puede demostrar que en su situación es óptima hasta un factor de 1/sqrt(x), que es el factor antes de que el exponente en la asymptotics de la distribución de poisson de la cola.

El uniforme de Berry-Esseen límites son inútiles cuando se trata con la concentración de las desigualdades de variables aleatorias independientes. Incluso los no-uniforme de versiones no te llevará muy lejos.

Mis sugerencias. El Hoeffding obligado que está utilizando no es la mejor obligado que pueden obtenerse mediante funciones exponenciales. La mejor posible esa desigualdad es dada en el papel de Hoeffding 1963. Tiene una bonita forma analítica (pero no un exponente). Se toma y se usa, no creo que le apuesta mucho más que este (excepto, tal vez, usted puede perder el factor que te dije arriba).

Answer 3

La aproximación normal es el camino más fácil.

P ~ N (p, p (1-p) / n) Q ~ N (q, p (1-q) / n)

wlog, p> q, para calcular la probabilidad de que P> Q, encontrar la distribución de PQ y encontrar cuando es 0.

PQ ~ N (pq, (p (1 - p) q (1 - q)) / n). Sólo integra desde allí y todo está bien.