¿Cómo se puede adivinar si uno de un par de números aleatorios es mayor con probabilidad > 1/2?

Question

Mis disculpas si esto es demasiado elemental, pero hace años que oí hablar de esta paradoja y nunca escuché una explicación satisfactoria. Ya lo he intentado con mi buena cantidad de doctores en matemáticas, y algunos de ellos postulan que algo profundo está sucediendo.

El problema:

Estás en un programa de juegos. El presentador ha elegido dos números (íntegros y distintos) y los ha escondido detrás de las puertas A y B. Te permite abrir una de las puertas, revelando así uno de los números. A continuación, te pregunta: ¿el número que hay detrás de la otra puerta es mayor o menor que el número que has revelado? Tu tarea consiste en responder correctamente a esta pregunta con una probabilidad estrictamente superior a la mitad.

La solución:

Antes de abrir cualquier puerta, elige un número $r$ al azar utilizando cualquier distribución de probabilidad continua de su elección. Para simplificar el análisis, se repite hasta $r$ no es integral. Entonces se abre cualquiera de las puertas (eligiendo uniformemente al azar) para revelar un número $x$ . Si $r < x$ , entonces adivinas que el número oculto $y$ también es menor que $x$ ; de lo contrario se adivina que $y$ es mayor que $x$ .

¿Por qué es una estrategia ganadora? Hay tres casos:

1) $r$ es menor que $x$ y $y$ . En este caso, se adivina "más pequeño" y se gana el juego si $x > y$ . Porque las variables $x$ y $y$ se asignaron a los números ocultos uniformemente al azar, $P(x > y) = 1/2$ . Por lo tanto, en este caso se gana con una probabilidad de la mitad.

2) $r$ es mayor que $x$ y $y$ . Por un argumento simétrico a (1), se adivina "más grande" y se gana con una probabilidad de la mitad.

3) $r$ está entre $x$ y $y$ . En este caso, se adivina "más grande" si $x < y$ y "más pequeño" si $x > y$ -- es decir, siempre ganas el juego.

El caso 3 ocurre con una probabilidad finita no nula $\epsilon$ , equivalente a la integral de su distribución de probabilidad entre $x$ y $y$ . Haciendo un promedio de todos los casos, su probabilidad de ganar es $(1+\epsilon)/2$ que es estrictamente mayor que la mitad.

La paradoja:

Dado que los números originales se eligieron "arbitrariamente" (es decir, sin utilizar ninguna distribución determinada), parece imposible saber nada sobre la relación entre un número y otro. Sin embargo, la prueba parece sólida. Tengo algunas ideas sobre el culpable, pero nada completamente satisfactorio.

Miembros perspicaces, ¿podrían ayudarme con esto? Gracias.

Answer 1

Como se ha explicado anteriormente, el éxito de la estrategia propuesta por el concursante depende totalmente de la suposición que haga el concursante sobre el método del anfitrión para elegir x e y.

Un ejemplo en el que la estrategia del concursante fijo casi siempre fracasa. Supongamos que el anfitrión siempre elige un número negativo "inesperadamente" grande para x, digamos x = -n, donde n tiene >1000 dígitos, y r es más "ordinario", digamos que tiene <100 dígitos. El método depende de que el concursante apueste que x < r < y. Si la estrategia uniforme del anfitrión siempre ha elegido y = x-1, entonces el concursante perderá casi con toda seguridad ronda tras ronda. (Si, después de numerosas rondas de esto, el concursante se da cuenta de esta estrategia del anfitrión y trata de cambiar su estrategia de apuestas, el anfitrión puede adaptarse también, eligiendo y = -x = n para rondas posteriores)

Answer 2

Este es un problema que se simplifica mucho si se hace el esfuerzo de precisar el problema. Lo que sigue se inspira un poco en [Alexander Gnedin. "Adivina el número mayor. " arXiv:1608.01899 (2016).] que contiene una gran cantidad de discusiones, variaciones e historia respecto al problema.

A estrategia pura especifica para cada número observado si se acepta como el mayor o al menos igual de grande ( $1$ ) o pasa al otro número ( $0$ ). Así que podemos tomar el espacio de las estrategias puras como $\{0,1\}^\mathbb{Z}$ . Para cada let $t_n\in\{0,1\}^\mathbb{Z}$ sea el $n^\text{th}$ estrategia de umbral para lo cual $t_n(l)=1$ si $l\geq n$ .

