Cadenas de Markov y procesos estocásticos en el Monopoly PDF

Preview

Summary

Informe donde se explora la mejor estrategia en el juego de mesa del Monopoly haciendo uso de la herramienta matemática conocida como cadenas de Markov...

Description

Evaluación Interna Matemáticas: Análisis y Enfoque NM

Cadenas de Márkov para hacer un modelo matemático del Monopoly

Índice Introducción ……………………………………………………………………………………. Pág. 2 Conceptos matemáticos …………………………………………………………………….. Pág. 4 Consideraciones …………………………………………………………………………….. Pág. 7 Construcción de la matriz …………………………………………………………………… Pág. 8 Conclusiones ………………………………………………………………………………… Pág. 10 Fuentes ……………………………………………………………………………………….. Pág. 11

1

Código del alumno: Manuel Álvarez Martínez Introducción He elegido este tema porque la probabilidad es una de las áreas que más me gustan de las matemáticas y quería hacer una Evaluación Interna de algo desconocido pero que a la vez me atrajese. Uno de mis juegos de mesa favoritos es el Monopoly y siempre me ha gustado saber si es mejor comprar en unas casillas que en otras. El tema que he elegido es la aplicación de las Cadenas de Márkov en la modelización de una partida del Monopoly. Esta herramienta matemática es ideal para la investigación pues presenta un rasgo indispensable, no tiene memoria. Lo que esto significa es que una Cadena de Markov presenta la probabilidad de ciertas variables de una forma en la que las variables en tiempo t+1 son independientes de las variables en tiempo t. Esta característica intrínseca nos permite determinar la probabilidad de transición entre casillas a largo plazo. Haciendo uso de este sistema, trataré de hallar las mejores casillas para comprar, aquellas donde es más probable caer y por ende cobrar más a tus oponentes, encontrar las más fáciles para edificar y en general con toda esta información conseguir dominar una partida de este juego. Para ello, usaré las Cadenas de Márkov que es un proceso estocástico donde la probabilidad de un suceso depende directamente del anterior (Juan Antonio del Valle,2014). Un proceso estocástico es un conjunto de variables aleatorias que depende de un parámetro o de un argumento (Economipedia, 2017) Un ejemplo sencillo relacionado con la meteorología sería: si llueve un día es más probable que vuelva a llover al día siguiente a que haga sol. Por el contrario, si hace sol un día, hay mayor probabilidad de que al día siguiente ese mismo evento se repita. Con el uso de estos procesos podemos determinar la probabilidad de caer en una casilla en el primer turno, en el segundo… Hoy en día, las Cadenas de Márkov tienen infinidad de aplicaciones en diversos campos (Universidad de Ottawa, 2013): - Modelos epidemiológicos - Posicionamiento de páginas web en buscadores - Prevención de morosidad y estudio de consumidores - Juegos de azar, véase la ruina del jugador, un enunciado matemático que afirma que en juego justo (donde las probabilidades de ganar son parejas) ganará siempre el jugador con más dinero (Revista Suma, 2009) - Previsión meteorológica - Inventarios y mantenimiento de empresas Como dice Juan Antonio del Valle de la UNAM, el rasgo característico de este proceso estocástico es que sigue la propiedad de Márkov, esto es, carece de memoria. La probabilidad de un valor futuro para una variable depende exclusivamente del valor actual y no del historial de la misma.

2

Se suelen expresar con un diagrama de transición donde se muestra la probabilidad de transición entre estados. He diseñado un diagrama para representar el cambio de estados entre la lluvia y el sol. Imaginemos que cuando hace sol hay un 20% de probabilidad de que llueva al día siguiente mientras que hay un 80% de que siga soleado. Por el contrario, cuando llueve hay

0.8

0. 8

0 . 7

0.2 0.2

SOL

0 .0 . 2

0.7

LLUVIA 0.3

0. 3

un 70% de probabilidad de que siga lloviendo y un 30% de que haga sol. Para cualquier diagrama, la suma de las probabilidades consecuentes de un estado deber ser igual a 1 Fig. 1: Diagrama de transición entre los estados “sol“ y “lluvia”

