Juego aleatorio usando números reales

Question

La pregunta original:

Alice y Bob jugar a un juego. Para ganar el juego, Alice necesidades de $a$ puntos, y Bob necesidades de $1$ punto de ($a$ es fijo para cada juego). En cada ronda del juego, Alice elige un número real $x$. A continuación, una moneda, se voltea, y Alice se concede $x$ puntos si la moneda sale cara, y Bob se concede $x$ puntos si la moneda sale de la cola. Supongamos que Alice siempre juega de manera óptima. Su tarea es encontrar la probabilidad de que Alicia gana dado que ella está usando la mejor estrategia.

Este problema es un poco difícil de formalizar, así que voy a ofrecer la siguiente formalización. En primer lugar, tenga en cuenta que al principio de cada ronda, se puede normalizar el juego, así que Bob necesita exactamente $1$ punto más. Vamos a definir una estrategia de $s:\mathbb{R^+}\to\mathbb{R^+}$ como una función que toma como entrada el número de puntos de Alice necesidades, y las salidas de su elección $x$. Definir $p_s(a)$ a la probabilidad de que Alicia gana el juego necesita $a$ puntos y estrategia de juego $s$. Deje $S$ ser el conjunto de todas las estrategias. Encontrar $$p, p(a)=\sup_{s \in S}p_s(a).$$

En primer lugar, tomamos nota de que $p(a) = 1$ si $a = 1 - \epsilon < 1$, como Alice puede elegir una lo suficientemente pequeño $x$ y jugar varias veces hasta que ella gana. He incluido una prueba formal de abajo.

Segundo, se nota que $p(1)$ sigue siendo igual a $1$. Pick $\epsilon, 2\epsilon, 4\epsilon, 8\epsilon, \dots$ hasta ella ha ganado uno de estos. Por lo suficientemente pequeño $\epsilon$, esto siempre va a pasar antes de que ella es derrotado por Bob. En este punto, ella está por delante de Bob por $\epsilon$, y el argumento de $a < 1$ se aplica. De nuevo, he incluido una prueba formal de abajo

Claramente esto también implica que $\lim_{a \to 1^+}p(a)=1$.

Estos son fáciles de casos. Ahora, la intuición sugiere que $\lim_{a \to \infty}p(a)=\frac 12$ (se ve forzada a elegir a$x=a$ cuando $a$ es lo suficientemente grande). No he tratado de probar esto, pero no parece demasiado difícil.

Finalmente, puedo demostrar que $p(2) \geq \frac 34$. Esto se hace fácilmente por tener la primera Alice elige $x=1-\epsilon$ para suficientemente pequeño $\epsilon$. Si gana los puntos, invocar la $\lim_{a \to 1^+}$ caso de ganar con una probabilidad de $1$, y si no, a continuación, elija $x=2$ ganar con una probabilidad de $\frac 12$. Esta estrategia puede ser ampliado a cualquier $n \in \mathbb{N}$ simplemente recoger $1-\epsilon$ repetidamente, $n-1$ veces. Esto demuestra que $p(n) \geq \frac 12 + 2^{-n+1}$ para los números naturales $n$.

Pregunta: ¿Puede esta obligado a ser mejorado, demostrado ser apretado, o se extiende a todos los números reales?

---

La prueba de una < 1: Considerar el juego en el que Bob necesidades de $1$ punto de Alice y necesidades de $1-\epsilon, \epsilon > 0$ puntos. Vamos a mostrar que para cada $\delta > 0$, existe una estrategia que permite a Alice para ganar con una probabilidad de al menos $1-\delta$.

