Tirar monedas con poco presupuesto

Question

Se lanza una moneda al aire $n$ veces y ganas si sale cara al menos $k$ tiempos. La moneda es inusual en el sentido de que se le permite elegir la probabilidad $p_i$ que sale de cabeza en el $i$ de la vuelta, con la única restricción de que $\sum_i p_i \le b$ , donde $b$ es un "presupuesto" predeterminado que tienes. Además, se le permite esperar hasta que haya visto los resultados de la primera $i-1$ antes de elegir el valor de $p_i$ . Dado $n$ , $k$ y $b$ ¿Cuál es su estrategia óptima y cuál es su probabilidad de ganar?

Una forma vistosa de plantear el problema es que si eres un equipo deportivo al que se le encomienda ganar una competición al mejor de $n$ serie y tienes recursos limitados (por ejemplo, un bullpen limitado para las Series Mundiales de béisbol de las grandes ligas), ¿cómo debes presupuestarlos?

---

Naturalmente, si $b\ge k$ , puede simplemente elegir $p_i=1$ para $k$ de la $n$ y ganan con probabilidad 1. Así que la pregunta es interesante sólo si $b\lt k$ .

He hecho circular este problema de manera informal entre los colegas, que han obtenido resultados parciales diversos pero no una solución completa. Ocuparía demasiado espacio resumir todos los resultados parciales, pero permítanme mencionar algunos de los más destacados.

1. Incluso el "caso no adaptativo", en el que se no permite ver los resultados de sus volteos antes de elegir $p_i$ no es trivial. La mejor estrategia es dividir el presupuesto de manera uniforme entre $r$ voltea para algunos $r$ pero el valor exacto de $r$ es más complicado de lo que se cree. Para un determinado $r$ la probabilidad de $k$ éxitos es $$\sum_{m=k}^r {r \choose m} \left({b\over r}\right)^m\left(1-{b\over r}\right)^{r-m}.$$ De esto se desprende que si $b\lt k-1$ entonces debemos elegir $r=n$ y si $k-1 \le b \lt k$ entonces $r\approx (k-1)/3(b-k+1)$ pero sólo tenemos una prueba en casos especiales.

2. En el problema real planteado, dejemos que $d=k-b$ El déficit . Entonces, al menos en el caso de déficit pequeño, la mejor estrategia general que tenemos hasta ahora es hacer un lanzamiento de moneda inicial con probabilidad $1-\lbrace d\rbrace$ (donde $\lbrace d\rbrace$ denota la parte fraccionaria de $d$ ), y luego tomar $p_i=1/2$ hasta que nos encontremos en una situación en la que podamos "cerrar" la victoria tomando las $p_i=1$ . (Es posible analizar esta estrategia cuantitativamente, pero omitiré los detalles aquí). En particular, se puede demostrar que las estrategias adaptativas superan significativamente a las estrategias no adaptativas.

3. Si $b$ es pequeño, entonces se puede demostrar que la mejor estrategia no adaptativa está dentro de un factor constante del óptimo. Por ejemplo, si $b\le 1$ entonces se puede demostrar que la probabilidad global de ganar $p$ satisface $${1\over 4}{n\choose k}\left({b\over n}\right)^k \le p \le {n\choose k}\left({b\over n}\right)^k.$$ El límite superior es realmente cierto para todos los $b$ y el límite inferior puede derivarse de la mejor estrategia no adaptativa.

Answer 1

Quiero proponer una estrategia en el caso límite $n=\infty$ . Tal vez esto se describa mejor como un límite de estrategias, ya que permitiré una secuencia de lanzamientos de monedas a los que se les asigna una probabilidad $\epsilon$ de éxito (donde $\epsilon$ es infinito). La cantidad total de probabilidad que "gastaremos" antes de que aparezca la siguiente cabeza estará entonces distribuida exponencialmente, con media 1.

Denotaré por $f_k(x)$ la probabilidad de que mi estrategia tenga éxito si todavía necesitamos $k$ cabezas, y tienen $x$ probabilidad que queda en nuestro "presupuesto". Así es como funciona la estrategia: Si $x\geq k$ asignamos la probabilidad 1 al siguiente $k$ voltea. Esto resulta en $f_k(x)=1$ .