Para poder modelizar una partida de Monopoly es imprescindible conocer las reglas por las que se rige el juego. El juego del Monopoly tiene una serie de reglas básicas (El juego de mesa, 2013). A continuación, enunciaré las más importantes para el desarrollo de este proyecto que son aquellas relacionadas con el movimiento del jugador por el tablero. El objetivo del juego es convertirse en el jugador más rico. Al empezar la partida todos reciben la misma cantidad de dinero Cada jugador lanza los dados y mueve el número de espacios indicados por los dados. Es conveniente indicar que dos o más fichas pueden estar en el mismo espacio al mismo tiempo. Dependiendo de donde llegue, puedes comprar la propiedad si esta no pertenece a nadie, pagar impuestos/multas, ir a la cárcel o coger una carta de Chance o Community Chest (pueden ser beneficios o desventajas para el jugador). Si lanzas dobles, vuelves a tirar. Si lanzas dobles tres veces seguidas, estarás obligado a ir a la cárcel. Cuando eres enviado a la cárcel, debes esperar 3 turnos o usar la carta “Salir gratis de la cárcel”. Por el contrario, si caes en ese espacio estás “Sólo visitando” y podrás avanzar de manera habitual en el siguiente turno. Lo más importante del juego es que para evaluar el valor de cada propiedad es necesario saber como de probable es caer en esta. Con esta exploración matemática busco eso mismo para poder tener una mejor idea

3

Fig. 2: Tablero del Monopoly Edición España (Wikipedia, 2015)

Conceptos matemáticos Para hacer uso de las cadenas de Márkov y poder aplicarlas a problemas reales es necesario usar matrices de transición. Una matriz de transición ( Pt) en tiempo t es una matriz que muestra las probabilidades de cambio entre estados (Universidad Carlos III, 2012). Para ello, debemos saber también que es una matriz. Una matriz es un conjunto de números reales dispuesto en “ m” filas y “n” columnas. Esos números se denominan elementos. El número de filas por el número de columnas se denomina dimensión de la matriz y se designa como m x n, siendo m el número de filas y n el número de columnas. Un elemento cualquiera de la matriz se escribirá como a ij donde “ i” indica la fila y “j” la columna (Ekuatio, 2019). A continuación, tenemos una matriz de dimensión 2x2. Si queremos encontrar el elemento a2,1 tendremos que buscar el elemento que esté en la segunda fila y primera columna, en este caso, 5.

A 2 x 2=

(25 63)

Para sumar matrices deben tener las mismas dimensiones y se suman los elementos que ocupan las mismas posiciones. En el ejemplo de abajo, tenemos dos matrices de dimensión 1x2 y para sumarlas repetimos los pasos antes mencionados.

2 ¿ ¿ A 1 x 2=(1¿ ) 1 ¿ ¿ B 1 x 2=(2¿ ) 3 ¿ ¿ A +B=( 2+1 1+2 )=(3¿ )

4

Para multiplicar dos matrices es indispensable que el número de columnas de la primera matriz sea igual al número de filas de la segunda matriz. Para dos matrices A = (aij)mxn y B = (bij)pxq donde n=p, el número de columnas de la primera es igual al de filas de la segunda, el producto será: El elemento que ocupa el lugar (i, j) en la matriz producto se obtiene sumando los productos de cada elemento de la fila i de la matriz A por el correspondiente de la columna j de la matriz B. (profesorenlinea, 2014)

( ) ( 22) 1∗2+2∗2 = 5 6 ( 2∗2+1∗2 ) ( 7 6 )

A= 1 2 ∙ B= 3 2 1 1 AB= 1∗3+2∗1 2∗3+1∗1

Sólo podemos calcular potencias de matrices cuadradas, aquellas que tengan el mismo número de columnas que de filas. Por ejemplo, la potencia A2 es el producto de matrices A·A, lo que exige que A tiene que ser cuadrada. Para elevar potencias, deberemos multiplicar las matrices tantas veces como el exponente. Esto es, si elevamos A a la cuarta, multiplicaremos A*A y luego multiplicaremos A2 x A2. En una matriz de transición de estados, tenemos el espacio estado que está determinado por la dimensión de la matriz, esto es, el orden de las filas y columnas. En este tipo de matrices el elemento (i,j) viene determinado por:

