Alice genera $4$ números en $(0,1)$ de forma independiente y uniforme al azar. Ella revela uno de los números a Bob, a quien se le pide que adivine si el número revelado es extremo ( es decir el más pequeño o el más grande entre todos los números generados) o no. ¿Existe una estrategia determinista para que Alice se asegure de que las posibilidades de que Bob acierte son como máximo del 50%?
Respuestas
¿Demasiados anuncios?
Hago los 4 números en el rango (0,1/2] tomando x o 1-x. El número más pequeño es trivialmente extremo.
El segundo número más pequeño tiene la misma probabilidad de haber salido de (0,0,5] que de [0,5,1). Si viene del mismo lado que el número más pequeño no es extremo, pero si viene del otro lado debe ser extremo.
Presento el valor (original) de este número, que tiene una probabilidad de 0,5 de ser extremo.
Mark Fischler
Puntos
11615
Esta respuesta es más bien un comentario largo:
Consideremos un juego más sencillo pero similar: Alicia genera $2$ números en (0,1) de forma independiente y uniforme al azar. Ella revela uno de los números a Bob, que debe adivinar si es el número más alto o no.
Aquí, Alice tiene una estrategia determinista para asegurar una probabilidad de victoria del 50%: Presentar el número $x$ si $(x > y) \wedge (x+y < 1) $ o si $(x < y) \wedge (x+y > 1) $ . Esto funciona porque la distribución condicional de $x$ o $y$ sigue siendo plana, por lo que el número presentado como el más alto es siempre el 50%.
El juego tal y como se presenta no es una estrategia basada tirivamente en esa misma idea (por ejemplo, tomando el primer y tercer número más alto y aplicando los mismos criterios que antes), ya que la distribución del n-ésimo número más alto es cualquier cosa menos plana.
Una segunda observación es que este juego es similar al que me presentaron como el Juego de Spencer (aunque Joel Spencer negó haberlo inventado): Alice genera 3 números aleatorios uniformes en (0,1), selecciona uno al azar y lo cambia por el que quiera, y presenta los números a Bob. Bob entonces elige uno de los tres números presentados, y recibe el original valor de ese número.
Aquí, Alice tiene una estrategia que mantendrá la expectativa de mejor juego de Bob a exactamente $\frac{1}{2}$ pero la solución es muy poco trivial.
Uno puede ver fácilmente en este tipo de juego que para cualquier $\epsilon$ si hay una buena estrategia, entonces hay una estrategia determinista que está al menos dentro de $\epsilon$ de esa buena estrategia (posiblemente impura). Esto es así porque uno puede usar dígitos arbitrariamente tardíos de los aleatorios generados para elegir entre posibles selecciones específicas con cualquier probabilidad de elección requerida.
