Cadenas De Marcov

Cadenas de Markov
por Néstor Aguilera† Versión revisada, 7 de octubre de 2009‡

Universidad Nacional del Litoral y Consejo Nacional de Investigaciones Científicas y Técnicas, Argentina ‡ Versión original: 12 de diciembre de 2002

†

Índice
Índice de figuras 1. Introducción 2. Ejemplos 3. Usando grafos dirigidos 4. Usando matrices 5. Clasificación de estados y cadenas 6. Un caso particular7. Cadenas absorbentes: resultados teóricos 8. Dados y monedas 8.1. Repetir hasta obtener m consecutivos . . . . 8.1.1. Análisis directo . . . . . . . . . . . . . 8.1.2. Con cadenas de Markov . . . . . . . 8.2. Repetir hasta suma prefijada . . . . . . . . . 8.3. Sumar números entre 0 y 1 hasta llegar a 1 8.4. El problema del cumpleaños . . . . . . . . . 8.4.1. Análisis Directo . . . . . . . . . . .. . 8.4.2. Como cadena de Markov . . . . . . . 8.5. Movimiento Browniano . . . . . . . . . . . . 9. Cadenas regulares 10.Comportamiento Asintótico Apéndice A: Algunas soluciones A.1. Problema 7.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.2. Problema 8.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . A.3. Problema 8.12 . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . Apéndice B: Fórmulas relacionadas con el problema del cumpleaños Apéndice C: Programas en Pascal Bibliografía ii 1 2 5 7 7 9 10 13 15 15 16 17 18 19 19 20 21 23 27 28 28 29 30 31 33 35

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . ..

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

. . . . . . . . .

i

ii

Índice de figuras

Índice de figuras
3.1. Digrafo asociado al paseo por la peatonal. . . . . . . . . . 3.2. Árbol de posibilidades. . . . . . . . . . . . . . . . . . . . . . 3.3. Árbol de posibilidades, con probabilidades en los arcos. 5.1. Un digrafo no conexo . . . . . . . .. . . . . . . . . . . . . . 5.2. Conjunto ergódico y estados transientes . . . . . . . . . . 7.1. Una cadena absorbente simple. . . . . . . . . . . . . . . . . 10.1.Una cadena cíclica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 6 6 8 8 12 28

Cadenas de Markov

1

1. Introducción
Muchas veces nosencontramos con problemas como el del Certamen El Número de Oro(1) para profesores del año 2002: 1.1. Problema. Tres jugadores, A, B y C, arrojan alternativamente —en ese orden— una moneda equilibrada. Los jugadores A y B ganan el juego si en alguna de sus tiradas obtienen el mismo resultado que C en su tirada anterior, mientras que C gana si obtiene en alguna tirada el mismo resultado que A en suanterior intervención. El juego finaliza cuando algún jugador gana. Si A apuesta $20, ¿cuánto deben apostar B y C para que las chances sean parejas? £ O, un ejercicio muy común de los cursos de programación como: 1.2. Problema. Hacer un programa (en Basic, Pascal, etc.) para simular tirar un dado hasta que salga un uno m veces consecutivas, y repetir esta simulación n veces para obtener una estimacióndel número de tiradas esperado. £ En estas notas, basadas en un curso dado en la Reunión de Educación Matemática de la UMA(2) de 2002, veremos cómo la teoría de cadenas de Markov puede dar respuesta a ésta y otras preguntas similares. Desde el punto de vista del aprendizaje, es muy interesante intercalar experimentos numéricos para hacer conjeturas que luego se apoyan en los resultados teóricos,o al revés, hacer los experimentos numéricos para terminar de convencerse que los resultados teóricos se adecuan a la «realidad». Algunos experimentos pueden hacerse con tablas de números aleatorios, pero es más conveniente trabajar con una calculadora apropiada, o mejor una computadora con un lenguaje como Pascal o Basic, o un sistema similar a Mathematica o Matlab, como en el problema...