(Pt )i , j=P(X t=i ∣X t +1= j) La ecuación anterior indica que el elemento número ( i,j) siendo i un estado de salida, esto es, un estado inicial y j un estado de llegada de un determinado suceso siempre un intervalo de tiempo posterior a i, representa la probabilidad del cambio del estado indicado en la fila i al estado indicado en la fila j. Es decir, si un sistema de Márkov está en el estado i, hay una determinada probabilidad, pij, de ir al estado j en el próximo intervalo de tiempo, siendo pij la llamada la probabilidad de transición asociada a este cambio entre estados. Si P es la matriz de transición, la distribución de esta después de n intervalos de tiempo será Pn. Esto implica que la ijª entrada de Pn es la probabilidad de que el sistema pase del estado i al j en n intervalos de tiempo. (Universidad Carlos III, 2012) Para poder entender mejor esto voy a hacer uso del mismo ejemplo que en la Figura 1 donde hay dos estados: lluvia y sol. En nuestro ejemplo con datos ficticios, sabemos que si un día hace sol, hay una probabilidad de un 80% de que vuelva a hacer sol y un 20% de que haya lluvia (cambio de estado). Por otro lado, si un día hace lluvia, hay un 70% de probabilidad de que llueva de nuevo y un 30% de que el próximo día sea soleado (cambio de estado). Toda esta información podemos ponerla en una tabla que luego podremos organizar en una matriz de transición. Estado de llegada (t+1) Sol Lluvia Estado de Sol 0.8 0.2

5

Salida (t)

Lluvi a

0.3

0.7

Como vemos cada fila debe sumar 1 ya que al hablar de probabilidad esta debe ser exactamente 1. Con estos datos podemos elaborar una matriz de transición para este ejemplo:

(

P= 0.8 0.2 0.3 0.7

)

Esta muestra la distribución en el turno 1, para saber la probabilidad de transición en el turno n habrá que elevar la matriz a n. Por ejemplo, después de 4 intervalos de tiempo la matriz quedará así. Se podría decir que en este ejemplo un intervalo de tiempo corresponde a un día ya que asumimos que solo puede suceder una de los variables a la vez, sea sol o lluvia.

(

P4 = 0.625 0.375 0.563 0.438

)

Como dije anteriormente, la ijª entrada de Pn es la probabilidad de que el sistema pase del estado i al j en n pasos. Esto significa que el elemento de la fila 2 y columna 1 muestra la probabilidad del cambio entre el estado de la fila 2 y la columna 1, en este caso, que pase de la lluvia al sol. Haré uso de otro ejemplo para mostrar mejor el uso de matrices de transición. En este, tenemos un tablero de 4 casillas donde avanzamos del número 1 hasta la número 4 y continuamos por el 1, como un círculo. Usaremos un dado y avanzaremos el número de casillas que obtengamos en el dado. Si obtenemos más de 3 con el dado, seguiremos dando la vuelta al tablero de tal forma que si yo estoy en la casilla 1 y saco un 4, acabaré en la 1. En este contexto, un intervalo de tiempo corresponde a una ronda donde tiramos el dado 1 vez, será igual en el caso del Monopoly.

Estado de salida (t)

Casilla 1 1/6 1/6 2/6 2/6

Casilla 1 Casilla 2 Casilla 3 Casilla 4

Estado de llegada (t+1) Casilla 2 Casilla 3 Casilla 4 2/6 2/6 1/6 1/6 2/6 2/6 1/6 1/6 2/6 2/6 1/6 1/6

Como en el ejemplo anterior, cada fila debe sumar 1, ni más ni menos. A partir de los datos de esta tabla elaboramos una matriz de transición P de 4x4.

(

1/6 2/6 1/6 1/6 P= 2/6 1/6 2/6 2/6

2 /6 2 /6 1/6 1/6

)

1/ 6 2/ 6 2/ 6 1/ 6

6

Una vez tenemos la matriz construida, la elevaremos a un numero grande para saber la probabilidad de transición después de mucho tiempo. Por ejemplo, la elevo a 50 para hallar la probabilidad de moverse de una casilla a otra después de 50 turnos. Observamos que la probabilidad de movimientos es prácticamente la misma sin importar la casilla y es lo que busco encontrar en el Monopoly. Cabe decir que en las probabilidades subrayadas, no era 0.25 exactamente sino 0.249999998 por lo que he decidido aproximar.

