Borracho caminando con los pagos: cuando el borracho pagar?

Question

Un borracho se sitúa en el origen. Cada segundo que sale a la derecha con probabilidad de $p$, a la izquierda con probabilidad de $q$, y sigue siendo todavía con una probabilidad de $1-p-q$. Cuando llega a $x=+D$ o $x=-D$, se paga el $M$ dólares y es transportado de vuelta al origen.

Ahora, hay una nueva opción: en cada paso, después de que él sabe a dónde va a ir (a la izquierda o a la derecha), el borracho tiene una opción para pagar $m$ dólares y que permanezcan en su lugar. El borracho el objetivo final es minimizar su pago esperado más de mil billones de segundos. ¿Cómo debe el borracho decidir, en cada segundo, si se ha de pagar?

Creo que puedo resolver el caso especial en que $q=0$, yo.e, el borracho se mueve solo rightwards. En este caso, $D$ pasos rightwards costo $M$ dólares, por lo que un solo paso cuesta, en promedio, $M/D$ dólares. Por lo tanto, el borracho nunca debe pagar si $m>M/D$, y siempre hay que pagar si $m<M/D$ _{(puede haber excepciones en los primeros pasos o a la trillonésima paso, pero son insignificantes)}.

Sin embargo, no estoy seguro si el mismo argumento es true para arbitrario $q$.

Así, cuando debería de borracho pagar?

Answer 1

Incluso para el caso de $q=0$ tu argumento no funciona. Supongamos $N$ es el número de segundos que el borracho tiene que caminar (una constante). Vamos a llamar cada vez que el borracho se va todo el camino a $D$ un tour.

Supongamos $k$ tours se completó en $N$ segundos, con, respectivamente, $\{n_1, \cdots, n_k\}$ adicional veces los borrachos se ha pagado. También suponga que la última gira sigue siendo incompleta $\nu$ payups y $\mu$ no payups. A continuación, el total de dinero pagado será $$ P=Mk+\nu m+m\sum_{j=1}^{k} n_j $$ Ahora el $j$th tour lleva a los $D+n_j$ segundos. Y la última incompleta tour es $\nu+\mu$ segundos, con $\mu<D$ del curso. Por lo que la anterior está condicionado a $$ N=Dk +\mu +\nu + \sum_{j=1}^{k} n_j $$ Este es verdaderamente un condicional problema de optimización. Ahora supongamos $m>M/D$, sugiere usted nunca pagar un solo centavo. Su pago será de $M\lfloor N/D\rfloor$. Pero si, por el contrario, en cada tour, pagamos exactamente $n$ a veces, y no tener que pagar nada en la última incompleta gira, $$ N=(D+n)k+\mu\Longrightarrow k=\lfloor N/(D+n)\rfloor $$ El payup es, a continuación,$P_n=M\lfloor N/(D+n)\rfloor+mn$. El payup que proponemos es el $n=0$ de los casos. Por ejemplo, supongamos $N=2D\ell$ para algunos un gran$\ell$$n=D$. Entonces $$ P_0=\ell M+\ell M, \qquad P_D=M\ell +Dm $$ Claramente si $\ell M>Dm$ $P_D$ de los casos es mucho mejor. Esto sucede cuando $\ell>Dm/M$ o $N>2D^2m/M$. Este le dice $m>M/D$ o no, nunca se pagan no es una buena idea, si $N$ es lo suficientemente grande.

Su estimación para $m<M/D$ es mucho mejor. Supongamos que uno va con la estrategia de siempre pagando. A continuación, el payup es $P'=mN$. En el mismo ejemplo que antes de esto es peor que el $P_D$ menos que la condición $(2mD-M)\ell<Dm$ está satisfecho. Considerando $\ell\ggg 1$, la condición es más o menos limitada a los casos en los $m<M/2D$, que es similar a la estimación en este ejemplo.