Ahora dejemos que $\nu$ sea cualquier distribución de probabilidad sobre $\mathbb{Z}$ y que $\pi(\nu,t)$ sea la probabilidad de ganar de elegir el número mayor o igualmente mayor de alguien utilizando la estrategia pura $t$ cuando ambos números se eligen independientemente de $\nu$ . (Nótese que esto no concuerda del todo con el enunciado original en el que ambos números deben ser distintos, pero si tenemos suficiente libertad para elegir ambas distribuciones por separado, no se puede asegurar una probabilidad de ganar superior a $1/2$ para cada $\nu$ .)

Es fácil ver que para cada $\nu$ la probabilidad de ganar $\pi$ se maximiza en alguna estrategia umbral y que cualquier otra estrategia maximizadora debe ser igual a una estrategia umbral $\nu$ -casi seguro.

Obsérvese que una estrategia de umbral garantiza una probabilidad de ganar de al menos $1/2$ contra cualquier distribución $\nu$ en los enteros. Además, para cualquier distribución $\nu$ en los números enteros, alguna estrategia umbral tiene una probabilidad de ganar estrictamente mayor que $1/2$ .

Hasta ahora, nada debería haber sido realmente sorprendente. Ahora dejemos que $\mu$ sea cualquier distribución de probabilidad de soporte completo en $\mathbb{Z}$ . Hay una inducción estrategia de umbral aleatorio $t_\mu$ que elige la estrategia del umbral $t_n$ con probabilidad $\mu(n)$ . Si ampliamos $\pi$ de forma obvia a una función $\pi:\Delta(\mathbb{Z})\times\Delta(\{0,1\}^\mathbb{Z})\to\mathbb{R}$ donde $\Delta(X)$ es el conjunto de medidas de probabilidad de Borel sobre $X$ vemos que $\pi(\nu,t_\mu)>1/2$ para todos $\nu\in\Delta(\mathbb{Z})$ . De hecho, para cada $\nu$ y cada $n$ , $\pi(\nu,t_n)\geq 1/2$ y con probabilidad positiva, elegimos algún $n$ tal que $\pi(\nu,t_n)>1/2$ .

Por último, hay que tener en cuenta que la estrategia originalmente propuesta basada en una variable aleatoria de distribución continua $r$ corresponde a $t_\mu$ con $\mu(n)$ siendo la probabilidad de que $n>r$ .

Answer 3

Existe una "paradoja" relacionada conocida como la problema de los dos sobres que tiene un buen artículo en la wikipedia.

Answer 4

Los números son supuestamente elegidos de una distribución infinita...

No hay ninguna forma válida de "muestrear" una distribución infinita de enteros para obtener x e y, ni tampoco hay forma de obtener r de una distribución real infinita.

Si nos ceñimos a los números enteros, la probabilidad de "muestreo" de cualquier número entero es cero. La probabilidad de "muestrear esta distribución" con un entero entre y dos enteros arbitrarios, por muy ridículamente grandes que sean, también es cero.

Dicho de otro modo, no hay manera de definir la probabilidad de que un número entero "así elegido" dentro de cualquier rango arbitrario sea algo distinto de cero.

Todos los valores p(i) son cero.

Ahora bien, si pudiéramos poner algunas restricciones a los valores que el presentador del concurso puede elegir, y a las probabilidades de los mismos, podríamos integrar efectivamente sobre rangos y hablar de probabilidades y formular una estrategia ganadora...

Answer 5

Consideremos el siguiente problema simplificado: voy a elegir dos números de entre los enteros no nulos con probabilidad proporcional a $ \frac{1}{|k|} $ . Así que:

$$ p(|k|) \propto \frac{1}{|k|} $$

Y jugamos al mismo juego que el anterior, yo revelo uno y te pregunto si el otro es más pequeño o no. Ahora, ¿cuál es p(5)? Esto es sólo $ \frac{1}{R} \frac{1}{|5|} $ , donde $R$ es la constante de renormalización. Entonces:

$$ R = 2 \sum_{k=1}^{\infty} \frac{1}{k} $$

¡Ups!

Así que, ahora, ¿qué significa esto? es $p(5) = 0$ ? es $p(k) = 0$ para todo k? ¿Tiene este problema más sentido si tomo la probabilidad proporcional a $\frac{1}{|k|}^\alpha$ como $\alpha \to 0$ ? ¿Qué significa elegir un número cuya probabilidad es 0?

¿Cómo podría anotar estas cifras para compararlas? Obviamente son mucho más grandes que el número de átomos del universo... ¿Tengo un algoritmo para escupir los bits y tratar de compararlos de esa manera?

Este problema es un error de sintaxis. La premisa de que se puede "elegir un número al azar" de todo enteros no es válido. No puedes hacer esto. La razón por la que tu lógica (defectuosa) parece funcionar es porque estás limitando implícitamente la distribución de $[-M,M]$ y luego agitar las manos tomando $M \to \infty$ que no se puede hacer.