(

1/4 P50= 1/4 1/4 1/4

1/4 1/4 1/4 1/4

1 /4 1/4 1/4 1/4

1/ 4 1/ 4 1/ 4 1/ 4

)

Este mismo concepto deberá ser aplicado para poder modelizar la partida de Monopoly. En ese caso, en vez de una matriz de dimensión 2x2 tendremos una de nxn donde n representa el número de estados en la partida. Consideraciones Un estado es un tipo de suceso que queremos analizar con la Cadena de Márkov. Por ejemplo, los estados en la matriz anterior son “Lluvia” y “Sol”, son características o eventos específico. Una vez sabemos esto, debemos averiguar cuantos “estados” hay en el Monopoly y a partir de ahí determinar la probabilidad de llegar a cada casilla. Hay que tener en cuenta varios factores: 1. Hay que llevar la cuenta de las veces que se han sacado dobles ya que, si sacas dobles tres veces consecutivas, deberás ir a la cárcel 2. Si estás en la cárcel hay que llevar la cuenta de los turnos que llevas en ella 3. Hay cartas de Community Chest y Chance que afectan al movimiento del jugador, por ejemplo, hay algunas que te obligan a ir a la cárcel, ir a una estación en concreto… Otro aspecto importante que no es posible modelizar sería la voluntad del jugador de salir de la cárcel haciendo uso de la opción del pago de la fianza por la cual un jugador paga una cantidad de dinero con el fin de no tener que permanecer en la cárcel durante 3 turnos. Esto no depende de la probabilidad ni del azar por lo que se me ha ocurrido una forma de tener en cuenta esta opción que nos brinda el juego gracias a múltiples guías de juego que he leído. Al comienzo de la partida, los terrenos no tienen dueño por lo que el objetivo de los jugadores es comprar la mayor cantidad posible. Si tienen la mala suerte de caer en la casilla de la cárcel, no podrán comprar en 3 turnos mientras que los demás jugadores sí lo harán. Por ello, el jugador será más partidario de pagar la fianza en los primeros turnos. Por el contrario, al final de la partida, cuando todos los terrenos han sido ya comprados y algunos han sido edificados, al jugador que esté en la cárcel, creo que le interesa permanecer allí el mayor tiempo posible ya que no deberá pagar ningún alquiler a otro jugador mientras que el podrá cobrar los alquileres de sus propiedades. (J. Fantozzi, 2018)

7

Es por esto que podríamos definir la probabilidad de que un jugador pague para salir de la cárcel como una función inversamente proporcional al número de propiedades ya compradas. Cuando estas sean 0 la probabilidad de que pague será del 100% mientras que cuando no quede ninguna es muy probable que el jugador no vaya a pagar.

Si sólo dependiese de los factores mencionados en el gráfico, esa sería la distribución, pero como también hay que analizar el dinero que tenga, las propiedades que quiera comprar, la suposición no es del todo correcta. Al final, no importa que todas las variables indiquen que el jugador vaya a hacer una cosa u otra, todo dependerá de lo que él decida por lo que es prácticamente imposible modelizar ese rasgo de la partida. Por ese motivo, para este estudio matemático, suprimiré la opción del jugador de poder pagar para salir de la cárcel ya que si no, no satisfacería las condiciones markovianas. Otra modificación que habría que hacer a las reglas del juego para poder llevar a cabo esta investigación sería la eliminación de las cartas “Queda libre de la prisión” que te permiten usarlas para no tener que esperar 3 turnos en la prisión. Cabe decir que la posibilidad de que te toque una de estas cartas es bastante baja ya que solo es de 1/16 (1 de las 16 de Community Chest y 1 de las 16 de Chance). La última modificación que hay que hacerle al juego está relacionada con las cartas de Community Chest y Chance. Según las reglas oficiales, se deberá dejar la carta usada debajo de todas las demás. Esto incumple las reglas de un proceso markoviano ya que este solo busca la probabilidad de ir de un estado i a un estado j sin tener en cuenta como se ha llegado al estado i. En este caso, si dejamos las cartas debajo, las siguientes estarán determinadas por los estados anteriores. Para que siga siendo markoviano, deberemos barajar las cartas siempre y cuando se coja una para que no sigan ningún orden específico. Con esto damos por terminado las modificaciones que habría que hacerle al juego para hacer el estudio mediante Cadenas de Markov posible. Construcción de la matriz

