Saltar al contenido

Problema con la ruina del jugador

Ya no tienes que indagar más por todo internet ya que llegaste al sitio indicado, tenemos la respuesta que buscas sin complicarte.

Solución:

Proporcionamos una respuesta y la vinculamos con las respuestas ya dadas que pueden ayudar a ver las conexiones.

Algunas observaciones:

  • Podemos reducir el problema a uno combinatorio contando todos los caminos a partir de $ (0, k) $ para $ (m-1, n-1) $ usando pasos $ (1,1) $ y $ (1, -1) $ que no llegan a las lineas $ y = 0 $ y $ y = n $.

  • El punto de partida representa el $ k $ monedas del jugador que tiene desde el principio. Ganar una ronda aumenta sus monedas en una, lo que está representado por un paso. $ (1,1) $ y perder una ronda también significa entrar $ x $-dirección en uno, pero disminuyendo $ y $ por uno, así que damos un paso $ (1, -1) $.

  • Cada ruta válida desde $ (0, k) $ para $ (m-1, n-1) $ tiene longitud $ m-1 $ y se realiza con probabilidad $ frac 1 2 ^ m-1 $. Con el fin de alcanzar $ (m, n) $ esto solo se puede hacer en un paso desde $ (m-1, n-1) $ para $ (m, n) $ con probabilidad $ frac 1 2 $, de modo que el número de rutas válidas desde $ (0, k) $ para $ (m-1, n-1) $ finalmente tiene que ser dividido por $ 2 ^ m $ para encontrar la probabilidad deseada.

Comenzamos con un ejemplo que confirma el enfoque de @GCab.

Ejemplo (parte 1): k = 2, m = 14, n = 6

Contamos el número de rutas válidas desde $ (0,2) $ para $ (14,6) $, que es el número de rutas de celosía desde $ (0,2) $ para $ (13,5) $ que no tocan las lineas $ y = 0 $ y $ y = 6 $, seguido de un $ m $-th paso desde $ (13,5) $ para $ (14,6) $.

Vemos de acuerdo con la tabla presentada por @GCab que tenemos $ color rojo 364 $ rutas válidas que están marcadas en rojo en el gráfico siguiente.

