El problema del jugador, el problema del paseo del borracho o del camino aleatorio, es un clásico de la probabilidad que tiene enorme interés en distintos campos de matemática aplicada, como en la segmentación de imágenes o en las finanzas. El problema, en su formulación más sencilla, podría describirse de la siguiente manera:
Sea un jugador que partiendo de una cantidad inicial de dinero, desea alcanzar un cierto objetivo apostando en un juego. La mecánica del juego es tal que si el jugador gana (con probabilidad p) se embolsa una cantidad igual a la apostada, perdiendo el dinero de la apuesta (con probabilidad q) en caso contrario. El juego solo finaliza si el jugador alcanza su objetivo o si termina en la banca rota. El problema consiste en establecer la probabilidad de terminar en bancarrota antes de alcanzar el objetivo, en función del objetivo y de la cantidad de dinero con la que se parte, así como de las probabilidades p y q.
Vamos a resolver el problema usando probabilidad, de forma teórica, para luego solucionarlo de forma empírica empleando Python. Ambas deberían converger cuando el número de ensayos es lo suficientemente grande (Ley de los grandes números).
Supongamos que la cantidad apostada es tratada como unidad, no hay problema en esto ya que todas las apuestas deben ser iguales a lo largo del juego. Sea $u_{j}$ la probabilidad de que termine en la bancarrota y j la cantidad con la que se parte. En ese caso es claro que:
$u_{j}=p\cdot u_{j+1}+q\cdot u_{j-1}$
Con las condiciones de frontera:
$u_{0}=1$ y $u_{c}=0$ , siendo c el objetivo
Tras algunas operaciones algebraicas, obtenemos la probabilidad buscada:
$u_{j}=\frac{r^{j}-r^{c}}{1-r}$ siendo r=q/p
Para los detalles matemáticos se puede consultar cualquier libro de probabilidad que trate el tema de los caminos aleatorios, como por ejemplo Elementary Probability Theory, K. L. Chung. Springer (2003).
Evidentemente este resultado solo es válido si r es distinto de 1 ya que en ese caso la probabilidad nos da una indeterminación. Para el caso en el que r=1, se llega a la siguiente conclusión:
$u_{j}=\frac{c-j}{c}$
Una vez establecido el marco teórico, vamos a realizar un algoritmo que realice el papel de jugador. Empecemos con el caso más sencillo, aquel en el que las probabilidades son 1/2 para el jugador y la banca, esto es p=q=1/2, por lo que r=1.
import random as rnd
def gambler(money0,objective, bet = 1):
cont = 1
lines =[]
num = money0
while (num > 0 and num < objective):
num = num + rnd.choice([-bet,bet])
lines.append([cont,num])
cont= cont + 1
return lines
Como puede verse el algoritmo es muy sencillo, se parte de una cantidad inicial de dinero (money0), de una apuesta (bet) que tomaremos como 1, y un objetivo. En la función un número pseudoaleatorio [-1,1] con idéntica probabilidad hace las veces de resultado. Los distintos juegos se van sumando (o restando) a la cantidad inicial, el bucle continua hasta que se alcanza el objetivo o hasta que el jugador cae en bancarrota. El resultado de los distintos juegos se mete en una tupla (línea 7).
A continuación dibujamos el resultado de las partidas. Para el caso que nos ocupa he elegido pygame para representar los resultados. La función que dibuja los distintos lances de la partida es como sigue:
En la línea 8 encontramos la función que dibuja la gráfica con los resultados, su uso es muy intuitivo y no requiere demasiadas explicaciones. Antes de poder dibujar con Pygame es necesario inicializar el área donde se va a dibujar, esto se realiza de la siguiente forma:
La línea 4 es necesaria para refrescar el contenido de la ventana del dibujo y debe ser invocada cada vez que pintemos algo. El resultado de un solo juego, queda gráficamente como:
Se han añadido los resultados de calcular la frecuencia relativa, así como los casos ganados y perdidos. También figura la probabilidad calculada según la formula ofrecida más arriba para el caso r=1. El resultado que arrojan para este caso es:
Los datos ofrecidos no arrojan demasiada información. Las frecuencias relativas no se parecen en nada a los cálculos teóricos. Al aumentar el número de jugadas, a 100, por ejemplo, los resultados van cambiando:
Los resultados numéricos son:
Como puede comprobarse los valores teóricos empiezan a parecerse a los resultados empíricos. Si aumentamos el número de juegos a 100000 tenemos que:
Aquí las frecuencias relativas son casi idénticas a las obtenidas mediante el pequeño juego que hemos elaborado. Si quisiéramos trabajar con probabilidades distintas de r=1 seria necesario modificar:
Ya que esta función de random selecciona entre -bet y bet con igual probabilidad. Una solución sencilla es emplear sample(population,k), donde population es una población y k la longitud de la lista extraída de population. En el siguiente ejemplo (+1) tiene una probabilidad de 0.333 mientras que (-1) de 0.666:
Los dibujos que representan los distintos caminos que sigue la jugada, hasta alcanzar la bancarrota o el objetivo, forman una curiosa forma geométrica. Es un caso unidimensional de un paseo aleatorio también podría decirse que es un paseo aleatorio por una recta. La figura cumple con los requisitos de dimensión fraccionaria, lo que los convierte en una figura fractal. Son una versión sencilla de la curva de Korch, o una curva aleatoria de Peano, con un generador mucho más sencillo. Si se desea profundizar en este tipo de fractales recomiendo la lectura de los capítulos 7,8,9 y 10 del magnifico libro La Geometría Fractal de la Naturaleza, Benoît Mandelbrot, TusQuets (2003).
A continuación dibujamos el resultado de las partidas. Para el caso que nos ocupa he elegido pygame para representar los resultados. La función que dibuja los distintos lances de la partida es como sigue:
import pygame as pyg
def draw(points,color,screen,init_point):
point0 = init_point
point_end = [0,150]
for point in points:
point_end = [point_end[0] + 10, point[1] + 150]
print point_end
pyg.draw.line(screen,color,point0,point_end,1)
point0 = point_end
En la línea 8 encontramos la función que dibuja la gráfica con los resultados, su uso es muy intuitivo y no requiere demasiadas explicaciones. Antes de poder dibujar con Pygame es necesario inicializar el área donde se va a dibujar, esto se realiza de la siguiente forma:
screen = pyg.display.set_mode((1000, 250 + OBJECTIVE))
pyg.init()
pyg.display.set_caption('Game')
pyg.display.flip()
La línea 4 es necesaria para refrescar el contenido de la ventana del dibujo y debe ser invocada cada vez que pintemos algo. El resultado de un solo juego, queda gráficamente como:
Se han añadido los resultados de calcular la frecuencia relativa, así como los casos ganados y perdidos. También figura la probabilidad calculada según la formula ofrecida más arriba para el caso r=1. El resultado que arrojan para este caso es:
Los datos ofrecidos no arrojan demasiada información. Las frecuencias relativas no se parecen en nada a los cálculos teóricos. Al aumentar el número de jugadas, a 100, por ejemplo, los resultados van cambiando:
Los resultados numéricos son:
Como puede comprobarse los valores teóricos empiezan a parecerse a los resultados empíricos. Si aumentamos el número de juegos a 100000 tenemos que:
Aquí las frecuencias relativas son casi idénticas a las obtenidas mediante el pequeño juego que hemos elaborado. Si quisiéramos trabajar con probabilidades distintas de r=1 seria necesario modificar:
Ya que esta función de random selecciona entre -bet y bet con igual probabilidad. Una solución sencilla es emplear sample(population,k), donde population es una población y k la longitud de la lista extraída de population. En el siguiente ejemplo (+1) tiene una probabilidad de 0.333 mientras que (-1) de 0.666:
num_pos = [x/x for x in xrange(1,4)] num_neg = [-x/x for x in xrange(1,7)] space = num_pos + num_neg rnad_num = rnd.sample(space,1)[0]
Los dibujos que representan los distintos caminos que sigue la jugada, hasta alcanzar la bancarrota o el objetivo, forman una curiosa forma geométrica. Es un caso unidimensional de un paseo aleatorio también podría decirse que es un paseo aleatorio por una recta. La figura cumple con los requisitos de dimensión fraccionaria, lo que los convierte en una figura fractal. Son una versión sencilla de la curva de Korch, o una curva aleatoria de Peano, con un generador mucho más sencillo. Si se desea profundizar en este tipo de fractales recomiendo la lectura de los capítulos 7,8,9 y 10 del magnifico libro La Geometría Fractal de la Naturaleza, Benoît Mandelbrot, TusQuets (2003).
No hay comentarios:
Publicar un comentario