La estrategia es simple: Alice repetidamente elija $x=k$, donde $k=\frac{\epsilon^2}{8(2-\epsilon)\log \delta}$. Tomamos nota de que una vez $2-\epsilon$ puntos han sido premiados, uno de los dos jugadores debe haber ganado. Como resultado, uno de los dos jugadores que siempre han ganado después de $\frac{2-\epsilon}{k}$ rondas se han jugado. Deje $X_i, 1 \leq i \leq \frac{2-\epsilon}{k}$ ser el indicador de la variable aleatoria que es $1$ si Bob gana la ronda $i$ e $0$ lo contrario, y deje $X=\sum X_i$. Entonces es claro que Bob se ha otorgado un total de $Xk$ puntos, y así se gana sólo si $X \geq \frac 1k.$a Continuación, $$\begin{aligned} \Pr [\text{Bob wins}] =& \text{Pr }\left[X \geq \frac 1k\right] \\ =& \Pr \left[X \geq \frac 1k - \frac \epsilon {2k} + \frac \epsilon {2k}\right] \\ =& \Pr \left[X \geq \mathbb{E} [X] + \frac{\epsilon}{2k}\right] \\ =& \Pr \left[X \geq \mathbb{E} [X] \left(1+ \frac{\epsilon}{2-\epsilon}\right)\right] \\ \leq & \text{exp }\left(-\frac{2-\epsilon}{8k}\left(\frac{\epsilon}{2-\epsilon}\right)^2\right) \hspace{20 px} (*)\\ = & \delta \end{aligned}$$ donde $(*)$ es debido a Chernoff Límites.

Prueba para a=1: vamos a describir un conjunto de estrategias que permiten a Alice para ganar el juego en el que tanto ella y Bob $1$ punto con probabilidad de $\geq 1-\delta$ cualquier $\delta > 0$.

Deje $\delta ' = \frac \delta 2$, e $r=\frac{\delta '}2$. Alice va a comenzar por la elección de $x=r, 2r, 4r, 8r, \dots$ hasta Bob gana el juego, o hasta que Alice gana alguno de estos coin flips. Es fácil comprobar de forma algebraica que la probabilidad de que Bob gana en esta etapa es $\leq \delta '$. Una vez que Alice gana en cualquier tirón de la moneda, ella está por delante de Bob por exactamente $r$ puntos. En este punto, se puede abandonar su actual esquema de apuestas, normalizar Bob puntos y jugar una estrategia para $a<1$ que le da una oportunidad de ganar de $1-\delta '$. Por la unión de obligado, la probabilidad de Bob ganar es entonces $\leq 2\delta ' = \delta$, como se desee.

Answer 1

Crédito para esta prueba va a un amigo.

---

Teorema: $p(a) \leq \frac 12 +\frac 1{2a}$.

Prueba: Comenzar por hacer un par de supuestos simplificadores. En primer lugar, asumir que Alice nunca se elige un $x$ que le daría más de $a$ puntos si ella ganó. Esto significa que cuando el juego termina, Bob siempre tiene menos de $a+1$ puntos $x \leq a$. Del mismo modo, Alice siempre tiene exactamente $a$ puntos.

A continuación, vamos a $X$ ser la variable aleatoria que denota la de Alice puntos al final del juego menos de Bob puntos al final del juego. Por una simple linealidad de la expectativa de argumento, $\mathbb{E}[X]=0$. Pero por las propiedades anteriores, $$\begin{aligned} \mathbb{E}[X] &\leq p(a)(a-1)+(1-p(a))(-a-1)\\ \Rightarrow p(a) &\leq \frac {1+a}{2a} \end{aligned}$$

Answer 2

Podemos demostrar que el límite superior \begin{align} p(a)\le 2^{-1}+2^{-a}&&{\rm(1)} \end{align} cuenta con más de todos los $a > 0$ y que tenemos la igualdad, $p(n)=2^{-1}+2^{-n}$ en todos los enteros positivos $n$. Comparando con el obligado \begin{align} p(a)\le 2^{-1}+(2a)^{-1}&&{\rm(2)} \end{align} dado en la respuesta por DreamConspiracy, vemos que (1) es el más fuerte obligado a $1 < a < 2$ y (2) es más fuerte en $a > 2$. En $a=2$ son iguales y son también una igualdad, $p(2)=3/4$.

Para demostrar la envolvente (1), se puede empezar con la siguiente instrucción.

Si $f:\mathbb{R}_+\to\mathbb{R}$ satisface