![enter image description here

We can normalise the situation by shifting $(0,k)$ to $(0,0)$ and consider the equivalent problem to count the number of lattice paths from $(0,0)$ to $(m-1,n-1-k)$ using steps $(1,1)$ and $(1,-1)$ without reaching the boundaries $y=n-k$ and $y=-k$. We denote this number of valid paths by
beginalign*
L_m-1,n-1-k;n-k,k
endalign*

Formula:

The formula above in the form $L_m,n;r,s$ counting valid paths from $(0,0)$ to $(m,n)$ which do not reach the boundaries $y=r$ and $y=-s$ is established in this post. It can be written as

beginalign*
L_m,n;r,s&=binommfracm+n2-sum_jgeq1left[binommfracm+n2-r+j(r+s)
+binommfracm+n2+s-j(r+s)right]\ & qquad qquad qquad + sum_ j geq1 left[binommfracm+n2+j(r+s)
+binommfracm+n2-j(r+s)right] etiqueta 1 \ end align *

En la situación actual obtenemos de (1) el número de caminos válidos para el problema de OP:

begin align * & color blue L_ m-1, n-1-k; nk, k = binom m-1 frac m + nk 2 – 1 \ & quad qquad- sum_ j geq1 left[binomm-1fracm+n-k2-1-n+k+jn+binomm-1fracm+n-k2-1+k-jnright]\ & quad qquad + sum_ j geq1 left[binomm-1fracm+n-k2-1+jn+binomm-1fracm+n-k2-1-jnright] etiqueta 2 \ & quad = – sum_ j geq0 binom m-1 frac m + nk 2 -1 + k + jn – sum_ j geq1 binom m-1 frac m + nk 2 -1 + k-jn \ & quad qquad + sum_ j geq0 binom m-1 frac m + nk 2 -1 + jn + sum_ j geq1 binom m-1 frac m + nk 2 -1-jn etiqueta 3 \ & quad , , color azul = sum_ j = – infty ^ infty left[binomm-1fracm+n-k2-1+jn-binomm-1fracm+n+k2-1+jnright] etiqueta 4 end align *

Comentario:

  • En (3) cambiamos en la serie más a la izquierda el índice en uno para comenzar con $ j = 0 $. En la tercera serie fusionamos el término más a la izquierda de (2).

  • En (4) combinamos las dos series más a la derecha así como las dos series más a la izquierda.

La probabilidad resultante es
begin align * color blue frac 1 2 ^ m L_ m-1, n-1-k; nk, k end align *

Las sumas en (2) son una consecuencia de la aplicación del principio de inclusión-exclusión a las rutas reflejadas. Esto es necesario para compensar el conteo doble como se indica en la respuesta de @Hans.

.

Ejemplo (parte 2): k = 2, m = 14, n = 6

Para verificar (2) calculamos el número de rutas válidas del ejemplo anterior.

Obtenemos

begin align * color blue L_ 13,3; 4,2 & = binom 13 8 – left[binom1310+binom134right]+ izquierda[binom132right] etiqueta 3 \ & = 1 , 287- (286 + 715) +78 \ & , , color azul = 364 end align *

de acuerdo con la primera parte del ejemplo. Tenga en cuenta que el número de trayectorias reflejadas entre paréntesis en (3) se indica en el gráfico mediante $ A_1, B_1 $ y $ B_2 $.

Esto se resuelve mediante la aplicación repetida del principio de reflexión.

Solo necesitamos enumerar el número de trayectorias de pérdidas y ganancias que satisfacen la condición que luego se divide por $ 2 ^ m $ para obtener la probabilidad. El número de caminos a partir de $ 0 $ monedas y terminando en $ y $ monedas en el $ x $la ronda es
$$ y elija l tag1 $$
dónde $ l = frac xy 2 $ es el número de pérdidas en este camino.

Primero resolvemos el problema parcial de partir de $ k $ monedas y terminando en $ n $ monedas en ronda $ m $ por primera vez (así que cayendo debajo $ 0 $ se permite la moneda). Cada ruta admisible da una ruta única de $ m-1 $ rondas que alcanza $ n-1 $ monedas en ronda $ m-1 $ sin poseer nunca $ n $ monedas antes. Cada uno de esos caminos de $ m-1 $ rondas genera una única requerida $ m $ redondea el camino ganando una ronda más. Debido a esta correspondencia uno-uno, solo necesitamos calcular el número de tales $ m-1 $ caminos redondos $ N_1 (m, k, n) $. Por el principio de reflexión aplicado a la línea reflectante de $ n $ monedas y ecuación $ (1) $$$ f_1 (n, k, m) = m-1 elija frac m-n + k 2 – m-1 elija frac mn-2 + k 2. $$

Ahora agregamos la condición de que el camino nunca debe tocar el $ 0 $ línea de monedas. Por el principio de reflexión aplicado a la línea de monedas. $ 0 $, los caminos que satisfacen la condición del párrafo anterior pero no tocan el $ 0 $ línea de moneda uno a uno corresponde a

$$ f_2 (n, k, m) = m-1 elija frac m-n + k 2 – m-1 elija frac mn-2 + k 2 – m- 1 elija frac m + n-2 + k 2 + m-1 elija frac m + n + k 2. $$

Necesitamos reflejar el camino ad infinitum alrededor de las líneas. $ ni _ i = 0 ^ infty $ hasta que se agote la longitud del camino para tal reflexión. Por inducción matemática, podemos obtener la enumeración final deseada.
$$ f (n, k, m) = sum_ i = – infty ^ infty Bigg (m-1 choose frac m- (2i + 1) n + k 2 – m-1 elige frac m- (2i + 1) n-2 + k 2 Bigg) $$
dónde $ a elija b: = 0, , forall b not in[0,a]PSo entero $ i in big[-frac12big(fracm-kn+1big),,frac12big(fracm+kn-1big)big]PS. La probabilidad buscada es simplemente $ frac f (n, k, m) 2 ^ m $.

El enfoque estándar sería a través de la matriz de Markov.
La matriz de transición, que denota la probabilidad de cambios en el capital en cada corrida, es simple. Para $ n = 4 $ por ejemplo, es
$$ bf T (4) = left ( matrix 1 & 0 & 0 & 0 & 0 cr 1/2 & 0 & 1/2 & 0 & 0 cr 0 & 1/2 & 0 & 1/2 & 0 cr 0 & 0 & 1/2 & 0 & 1/2 cr 0 & 0 & 0 & 0 & 1 cr derecha) $$
y computacionalmente funciona bastante bien. Tomando los diversos poderes de la matriz ($ bf T ^ m $) los $ k $-th fila dará la probabilidad de obtener el capital correspondiente al índice de la columna.
Ya que en $ 0 $ y $ n $ tenemos una barrera absorbente, esas columnas darán la probabilidad acumulativa de perder o ganar.
De esta forma obtenemos por ejemplo, para $ n = 5,6 $, las siguientes tablas para $ f (n, k, m) $

Gambler_ruin_1

que se corresponden con el tuyo. Sin embargo, los resultados son difíciles de representar en términos analíticos, porque la forma canónica de Jordan es complicada y la posible división en componentes más simples conduce a términos no conmutativos.

Así que adoptamos un enfoque diferente.

Si llegamos a redondear $ q $ con mayúscula $ 1 le c le n-1 $, luego el número de formas de proceder desde aquí y ganar en la ronda $ m $ ($ w_n (q, m, c) $) es claramente igual al número de formas de alcanzar ese objetivo a partir de la ronda anterior ($ q-1 $) con mayúscula $ c-1 $
más los que tienen mayúscula $ c + 1 $, ya que la probabilidad de ganar y perder es la misma. Es decir
$$ w _ , n (q, m, c) = izquierda[ 1 le c le n – 1 right] left (w _ , n (q – 1, m, c – 1) + w _ , n (q – 1, m, c + 1) right) $$
dónde PS[P]PS denota el Soporte Iverson$$ left[ P right] = left { begin array * 20 c 1 & P = VERDADERO \ 0 & P = FALSO \ end array Derecha. $$
y la condición $ left[ 1 le k le n – 1 right]PS es asegurar que nos mantengamos en juego.

Yendo hacia atrás desde el punto $ (m, n) $ y complementando el capital, es fácil transformar lo anterior en una recursividad para $ f $, comenzando desde el punto$ (n, 0) $$$ bbox[lightyellow] eqalign & f_n (k, m) = cr & = left[ 1 le k le n – 1 right] left (f_n (k – 1, m – 1) + f_n (k + 1, m – 1) right) + left[ 0 = m right]izquierda[ n = k right] = cr & = left[ 0 le k – 1 le n – 2 right]f_n (k – 1, m – 1) + izquierda[ 2 le k + 1 le n right]f_n (k + 1, m – 1) + izquierda[ 0 = m right]izquierda[ n = k right] cr $$
esto se comprueba con las tablas anteriores y proporciona una herramienta de cálculo más eficaz.

Comentarios y valoraciones

Eres capaz de añadir valor a nuestra información colaborando tu experiencia en las notas.

¡Haz clic para puntuar esta entrada!
(Votos: 0 Promedio: 0)



Utiliza Nuestro Buscador

Deja una respuesta

Tu dirección de correo electrónico no será publicada. Los campos obligatorios están marcados con *