Teoría de los juegos probabilísticos

Question

Me gustaría que me ayudaran con el siguiente problema:

El problema. Acaba de comprar una nueva impresora de tarjetas que imprime continuamente tarjetas de color rojo o azul, elegidas de forma independiente y uniforme al azar. Juegas al siguiente juego con tu amigo: Puedes desenchufar la impresora una vez al menos $n$ se han imprimido las tarjetas. A continuación, se barajan las cartas y se revela la superior. Si es roja, ganas tú, si no, gana tu amigo. Demuestre que no puede ganar con una probabilidad mayor que $1/2 + o(1)$ para $n\to\infty$ .

Para mayor claridad: Siempre vemos todas las cartas que se han impreso, es decir, conocemos nuestra probabilidad de ganar al parar la impresora.

Veo que un límite de Chernoff puede demostrar que con alta probabilidad, no hay más de $\frac{n}{2} + \sqrt[3]{n}$ tarjetas rojas después de la impresión $n$ cartas, y esto da una probabilidad de ganar de $1/2 + o(1)$ al detener la impresora después de la $n$ -Carta de la ONU. Pero, ¿cómo se puede ampliar esto para cubrir otras estrategias?

Answer 1

Resulta que la estrategia óptima es detenerse en el $n$ -en la carta si hay más rojos que azules, y si no, parar la primera vez a partir de entonces que haya más rojos que azules (lo que acabará ocurriendo con probabilidad $1$ ). La prueba no es muy difícil.

El valor esperado, en función de $n$ es entonces

$$\frac{E\left<|S_n|\right>}{2n} + \sum_{k>n} \frac{P_n(k)}{k}$$

donde $S_n$ es una variante aleatoria que representa la posición de un paseo aleatorio equilibrado en el tiempo $n$ y $P_n(k)$ es la probabilidad de que el primer valor positivo de un paseo aleatorio después del tiempo $n$ se producirá en el momento $k$ dado que $S_n \leq 0$ para ese paseo.

La primera expectativa se expresa fácilmente de forma analítica, al igual que $P_n(k)$ . Así que hay que trabajar con esa suma y ver si se puede acotar con alguna expresión que resulte de la forma $Cn^{-\frac12}$ . Esto dará un resultado más fuerte de lo que pide el problema.