Encontrar el mejor de la moneda: ¿cuál es la probabilidad de éxito?

Question

Sólo por diversión, estoy trabajando mi camino a través de Motwani y Raghavan del Aleatorizado Algoritmos de libros de texto. Como parte de una solución a uno de los problemas que he planteado, me he encontrado con un problema de probabilidad no sé cómo resolver:

Supongamos que se tienen dos monedas, una de las cuales se voltea cabezas $\frac{2}{3}$ del tiempo y uno de los que gira cabezas $\frac{1}{3}$ del tiempo. Le da la vuelta a cada una de las monedas $k$ veces y supongo que coin flips cabezas $\frac{2}{3}$ del tiempo por la elección de la moneda que volcó en la mayoría de los jefes. (Si hay un empate, suponga que usted adivina incorrectamente). ¿Cuál es la probabilidad de que, como una función de $k$, que elegir la correcta de la moneda?

Para intentar solucionar esto, he intentado modelo de la distribución de los jefes de las monedas de dos distribuciones binomiales y luego restando ellos para conseguir una distribución de la diferencia entre la buena moneda del número de cabezas y la mala moneda del número de cabezas, pero no podía hacer mucho progreso, porque no sé cómo restar estas distribuciones. También probé el modelado de las distribuciones binomiales como distribuciones normales y restar, pero se topó con un problema similar (no sé cómo restar ellos).

¿Alguien tiene algún consejo sobre cómo abordar este problema?

Answer 1

Usted tiene algunas respuestas exactas aquí, así que sólo voy a responder a la pregunta más fácil: ¿cómo se puede aproximar el resultado de un gran $k$? Colocar un contador en cero, luego voltear la cabeza ponderado de la moneda y la cola ponderado en moneda junto a $k$ veces; mover el contador a la derecha de cada uno de los "buenos" flip en cualquier moneda y a la izquierda de cada uno de los "malos" flip. Por flip, cada moneda se mueve el contador $\pm 1$ con probabilidades $2/3$ $1/3$ respectivamente (media de $1/3$ de la varianza $8/9$). La media y la varianza simplemente añadir, así que después de $k$ voltea a tener una distribución con una media de $2k/3$ y la varianza $16k/9$; y por el teorema del límite central, la forma será aproximadamente Gaussiana. Usted tendrá que tomar la decisión equivocada si la ficha cae a la izquierda del origen, lo cual ocurre con probabilidad aproximada $$ \frac{1}{2}\left(1+\text{fer}\left(-\frac{2k/3}{\sqrt{2\cdot 16k/9}}\right) \right)=\frac{1}{2}\left(1+\text{fer}\left(-\sqrt{\frac{k}{8}}\right)\right)\sim e^{-k/8}\sqrt{\frac{2}{\pi k}}. $$ Estos asymptotics indicar que usted necesita $20-25$ voltea a ser $99\%$ seguro de tu elección, razonablemente consistente con la respuesta exacta dada en otros lugares.

Answer 2

Cada vez que las cabezas de los 2/3 de la moneda, escribir +1; cada vez que usted consigue colas escribir -1.

Cada vez que llegues a los jefes en el 1/3 de la moneda, la escritura -1; cada vez que usted consigue colas escribir +1.

Usted obtendrá la respuesta correcta, si el total al final es positivo.

---

Más info por solicitud: Usted tiene $2k$ eventos, y cada uno de ellos tiene un buen resultado (2/3 de los casos), y un mal resultado (1/3 del tiempo). Usted necesita tener más de $k$ buenos resultados para tener un buen resultado.

Answer 3

Una cabeza con la izquierda de la moneda, así como una cola con el derecho de la moneda tanto el apoyo de la hipótesis de que la izquierda de la moneda es el pro-caras de la moneda. En una disposición de las monedas de estos dos eventos ocurren con $\frac 23$, en el resto disposición hapen con $\frac13$. Su método de conteo de cabezas y suponiendo que la moneda con más cabeza es el pro-los jefes de la moneda es equivalente a contar cuántas lanzar una moneda apoyo "a la izquierda de la moneda es pro-cabezas" frente "a la derecha de la moneda es pro-cabeza" y yendo por la mayoría. Para ejemplificar: Si $a,b,c,d$ son los números de los jefes de la izquierda, la cola de la izquierda, los jefes de la derecha, la cola de la derecha, entonces los métodos originales pide a decidir por $a-c$, el otro método compara $(a+d)-(b+c)$. Pero $a+b=c+d=k$, así que esto es sólo $a+(k-c)-(k-a)b-c =2(a-c)$.

Así que la pregunta es: ¿Cuál es la probabilidad de que un $\frac23$ evento se produce con más de $k$ $2k$ veces? Para $k=1$ esto es $\frac49$. Para $k=2$ $\frac {2^4}{3^4}+4\cdot\frac{2^3}{3^4} =\frac{16}{27}$ y, en general, es $$ \sum_{i=0}^{k-1}{2k\choose i}\frac{2^{2k-i}}{3^{2k}}$$

Answer 4

Si una moneda rendimientos de los jefes con una probabilidad de $p$, la probabilidad de que exactamente $h$ cabezas en $k$ tiros es $\displaystyle \binom k h p^h (1-p)^{k-h}$. Tienes dos monedas, una con $p=1/3$ y un con $p=2/3$. La moneda gira son independientes, entonces la probabilidad de obtener los $i$ de los jefes de la primera moneda y $j$ de los jefes de la segunda moneda es $\binom k i \left(\frac{1}{3}\right)^i \left(\frac{2}{3}\right)^{k-i}\cdot\binom k j \left(\frac{2}{3}\right)^j \left(\frac{1}{3}\right)^{k-j}$. La probabilidad de elegir la correcta de la moneda es que, a continuación, $$\sum_{i<j} \left(\binom k i \left(\frac{1}{3}\right)^i \left(\frac{2}{3}\right)^{k-i}\cdot\binom k j \left(\frac{2}{3}\right)^j \left(\frac{1}{3}\right)^{k-j}\right)\textrm.$ $ Para lo que vale, que lleva 26 se da vuelta por la probabilidad de que en un buen resultado para superar el 99%.