¿Modo óptimo de apilar la baraja contra un oponente uniformemente aleatorio?

Question

Un juego de cartas que se juega repartiendo equitativamente entre dos jugadores una baraja barajada boca abajo. La baraja consta de cartas numeradas del 1 al 52. Cada jugador revela la carta superior de su mazo, y el jugador cuya carta tenga mayor valor se anota 1 punto. A continuación, ambas cartas se descartan. El proceso se repite hasta agotar ambos mazos. El ganador del juego es el que tiene el mayor número de puntos.

Supongamos que puedes hacer trampas en este juego: primero, conoces el contenido, pero no el orden, de ambos mazos. En segundo lugar, en cada ronda, antes de que tu oponente revele una carta, puedes elegir qué carta de tu mazo revelarás. (Es decir, puedes elegir qué carta revelarás a continuación basándote en toda la información que tengas hasta el momento en que el oponente revele una nueva carta).

Mi amigo me sugirió que, aunque puedas hacer trampas de esta manera, no hay ninguna estrategia que te dé una puntuación media más alta que jugar al azar. Esto no me parece cierto, pero he tenido problemas para demostrar que hacer trampas ayuda en casos sencillos, o para demostrar (por ejemplo, inductivamente) que no importa. Se agradece cualquier ayuda.

---

Edición: Si te sirve de ayuda, ya he considerado una versión más sencilla de este juego, en la que conoces el orden fijo de las cartas de tus oponentes, que se juegan en orden. Si se te permite hacer trampas en esta versión determinista, puedes optimizar tu puntuación según la siguiente estrategia. En primer lugar, basta con establecer una correspondencia entre sus cartas y las tuyas: la carta que jugarás cuando ellos jueguen la suya. Para crear este mapeo, enumera tus cartas en orden ascendente de rango y enumera las cartas de ellos de la misma manera. Si su carta mejor valorada es mejor que la tuya, emparéjala con tu carta peor valorada. En caso contrario, emparéjala con la carta de rango más bajo que tengas y que aún la supere. Retira ambas cartas y repite el proceso.

Edita 2: Conjetura . Aunque hagas trampas, no hay ninguna estrategia que funcione mejor que el azar. En concreto, independientemente de la estrategia que emplees, tu puntuación esperada es simplemente la probabilidad de que una carta aleatoria de tu mazo supere a una carta aleatoria del mazo de ellos, multiplicada por el número total de cartas de cada mazo. Si crea una $n\times n$ cuya matriz $(i,j)$ es 1 si su $i$ a tarjeta supera su $j$ tu puntuación esperada en cualquier estrategia es 1/ $n$ veces la suma de las entradas de la matriz. Creo que tengo una prueba inductiva de esto, pero todavía estoy pensando en cómo escribirlo formalmente.

Answer 1

Teorema : Aunque hagas trampas, no puedes hacerlo mejor que el azar. En concreto, tu número esperado de puntos es igual a tu probabilidad de ganar una sola ronda entre una carta aleatoria tuya y una carta aleatoria de tu oponente, multiplicada por tu número total de cartas.

Prueba : La prueba es por inducción. Supongamos que usted y su oponente tienen cada uno una baraja de $n=2$ cartas en un orden fijo pero arbitrario. Considere la matriz de pagos $\mathbf{P} = \begin{bmatrix}a&b\\c&d\end{bmatrix}$ que tiene un $1$ en la entrada $(i,j)$ si su $i$ a tarjeta supera su $j$ y 0 en caso contrario. Si elige la fila 1, su adversario elegirá al azar una columna $j$ . Su pago será $a+d$ (si eligen la columna 1), o $b+c$ (si eligen la columna 2). Su pago esperado al elegir la fila 1 es $(a+b+c+d)/2$ . Un argumento similar muestra el mismo pago esperado al elegir la fila 2. Esto establece el resultado de que sus elecciones no influyen en la puntuación esperada cuando $n=2$ .

En el caso inductivo, supongamos que tenemos un $(n+1)\times (n+1)$ matriz de pagos $\mathbf{P}$ . Eliminar cartas equivale a eliminar una fila/columna de la matriz. $\mathbf{P}^{i,\times}$ denotan $\mathbf{P}$ con fila $i$ borrado; $\mathbf{P}^{\times,j}$ con columna $j$ borrado, y $\mathbf{P}^{i,j}$ con ambos borrados. Por último, dejemos que $|\mathbf{P}|$ denotan la suma de todas las entradas de $\mathbf{P}$ .

Ahora considere su estrategia de elección de fila $i$ . Su adversario elige una columna $j$ . Para una columna determinada $j$ su pago será $P_{i,j}$ , más el pago esperado resultante de continuar el juego; por hipótesis, es $\frac{1}{n}|\mathbf{P}^{i,j}|$ . Por lo tanto, al elegir fila $i$ su pago esperado sobre todas las respuestas del oponente $j$ es:

$$\frac{1}{n+1} \sum_{j=1}^{n+1}\left[ P_{i,j} + \frac{1}{n}|\mathbf{P}^{i,j}|\right]$$

Tenga en cuenta que el término $|\mathbf{P}^{i,j}|$ se produce una vez por cada $j$ de 1 a $n+1$ . Por lo tanto, podemos reunir las columnas eliminadas en un único término negativo $-|\mathbf{P}^{i,\times}|$ .

$$\frac{1}{n+1} \sum_{j=1}^{n+1}\left[ P_{i,j} + \frac{1}{n}|\mathbf{P}^{i,j}|\right] = \frac{1}{n+1} \left[ \sum_{j=1}^{n+1} P_{i,j} + \frac{1}{n}\sum_{j=1}^{n+1}|\mathbf{P}^{i,j}|\right] = \frac{1}{n+1} \left[ \sum_{j=1}^{n+1} P_{i,j} + \frac{1}{n}\left(-|\mathbf{P}^{i,\times}| +\sum_{j=1}^{n+1}|\mathbf{P}^{i,\times}|\right)\right] = \frac{1}{n+1}\left[|\mathbf{P}^{i,\times}|+\sum_{j=1}^{n+1} P_{i,j}\right] = \frac{1}{n+1}|\mathbf{P}|$$

Esto establece el resultado para el caso inductivo.