8

Para construir la matriz de transición, he hecho una tabla de datos para organizar mejor la información. La tabla es de 120x120 ya que hay 40 casillas en el Monopoly y debemos llevar la cuenta de las veces que hemos sacado dobles. He ordenado las casillas numéricamente de manera ascendente de forma que la casilla “Salida” sea la número 1 y la casilla “Paseo del Prado” sea la 40. Para mostrar cuando se ha llegado a una casilla con dobles, he numerado todas las casillas con un símbolo ‘(Ejemplo: 3’). He hecho lo mismo para cuando se llega a dobles solo que repitiendo el símbolo 2 veces (Ejemplo: 5’’). Hay cartas de Community Chest y Chance que implican movimiento, esto es nos hacen movernos a una casilla diferente. Para estas cartas, lo interpretaremos como un cambio directo a la casilla representada por la carta sin haber pasado por la casilla de Community Chest o Chance. Por ejemplo, si salgo desde “Salida”, tengo una probabilidad de 6/36 (sacar un 7) de llegar a la casilla número 8 (que es de Chance). Sin embargo, no pondré ese valor en la matriz puesto que de las 16 cartas que hay de Chance hay 9 que implican movimiento. Es por esto que la probabilidad que insertaré en la matriz de transición será

(

)

6 9 5 ∗ 1− = . De igual forma, la probabilidad de llegar a las casillas incluidas en 36 16 216 las cartas movimiento incrementará. Otra característica de esta tabla es que para aquellos movimientos donde se salga de una casilla x’’ (casilla con dos dobles consecutivos), habrá una probabilidad 1/6 de ir a la cárcel debido a que es la probabilidad de sacar dobles. A este número, habrá que sumarle la probabilidad de ir a la cárcel por cartas o por llegar a esa casilla con los dados. Debido al tamaño de la matriz que voy a usar, me es imposible mostrarla en este documento por lo que aquí solo mostraré el resultado final. Una vez he construido la matriz de transición en Excel, hago uso de Wolfram Alpha para elevar a matriz y hallar las probabilidades de movimiento. He decidido elevarla a 30 ya que es el número medio de turnos de una partida de Monopoly (T. Oléron, 2017). A continuación, mostraré una relación de casillas con la probabilidad media de llegar a esa casilla desde cualquier lugar del tablero. Para calcularla, he sumado todas las probabilidades de llegar a esa casilla sin dobles, con dobles por primera vez y con dobles por segunda vez y he dividido entre 120, el número de datos que daban información de la llegada a esa casilla. La suma de las probabilidades de las casillas debe ser 100 para que sea correcto. Casilla

Probabilidad media de llegada (%)

Salida Ronda de Valencia Caja Comunidad Plaza Lavapiés Impuesto capital Estación Goya Glorieta Cuatro Caminos Suerte Avenida de Reina Victoria

2,906 2,015 1,773 2,041 2,187 2,806 2,122 0,818 2,183

9

Calle Bravo Murillo Cárcel Glorieta de Bilbao Compañía de electricidad Calle Alberto Aguilera Calle Fuencarral Estación de las Delicias Avd. Felipe II Caja Comunidad Calle Velázquez Calle Serrano Párking Avd. de América Suerte Calle María de Molina Calle Cea de Bermúdez Estación del Mediodía Avd. Reyes Católicos Calle Bailén Compañía de Aguas Plaza de España Ve a Cárcel Puerta del Sol Calle Alcalá Caja Comunidad Gran Vía Estación del Norte Suerte Paseo de la Castellana Impuesto lujo Paseo del Prado Total

2,171 2,136 2,566 2,617 2,172 2,426 2,642 2,632 2,296 2,829 2,802 2,829 2,611 1,039 2,571 2,997 2,890 2,533 2,524 2,658 2,445 9,451 2,518 2,479 2,233 2,356 2,2...