Un juego de monedas y una loca recurrencia

Question

Considera el siguiente juego entre dos personas. Se empieza con una gran pila de $n$ monedas justas y las lanza todas. Para todas las monedas que salgan cara, lanza esas monedas por la ventana y pasa las monedas restantes al otro jugador. Repite este proceso hasta que algún jugador lance no cabezas. Si un jugador no consigue sacar ninguna cara, pierde.

Pregunta: Dado un valor (grande) de $n$ determinar qué jugador tiene más probabilidades de ganar esta partida.

Dejemos que $P_n$ la probabilidad de perder este juego cuando se va primero y se empieza con $n$ monedas. Entonces $P_0=1$ (no se puede lanzar cara si no hay monedas) y $P_n$ satisface la siguiente recurrencia: $$P_n=1-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}P_{n-k}$$ Al analizar esto, descubrí rápidamente que $P_n$ converge a $1/2$ Así que dejé que $P_n=1/2+Q_n$ y encontró la siguiente recurrencia para $Q_n$ : $$Q_n=-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}$$ Algunos valores iniciales de $Q_n$ , comenzando por $Q_0=1/2$ son $$\frac{1}{2},\space 0,\space -\frac{1}{4},\space \frac{1}{64},\space \frac{5}{256},\space ....$$ Por supuesto, el signo de $Q_n$ determina a qué jugador favorece el juego. Ejecutando un script de Python, determiné que $Q_n$ cambia los signos después de $n=8,17,35,72,145,291,583$ (en ese momento los números se volvieron demasiado grandes para mi programa, ya que estaba tratando con coeficientes binomiales). Sé que estos valores en los que se producen cambios de signo son $\sim c\cdot 2^k$ para alguna constante $c$ .

Con lo que necesito ayuda: ¿Puede alguien calcular el valor de $c$ o inventar una forma inteligente de calcular el signo de $Q_n$ para un tamaño arbitrario de $n$ ?

Lo que ya sé: Si sirve de ayuda, he descubierto que la EGF (función generadora exponencial) de $Q_n$ , denotado como $f$ satisface la siguiente ecuación funcional: $$f(2x)=(1-e^x)f(x)$$ Sin embargo, no estoy seguro de cómo utilizar este hecho. Además, sé que la duración esperada del juego (es decir, el número de turnos antes de que alguien pierda) es asintóticamente $\log_2(n)$ para grandes $n$ . Sin embargo, este hecho es casi trivial porque esperamos que la mitad de las monedas salgan caras (y se tiren) después de cada vuelta.

Answer 1

Siento decirte que te has equivocado con el $Q$ la recurrencia...

Para que quede claro, la regla del juego es que se descarta cualquier cara, y si no se tira ninguna cara (equivalente: no se descarta ninguna moneda) entonces se pierde.

Reclamación: $\forall n \ge 1: P_n = 1/2$

Prueba por inducción: Con $n$ monedas, puedes ganar inmediatamente si lanzas $n$ Cara (descartar todas las monedas para forzar a tu oponente a perder). También puede perder inmediatamente si lanza $n$ Colas. Estos dos resultados son igualmente probables.

Con cualquier otro resultado, es decir, si se lanza al menos una pero no todas las cabezas, el juego se reduce a unas $P_m$ enfrentado a su oponente, donde $1 \le m < n$ . Por hipótesis de inducción, este número $P_m = 1/2$ . Por lo tanto:

$$P_n = 0 \times P(\text{all Heads}) + 1 \times P(\text{all Tails}) + \frac12 \times P(\text{at least one but not all Heads}) = \frac12$$

QED

---

Intentemos "depurar" sus recurrencias. Su $P$ es la recurrencia:

$$P_n=1-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}P_{n-k}$$

Esto me parece bien. Se pierde por no ganar, y se gana por voltear $k\ge 1$ Cara, y entonces tu oponente pierde de $n-k$ monedas. Y esta recurrencia concuerda con mi afirmación:

• $P_0 = 1$ por definición

• $P_1 = 1 - \frac12 {1 \choose 1} P_0 = 1 - \frac12 = \frac12$

• $P_2 = 1 - \frac14 ( {2 \choose 1} P_1 + {2 \choose 2} P_0 ) = 1 - \frac14 (2 \times \frac12 + 1 \times 1) = \frac12$

• $P_3 = 1 - \frac18 ( {3 \choose 1} P_2 + {3 \choose 2} P_1 + {3 \choose 3} P_0 ) = 1 - \frac18 ( 3\times \frac12 + 3 \times \frac12 + 1 \times 1) = \frac12$

etc. Sin embargo, al convertirlo en el $Q$ recurrencia, cometiste un error:

$$ \begin{array}{rrcl} &\frac12 + Q_n &=& 1-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}(\frac12 + Q_{n-k})\\ &Q_n &=& \frac12-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}(\frac12)-\frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}\\ &&=& \frac12 ( 1 - \frac{1}{2^n}\sum_{k=1}^n \binom{n}{k} ) - \frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}\\ \end{array} $$

Lamentablemente para ti, $\sum_{k=\color{red}{1}}^n \binom{n}{k} = 2^n - \color{red}{{n \choose 0}} = 2^n -1$ . Así que lo correcto es $Q$ es la recurrencia:

$$Q_n = \frac{1}{2^{n+1}} - \frac{1}{2^n}\sum_{k=1}^n \binom{n}{k}Q_{n-k}$$