¿Necesitas la verdadera aleatoriedad para ganar el juego de los dos sobres?

Question

Una conocida (no) paradoja de la probabilidad consiste en un juego de dos sobres entre dos jugadores, $A$ y $B$ :

1. $A$ selecciona dos números distintos (reales), $x$ y $y$ La gente de la ciudad se siente muy orgullosa de su trabajo, escribe cada una de ellas en una tarjeta y las cierra en un sobre, y luego presenta los dos sobres a $B$ .
2. $B$ elige uno de los sobres y mira la tarjeta que hay dentro. A continuación, adivinan si el número de la tarjeta que han elegido es el mayor o el menor de los dos números.

La "paradoja" aquí es que, independientemente de $A$ para elegir los números, e incluso si $A$ conoce $B$ de antemano - hay una estrategia para $B$ que logrará una tasa de éxito superior a la par a largo plazo: elegir un sobre al azar, y luego asignar el número que contiene al intervalo $(0,1)$ utilizando alguna función monótona (arbitraria). Elija una desviación aleatoria $U\in(0,1)$ y luego adivinar "mayor" o "menor" según si (el mapeo de) el número mirado es mayor o menor que la desviación aleatoria generada.

Me saltaré el análisis de esta estrategia aquí (ver Hacerlo mejor que el azar o ¿Quién descubrió esta paradoja numérica? para más detalles), pero nótese que depende explícitamente de tener una fuente de desvíos aleatorios. Mi pregunta es si esto es necesario para $B$ para tener la ventaja. Más concretamente, considere la siguiente variante del juego:

1. B elige funciones computables $f():\mathbb{N}\mapsto\{0,1\}$ y $g():\mathbb{N}\mapsto\mathbb{Q}\cap(0,1)$ . Tenga en cuenta que $A$ no sabe nada de estas funciones, aparte de que son computable.
2. Para cada número entero $n$ , a su vez:
   • $A$ selecciona dos números reales distintos $x,y\in(0,1)$ , anotando cada una de ellas en una tarjeta y presentándolas en sobres cerrados. (Restrinjo los números aquí para eliminar el paso de mapeo matemático).
   • $B$ calcula $f(n)$ ; si $f(n)=0$ entonces $B$ elige $x$ y si $f(n)=1$ entonces $B$ elige $y$ . Llame a $B$ El número escogido por el usuario $z$ .
   • $B$ calcula $g(n)$ ; si $g(n)\leq z$ entonces $B$ adivina "más alto", de lo contrario $B$ adivina "más bajo".

Tenga en cuenta que esto es esencialmente $B$ siguiendo la estrategia de la versión habitual del juego, salvo que $B$ sigue una estrategia computable en lugar de una puramente aleatoria.

Puede $A$ ¿Ganar este juego a largo plazo?

Desde $A$ no sabe qué estrategia computable $B$ que sigue, está claro que tendrán que adoptar algún enfoque de cola de milano; instintivamente se siente como la aleatoriedad es inherente a $B$ de ganar con la estrategia habitual y que $A$ con el conocimiento de que $B$ Si la estrategia de la empresa es realmente computable, debería ser capaz de "jugar con el sistema" y ganar. Desgraciadamente, no veo una prueba clara al respecto (y no me sorprendería del todo saber que estoy equivocado). ¿Se sabe algo sobre este problema?

EDITAR: para aclarar, debo señalar que a diferencia de $B$ La estrategia que $A$ sigue hace no tienen que ser computables; $A$ puede, por ejemplo, aprovechar un oráculo que enumere el total de funciones computables. Por ejemplo, esto garantiza que $A$ pueden garantizar que ganarán al menos una vez: enumerar todas las parejas posibles $\langle f_n(), g_n()\rangle$ de funciones recursivas y en ronda $i$ se comportan como si $B$ Las selecciones de la ronda serán $f_i(i)$ y $g_i(i)$ (eligiendo los valores que ganarán dado que estos son $B$ de las selecciones). Además, sospecho que $f()$ es en realidad superflua y que podemos hacer la pregunta análoga para la estrategia donde $B$ siempre adivina $x$ pero si la presencia o ausencia de $f()$ sí importa, entonces sería interesante saberlo también.

Answer 1

Su pregunta es demasiado ambigua. Supongo que estás pidiendo una estrategia para A que garantice ganar a largo plazo sin importar la estrategia que elija B y que sea desconocida para A, pero incluso en ese caso no está claro qué se considera ganar. En esta respuesta asumo que quieres que el infimo del límite de la relación entre victorias y partidas sea más de la mitad.

(1) A juega igual contra cualquier B : ¡A no puede garantizar la victoria!

Si la estrategia de A no depende de la historia del juego, entonces A ciertamente no tiene una estrategia ganadora porque para cualquier estrategia de A que gane contra una estrategia de B, la estrategia opuesta de B (escoge el mismo camino pero adivina el opuesto) gana contra esa estrategia de A. Esto se aplica incluso si la estrategia de A no es computable. Sin embargo, B puede tener una estrategia mejor si A está restringido, como veremos a continuación.

(2) A y B juegan de forma computable: ninguno puede garantizar la victoria

Si A tiene una estrategia computable, podemos construir trivialmente una estrategia para B de modo que B siempre gane a A, simplemente simulando la estrategia de A para cada movimiento y jugando contra ella. Del mismo modo, si A conoce la estrategia de B, puede ganar siempre. Por lo tanto, no hay una estrategia única que cualquiera de los dos bandos pueda utilizar para garantizar una victoria, al igual que en Tijeras-Papel-Piedra. Nótese que esto se aplica incluso si el oponente no recuerda la historia del juego, ya que la estrategia de contraejemplo no necesita hacerlo.

(3) A puede usar el oráculo de parada y B juega computacionalmente: ¡A gana!

Para el $k$ -En el momento en que se realiza la última jugada, A ejecuta todas las funciones computables de parada con el historial de juego completo como entrada. Si una de ellas produce una secuencia de longitud $k$ que coincide con todos los anteriores $(k-1)$ movimientos de B, entonces A juega contra esa secuencia para el movimiento actual. Como antes, si hay más de una función computable de parada, A toma la que tenga la descripción más pequeña. Si B está jugando con alguna función computable, entonces claramente A se decantaría finalmente por una función equivalente con la menor descripción (cuya existencia está garantizada por inducción) porque finalmente ninguna función con menor descripción satisfaría el criterio. A partir de ese momento, A ganaría todas las partidas.

(3') B puede usar el oráculo de parada y A juega computacionalmente: ¡B gana!

El mismo argumento que en (3).

Answer 2

Fuentes $f$ y $g$ son funciones recursivas totales. Para el jugador $B$ para poder jugar con el sistema El principal problema es que el conjunto de funciones recursivas totales no es recursivamente enumerable. Por lo tanto, no puede (ya que es la única manera) enumerarlas hasta encontrar algunas funciones que coincidan con los valores ya dados, sabiendo que en última instancia este proceso le dará las funciones reales $f$ y $g$ utilizado por el pagador $A$ .

Pero en la práctica, el jugador $B$ puede observar el tiempo utilizado por el jugador $A$ para dar sus respuestas, y luego adivinar el tiempo (o más exactamente, el número de pasos de cálculo) necesario para calcular $f$ y $g$ . Sabiendo que puede encontrar el programa más pequeño que coincida con las dos respuestas de $f$ y $g$ ya conocido en el tiempo de cálculo (estimado). El proceso convergerá en última instancia al verdadero $f$ y $g$ y conduce $B$ a la victoria final.