Si $x\in (k-1,k)$ entonces asignamos la siguiente probabilidad de volteo $x-(k-1)$ . Si esta tirada sale cara, ganaremos con una probabilidad de 1. Si sale cruz, ganaremos con probabilidad $f_k(k-1)$ . De ello se desprende que $$ f_k(x)=(x-(k-1))+(k-x)f_k(k-1) $$

Por último, si $x\leq k-1$ entonces asignaremos la probabilidad $\epsilon$ a cada volteo subsiguiente, hasta que veamos una cara. Esto da $$ f_k(x)=\int_0^x e^{-t}f_{k-1}(x-t)\,dt $$

Podemos calcular recursivamente $f_k(x)$ para cualquier $k$ . Cada $f_k$ es una función continua y analítica a trozos. Los primeros valores (calculados con la ayuda de Mathematica; espero que sean correctos) son: $$ f_1(x)=\begin{cases} x&\text{ if }0\leq x\leq 1\newline 1&\text{ if }x>1 \end{cases} $$

$$ f_2(x)=\begin{cases} -1+x+e^{-x}&\text{ if }0\leq x\leq1\newline -1+\frac{2}{e}+(1-\frac{1}{e})t&\text{ if }1\leq x\leq 2\newline 1&\text{ if }x>2 \end{cases} $$

$$ f_3(x)=\begin{cases} -2+x+(x+2)e^{-x}&\text{ if }0\leq x\leq 1\newline e^{-x}+\frac{3}{e}-2-\frac{x}{e}+x&\text{ if }1\leq x\leq 2\newline -2+x+\frac{(1+e)(3-x)}{e^2}&\text{ if }2\leq x\leq 3\newline 1&\text{ if }x\geq 3 \end{cases} $$

Aunque no tengo una prueba de que esta estrategia sea óptima, tengo un argumento heurístico de que asignar la probabilidad $\epsilon$ a cada vuelta es una buena idea. Si nuestro presupuesto es $x$ entonces, sea cual sea nuestra estrategia, el número esperado de cabezas que habremos visto cuando agotemos nuestro presupuesto es $x$ . Si el número de cabezas deseado es mucho mayor que $x$ tendremos que hacer que la varianza en el número de cabezas sea grande. Si asignamos probabilidades $p_1,p_2,\ldots$ a los lanzamientos de monedas (con $p_1+p_2+\ldots=x$ ), entonces la varianza del número de cabezas es $\sum p_i(1-p_i)$ que está limitada por encima de $x$ . Podemos hacer que la varianza se acerque arbitrariamente a $x$ tomando cada $p_i$ lo más pequeño posible.

El argumento es un poco diferente si la siguiente cabeza que aparece puede hacer que nuestro presupuesto restante sea mayor que el número de cabezas adicionales que necesitamos para ganar.

Answer 2

Este problema se presta a un enfoque recursivo. El método que se presenta a continuación permite calcular la máxima probabilidad de ganar sobre todas las estrategias para cualquier $n,k$ de forma recursiva, en función de $b$ . Por tanto, todas estas soluciones son óptimas.

Sin embargo, la función de máxima probabilidad de ganar varía en el intervalo $0 \le b < k$ y teniendo en cuenta los cálculos de ejemplo que aparecen a continuación, parece que una fórmula general puede no ser tan fácil de encontrar.

Dejemos que $S_{n,k}(b)$ sea la máxima probabilidad de ganar el juego para las entradas dadas. Supongamos que $S_{n',k'}(b)$ es conocido por todos $n' < n$ y $k' \le k$ . Dado que en cualquier fase sólo hay que elegir una opción, a saber, qué parte del presupuesto $b$ para asignar a $p$ la probabilidad de obtener una cabeza - todas las estrategias posibles están parametrizadas por $0 \le p \le \text{min}(1,b)$ . Por lo tanto, por la suposición inductiva tenemos la siguiente relación de recurrencia:

$$ S_{n,k}(b) = \text{max}_{0 \le p \le \text{min}(1,b)} \ \{p \cdot S\_{n-1,k-1}(b-p) + (1-p) \cdot S\_{n-1,k}(b-p) \}, $$

ya que una cabeza (que ocurre con probabilidad $p$ ) disminuye tanto $n$ y $k$ mientras que una cola disminuye $n$ sólo.

Definimos $S_{n,k}(b) = 0$ si $n < k$ y $S_{n,0}(b) = 1$ para $n \ge 1$ y cualquier $b$ . Utilizando la recurrencia y estos casos base es fácil obtener $S_{n,1}(b) = \text{min}(1,b)$ para $n \ge 1$ . También es fácil demostrar que $S_{2,2}(b) = \text{min}(1,b^2/4)$ , ajuste $p=b/2$ para cada lanzamiento.