1. $f(0)\ge1$
2. $f(a) \ge 1/2$, todos los $a$.
3. $f(a)\ge \frac12\left(f(a-x)+f(a/(1-x))\right)$ sobre $a\ge0$, $0 < x < 1$ e $x\le a$.

A continuación, $p(a)\le f(a)$ sobre todo $a > 0$.

Este es un argumento estándar para los procesos de Markov. Es conveniente cambiar la escala de las cantidades en relación con el número de puntos restantes Bob requiere para ganar. es decir, justo antes de que el enésimo lanzamiento de la moneda, vamos a $a_n$ denotar el resto de los puntos Alice requiere para ganar dividido por los puntos Bob requiere para ganar. Así, $a_1=a$. También vamos a $x_n$ ser la apuesta en la n-esima de la sacudida dividido por los puntos Bob requiere. En la n-esima de lanzamiento, cualquiera de los siguientes casos,

• Alice gana el sorteo y $a_{n+1}=a_n-x_n$ o si $x_n\ge a_n$, Alicia gana el juego.
• Bob gana el sorteo y $a_{n+1}=a_n/(1-x_n)$ o si $x_n\ge1$, Bob gana el juego.

Supongamos que Alice siempre elige $x_n\le a_n$ como un mayor valor de $x_n$ no puede aumentar su probabilidad de ganar. También, si $x_n\ge1$ entonces Alice de mayo, como así también asegurarse de que $x_n\ge a_n$ ya que se asegurará de que se gana el juego si sale cara y no afecta el resultado en caso de que las colas (es decir, Bob gana el juego).