Sin embargo, supongamos que en lugar de $N=sD\ell$ $s$ un pequeño número entero y $n=(s-1)D$. A continuación, un análisis similar se muestra que $$ P=M\ell+(s-1)Dm $$ Comparando con $P'=sD\ell M$ (siempre pagando caso), la condición para $P'$ es mejor que la $P$ ahora $m<M/sD$. Supongo que mi punto es, que este es un problema complicado, incluso en el caso de $q=0$. El comportamiento es muy sensible a los valores de $m,M,D,N$.

Answer 2

Esta es sólo una respuesta parcial, buscando lo más sencillo es no trivial caso, $D=2$.

Es de suponer que la cantidad de interés que puede ser descrito como el promedio de gasto por ronda, donde el proceso puede continuar indefinidamente (que yo considero que es el significado esencial de "billones"). Con esto en mente, podemos muy bien suponer que los $p+q=1$. Lo que permite la posibilidad de azar permanece inmóvil sólo significa que usted está ralentizando el gasto medio por vuelta abajo por un factor de $p+q$, cualquiera que sea nuestra estrategia se emplea.

En general, ya que la opción de permanecer estacionario no se decidió hasta después de la próxima putativo paso ha sido elegido al azar, no hay nunca ninguna necesidad de hacerlo, a menos que usted está en el $M$-dólar "precipicio" en uno de los dos extremos, en este caso en $+1$ o $-1$. En cualquier momento usted puede también dar el paso, incurrir en ningún costo, en la esperanza de revertir en la siguiente ronda.

Vamos a denotar por $N$ el gasto medio por paso si usted Nunca pagar a permanecer inmóvil. Bajo esta estrategia, que siempre terminan de vuelta en el origen de todos los demás de la ronda, por lo que sólo en el par de rondas, cuando estás en $\pm1$, que el riesgo de tener que pagar el $M$. El promedio de gasto es

$$N={p^2+q^2\over2}M$$

A continuación, vamos a denotar por $B$ el gasto medio por vuelta si usted paga a permanecer inmóvil en Tanto $+1$ $-1$ (si la alternativa llevaría a $+2$ o $-2$). Esto da un proceso de Markov en los estados $\{-1,0,1$} con la matriz de transición

$$\pmatrix{q&q&0\\p&0&q\\0&p&p}$$

y dominante eigenstate

$${1\over1-pq}\pmatrix{q^2\\pq\\p^2}$$

(Nota: $q^2+pq+p^2=1-pq$.) De ello se desprende que el gasto medio por vuelta (en el límite) es

$$B={q^3+p^3\over1-pq}m$$

Por ejemplo, si $p=q=1/2$, luego

$$N={1\over4}M\quad\text{and}\quad B={1\over3}m$$

así se produce el cruce en $m={3\over4}M$. (Nota, si $pq=0$,$N=M/2$$B=m$, con un crossover en $m=M/2=M/D$, como el OP observado.)

Hay, por supuesto, más dos estrategias: pagar a permanecer inmóvil en $-1$ pero no $+1$, y viceversa. Vamos a denotar por $L$ $R$ el gasto medio por ronda para estas dos estrategias. Si me he hecho el álgebra correctamente, los resultados son

$$L={p^3\over1+p^2}M+{q^2\over1+p^2}m$$ y $$R={q^3\over1+q^2}M+{p^2\over1+q^2}m$$

Para $p=q=1/2$ tenemos

$$L=R={1\over10}M+{1\over5}m$$

No es difícil comprobar que, para$p=q=1/2$,$600(N-L)(L-B)=(3M-4m)^2$, lo que significa que el $L$ (e $R$), la estrategia siempre se encuentra entre el $N$ $B$ estrategias, con el cruce en $m={3\over4}M$, por lo que para el clásico, simétrica borracho a pie, uno debe estar dispuesto a pagar a permanecer inmóvil o Nunca o Ambos extremos (lo cual tiene sentido, por simetría).. Para general $p+q=1$, sin embargo, puede haber casos en que $L$ o $R$ es óptimo.

Podría ser vale la pena mirar con cuidado en el caso de $D=3$, pero esperemos que esto da una indicación de cómo las cosas van a ir.