El primer caso no trivial es $$ S_{3,2}(b) = \begin{cases} \frac{b^2}{3} - \frac{b^3}{27} & \text{if} \ 0 \le b \le 3/2 & (\text{set} \ p = b/3)\\ \newline \frac{3b-2}{4} & \text{if} \ 3/2 \le b \le 2 & (\text{set} \ p = b-1)\\ \newline 1 & \text{if} \ b \ge 2, \end{cases} $$ que se obtiene por sustitución y diferenciación con respecto a $p$ .

$S_{3,3}(b) = \text{min}(1,b^3/27)$ , estableciendo $p = b/3$ mientras que el siguiente caso interesante es $$ S_{4,2}(b) = \begin{cases} \frac{b^4}{256} - \frac{b^3}{16} + \frac{3b^2}{8}& \text{if} \ 0 \le b \le 4/3 & (\text{set} \ p = b/4)\\ \newline \frac{19b-11}{27} & \text{if} \ 4/3 \le b \le 2 & (\text{set} \ p = b-1)\\ \newline 1 & \text{if} \ b \ge 2. \end{cases} $$

Debería ser posible demostrar una fórmula (recursiva) para $S_{n,2}(b)$ basado en lo anterior. Sin embargo, para $k=3$ , $n \ge 4$ esto puede ser algo más difícil. En particular, para $0 \le b \le 2$ tenemos $S_{4,3}(b) = b^3/16 - b^4/128$ , ajuste $p = b/4$ .

Para $2 \le b \le \alpha \approx 2.84$ tenemos $S_{4,3}(b) = r(b) \cdot \frac{3(b-r(b))-2}{4} + (1-r(b))\cdot\frac{(b-r(b))^3}{27}$ , donde $r(b)$ es la raíz en $[0,1]$ satisfaciendo $$ 16r^3 - (36b+12)r^2 +(24b^2 +24b - 162)r -4b^3 -12b^2 + 81b -54 = 0, $$ y $p = r(b)$ . Para $\alpha \le b \le 3$ , ajuste $p = b-2$ es óptimo y da $S_{4,3}(b) = 19b/27 - 10/9$ .

Parece que para las grandes $k$ (y $n$ ) estos cálculos se vuelven cada vez más engorrosos (o interesantes, según la perspectiva de cada uno).

---

EDITAR: Frente a la dificultad de encontrar una solución analítica, se puede resolver alternativamente para $S_{n,k}(b)$ numéricamente, mediante la subdivisión de la $p$ -intervalos con la precisión deseada y maximizando sobre $p$ .

Por ejemplo, dividiendo los intervalos por $1000$ encontramos que para el ejemplo de la serie mundial con $n=7$ , $k=4$ y asumiendo un presupuesto de $3.5$ tenemos $S_{7,4}(3.5) \approx 0.72826$ que se obtiene fijando $p_1 \approx 0.619$ etc. y siguiendo el árbol de decisión precalculado. Dado que hay que optimizar todo el árbol de decisión desde las hojas hasta la raíz antes de tomar la primera decisión, el $p_i$ no se eligen realmente de forma dinámica/reactiva en absoluto.

Answer 3

Una versión del problema no adaptativo fue estudiada por Uriel Feige, utilizando un lenguaje ligeramente diferente. En su papel En su libro "On Sums of Independent Random Variables with Unbounded Variance, and Estimating the Average Degree in a Graph", demuestra el siguiente teorema.

Dejemos que $X_1,\ldots,X_n$ sean variables aleatorias independientes no negativas con expectativas $\mu_1,\ldots,\mu_n$ respectivamente, con todos los $\mu_i \le 1$ . Sea $X=\sum_{i=1}^n X_i$ y $\mu=\sum_{i=1}^n \mu_i=\mathbb{E}X$ . Entonces, para todos los $\delta > 0$ ,

$$ \mathbb{P}[ X < \mu + \delta] \ge \min(\delta/(1+\delta),1/13). $$

El valor $1/13$ se mejoró posteriormente a $1/8$ por He, Zhang y Zhang . Feige conjetura que en el entorno del teorema anterior, para cada $n$ para todos $\delta > 0$ uno de los dos ejemplos siguientes minimiza $\mathbb{P}[ X < \mu + \delta]$ .