Tenga en cuenta que $a_n$ es un proceso estocástico, y considerar la posibilidad de definir un nuevo proceso de $X_n$ por $X_n=1$ si Alice ha ganado antes de que el enésimo lanzamiento, $X_n=0$ si Bob ha ganado, y $X_n=f(a_n)$ lo contrario. Este es un submartingale. Si ninguno ha ganado por la n-esima de la sacudida a continuación, $$ \mathbb{E}[X_{n+1}\vert a_1,a_2,\ldots,a_n]=\frac12\left(f(a_n-x_n)+f(a_n/(1-x_n)\right)\le f(a_n)=X_n. $$ Tenemos que ser un poco cuidadoso aquí y considerar el caso de $x_n\ge1$ por separado. En este caso también tenemos $x_n\ge a_n$, así que Bob o Alice va a ganar el juego en la n-esima de lanzamiento, cada uno con una probabilidad de 1/2. La condición de $f\ge1/2$ asegura que la desigualdad aún se mantiene.

Así, por opcional de frenado para submartingales,si $N$ es el sorteo en el que alguien gana el juego, $$ f(a)=X_1\ge\mathbb{E}[X_N]=\mathbb{P}({\rm Alice\ wins}). $$ como se requiere.

Para demostrar atado (1), solo necesita ser demostrado que $f(a)=\min(2^{-1}+2^{-a},1)$ satisface la propiedad 3 de arriba. Para $a\le 1$, $f(a)=1$, y la desigualdad se cumple trivialmente. Así, considere la posibilidad de $a > 1$ y, wlog, supongamos que $a-x\ge1$ (como el lado derecho de la desigualdad en el estado 3 es decreciente en $x$ sobre $a-x\le1$). Tenemos que mostrar que $$ f(a)\ge\frac12\left(f(a-x)+f(a/(1-x)\right). $$ Conectar en la definición de $f$ y restando 1/2 de ambos lados, tenemos que mostrar $$ 2^{-a}\ge2^{x-1}+2^{-a/(1-x)-1}. $$ Multiplicando por $2^a$, esto es equivalente a $$ 1\ge2^{x-1}+2^{-ax/(1-x)-1}. $$ Como el lado derecho es la disminución en el $a$, es suficiente para probar esto en un=1. Establecimiento $y=1-x$, entonces sólo tenemos que demostrar que $$ g(y)\equiv2^{-y}+2^{-1/y}\le1 $$ más de $0 < y < 1$. Tomando la derivada, $$ g^\prime(y)=2^{-y}\log 2\left(2^{y-1/y}y^{-2}-1\right) $$ La derivada de la expresión dentro del paréntesis es $2^{y-1/y}y^{-2}(1-1/y)^2\log2$, lo cual es positivo. Así, en $0 < y <1$, $g$ inicialmente es decreciente, entonces se incrementa, por lo que su máximo se alcanza en los límites de $g(0)=1$ o $g(1)=1$. Esto le da a $g\le1$ como se requiere.

Answer 3

No veo cómo se puede tener $p(a) > \frac{a+2}{2(a+1)} = \frac12+\frac{1}{2(a+1)}$ cualquier $a \gt 0$ y, en particular, cómo se puede tener $p(1) \gt \frac34$ o $p(\frac12) \gt \frac56$ incluso con Alice, variando las apuestas a través del juego

Yo no estoy convencido por el argumento inicial de que para $a < 1$ Alice puede obtener una probabilidad de ganar el partido arbitrariamente cerca de $1$ mediante el uso de una constante pequeña participación. Mi comprensión de la Ruina del Jugador es que la probabilidad de ganar en la general con una moneda se $\frac{1}{a+1}$ (al menos cuando la constante apuesta divide tanto a a$a$ e $1$, y cerca de este, si el juego es relativamente pequeño, pero no se dividen)

Mi argumento para el caso general:

Deje $W_A$ ser el condicional espera que la cantidad que Alice recibe, dado que Alice gana el partido. Claramente $W_A \ge a$

Deje $W_B$ ser el condicional espera que la cantidad que Bob se, dado que Bob gana el partido. Yo habría pensado que $1 \le W_B \le a+2$, desde la penúltima posición no puede ser más negativo que $-1$ y por lo de la apuesta final nunca será más grande que $a+1$, lo cual es suficiente para decidir el partido con una sola apuesta desde cualquier posición; si fuera más grande que el mismo resultado puede ser obtenido con un más complicado el análisis de $W_A$ , pero que parece innecesario

Entonces yo habría pensado que ya que tienes una moneda, usted tiene $pW_A-(1-p)W_B =0$ e lo $pa-(1-p)(a+2)\ge 0$ conduce a $p \le \frac12+\frac1{2(a+1)}$

Este es un obligado en lugar de una estrategia. Considerar, como una estrategia que pone arbitrariamente cerca, la elección de algunas pequeñas $\epsilon$ y el uso de la igualdad de apuestas para la apuesta hasta llegar a $a+\delta_a$ o $-1+\delta_{-1}$, tanto de estos múltiplos enteros de $\epsilon$ con ambos $\delta$s positivo pero inferior o igual a $\epsilon$:

• Usted llegará a $a+\delta_a$ primera (Alice gana el partido) con una probabilidad de $\frac{1-\delta_{-1}}{a+1-\delta_{-1}+\delta_{a}}\approx \frac{1}{a+1}$
• Usted llegará a $-1+\delta_{-1}$ primero (partido todavía continua) con una probabilidad de $\frac{a+\delta_{a}}{a+1-\delta_{-1}+\delta_{a}}\approx \frac{a}{a+1}$; en este último caso, su próxima apuesta puede tener estaca $a+1-\delta_{-1}$ así
  • llegar a $a$ esta manera (Alice gana el partido) con probabilidad total $\frac{a+\delta_{a}}{2(a+1-\delta_{-1}+\delta_{a})}\approx \frac{a}{2(a+1)}$
  • llegar a $-a-2+2\delta_{-1}$ (Bob gana el partido) con la misma probabilidad total

Con esta estrategia combinada, Alice gana el partido con una probabilidad de $\frac{a+2-2\delta_{-1}+\delta_{a}}{2(a+1-\delta_{-1}+\delta_{a})} \approx \frac12+\frac{1}{2(a+1)}$ y Bob gana el partido con una probabilidad de $\frac{a+\delta_{a}}{2(a+1-\delta_{-1}+\delta_{a})} \approx \frac12-\frac{1}{2(a+1)}$