Probabilidad mínima de sesgada de la moneda para satisfacer la condición particular

Question

Tome $n$ pares de números enteros $(x_i,y_i)$, $1\leq i\leq n$, seleccionados de manera independiente como sigue:

Lanzar una moneda no trucada $X$ y una visión sesgada de la moneda $Y$ $$\Pr[Y=\text{heads}] = p \neq 1$ $

• Si $(X=\text{heads})$,$x_i=-1$, de lo contrario $x_i=1$
• Si $(Y=\text{heads})$,$y_i=0$, de lo contrario $y_i=1$

Encontrar $\min(p)$ tal que $\Pr[\sum_{i=1}^{n}x_iy_i=0]\geq a$ para un determinado $a$.

(Nota: no es una tarea pregunta)

Answer 1

Warm-up ($n=4$ de los casos)

Iniciar con el caso de $n=4$. Queremos saber $\text{Pr}\left(\sum_{i=1}^4 x_i y_i = 0\right)$. Hay tres casos en que esta suma podría ser cero:

1. Ninguno de los $\{y_i\}$ es igual a 1, lo que ocurre con probabilidad de $p^4$.
2. Exactamente dos de las $\{y_i\}$ es igual a 1, que sigue una distribución Binomial, es decir,. $\binom{4}{2}p^2\left(1-p\right)^2$. Además, exactamente 1 de los dos $\{x_i\}$ relacionada con la no-cero $y_i$'s debe tomar el valor de -1, que es también Binomial: $\binom{2}{1}\left(\widetilde p\right)^1\left(1-\widetilde p\right)^{2-1}$ donde $\widetilde p$ es la probabilidad de $x_i$ -1, por lo $\widetilde p=\frac{1}{2}$ en su caso. Por lo tanto, la probabilidad de este evento es $$\binom{4}{2}p^2\left(1-p\right)^2 \binom{2}{1}\left(\widetilde p\right)^1\left(1-\widetilde p\right)^{2-1}$$
3. Exactamente cuatro de la $\{y_i\}$ es igual a 1 (es decir. todos ellos), que tiene probabilidad de $\binom{4}{4}\left(1-p\right)^4$, y el cuatro $x_i$'s asociados con la no-cero $y_i$'s debe tomar el valor de -1, lo cual ocurre con probabilidad: $\binom{4}{2}\left(\widetilde p\right)^2\left(\widetilde p\right)^{4-2}$. Por lo tanto la probabilidad es $$\binom{4}{4}\left(1-p\right)^4 \binom{4}{2}\left(\widetilde p\right)^2\left(1-\widetilde p\right)^{4-2}$$

Y para conseguir $\text{Pr}\left(\sum_{i=1}^4 x_i y_i = 0\right)$, podemos simplemente sumar estos casos.

Caso General

Este método se puede generalizar a $n$ enteros pares, dando

$$\text{Pr}\left(\sum_i^n x_i y_i = 0\right) = \sum_{j=0,2,4,\ldots}^n \binom{n}{j}p^{n-j} (1-p)^j \binom{n-j}{\frac{n-j}{2}}\left(\widetilde p\right)^{\frac{n-j}{2}}\left(1-\widetilde p\right)^{\frac{n-j}{2}}$$

donde $\widetilde p \equiv \text{Pr}\left(x_i=-1\right)=\frac{1}{2}$, y en la suma en el lado derecho, si $n$ es extraño, deje de suma en $n-1$.

La pregunta ahora es: ¿para qué valor de $p$ no esta probabilidad igual $a$? Por lo tanto, debe resolver para $p$ $n$- ésimo polinomio de orden de $p$. Si $n\geq5$, usted no puede resolver este analíticamente, pero un equipo puede resolver numéricamente para determinados valores de $a$.