1. Para cada $1 \le i \le n$ , $X_i=n+\delta$ con probabilidad $1/(n+\delta)$ y en caso contrario es igual a $0$ .
2. $X_1=1+\delta$ con probabilidad $1/(1+\delta)$ y por otra parte $X_1=0$ . Para todos los $1 < i \le n$ , $\mathbb{P}[X_i=1]=1$ .

Si la conjetura de Feige es correcta, el término $1/13$ puede, de hecho, ser sustituido por $1/e$ . El primer paso en el argumento de Feige es mostrar que la cuestión general puede reducirse al caso de las variables aleatorias cuyo soporte contiene a lo sumo un valor distinto de cero; esto hace que el problema se parezca bastante al planteado anteriormente.

Answer 4

Doy aquí una solución al límite $b$ , $n$ , $k$ muy grande: La estrategia óptima es jugar siempre $\frac{b}{n}$ hasta que le quede más presupuesto que el número de cabezas a conseguir. Dará una probabilidad de ganar igual a $$2 \mathcal{N}([\frac{k-b}{\sqrt{b(1-\frac{b}{n})}},\infty])$$ Con $\mathcal{N}$ la medida gaussiana.

Observamos $S(i)$ el número de cabezas hasta el momento $i$ y $b(i)=b-\sum_{j<i}p(j)$ el presupuesto que le queda después de $i$ de un tirón. Definimos $X$ como $$X(i)=k-S(i)-b(i) $$ La observación central es la siguiente: sea cual sea la estrategia elegida $X$ es una Martingala. Por lo tanto, para $n,b,k $ grande y con un escalado correcto convergerá a un proceso estocástico continuo. Observamos que $t=\frac{i}{n}$ y en $[0,1]$ y cambiamos la notación de manera que $p(t)=p(i)$ , $b(t)=\frac{b(i)}{n}$ , $X(t)=\frac{1}{\sqrt{n}}X(i)$ . En el límite, el sistema evoluciona como sigue:
$$\begin{cases}dX_t = \sigma(p(t))dB_t \\ db_t=-p(t)dt \end{cases}$$ donde $\sigma(p(t))=\sqrt{p(t)(1-p(t))}$ . El proceso $p(t)$ es nuestra estrategia y debe ser pensada como $p(t,b_t,X_t)$ donde $0\leq p(t)\leq 1$ . Con la condición inicial $X_0 = \frac{1}{\sqrt{n}}(k-b)$ y la condición final $b(t=1)=0$ .

Tan pronto como $X_t=0$ Estamos en la situación $b\geq k$ se puede establecer $p(s)=1$ y luego $p(s)=0$ para terminar. Por lo tanto, hay que obtener $$ \mathbb{P}(\exists t : X_t\leq 0)$$ Tenemos una solución explícita para $X$ : $$X_t=X_0+B_{\int_0^t \sigma(p(s))^2 ds} $$ Y luego $$ \mathbb{P}(\exists t \in [0,1]: X_t\leq 0)= \mathbb{P}(\exists u \in [0,\int_0^1 \sigma(p(s))^2 ds]: B_u\leq -X_0)$$ Recordamos que $\int_0^1 \sigma(p(s))^2 ds$ no es una constante sino una variable aleatoria que depende de la estrategia elegida. Sin embargo, observamos que la probabilidad es monótona en $\int_0^1 \sigma(p(s))^2 ds$ y podemos concluir: debemos elegir siempre $p$ tal que $$\int_0^1 \sigma(p(s))^2 ds = \max_{p'} \int_0^1 \sigma(p'(s))^2 ds=\int_0^1 \frac{b}{n}(1-\frac{b}{n})ds= \frac{b}{n}(1-\frac{b}{n})$$ Las últimas igualdades se derivan del hecho de que $x\rightarrow \sigma(x)^2$ es cóncavo. Y tenemos $$\max_{p'} \mathbb{P}(\exists t : X_t\leq 0)= \mathbb{P}(\min_{u\in [0,\frac{b}{n}(1-\frac{b}{n})]} B_u\leq -X_0)=2 \mathcal{N}(y \leq \frac{k-b}{\sqrt{b(1-\frac{b}{n})}})$$ Con $\mathcal{N}$ la medida gaussiana. (la última igualdad es una propiedad bien conocida del máximo del movimiento browniano)