Cadena de Markov

Cadenas de Markov
por N´stor Aguilera
e

´
Indice
1. Introducci´n
o

1

2. Ejemplos

1

3. Usando grafos dirigidos

5

4. Usando matrices

7

5. Clasificaci´n de estados y cadenas
o

7

6. Un caso particular

9

7. Cadenas absorbentes: resultados te´ricos
o
8. Problemas de dados y monedas
8.1. El problema de repetir hasta obtener m consecutivos . .
8.2. Elproblema de repetir hasta superar una suma prefijada
8.3. Sumar n´meros entre 0 y 1 hasta llegar a 1 . . . . . . .
u
8.4. El problema del cumplea˜os . . . . . . . . . . . . . . . .
n
8.5. Movimiento Browniano en una dimensi´n . . . . . . . .
o

10
.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

.
.
.
.
.

13
15
17
18
19
22

9. Cadenas regulares

2410.Comportamiento Asint´tico
o

28

Ap´ndice A: Algunas
e
A.1. Problema 7.8 .
A.2. Problema 8.10 .
A.3. Problema 8.12 .

soluciones
29
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
. . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

Ap´ndice B: F´rmulas relacionadas con el problema del cumplee
o
a˜ os
n31
Ap´ndice C: Programas en Pascal
e

33

Bibliograf´
ıa

35

i

1. Introducci´n
o

1.

Introducci´n
o

Muchas veces nos encontramos con problemas como el del Certamen “El
N´ mero de Oro” para profesores del a˜ o 2002:
u
n
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 enalguna 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 su
anterior intervenci´n. El juego finaliza cuando alg´n jugador gana. Si A apuesta
o
u
$20, ¿cu´nto deben apostar B y C para que las chances sean parejas?
a
£
O, un ejercicio muy com´ n de programaci´n como:
u
o
1.2 Problema: Hacer unprograma (en Basic, Pascal, etc.) para simular tirar
un dado hasta que salga un 1 m veces consecutivas, y repetir esta simulaci´n n
o
veces para obtener una estimaci´n del n´mero de tiradas esperado.
o
u
£
En estas notas, basadas en un curso dado en la Reuni´n de Educaci´n Mao
o
tem´tica de la UMA de 2002, veremos c´mo la teor´ de cadenas de Markov
a
o
ıa
puede dar respuesta a ´sta yotras preguntas similares.
e
Desde el punto de vista del aprendizaje, es muy interesante intercalar experimentos num´ricos para hacer conjeturas que luego se apoyan en los resultados
e
te´ricos, o al rev´s, hacer los experimentos num´ricos para terminar de conveno
e
e
cerse que los resultados te´ricos se adecuan a la “realidad”. Algunos experimeno
tos pueden hacerse con tablas de n´merosaleatorios, pero es m´s conveniente
u
a
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 anterior.
El plan es el siguiente: primero veremos algunos ejemplos sencillos de cadenas de Markov, luego veremos c´mo interpretar las cadenas en el lenguaje de
o
digrafos (grafos dirigidos)y matrices. Despu´s de hacer una clasificaci´n sene
o
cilla, pasamos a mirar con alg´ n detalle las cadenas absorbentes, y usamos los
u
resultados obtenidos en problemas de tirar dados o monedas. Terminamos con
una breve menci´n de cadenas regulares, viendo algunos resultados y aplicacioo
nes. En los ap´ndices incluimos algunas soluciones a problemas planteados y
e
algunos programas enPascal (f´cilmente traducibles a otros lenguajes) con sus
a
resultados, para ir obteniendo ejemplos “concretos”.
La forma de presentar la teor´ en estos apuntes est´ tomada del libro de Roıa
a
berts [Rob76], el que a su vez est´ basado en la presentaci´n del libro de Kemeny
a
o
y Laurel Snell [KLS76], en donde se tratan los temas con mayor profundidad
(por ejemplo, se hace un an´lisis de la...