Cadenas de Markov

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 ii
1. Introducción 1
2. Ejemplos 2
3. Usando grafos dirigidos 5
4. Usando matrices 7
5. Clasificación de estados y cadenas 7
6. Un caso particular 9
7. Cadenas absorbentes: resultados teóricos 10
8. Dados y monedas 13
8.1. Repetir hasta obtener m consecutivos . . . . . . . . . . . . . . . . . . 15
8.1.1. Análisis directo . . . . . . . . . . . . . . . . . . . . . . . . . . . 15
8.1.2. Con cadenas de Markov . . . . . . . . . . . . . . . . . . . . . 16
8.2. Repetir hasta suma prefijada . . . . . . . . . . . . . . . . . . . . . . . 17
8.3. Sumar números entre 0 y 1 hasta llegar a 1 . . . . . . . . . . . . . . 18
8.4. El problema del cumpleaños . . . . . . . . . . . . . . . . . . . . . . . 19
8.4.1. Análisis Directo . . . . . . . . . . . . . . . . . . . . . . . . . . . 19
8.4.2. Como cadena de Markov . . . . . . . . . . . . . . . . . . . . . 20
8.5. Movimiento Browniano . . . . . . . . . . . . . . . . . . . . . . . . . . 21
9. Cadenas regulares 23
10.Comportamiento Asintótico 27
Apéndice A: Algunas soluciones 28

A.1. Problema 7.8 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
A.2. Problema 8.10 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29
A.3. Problema 8.12 . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30
Apéndice B: Fórmulas relacionadas con el problema del cumpleaños 31
Apéndice C: Programas en Pascal 33
Bibliografía 35
i
ii Índice de figuras
Índice de figuras
3.1. Digrafo asociado al paseo por la peatonal. . . . . . . . . . . . . . . . 5
3.2. Árbol de posibilidades. . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
3.3. Árbol de posibilidades, con probabilidades en los arcos. . . . . . . 6
5.1. Un digrafo no conexo . . . . . . . . . . . . . . . . . . . . . . . . . . . . 8
5.2. Conjunto ergódico y estados transientes . . . . . . . . . . . . . . . . 8
7.1. Una cadena absorbente simple. . . . . . . . . . . . . . . . . . . . . . . 12
10.1.Una cadena cíclica. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28
Cadenas de Markov 1
1. Introducción
Muchas veces nos encontramos 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 su anterior 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ón del 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 experimen-
tos 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 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 digrafos
(grafos dirigidos) y matrices. Después de hacer una clasificación sencilla, pasamos a
mirar con algún detalle las cadenas absorbentes, y usamos los resultados obtenidos
en problemas de tirar dados o monedas. Terminamos con una breve mención
de cadenas regulares, viendo algunos resultados y aplicaciones. En los apéndices
incluimos algunas soluciones a problemas planteados y algunos programas en Pascal
(fácilmente traducibles a otros lenguajes) con sus resultados, para ir obteniendo
ejemplos «concretos».
La forma de presentar la teoría en estos apuntes está tomada del libro de
Roberts [Rob76], el que a su vez está basado en la presentación del libro de Kemeny
y Laurel Snell [KLS76], en donde se tratan los temas con mayor profundidad (por
ejemplo, se hace un análisis de la varianza que nosotros no tratamos). Para los
que quieran profundizar aún más, recomendamos el volumen 1 del libro clásico de
Feller [Fel57].
Para aprovechar estas notas, es conveniente estar familiarizado con los elementos
de álgebra lineal y cálculo de límites, ¡y no asustarse cuando aparezcan grafos, o
programas en Pascal!
(1)
http://www.oma.org.ar/nacional/oro.htm
(2)
http://www.union-matematica.org.ar/
2 2. Ejemplos
2. Ejemplos
Empecemos con algunos ejemplos sencillos. El primero está tomado del libro de
Kemeny y Snell [KLS76, pág.29]:
2.1. Ejemplo (El clima en la Tierra de Oz). Según el cuento, en la Tierra de Oz

nunca hay dos días buenos en sucesión. Después de un día con buen tiempo, le
sigue (con igual probabilidad) un día con lluvia o nieve. Del mismo modo, si nieva
(o llueve), el día siguiente nevará (o lloverá) con probabilidad 1/2, pero si cambia
el tiempo sólo la mitad de las veces será un lindo día. $
Para estudiar este problema primeramente encontramos las probabilidades de
transición, es decir las probabilidades de que teniendo cierto clima un día, al día
siguiente se tenga otro clima. Así, si indicamos con b a un día bueno, con ` a uno
lluvioso y n si nieva, tendremos
p bb = 0 de un buen día a un buen día,

p b` = 1/2 de un buen día a un día lluvioso,
p bn = 1/2 de un buen día a un día con nieve,
p`` = 1/2 de un día lluvioso a un día lluvioso,
p`b = 1/4 de un día lluvioso a un buen día,
p`n = 1/4 de un día lluvioso a un día con nieve,
pnn = 1/4 de un día con nieve a un buen día,
pn` = 1/4 de un día con nieve a un día con lluvia,
pnb = 1/2 de un día con nieve a un buen día.
Es conveniente ordenar estos datos en una tabla o matriz,
b ` n
b 0 1/2 1/2
` 1/4 1/2 1/4
n 1/4 1/4 1/2
donde las filas indican el clima en el día, las columnas el clima en el día siguiente, y
las entradas son las probabilidades de cambio o transición. No es sorprendente que
la matriz se llame matriz de transición (o transiciones).
Observamos que en esta matriz no sólo los coeficientes son no-negativos, sino
que al sumarlos por filas obtenemos 1, indicando que alguna de las posibilidades,
en este caso b, ` o n, debe necesariamente suceder: una matriz con esta propiedad
—no-negatividad y suma 1 por filas— también se llama de probabilidad o estocástica.
En cambio, al sumar por columnas, a veces obtenemos menos de 1, a veces más, y
habrá casos donde dará 1.
El ejemplo del clima en la Tierra de Oz es un ejemplo típico de cadena de Markov:
1. tenemos ciertos estados, en este caso b, ` y n,
2. en cada momento estamos en uno de estos estados,
3. en el próximo momento (los «momentos» considerados son discretos) vol-
veremos a estar en ese u otro estado,
4. pasamos de un estado a otro con cierta probabilidad,
Cadenas de Markov 3
5. que sólo puede depender del estado inmediatamente anterior,

6. y esta probabilidad no cambia con el transcurso del tiempo.
La cadena de Markov es uno de los modelos más sencillos para tratar de predecir
el comportamiento de un «sistema», en este caso el clima en Oz. Por ejemplo nos
podemos preguntar: en 100 días, ¿cuántos serán de lluvia (en promedio)?; o, si hoy
está nevando, ¿cuántos días (en promedio) habrá que esperar hasta tener un buen
día?
Veamos otros ejemplos de cadenas de Markov.
2.2. Ejemplo (Paseando por la peatonal). La peatonal de mi pueblo tiene 6

cuadras de largo, que van de norte a sur. Estoy con ganas de deambular y pasar el
tiempo, y como tengo una moneda, se me ocurre tirarla y caminar una cuadra hacia
el norte si sale cara o una cuadra hacia el sur si sale ceca. Y continúo este juego
hasta salir de la peatonal, ya sea hacia el norte o hacia el sur. $
En este caso, podemos pensar que los estados son 0, 1, . . . , 5, 6, donde 0 es la
esquina sur donde empieza la peatonal, 6 la esquina norte, y las esquinas intermedias
se numeran entre 1 y 5.
La matriz de transición puede escribirse entonces como
0 1 2 3 4 5 6
 
0 1 0 0 0 0 0 0
1 1/2 0 1/2 0 0 0 0 


2 0 1/2 0 1/2 0 0 0 

3 0 0 1/2 0 1/2 0 0 
 
4 0 0 0 1/2 0 1/2 0 
 
5 0 0 0 0 1/2 0 1/2
6 0 0 0 0 0 0 1
En este caso tenemos que pensar que las filas y columnas corresponden a los
estados 0, 1,. . . , 6. Sin embargo, tenemos la novedad de que al llegar al estado 0
(la esquina sur) o 6 (la esquina norte), el «juego» se termina, por lo que ponemos
un 1 en la entrada correspondiente indicando que ya nos quedamos para siempre
en esa posición.
La teoría de cadenas de Markov que veremos servirá para responder a preguntas
como: si empiezo justo en la mitad de la peatonal (la esquina 3), en promedio (si
hago el juego muchas veces) ¿cuántas cuadras caminaré hasta llegar a la esquina 0
o 6?, ¿cuántas veces pasaré por la esquina 1?
2.3. Problema. Supongamos que decido no terminar el juego, y en cambio seguir

paseando por la peatonal, volviendo una cuadra para atrás cada vez que llego a la
esquina norte o sur. ¿Cómo se modificaría la matriz anterior? $
No todos los procesos estocásticos —básicamente procesos que dependen del
tiempo y que tienen probabilidades asociadas— son cadenas de Markov.
Por ejemplo:
2.4. Problema. Supongamos que en el ejemplo 2.1, las probabilidades dependen

de la estación del año: en verano e invierno las probabilidades son las mencionadas,
pero en primavera y otoño si nieva o llueve la probabilidad de que el día siguiente
sea bueno es ahora 1/8 (y la de continuar con el mismo clima sigue siendo 1/2).
4 2. Ejemplos
a) Ver que ahora no se forma una cadena de Markov con tres estados (b, n, `):
¿qué falla?
b) ¿Podrían considerarse más estados, de modo de que sí sea una cadena de
Markov? $
A veces se trata de una cadena de Markov «disfrazada»:
2.5. Problema. Consideramos dos estados, cara y ceca, y tiramos una moneda
repetidas veces saliendo cara o ceca con probabilidad 1/2 cada una.
a) Ver que se trata de una cadena de Markov definiendo estados apropiados, y
construir la matriz de transición correspondiente.
b) ¿Y si las probabilidades de que salga cara es 1/3 y de que salga ceca es
2/3? $
2.6. Problema (Modelo de urnas de Polya). ] Una urna contiene b bolas blancas
y r bolas rojas, y se saca una al azar. Se la reemplaza y se agregan c bolas del mismo
color que la elegida, y seguimos repitiendo el procedimiento (ahora hay b + r + c
bolas en la urna).
Si consideramos como estados a que salga una bola blanca o una roja, ¿se forma
una cadena de Markov?, ¿por qué?
Nota: Este ejemplo, tomado de [Fel57, pág.120], puede considerarse como un modelo
de dispersión de enfermedades contagiosas, donde cada ocurrencia de la enfermedad
aumenta la probabilidad de que vuelva a ocurrir. $
2.7. Problema (Teoría de Mendel). En 1866 el monje agustino Gregor Mendel

publicó sus estudios sobre cierta variedad de arvejas que tiene las vainas de color
verde o amarillo. A veces, todo un grupo de estas plantas es puramente verde, o
a veces todo un grupo es puramente amarillo. Cuando se cruzan plantas que son
puramente verdes entre sí, las nuevas plantas siguen teniendo vainas verdes, y de
modo similar para las puramente amarillas.
Mendel descubrió que cuando se cruzaban plantas de grupos «puros» distintos,
las nuevas plantas siempre tenían vainas verdes. Pero si dos de estas nuevas plantas
se cruzaban entre sí, aproximadamente 3 de cada 4 tenían vainas de color verde y
la restante de color amarillo.
Estos experimentos llevaron a Mendel a construir la teoría de que un rasgo tal
como el color de la vaina está determinado por dos «genes», cada uno de los cuales
puede ser de carácter dominante o recesivo. En el caso de las arvejas, los genes que
determinan el color verde de la vaina son dominantes, y los correspondientes al
color amarillo son recesivos, y —según la teoría— cuando de dos genes hay uno
dominante, el color queda determinado por éste, mientras que sólo puede tener
color amarillo si ambos genes son recesivos.
Siempre de acuerdo a la teoría, cuando dos individuos se cruzan el resultado
hereda un gen de cada uno de ellos, y esta elección de gen es aleatoria.
Suponiendo que la teoría sea válida, y que la probabilidad que la elección de
gen de un progenitor sea 1/2, determinar los estados y la matriz de transición
correspondiente para formar una cadena de Markov que modela la descendencia
de un individuo (en cada paso el descendiente da lugar a un nuevo individuo al
cruzarse con otro).
Sugerencia. Pensar en 3 estados (por ejemplo, D si tiene ambos genes dominantes,
H —híbrido— si tiene un gen dominante y otro recesivo, y R si ambos genes son
En el Ejemplo 2.2 de la peatonal, tendrı́amos ası́ V = {0, 1, 2, 3, 4, 5, 6}, los
arcos serı́an
A = {(0, 0),(1, 0), (1, 2), (2, 1), (2, 3), (3, 2),
(3, 4), (4, 3), (4, 5), (5, 4), (5, 6), (6, 6)},
que podemos representar gráficamente como en la Figura 1, donde sobre cada
arco hemos
Cadenas puesto la probabilidad de transición correspondiente (observar que
de Markov 5
no ponemos el arco si la probabilidad correspondiente es 0).
1 1!2 1!2 1!2 1!2 1!2 1

0 1 2 3 4 5 6
1!2 1!2 1!2 1!2 1!2
Figura
Figura 1: Digrafo
3.1: El digrafo asociado
asociado al paseo
al paseo peatonal.
por la peatonal.
recesivos), y hacer que las entradas pi j representen la probabilidad de que un

3.1 Problema: Hacer el digrafo correspondiente al clima en la Tierra de Oz
individuo de tipo i sea cruzado con un individuo de tipo j. $
(Ejemplo 2.1). !
A. A. Markov (1856–1922) trazó los fundamentos de la teoría de cadenas de
Pensar en digrafos ayuda a pensar en la estructura de la cadena de Markov.
Markov finitas, pero por bastante tiempo las aplicaciones concretas se restringieron
Pormayoritariamente
ejemplo, las probabilidades de transición nos dicen que, para el problema
al estudio de mezclar cartas y problemas lingüísticos. Posteriormente,
de la peatonal, si estoy en la esquina 3 en el
A. Kolmogorof introdujo la teoría de cadenas conpróximo
un número paso estoy
infinito deen la esquina
estados, y su 2
conlibro
probabilidad 1/2,
de 1938 hizo másenaccesible
la esquina 4 con
la teoría probabilidad
y la posibilidad de1/2, y no puedo
una mayor estar
cantidad de en
ninguna otra esquina. Pero, empezando en la esquina 3, ¿cuál es la probabilidad
aplicaciones.
de estar en la esquina 1 en dos pasos?, ¿en la esquina 2?, ¿en la esquina 3?
Nos ayudamos con un digrafo (o mejor dicho un árbol dirigido con raı́z),
3.
comoUsando grafos
el de la Figura dirigidos
2, empezando desde el nodo 3, poniendo en distintos niveles
(alturas) los lugares a los que puedo llegar según la cantidad de pasos (parecido
al triángulo
Una forma dedePascal).
entender mejor cadenas de Markov es usando grafos dirigidos, o
En la Figura 2 de
digrafos, con pesos, vemos
la forma (V, A, W ) donde
que empezando desde los3,nodos
en un—los
pasoelementos
llego a 2 ode4,Ven
—
son los estados, un arco a = (u,
dos pasos llego a 1, 3 o 5, y en tres pasos a uv
v) está en A si p >
0, 2, 4 o 6. Ya sabemos colocar
0, pudiendo darse el caso de
probabilidades
bucles para un
o lazos donde el primer paso (1/2
arco empieza en cada
y termina rama).
en un Para
mismo el segundo
nodo, paso
y se asigna a
cada arco (u,
tenemos en cuenta que: uv
v) el «peso» p .
En el ejemplo 2.2 de la peatonal, tendríamos así V = {0, 1, 2, 3, 4, 5, 6}, los arcos
serían
A = {(0, 0),(1, 0), (1, 2), (2, 1), (2, 3), (3, 2),
(3, 4), (4, 3), (4, 5), (5, 4), (5, 6), (6, 6)},
que podemos representar gráficamente como en la figura 3.1, donde sobre cada
arco hemos puesto la probabilidad de transición correspondiente (observar que no
ponemos el arco si la probabilidad correspondiente es 0).
3.1. Problema. Hacer el digrafo correspondiente al clima en la Tierra de Oz (ejem-

plo 2.1). $
Pensar en digrafos ayuda a pensar en la estructura de la cadena de Markov. Por

ejemplo, las probabilidades de transición nos dicen que, para el problema de la
peatonal, si estoy en la esquina 3 en el próximo paso estoy en la esquina 2 con
probabilidad 1/2, en la esquina 4 con probabilidad 1/2, y no puedo estar en ninguna
otra esquina. Pero, empezando en la esquina 3, ¿cuál es la probabilidad de estar en
la esquina 1 en dos pasos?, ¿en la esquina 2?, ¿en la esquina 3?
Nos ayudamos con un digrafo (o mejor dicho un árbol dirigido con raíz), como el
de la figura 3.2, empezando desde el nodo 3, poniendo en distintos niveles (alturas)
los lugares a los que puedo llegar según la cantidad de pasos (parecido al triángulo
de Pascal).
En la figura 3.2 vemos que empezando desde 3, en un paso llego a 2 o 4, en dos
pasos llego a 1, 3 o 5, y en tres pasos a 0, 2, 4 o 6. Ya sabemos colocar probabilidades
para el primer paso (1/2 en cada rama). Para el segundo paso tenemos en cuenta
que:
1 3 5
0 2 4 6
Pág. 6 Figura 2: Árbol de posibilidades.Cadenas de Markov

6 3. Usando grafos dirigidos
• Para llegar a 1 tengo que llegar3 primero a 2 (con probabilidad 1/2) y

después llegar a 1 desde 2 (con probabilidad 1/2): en total llego con pro-
babilidad 1/4.
2 4
• Para llegar a 3 pude haber pasado primero por 2 con probabilidad 1/4 para
esos dos pasos (como antes), o haber pasado primero por 4, también con
probabilidad 1/4. 1Como pude usar3 cualquiera5de los dos caminos, sumo
las probabilidades, obteniendo 1/2.
Siguiendo con0 este procedimiento,
2 en cada
4 arco de la6 figura ponemos la
probabilidad de recorrerlo, como en la Figura 3 (con letras más pequeñas y
hacia la izquierda del Figura
arco), de
Figura 2: modo
3.2: Árbolque
Árbol la suma de las probabilidades de los
de posibilidades.
de posibilidades.
arcos en cada nivel debe dar 1.
3
• Para llegar a 1 tengo que1!2llegar primero a 2 (con probabilidad 1/2) y
1!2
después llegar a 1 desde 2 (con probabilidad 1/2): en total llego con pro-
babilidad 1/4. 2 1!2 4 1!2
1!4 1!4
• Para llegar a 3 pude haber 1!4
pasado primero1!4por 2 con probabilidad 1/4 para
esos dos pasos (como
1 1!4 antes), o haber
3 1!2 pasado 5primero
1!4 por 4, también con
probabilidad1!81/4. Como pude1!4 usar cualquiera
1!8 de los dos caminos, sumo
1!8 1!4 1!8
las probabilidades, obteniendo 1/2.
0 1!8 2 3!8 4 3!8 6 1!8
Siguiendo con este procedimiento, en cada arco de la figura ponemos la
probabilidad
Figura de recorrerlo,
3.3: Árbol de como en la Figura
de posibilidades, 3 (con letras
con probabilidades en másarcos.
pequeñas y
hacia laFigura 3: Árbol
izquierda del arco),posibilidades,
de modo quecon probabilidades
la suma enlos
los arcos. de los
de las probabilidades
arcos en cada nivel debe dar 1.
•Para
Paracalcular
llegar a 1lastengo
probabilidades de llegar
que llegar primero
3 a 2a(con
un nodo en determinado
probabilidad nivel,
1/2) y después
sumamos las probabilidades de los
llegar a 1 desde 2 (con probabilidad
1!2 arcos que
1/2): en total llego con probabilidad3
llegan al nodo, que en la Figura
están1/4.
puestas con letras en negrita 1!2 algo mayores y hacia la derecha de cada
nodo. También la suma de las2 probabilidades
1!2 sobre los nodos en cada nivel debe
4 1!2
• Para llegar a 3 pude1!4haber pasado1!4 primero por 2 con probabilidad 1/4 para
dar 1.
esos dos pasos (como antes), 1!4 o haber pasado
1!4 primero por 4, también con
Ası́, para obtener la probabilidad de que empezando en 3 lleguemos a 4
probabilidad 1/4.1Como 1!4 pude usar3 1!2cualquiera5de1!4los dos caminos, sumo las
en tres pasos, miramos a las probabilidades1!8
1!8 obteniendo1!4
de los arcos que llegan al nodo 4
probabilidades, 1/2.
(ubicado en el tercer nivel)1!8 que son 1/8 1!4 y 1/4, las sumamos
1!8 y obtenemos 3/8.
0 1!8 2 3!8 4 3!8 6 1!8 ponemos la pro-
3.2Siguiendo
Problema:con esteelprocedimiento,
En Ejemplo 2.1 delenclima
cada arco
en de¿cuál
Oz, la figura
es la probabilidad de
babilidad deesrecorrerlo,
que si hoy como pasado
un dı́a bueno, en la figura 3.3 (con
mañana letraslomás
también sea?pequeñas y hacia la!
Figura
izquierda 3: Árbol
del arco), de posibilidades,
de modo que la suma decon
lasprobabilidades
probabilidades en de los arcos
arcos.en cada
nivel debe dar 1.
Para calcular las probabilidades de llegar a un nodo en determinado nivel,
Para calcular las probabilidades de llegar a un nodo en determinado nivel,
sumamos las probabilidades de los arcos que llegan al nodo, que en la figura 3.3
sumamos las probabilidades
están puestas de losalgo
con letras en negrita arcos que llegan
mayores al nodo,
y hacia que en
la derecha dela Figura
cada nodo.3
están puestas con letras en negrita algo mayores y hacia la derecha
También la suma de las probabilidades sobre los nodos en cada nivel debe dar 1. de cada
nodo. También la suma de las probabilidades sobre los nodos en cada nivel debe
dar Así,
1. para obtener la probabilidad de que empezando en 3 lleguemos a 4 en tres
Ası́,miramos
pasos, para obtener la probabilidad
a las probabilidades de arcos
de los que empezando
que llegan alen 3 lleguemos
nodo 4 (ubicadoaen4
en tres pasos,
el tercer miramos
nivel) que a las
son 1/8 probabilidades
y 1/4, las sumamosde los arcos que
y obtenemos 3/8.llegan al nodo 4
(ubicado en el tercer nivel) que son 1/8 y 1/4, las sumamos y obtenemos 3/8.
3.2 Problema:
3.2. Problema. En Enelelejemplo
Ejemplo
2.12.1
deldel clima
clima en en
Oz,Oz, ¿cuál
¿cuál es laesprobabilidad
la probabilidad de
de que
que si hoy es un dı́a bueno, pasado mañana también
si hoy es un día bueno, pasado mañana también lo sea? lo sea? !
$
Cadenas de Markov 7
4. Usando matrices
Podemos repensar la idea de que estando en un estado i lleguemos en dos pasos
al estado j: obviamente en el primer paso estaremos en algún estado intermedio
k (que puede ser i o j) y después pasar de k a j. En cada camino multiplicamos
(2)
las probabilidades, y después sumamos los caminos. Si indicamos con pi j a esta
probabilidad, tendremos
(2)
X
pi j = pik pk j .
k
De esta forma fabricamos una nueva matriz, P (2) , que reconocemos como el
producto matricial de P consigo misma,
P (2) = P × P.
4.1. Problema. Ver que P (2) es una matriz de probabilidad. $

(r)
Si definimos análogamente las probabilidades de transición pi j para ir del
estado i al estado j en exactamente r pasos, y formamos la matriz correspondiente,
P (r) , tenemos que
P (r) = P r = |P × P{z
× . . . P} ,
r veces
ya que, por ejemplo por inducción, para hacer r pasos tendremos que hacer r − 1
pasos primero y luego otro más, i.e., P (r) = P (r−1) × P, y si suponemos que P (r−1) =
P r−1 , llegamos a la ecuación anterior.
Nos va a resultar conveniente poner P (0) = P 0 = I —la matriz identidad— y
P = P, con las correspondientes definiciones para p(0) y p(1) . Así, tendremos (por
(1)
definición), ¨
(0) 1 si i = j,
pi j = δi j =
0 si i 6= j.
4.2. Problema. Ver que P r es una matriz de probabilidad para r ∈ N. $
5. Clasificación de estados y cadenas

Los digrafos también nos ayudan a pensar en que sólo nos interesan cadenas
de Markov en las que, olvidándose del sentido de los arcos y considerándolos
como caminos de ida y vuelta, el grafo resultante sea conexo: todos los puntos
se pueden conectar con caminos (no dirigidos). De otro modo consideraríamos
cada «componente conexa» por separado, como ilustramos en la figura 5.1, donde
trataríamos por separado a los nodos 1, 2, 3 y 4, 5.
Así que de ahora en más, sólo consideraremos cadenas «conexas».
Volviendo a considerar las flechas con dirección, vemos que algunos estados son
absorbentes, es decir, una vez que llego a ellos nunca puedo salir, como las esquinas
0 y 6 en el paseo por la peatonal.
Otras veces no hay estados absorbentes, y puedo «pasear» por cada estado tantas
veces como quiera, como en el ejemplo del clima en Oz. Decimos en este caso que
la cadena es ergódica.
En fin, lo más común es que haya una mezcla, en las que algunos estados forman
un conjunto ergódico, de modo que si llego a él no puedo salir —no hay flechas que
1
4 5
Pág.
8 8 3 2 Cadenas
5. Clasificación deyMarkov
de estados cadenas
Figura 4: Un digrafo “no conexo”. Los nodos 1, 2 y 3 forman una componente

1 otra.
conexa, y los nodos 3 y 4 forman
4 5
En fin, lo más común es que haya una mezcla, en las que algunos estados
forman un conjunto ergódico,
3 de modo2 que si llego a él no puedo salir —no hay
flechas que salgan— pero puedo seguir recorriendo indefinidamente todos los
estados
Figura 4:deUn
Figura 5.1: este conjunto
Undigrafo
digrafo“no
(2)
«no , como elLos
conexo”.
conexo». conjunto
Los nodos formado
nodos 1, por los una
1, 22 yy 3 forman estados 1 y 2 en
componente
la Figura
conexa, 5.
yy los
losnodos
nodos43yy54forman
formanotra.
otra.
1 2
En fin, lo más común es que haya una mezcla, en las que algunos estados
forman un conjunto ergódico, de modo que si llego a él no puedo salir —no hay
flechas que salgan— pero puedo seguir recorriendo indefinidamente todos los
estados de este conjunto(2) , como4 el conjunto3 formado por los estados 1 y 2 en
la Figura 5.
Figura 5.2:
Figura Losestados
5: Los estados11yy 22 forman
forman un
un conjunto
conjunto ergódico,
ergódico, 33 yy 44 son
son estados
estados
transientes.
transientes. 1 2
salgan— pero puedo

Los estados que noseguir
estánrecorriendo
en ningún indefinidamente
conjunto ergódicotodos los estados
se llaman de este
transientes,
(3)
conjunto,
como como 3elyconjunto
los estados formado5.por los estados 1 y 2 en la figura 5.2.
4 en la Figura
4 3
Ası́ como
Los estadoses conveniente
que no estánconsiderar
en ningúnsólo componentes
conjunto ergódicoconexas, es conveniente
se llaman transientes,
considerar en una3 primera
como los estados y 4 en la etapa
figura sólo
5.2. algunas cadenas particulares:
Figura 5: Loses estados
Así como 1 y 2considerar
conveniente forman un sóloconjunto ergódico,
componentes 3 y es
conexas, 4 conveniente
son estados
Cadenas en una primera donde
considerar absorbentes:
transientes. hayalgunas
etapa sólo solo estados transientes
cadenas y absorbentes (los
particulares:
conjuntos ergódicos tienen un único estado).
Cadenas
Cadenas
Los estados(ergódicas)
absorbentes: regulares:
donde
que no están enhay solo
ningúnenestados
las quetransientes
conjunto elergódico
total forma un conjunto
yseabsorbentes
llaman (losergó-
con-
transientes,
como dicojuntos ergódicos
los estados tienen
y existe3 ky ∈4 Nental un único
la Figura (k) estado).
que pij 5.> 0 para cualquier par de estados i, j . (3)
Ası́ como es conveniente considerar sólo componentes conexas, es conveniente

Ası́, el(ergódicas)
considerar
Cadenas Ejemplo 2.2regulares:
en una primera de laetapa
peatonal
sólo
en esalgunas
las unaelcadena
que absorbente,
cadenas
total formaparticulares: pues los
un conjunto estadosy
ergódico
(k)
0 y 6 son absorbentes
existe y losprestantes
k ∈ N tal que ij > 0 son
para transientes.
cualquier par Por
de otro
estados lado,
i, j.el
(4)Ejemplo 2.1
Cadenas
del clima en absorbentes:
Oz es una cadena donderegular,
hay solo estados
pues transientes
tomando y absorbentes (los
k = 2 tenemos
conjuntos ergódicos tienenun único estado). 
Así, el ejemplo 2.2 de la peatonal 1/4es una cadena
3/8 3/8absorbente, pues los estados 0
yCadenas (ergódicas) regulares:
6 son absorbentes y los restantes
P = 3/16
2 son en las que el3/8
transientes.
7/16 total
Porotroforma
lado,un conjunto2.1
el ejemplo ergó-
del
clima dico
en Ozy es una cadena regular, (k) tomando k = 2 tenemos
pues
existe k ∈ N tal que p3/16 ij > 03/8 para 7/16
cualquier par de estados i, j . (3)
queAsı́,
tiene el sólo entradas
Ejemplo 2.2 depositivas.
la peatonal1/4 es una 3/8 cadena
3/8 absorbente, pues los estados
 
0 (2)
y 6 son absorbentes y losPrestantes2
= 3/16 son 7/16
transientes.
3/8 Por
, otro lado, el Ejemplo 2.1
 
Ası́, un estado absorbente forma un conjunto ergódico.
del
(3) clima en Oz es(k) una cadena regular,
3/16 pues 3/8 tomando
7/16 k = 2 tenemos
La condición pij > 0 para todo i, j implica que el conjunto de estados es ergódico.
 
que tiene sólo entradas positivas. 1/4 3/8 3/8
P 2 = 3/16 7/16 3/8 
3/16 3/8 7/16
5.1. Problema. Clasificar las cadenas (absorbente, regular, o ninguna de las dos)
de los
que problemas
tiene 2.3 y 2.5.
sólo entradas positivas. $
(2)
(3) Ası́,ununestado
estado absorbente forma un conjunto ergódico.
Así, absorbente forma un conjunto ergódico.
(3)
(4) (k)(k)
Lacondición
La condiciónpi jpij> 0>para
0 para
todotodo i, j implica
i, j implica que el que el conjunto
conjunto de es
de estados estados es ergódico.
ergódico.
Cadenas de Markov 9
6. Un caso particular
Antes de pasar a estudiar los resultados teóricos sobre cadenas absorbentes, será
conveniente estudiar un caso particular, similar al problema 1.2, que nos ayudará a
entender los argumentos teóricos.
6.1. Problema. Si en un experimento la probabilidad de obtener un resultado
favorable es p, 0 < p < 1, ¿cuántos experimentos sucesivos habrá que hacer (en
promedio) hasta obtener un resultado favorable?(5) $
Para ejemplificar, si estamos tirando dados y el resultado favorable es que salga 1,
tendremos p = 1/6; en cambio, si estamos tirando monedas y el resultado favorable
es que salga cara, tendremos p = 1/2.
Como la solución al problema no es intuitiva (al menos para mí), es interesante
hacer un programa para simular en la computadora. Por ejemplo, usando el progra-
ma C.1 (pág. 33), tomando p = 0.16666 (el caso de los dados), m = 1 y haciendo
n = 1000 experimentos, hemos obtenido que el número de veces en promedio
es 5.917 (los resultados varían cada vez que se corre el programa), lo cual hace
sospechar que el resultado teórico debe ser 6 en este caso.
Para resolver el problema, usaremos dos técnicas que nos servirán para entender
los resultados teóricos de las secciones siguientes.
Variante I : Llamando q = 1 − p a la probabilidad de obtener un resultado desfavo-
rable y como suponemos que los experimentos son independientes, la probabilidad
de no haber obtenido un resultado favorable en n experimentos es
qn = q n ,
por lo que la probabilidad de que salga exactamente en el paso n es el producto de

las probabilidades de que no haya salido hasta n − 1 y salga en el paso n,
pn = p qn−1 = p q n−1 ,
y la esperanza es entonces
∞
X ∞
X
E= n pn = p n q n−1 .
n=1 n=1
Para calcular la última suma podemos usar el siguiente truco: consideramos

(para |x| < 1)
∞
X
f (x) = x n = 1/(1 − x),
n=0
que tiene como derivada a

∞
X
f 0 (x) = n x n−1 = 1/(1 − x)2 ,
n=1
y por lo tanto
1 1
E = p f 0 (q) = p = . ,
p2 p
Podemos poner entonces:

(5)
Suponemos que los experimentos son independientes.
10 7. Cadenas absorbentes: resultados teóricos
6.2. Resultado. Si en cada paso hay una probabilidad constante p de obtener un

resultado favorable, el número esperado de pasos hasta obtener el primer caso favorable
es 1/p.(6)
Por ejemplo, en promedio esperamos tirar 6 veces un dado hasta que aparezca el
primer 1, y si tiramos monedas, esperamos tirar (en promedio) dos monedas hasta
que aparezca la primer cara.
Veamos otra forma de resolver el problema:
Variante II : Si E la cantidad de pasos que espero hacer hasta llegar a un caso
favorable, tengo probabilidad p de hacerlo en un solo paso, pero si fallo en ese
primer paso, habré «gastado» un paso y estaré como al principio, por lo que tardaré
1 + E pasos.
Entonces
E = p + (1 − p)(1 + E) = 1 + (1 − p) E,
y despejando E, queda E = 1/p como ya sabíamos. ,
Más adelante veremos otras variantes (problema 8.1) y cómo usar los resultados
de cadenas de Markov para su resolución.
7. Cadenas absorbentes: resultados teóricos

Recordando que en una cadena hay sólo dos tipos de estados (absorbentes y
transientes), nos resultará conveniente llamar al conjunto de estados absorbentes
A y al conjunto de estados transientes T .
En una cadena absorbente y empezando en cualquier estado, sea transiente o
absorbente, tenemos una probabilidad positiva de llegar en algún momento a un
estado absorbente, ya que en otro caso se formaría un conjunto ergódico (que no
es el total) con más de un punto porque hay un número finito de estados. Desde
el punto de vista del digrafo asociado, esto se refleja en que desde todo estado
transiente existe un camino (dirigido) hacia algún estado absorbente.
En otras palabras, para cada estado u existe un estado v ∈ A y un número de
pasos r tales que la probabilidad de ir desde u hasta v en r pasos es positiva, o sea,
(r)
puv > 0.
Como una vez que llegamos a un estado absorbente nos tenemos que quedar
allí, podemos tomar un mismo r (el máximo de los anteriores) que sirva para todos
los estados. Del mismo modo, tomando ahora el mínimo de las probabilidades,
vemos que podemos encontrar α > 0 tal que para todo estado u existe un estado
(r)
absorbente v ∈ T tal que puv ≥ α.
Como estamos en un proceso de Markov, la probabilidad de que empezando
desde cualquier estado no lleguemos a un estado absorbente en a lo más r pasos es
menor o igual que 1 − α. Repitiendo el razonamiento, vemos que la probabilidad de
no llegar en kr pasos (k ∈ N) a un estado absorbente es menor o igual que (1 − α)k ,
pero como 1 − α < 1, esta probabilidad tiende a 0.
Podemos resumir este argumento en el siguiente:
7.1. Teorema. En toda cadena de Markov absorbente, la probabilidad de absorción

(que empezando en cualquier lugar se llegue a un estado absorbente) es 1.
(6)
Comparar con el análisis en el problema 9.5.
Cadenas de Markov 11
Eventualmente renumerando los estados, podemos escribir la matriz de transi-

ción asociada en forma canónica:
absorbentes transientes
z }| { z }| {
absorbentes {

I 0
(7.2)
transientes { R Q
En este caso, si hay n estados, de los cuales m son absorbentes y n − m transientes,

la submatriz I es la matriz identidad en Rm×m , la submatriz 0 ∈ Rm×(n−m) tiene
todos los coeficientes 0, y las submatrices R y Q están en R(n−m)×m y R(n−m)×(n−m)
respectivamente.
Puesto que comenzando desde un estado absorbente, la probabilidad de no
llegar a un estado absorbente se acerca a 0 a medida que aumenta el número de
pasos (por el teorema 7.1), y como las entradas de Q k son las probabilidades de
que empezando en un estado transiente después de k pasos lleguemos a otro estado
transiente, tenemos:
7.3. Teorema. En una cadena de Markov absorbente cuya matriz canónica tiene la
forma de la ecuación (7.2),
a) Q r → 0 (la matriz con todos 0’s) cuando r → ∞,
b) si I es la matriz identidad en R(n−m)×(n−m) , entonces I − Q es inversible y
∞
X
(I − Q)−1 = Qr .
r=0
La última parte del teorema anterior sigue las ideas de la demostración de que
∞
1 X
= x k,
1− x k=0
cuando x es un número real con |x| < 1, y no la hacemos, pero observamos desde
ya la relación con la variante I de la pág. 9.
Claro que si tenemos un estado transiente u ∈ T , en la forma canónica de la
matriz P tiene asociado un índice (digamos i), pero en la matriz Q tiene asociado
otro índice (i − m). En lo que sigue, para no complicar las notaciones supondremos
implícitamente que no tenemos esta ambigüedad y hacemos un corrimiento de
índices cuando apropiado.
Poniendo
N = (I − Q)−1 , (7.4)
a veces llamada matriz fundamental de la cadena absorbente, tenemos el siguiente:
7.5. Teorema. En una cadena absorbente, si se empieza en el estado transiente ui ∈ T ,

el número esperado de veces en que la cadena está en el estado transiente u j ∈ T es la
entrada i j de la matriz fundamental N .
Demostración: Pongamos
¨
1 si la cadena está en el estado u j en el paso s,
δ( j, s) =
0 en otro caso,
de interpretación. Tomemos por ejemplo la cadena absorbente de la Figura 6
donde hay dos estados. El estado 1 es absorbente, mientras que el estado 2 es
transiente pero la probabilidad de pasar al estado 1 en un paso es 1. La matriz
Q en este caso se reduce a Q = [0], de modo que N = (I − Q)−1 = [1]. Es
decir, seguro que empezando desde 2 en un paso llegamos al estado 1, ası́ que
esperamos llegar a 1 en un paso y permanecer 0 pasos en el estado 2. Esta
aparente contradicción resulta de haber considerado el término s = 0 en la
(0)
12 demostración del teorema, y como 7. = 1, elabsorbentes:
piiCadenas paso 0 siempre se cuenta
resultados en el
teóricos
teorema.
1
1 1 2
Figura7.1:
Figura 6: Una
Unacadena
cadena absorbente simple.
absorbente simple.
y para cualquier
Tomando sea Ei (x) el debidas,
las xprecauciones valor esperado deentonces
tenemos x si el proceso empieza
el siguiente en el
corolario
estado u .
que usaremos
i Entonces si e es
con frecuencia
ij la esperanza buscada,
en las aplicaciones:
7.6 Corolario.X∞ El número X ∞esperado de pasos ∞ hasta la absorción (sin ∞ contar el
(s) (s) (s)
X X
j = dado
pasoei 0), Ei δ( el
que = comienza
j, s)proceso Ei (δ( j, s))en
= el estado
(1 − pno-absorbente
ij ) 0 + p ij 1 =
u i es lai j suma
p ,
de las entradass=0 de la fila i-ésima
s=0 de N . s=0 s=0
dondeVeamos
la sumaunempieza desde s = antes
último resultado 0 puesdenopasar la posibilidad i = j.
a las aplicaciones.
eliminamos
(s)
Recordando que pi j es la entrada i j-ésima de Qs (después de un corrimiento
7.7 Teorema. Consideremos una cadena absorbente,Pcon ∞
matriz canónica en
de índices),
la forma de vemos que ei(7.2).
la ecuación j es laSea
entrada j-ésima de de
bij la i probabilidad Qs , empezando
s=0que que es N por
en el
el
teorema 7.3.
estado transiente ui se termine en el estado absorbente uj , y formemos la matriz ,
B ∈EnRel teoremacon
(n−m)×m
estos coeficientes.
no excluimos la condición i = j, lo cual trae algunos problemas de
Entonces Tomemos por ejemplo la cadena absorbente de la figura 7.1 donde
interpretación.
hay dos estados. El estado 1 es absorbente,B = N R, mientras que el estado 2 es transiente
dondela R
pero es como endelapasar
probabilidad ecuación (7.2)1 yenNunespaso
al estado la matriz
es 1. Lafundamental
matriz Q ende la
este
ecuación (7.4).
caso se reduce a Q = [0], de modo que N = (I − Q)−1
= [1]. Es decir, seguro que
empezando desde 2 en un paso llegamos al estado 1, así que esperamos llegar a 1
en un paso y permanecer 0 pasos en el estado 2. Esta aparente contradicción resulta
de haber considerado el término s = 0 en la demostración del teorema, y como
(0)
pii = 1, el paso 0 siempre se cuenta en el teorema.
Tomando las precauciones debidas, tenemos entonces el siguiente corolario que
usaremos con frecuencia en las aplicaciones:
7.6. Corolario. El número esperado de pasos hasta la absorción (sin contar el paso 0),
dado que el proceso comienza en el estado no-absorbente ui es la suma de las entradas
de la fila i-ésima de N .
Veamos un último resultado antes de pasar a las aplicaciones.
7.7. Teorema. Consideremos una cadena absorbente, con matriz canónica en la forma
de la ecuación (7.2). Sea bi j la probabilidad de que empezando en el estado transiente
ui se termine en el estado absorbente u j , y formemos la matriz B ∈ R(n−m)×m con estos
coeficientes.
Entonces
B = N R,
donde R es como en la ecuación (7.2) y N es la matriz fundamental de la ecuación (7.4).
Demostración: Buscamos una relación de recurrencia para los coeficientes bi j . Si
empezamos en el estado ui , en el próximo paso podemos ir al estado absorbente
u j con probabilidad pi j , o a otro estado absorbente uk , k 6= j, con probabilidad
pik , o ir a otro estado transiente u` con probabilidad pi` . La probabilidad de que
estando en estos estados, u j , uk o u` , terminemos en el estado absorbente u j es,
respectivamente, 1, 0 y b` j , de modo que
X
bi j = pi j + pi` b` j .
` : u` ∈T
Como ui es transiente y u j absorbente, pi j es la entrada correspondiente de la

matriz R (con algún eventual desplazamiento de índices). De modo similar, pi` es
la entrada i` de la matriz Q, y b` j es la entrada de la matriz B. Podemos escribir
entonces la ecuación anterior en forma matricial como
B = R + QB o (I − Q) B = R,
de donde sigue el resultado pues I − Q es inversible con inversa N . ,

Vale la pena observar que la técnica usada en la demostración es esencialmente
la usada en la variante II de la pág. 10.
7.8. Problema. Juntando los teoremas 7.1 y 7.7, para todo estado transiente ui
debe ser X
bi j = 1.
j∈A
Sin usar estos resultados, verificar directamente a partir de las definiciones que las
sumas de las filas de N R es siempre 1.(7) $
8. Problemas de dados y monedas

Pasemos ahora a estudiar problemas sobre los que seguramente habremos oído, y
que pueden mirarse como cadenas de Markov absorbentes. Muchas veces se simulan
en la computadora y son de la forma «repetir hasta que. . . »:
8.1. Problema (m consecutivos). ¿cuántas veces habrá que tirar un dado (en
promedio) hasta que salga un 1?, ¿hasta que salgan m 1’s consecutivos? $
8.2. Problema (Hasta que la suma supere). dado un número m ∈ N, ¿cuántas
veces habrá que tirar un dado (en promedio) hasta que la suma de los resultados
que se obtienen sea mayor o igual a m? $
8.3. Problema. Una variante del anterior es sacar números aleatorios entre 0 y 1
(uniformemente distribuidos) hasta que la suma sea 1 o más: ¿cuántos números (en
promedio) habrá que sacar? $
En vez de considerar consecutivos, podemos pensar en repetir el experimento
hasta el segundo caso favorable:
8.4. Problema (Problema del cumpleaños). Supongamos que todos los años tie-
nen 365 días, y que es igualmente probable nacer en cualquier día del año.
Si van entrando personas a una sala, ¿cuántas (en promedio) entrarán hasta que
haya dos con el mismo día de cumpleaños? $
8.5. Problema. Otro caso interesante es el de movimiento browniano o paseo al
azar en una dimensión,(8) como el paseo en la peatonal que hemos puesto en el
ejemplo 2.2: ¿cuántos pasos daremos (en promedio) hasta terminar? $
En fin, podemos agregar el ya mencionado problema 1.1, y un problema apa-
recido recientemente en la Revista de Educación Matemática [REM02], entre los
Problemas para resolver:
(7)
Una posibilidad se da en el apéndice A.1
(8)
En estas notas miramos a una dimensión, pero el estudio se hace para cualquier número de
dimensiones.
14 8. Dados y monedas
8.6. Problema.
a) Dos jugadores, A y B, juegan el siguiente juego: tiran una moneda hasta que
salgan dos caras seguidas, en cuyo caso A gana, o bien hasta que salga una
cara seguida de una cruz, en cuyo caso gana B. Probar que ambos tienen
iguales oportunidades de ganar.
b) Ahora deciden jugar el mismo juego, pero de la siguiente forma: A tira una
moneda hasta que salgan dos caras seguidas, y anota cuántas tiradas necesitó.
Luego, B tira una moneda hasta que salga una cara seguida de una cruz, y
anota cuántas tiradas necesitó. Comparan los dos números, y el que tiene el
número más bajo gana. Probar que en esta versión, B tiene ventaja sobre A.
c) Explicar la aparente contradicción entre la parte a) y la b).
Un nuevo jugador, C, entra en el juego. Él ganará si sale una cruz seguida de

una cara.
d) Observar que si juegan la versión del juego en b), el jugador C tiene las
mismas posibilidades que B, y por lo tanto tiene ventaja sobre A.
e) Suponer en cambio que juegan la versión a). Si C y B juegan solos, probar
que ambos tienen las mismas oportunidades de ganar. En cambio si C y A
juegan solos, probar que C tiene muchas más oportunidades de ganar que A.
f ) Explicar la aparente contradicción entre los puntos e) y a).
g) Si A, B y C juegan los tres juntos la versión de a), probar que A y B cada uno
ganará un juego de cada 4 y C uno de cada 2. $
La mayoría de estos problemas son suficientemente sencillos como para resolver-

los sin apelar a la teoría de cadenas de Markov, como ya hemos visto en la sección 6,
pero por el momento nos interesa pensar estos procesos como cadenas de Markov.
Repasando lo que vimos en las secciones anteriores, miremos a las matrices
de transición para estos problemas. Para ello suponemos que cuando tiramos un
dado una tirada resulta favorable si sale 6 (o lo que sea) con probabilidad p, y es
desfavorable con probabilidad q = 1 − p.
En el problema 8.1 de obtener m consecutivos, consideramos un contador que
inicialmente está en 0 y se incrementa en 1 cuando hay un resultado favorable y
vuelve a 0 cuando el resultado es desfavorable. Los estados son los valores posibles
del contador, 0, 1, . . . , m, y las probabilidades de transición son:
pk,k+1 = p si 0 ≤ k < m,
pk,0 = q para k = 0, 1, . . . , m − 1,
pm,m = 1,
pi, j = 0 en cualquier otro caso.
En el problema 8.2 donde continuamos hasta que la suma supere un valor prefi-
jado m, consideramos la suma s que inicialmente está en 0 y se va incrementando
a medida que se tiran los dados. Los estados son los valores que puede tomar s,
0, 1, . . . , m, donde en el estado m ponemos la condición s ≥ m.
Las probabilidades de transición son (en el caso de los dados):
pk,k+i = p para i = 1, 2, . . . , 6, k = 0, 1, . . . , si k + i < m,

pk,m = (k − m + 7)p para k = m − 6, m − 5, . . . , m − 1,
pm,m = 1,
pi, j = 0 en cualquier otro caso.
Finalmente, en el problema 8.3 donde los números obtenidos en cada paso

están entre 0 y 1, consideramos una división en n del intervalo (0, 1], suponemos
que los «dados» a salir son 1/n, 2/n, . . . , 1 con probabilidad p = 1/n cada uno,
y numeramos los estados 0, 1, . . . , n − 1, n, correspondientes a que la suma sea
0, 1/n, 2/n, . . . , 1 − 1/n o mayor o igual a 1. O sea, es una variante del caso anterior,
con m = n, y donde

 p = 1/n para 0 ≤ k < j ≤ n,
pk, j = 1 para k = j = n,

0 en otro caso.
En el apéndice C bosquejamos algunos programas en Pascal para los proble-

mas 8.1 (en C.1), 8.2 (en C.2), 8.3 (en C.3), 8.4 (en C.4) y 8.5 (en C.5). Aunque el
lector no sepa programar, recomendamos echar ahora una mirada para la estrecha
relación entre los «algoritmos» y los planteos que acabamos de hacer.
8.1. El problema de repetir hasta obtener m consecutivos

8.1.1. Análisis directo
En el problema 8.1, en cada paso tenemos una probabilidad constante p de tener
un resultado favorable (por ejemplo, cara o un 6), una probabilidad q = 1 − p de
obtener un resultado negativo, y queremos obtener m casos favorables consecutivos.
Ya hemos visto (resultado 6.2) el caso m = 1, obteniendo que, por ejemplo en el
caso de los dados, en promedio esperamos tirar 6 veces un dado hasta que aparezca
el primer 1.
Pasando al caso m = 2, podemos tratar de repetir el razonamiento de la varian-
te II (pág. 10). Llamando a a un resultado favorable y b a uno negativo, en el primer
paso no puedo terminar, pero obtengo a con probabilidad p o b con probabilidad
q = 1 − p. Suponiendo que saque a y luego otra vez a, habré llegado en dos pasos,
pero si en la segunda tirada saco b tengo que empezar de nuevo, habiendo «gastado»
dos pasos. Si la primera vez saco b, entonces hay que empezar de nuevo, habiendo
«gastado» un paso. En total tenemos
E = p2 2 + pq (2 + E) + q (1 + E).
Despejando E, obtenemos
1 1
E= + . (8.7)
p p2
No es difícil intuir cuál será el caso general: tendremos una probabilidad p m

de obtener resultados favorables en las primeras m tiradas, o podría suceder que
16 8.1. Repetir hasta obtener m consecutivos
obtuve resultados favorables en las primeras m − 1 pero desfavorable en la siguiente

de modo que tengo que volver a empezar y espero tardar ahora m + E, o podría ser
que las m − 2 primeras fueron favorables y falló la tirada m − 1 y entonces tengo
que volver a empezar esperando tardar m − 1 + E, o. . .
Podemos poner entonces
E = p m m + p m−1 q (m + E) + p m−2 q (m − 1 + E) + · · · + q (1 + E) =
m−1
X m−1
X
= m pm + q (i + 1) p i + qE pi .
i=0 i=0
Para continuar debemos evaluar las sumas «internas». Es sencillo calcular la

segunda,
m−1
X 1 − pm 1 − pm
pi = = .
i=0
1−p q
Para la primera podemos usar el truco de la función f y su derivada que vimos
en la Variante I (pág. 9), obteniendo
m−1
X mp m+1 − (m + 1)p m + 1
(i + 1) p i = ,
i=0
q2
de modo que llegamos a
mp m+1 − (m + 1) p m + 1
E = m pm + + (1 − p m ) E.
q
Despejando E llegamos al resultado general:
8.8. Resultado. Si en cada paso hay una probabilidad constante p de obtener un
resultado favorable, el número esperado de pasos hasta obtener m resultados favorables
consecutivos es
1 1 1 (1/p)m − 1
E = + 2 + ··· + m = .
p p p q
8.1.2. Con cadenas de Markov

Tratemos ahora de mirar el problema desde el punto de vista de cadenas de
Markov, y usar los resultados que obtuvimos. Recordando que tomamos como
estados a 0, 1, . . . , m, en el problema 8.1 la matriz Q es
 0 1 2 ... m−2 m−1


0 q p 0 ... 0 0
q 0 p ... 0 0 
 
1 
..  .. ,
.  .
 

q 0 0 ... 0 p 
 
m−2 
m−1 q 0 0 ... 0 0
y la matriz I − Q es  
p −p 0 ... 0 0
−q 1 −p ... 0 0 
 
 . 
 . .
 . 
−q 0 0 ... 1 −p
 
−q 0 0 ... 0 1
Podemos encontrar la primer fila de la matriz N correspondiente —que es lo

que necesitamos según el corolario 7.6— resolviendo el sistema
(a0 , a1 , . . . , am−2 , am−1 ) · (I − Q) = (1, 0, . . . , 0),
que tiene por solución

1
ai = para i = 0, 1, . . . , m − 1. (8.9)
p m−i
8.10. Problema. Verificar que efectivamente se obtiene la solución.(9) $

No es difícil ver ahora que volvemos a obtener el resultado 8.8:
1 1 1
E = a0 + a1 + · · · + am−2 + am−1 = + + ··· + .
p p2 pm
8.2. El problema de repetir hasta superar una suma prefijada

En el problema 8.2, por ejemplo para los dados, la matriz Q es
seis p
 z }| { 
0 0 p p ... p 0 ... 0
1 0 0 p ... p p ... 0
 
.. 
 ..

. .


m−2 0 ... 0 p
 
m−1 0 ... 0 0
donde las filas tienen seis p consecutivos (excepto en las últimas) que se van
corriendo hacia la derecha a medida que descendemos.
La matriz I − Q es
 
1 −p −p . . . −p 0 . . . 0
0 1 −p . . . −p −p . . . 0 
 
. 
. ,
. 
0 ... 1 −p
 
0 ... 0 1
pero la matriz N o su primer fila, no tiene una forma explícita sencilla en general.(10)
Un caso particular sencillo es m = 7. En este caso toda la parte triangular
superior de Q tiene p’s, la primer fila de N = (I − Q)−1 es
(1, p, p (1 + p), p (1 + p)2 , . . . , p (1 + p)5 ),
y la esperanza es
1 + p (1 + p) + (1 + p)2 + · · · + (1 + p)5 =

(1 + p)6 − 1
=1+p = (1 + p)6 = (1 + 1/6)6 .
p
(9)
Una solución posible está en el apéndice A.2
(10)
Pero resolver el sistema numéricamente es sencillo por ser I − Q triangular.
18 8.3. Sumar números entre 0 y 1 hasta llegar a 1
Es decir, en promedio habrá que hacer aproximadamente 2.52163 tiradas hasta

sumar 6 o más.
Si en vez de un dado con 6 valores tomamos un «dado» con n caras, y luego
hacemos crecer n, llegamos al problema 8.3 que pasamos a considerar.
8.3. Sumar números entre 0 y 1 hasta llegar a 1

Recordando lo ya dicho sobre el problema 8.3 (pág. 15), hacemos una discretiza-
ción dividiendo el intervalo (0, 1] en n partes iguales y ponemos p = 1/n. Entonces
la matriz Q tiene la forma
 
0 0 p p ... p p
1 0 0 p . . . p p
 
..  ..
 
,
. . 
n−2 0 ... 0 p
 
n−1 0 ... 0
la matriz I − Q tiene la forma

 
1 −p −p ... −p −p
0 1 −p ... −p −p
 
. 
. ,
. 
0 ... 1 −p
 
0 ... 1
y la matriz N tiene la forma

 
1 p p (1 + p) p (1 + p)2 ... p (1 + p)n−2
0 1 p p (1 + p) ... p (1 + p)n−3 
 
. 
. . (8.11)
. 
0 ... 0 1 p
 

0 ... 0 1
8.12. Problema. Verificar que efectivamente N (I − Q) = I.(11) $

Entonces, la esperanza buscada es la suma de la primer fila de N (corolario 7.6):
n−2
(1 + p)n−1 − 1 1 n−1
X
1+p (1 + p)i = 1 + p = (1 + p)n−1 = 1 + .
i=0
(1 + p) − 1 n
El lector recordará que estamos frente a uno de los «límites notables»: cuando
n → ∞, i.e., en el caso continuo, la esperanza es e ≈ 2.718.
8.13. Resultado. Si vamos sacando aleatoriamente (y uniformemente) números entre

0 y 1 hasta que su suma supere 1, en promedio habrá que sacar e números.
8.14. Problema. Con una tabla de números aleatorios, o con una computadora,
hacer experimentos numéricos para ver esta forma de aproximar e.(12) $
(11)
Algunas soluciones posibles se muestran en el apéndice A.3
(12)
Ver el programa C.3.
8.4. El problema del cumpleaños

8.4.1. Análisis Directo
Recordemos que en este problema estamos suponiendo que todos los años tienen
365 días, y que es igualmente probable nacer en cualquier día del año. Podemos
pensar que tenemos un dado con 365 caras, y es razonable pensar que el problema
admite un análisis directo como los que hicimos en las secciones anteriores, sin
apelar a la potencia de la teoría de cadenas de Markov.
Nuestra primera preocupación para estudiar el problema es calcular la probabili-
dad de que haya n personas, todas con distinto día de cumpleaños.
Considerando casos favorables sobre casos posibles, si hay n − 1 personas, todas
con distinto día de cumpleaños, y entra la persona n-ésima, la probabilidad de que
ésta no tenga el mismo día de cumpleaños que alguna de las ya presentes es
365 − (n − 1)
.
365
Por lo tanto, la probabilidad de que entre n personas no haya dos con el mismo
cumpleaños es
364 363 365 − (n − 2) 365 − (n − 1)

qn = ··· =
365 365 365 365
364 365
1 Y 1 Y
= k= k=
365n−1 k=366−n
365n k=366−n
366
1 Y
= k.
365n+1 k=366−n
Observar que por el principio del palomar, qn = 0 para n = 366, lo que se refleja
en la última forma (pero no mucho en otras).
Del mismo modo, la probabilidad de que recién al entrar la n-ésima haya dos
con el mismo cumpleaños es
n−1
pn = qn−1 ,
365
con p367 = 0 pero p366 > 0, siendo p1 = 0.
Por lo tanto la esperanza es
366 366 365

X X 1 Y
E= n pn = n(n − 1) k =
n=1 n=2
365n k=367−n
365
X i(i + 1) · · · 365
= (367 − i)(366 − i) =
i=1 365367−i
(8.15)
365
365! X 365i−1
= (367 − i)(366 − i) =
365366 i=1
(i − 1)!
364
365! X 365i
= (367 − i)(366 − i).
365366 i=0
i!
20 8.4. El problema del cumpleaños
Haciendo los cálculos —tal vez con un buen software— se puede ver que
E ≈ 24.6166,
es decir, en promedio debemos esperar que entren un poco menos de 25 personas

hasta tener dos con el mismo cumpleaños. Dado el tamaño de las clases en nuestras
escuelas, es fácil realizar la siguiente actividad:
8.16. Problema. Considerando la mayor cantidad de grados posibles en la escuela,

hacer una estadística sobre la cantidad de alumnos por aula y si en cada una de
ellas hay dos o más alumnos con el mismo día de cumpleaños. $
Volviendo a la esperanza, también tenemos el milagro de que
366 365
X X i (i + 1) · · · 365
pn = (366 − i) = 1,
n=1 i=1 365367−i
y en general, para todo n ∈ N,

n−1
n! X ni
n+1
(n − i) = 1. (8.17)
n i=0
i!
En el apéndice B tratamos éstas y otras fórmulas relacionadas.
8.4.2. Como cadena de Markov
Pasando a cadenas de Markov, la primer pregunta es qué estados considerar. Co-

mo las probabilidades de transición dependen de la cantidad de días de cumpleaños
ya aparecidos, después de pensar un poco vemos que podríamos considerar 366
estados transientes, representando la cantidad de días de cumpleaños ya aparecidos
(de 0 a 365) y un estado absorbente que por comodidad llamamos final, al que
llegamos cuando hay dos personas con el mismo cumpleaños.
Usando la notación p∗ —para no confundir con las del análisis hecho en la
sección anterior— en este caso las probabilidades de transición son:
∗
365 − i
pi,i+1 = , para i = 0, 1, . . . , 364,
365
∗ ∗
i
pi,final = 1 − pi,i+1 = para i = 0, 1, . . . , 365,
365
∗
pfinal,final = 1,
pi,∗ j = 0 en otro caso.
La matriz Q es de la forma
0 1 0 0 ... 0 0
 
0
1 0 0 364/365 0 ... 0 0 

2 0 0 0 363/365 ... 0 0 
,
 
..  ..
. 
.


364 0 ... 0 1/365
365 0 ... 0 0
y la matriz I − Q es de la forma
1 −1 0 0 ... 0 0
 
0
 1 −364/365 0 ... 0 0

0 0 1 −363/365 ... 0 0
.
 
 ..
. 
 
0 0 ... 1 −1/365
0 0 ... 0 1
Si (a0 , a1 , . . . , a365 ) es la primer fila de la matriz N , debe ser
1 0 0 ... 0 0 1
    
a0
−1 1 0 ... 0 0
  a1  0
   

0
 −364/365 1 ... 0   a2  0
0    
0 0 −363/365 ... 0 0  a3 
 
 = 0 ,
 
 ..   ..   .. 

 .  .  .
    
0 0 ... 1 0 a364  0
0 0 ... −1/365 1 a365 0
de modo que a0 = 1 y
366 − i
ai = ai−1 para i = 1, · · · , 365,
365
o, en forma explícita,
(366 − 1) · · · (366 − i)
ai = para i = 1, 2, · · · , 365.
365i
Por lo tanto, la esperanza es
365 365
X (366 − 1) · · · (366 − i) X k(k + 1) · · · 365
1+ =1+ =
i=1 365i k=1 365366−k
(8.18)
365
365! X 365k
= .
365365 k=0
k!
Otra vez milagrosamente, esta esperanza coincide con la encontrada en (8.15)

mediante el análisis directo. En el apéndice B estudiamos estas fórmulas, mientras
que en el problema 9.5 vemos cómo interpretar el problema del cumpleaños co-
mo cadena regular, haciendo una comparación con los resultados recientemente
obtenidos.
8.5. Movimiento Browniano en una dimensión

En el problema de paseo al azar comienza a manifestarse la potencia de la teoría
de cadenas de Markov. Aunque ciertamente podemos pensar que el problema está
relacionado con monedas (o dados), el tipo de preguntas que nos hacemos es algo
diferente.
Supongamos que estamos en el eje x y la posición inicial es x = 0, y vamos
hacia derecha con probabilidad p y hacia la izquierda con probabilidad q = 1 − p,
22 8.5. Movimiento Browniano
Pn
nuestra posición después de k pasos será k=1 ak , donde ak = ±1 dependiendo de
si fuimos hacia la derecha o hacia la izquierda, de modo que vemos la relación con
el problema de la suma que vimos en la sección 8.2. Sin embargo ahora tenemos
dos estados absorbentes.
Para fijar ideas, pensemos que sólo hacemos n movimientos (pasos) y tenemos
«barreras absorbentes» en −n − 1 y en n + 1. Entonces podemos poner
1 0 0 0 0 ... 0 0 −n−1
 
q
 0 p 0 0 ... 0 0
 −n
0 q 0 p 0 ... 0 0
  −n+1
P = 0 0 q 0 p ... 0 0
 −n+2

 ..  ..
.  .
 
0 ... q 0 p n
0 ... 0 0 1 n+1
Nos preguntamos: después de n pasos, ¿dónde esperamos estar?

La respuesta es
∞
(n)
X
E= j p0 j ,
j=−∞
(n)
donde pi j son las entradas de la matriz P n .
En el caso sencillo p = q = 1/2, la matriz es simétrica en el sentido que
pi, j = p−i,− j , y esta propiedad se conserva para las potencias,
(n+1) (n) (n) (n) (n+1)

X X X
p−i,− j = p−i,` p`,− j = pi,−` p−`, j = pi,` p`, j = pi, j .
` ` `
(n) (n)
En particular, p0 j = p0,− j , de modo que:
8.19. Resultado. Si p = q = 1/2 y empezando en 0, cualquiera sea n después de n

pasos esperamos estar en x = 0, o sea
E = 0.
Este resultado también puede verse de forma intuitiva: hay tanta probabili-
dad de hacer un camino (x 0 = 0, x 1 , x 2 , . . . , x n ) como de hacer el camino (x 0 =
0, −x 1 , . . . , −x n ), y el promedio de estos caminos es 0.
En el caso p = 1/2, la matriz I − Q es
1 −1/2 0 0 ... 0 0
 
−n
−n+1 
 −1/2 1 −1/2 0 ... 0 0 

−n+2  0 −1/2 1 −1/2 ... 0 0 
, (8.20)
 
..  ..
. 
 .


n−1  0 ... −1/2 1 −1/2
n 0 ... 0 −1/2 1
y es interesante ver que la primer fila (i = −n) de N es de la forma
b (2n + 1, 2n, 2n − 1, . . . , 3, 2, 1),

donde b = 1/(n + 1) (por la simetría, la última fila es b (1, 2, 3, . . . )), y la fila del
medio (i = 0) de N es
(1, 2, 3, . . . , n, n + 1, n, . . . , 3, 2, 1).
Esto puede verse usando que

1 1
− (u − v) + u − (u + v) = 0 para cualquier u y v,
2 2
1

c − 2+1 =0 cuando i = −n o i = 0 y cualquier c,
2
1

b (2n + 1) − (2n) = 1 cuando i = −n,
2
1 1
− (a − 1) + a − (a − 1) = 1 cuando i = 0 y para cualquier a.
2 2
8.21. Resultado. Si p = 1/2, para un n dado y empezando desde 0,
a) la esperanza es 0,
b) usando el teorema 7.5, el número de veces que visito a un j dado, antes de llegar
a −n − 1 o n + 1, es = n + 1 − | j|,
c) espero hacer
2 (1 + 2 + · · · + n) + n + 1 = n(n + 1) + n + 1 = (n + 1)2
pasos entre −n y n hasta llegar a algún extremo (n + 1 o −n − 1).

Este resultado implica que para el ejemplo 2.2 de la peatonal con 6 cuadras, si
empezamos en la esquina 3 entonces podemos ir n = 2 cuadras hacia cada lado sin
salir, y esperamos hacer (n + 1)2 = 9 cuadras antes de terminar el paseo (al llegar a
la esquina 0 o la 6).
Observamos finalmente que la matriz de la ecuación (8.20) puede resultar
familiar para quienes hayan visto cálculo numérico, pues se trata de la matriz que
resulta al discretizar la ecuación diferencial
−u00 = f ,
en intervalos de igual longitud.

El movimiento browniano, en efecto, está relacionado con los procesos de
difusión en los que aparecen las ecuaciones armónicas y la ecuación del calor en
más dimensiones. La matriz N es entonces una discretización de la función de Green
(asociada al problema de Dirichlet): una función armónica (lineal en una dimensión)
excepto en el «polo», como muestran las ecuaciones explícitas para las filas primera
y del medio que pusimos.
También es posible estudiar variantes del movimiento browniano que son cade-
nas regulares, como veremos en el problema 9.3 en la próxima sección.
9. Cadenas regulares
Pasemos ahora a ver algunos resultados de otras cadenas «simples» como son
las cadenas ergódicas regulares. Recordemos que estas cadenas están caracterizadas
porque existe k ∈ N tal que P k = P (k) tiene todas sus entradas positivas.
24 9. Cadenas regulares
El primer resultado fundamental es que en el límite cuando n → ∞, P n converge

a una matriz, y que esta matriz límite tiene todas sus filas constantes:
9.1. Teorema. Si P ∈ Rn×n es la matriz de transición de una cadena de Markov
regular, entonces existe una matriz W ∈ Rn×n y un vector w ∈ Rn tales que
a) las entradas de w son positivas y i w i = 1,
P
b) las filas de W son todas iguales a w,

c) w es la única solución de w P = w con i w i = 1,(13)
P
d) lı́ms→∞ P s = W ,
e) W P = PW = W .
Observemos que siempre el vector v = (1, 1, . . . , 1) es un autovector para cual-
quier matriz de probabilidad, pues si x = P v,
n
X
xi = pi j 1 = 1,
j=1
de modo que P v = v, y la novedad del teorema es considerar un autovector

(con autovalor 1) a izquierda, o lo que es lo mismo, un autovector (usual) de la
transpuesta de P, P T .
Daremos una idea de la demostración del teorema más adelante; en cambio,
tratemos ahora de ver el teorema en acción.
Recordando el ejemplo 2.1, la matriz de transición es P
 
0 1/2 1/2
P = 1/4 1/2 1/4 .
 
1/4 1/4 1/2
Si el vector w tiene coordenadas (w1 , w2 , w3 ), debe satisfacer las ecuaciones
1 1
4
w2 + 4
w3 = w1
1 1 1
2
w1 + 2
w2 + 4
w3 = w2
1 1 1
2
w1 + 4
w2 + 2
w3 = w3
o, en forma homogénea,
1 1
−w1 + 4
w2 + 4
w3 = 0
1 1 1
2
w1 − 2
w2 + 4
w3 = 0
1 1 1
2
w1 + 4
w2 − 2
w3 = 0
Estas ecuaciones no son independientes, pues w es un autovector de P T , de
modo que no hay solución única. En nuestro ejemplo, la primer fila es la suma de las
otras dos cambiadas de signo. Sin embargo, el teorema nos asegura que agregando
la condición i w i = 1, obtendremos solución única.
P
Eliminando la tercer ecuación (o cualquier otra) y agregando la condición de

suma 1 llegamos a
1 1
−w1 + 4
w2 + 4
w3 = 0
1 1 1
2
w1 − 2
w2 + 4
w3 = 0
w1 + w2 + w3 = 1
(13)
O sea w es un autovector a izquierda de P con autovalor 1, y la multiplicidad de este autovalor es 1.
que tiene por solución a (1/5, 2/5, 2/5).

Unas pocas iteraciones (usando software o calculadora adecuados), muestran
que en este caso la convergencia de P k a W es rápida:
 
0.25 0.375 0.375
P 2 = 0.1875 0.4375 0.375  ,
 
0.1875 0.375 0.4375
 
0.1875 0.40625 0.40625
P 3 = 0.203125 0.40625 0.390625 ,
 
0.203125 0.390625 0.40625
 
0.200195 0.399902 0.399902
P 6 = 0.199951 0.400146 0.399902 .
 
0.199951 0.399902 0.400146
Así, vemos que en el caso del clima de Oz, «a la larga» habrá 1 de cada 5 días de
tiempo bueno, 2 de cada 5 serán lluviosos y en 2 de cada 5 nevará.
El teorema 9.1 nos dice que en las cadenas regulares siempre tendremos com-
portamientos similares. El proceso después de un número grande de iteraciones se
asemeja a un «dado» con n caras, en el que cada estado (cara del «dado») tiene
probabilidad w i de aparecer. De «yapa», el teorema nos da una forma de calcular
el vector w sin necesidad de hacer iteraciones (aunque la convergencia es bastante
rápida en todo caso).
9.2. Problema. En el pueblo hay dos supermercados, Mejor Valor y LucSil, cuyos
clientes son bastante leales, pero cada semana 10 % de los clientes de Mejor Valor
cambian por LucSil, y 20 % de los clientes de LucSil cambian por Mejor Valor. Una
compañía de marketing elige al azar un residente local y le pregunta (al mismo
residente) cada semana en que super compró.
a) Ver que se trata de una cadena de Markov y encontrar la matriz de transición.
b) Ver que la cadena es ergódica regular y encontrar el vector w mencionado en
el teorema 9.1.
c) Si en el pueblo están sólo estos dos supermercados, de acá a unos años
¿qué cantidad de clientes tendrá aproximadamente cada supermercado (en
términos de porcentaje de la población)? $
9.3. Problema. Consideremos la siguiente variante del paseo por la peatonal (ejem-
plo 2.2) pero ahora con 4 cuadras(14) donde usamos las siguientes reglas:
regla 1: Tiro una moneda. Si sale cara me quedo en la esquina por 2 minutos y
vuelvo a usar la regla 1, si sale ceca voy a la regla 2.
regla 2: Si estoy en la esquina norte camino una cuadra hacia el sur, si estoy en
la esquina sur camino una cuadra hacia el norte, en otro caso tiro de nuevo
la moneda y voy una cuadra hacia el sur si es cara o una hacia el norte si es
ceca. Luego vuelvo a la regla 1.
a) Ver que se forma una cadena de Markov y encontrar la matriz de transición P.
b) Encontrar k ∈ N tal que P k tenga todas sus entradas positivas (y que por lo
tanto se trata de una cadena ergódica regular).
(14)
Para hacer más fáciles las cuentas nos vamos a otro pueblo.
26 9. Cadenas regulares
c) Pensar cuál podría ser un valor «razonable» para el vector w (sin calcularlo).
d) Encontrar el vector w del teorema 9.1. ¿Concuerda con lo pensado en el
inciso anterior? $
Otro resultado de interés para cadenas regulares es el siguiente:
9.4. Teorema. En una cadena regular, con las notaciones del teorema 9.1, el número
de pasos esperado para retornar al estado ui (habiendo empezado en ui ) es
ei = 1/w i .
Remitiendo al lector interesado al libro de Kemeny y Laurel Snell [KLS76,

Sec. 4.4] para una demostración de este resultado, apliquémoslo al problema del
cumpleaños:
9.5. Problema (El problema del cumpleaños como cadena regular). Suponga-
mos que tenemos una cola «muy larga» de personas,(15) y a medida que van pasando
vamos anotando el día del cumpleaños. Si en algún momento anotamos una fecha,
¿cuántas personas esperamos que pasarán hasta volver a repetir esa fecha? $
En este caso podemos considerar como estados a {1, 2, . . . , 365}, siendo la
probabilidad de estar en cualquiera de ellos la misma. Consecuentemente, todas las
entradas de la matriz de transiciones P tienen el valor p = 1/365, y la matriz W
del teorema 9.1 coincide con P. De modo que si acaba de pasar una persona con
determinado día de cumpleaños, en promedio pasarán 1/p = 365 personas antes de
volver a repetir ese día. Es interesante comparar este resultado con el resultado 6.2
donde se obtiene el mismo valor.
Dejamos que el lector aplique el teorema 9.4 en casos más sustanciosos:
9.6. Problema.
a) Teniendo en cuenta el problema 9.2, si un cliente esta semana compra en
Mejor Valor, ¿dentro de cuántas semanas esperamos que volverá a hacerlo?
b) Con referencia ahora al problema 9.3, si estoy en la esquina 2, ¿cuántas veces
espero tirar la moneda hasta regresar a la misma esquina? $
Concluimos esta sección comentando brevemente la demostración del teore-
ma 9.1, para lo cual necesitamos previamente el siguiente lema:
9.7. Lema. Si P ∈ Rn×n es la matriz de transición de una cadena ergódica regular y
x ∈ Rn , entonces para algún α ∈ R,
lı́m P s x = α (1, 1, . . . , 1).

s→∞
Más aún, si las coordenadas de x son no-negativas y alguna es positiva, entonces

α > 0.
La idea de la demostración del lema es que si la coordenada i de P x es
yi = (P x)i = pi1 x 1 + pi2 x 2 + · · · + pin x n ,
como los coeficientes pi j son no-negativos y suman 1, yi es un «promedio» de las

coordenadas de x, y
mı́n x j ≤ yi ≤ máx x j .
j j
(15)
¡y son personas pacientes!
Si las entradas de P son estrictamente positivas, es posible ver un poco más:
(máx yi − mı́n yi ) < " (máx x j − mı́n x j ),

i i j j
para alguna constante apropiada ", 0 < " < 1. Después de s pasos, siempre supo-
niendo que las entradas de P son positivas, llegamos a
máx(P s x)i − mı́n(P s x)i < " s (máx x i − mı́n x i ),

i i i i
de donde se deduce el resultado para este caso especial. Puede suceder que algunas
de las entradas de P sean nulas, y allí es donde se usa la hipótesis de regularidad de
la cadena.(16)
Demostración del teorema 9.1: Tomando x = ei , el vector i-ésimo de la base canónica
de Rn , en el lema, P s ei converge a un vector de la forma αi (1, 1, . . . , 1), y por lo
tanto P s converge a una matriz cuya i-ésima columna tiene siempre el coeficiente
αi : la entrada w i , que será positiva.
Es claro que como P s → W , entonces

W P = lı́m P s P = lı́m P s P = W,
s→∞ s→∞
y de modo similar se ve que PW = W . En particular, de W P = W , tomando una fila

de W (que es w), queda w P = w.
También dado que las suma de cada fila de P s es 1 (recordar el problema 4.2),
W también es una matriz de probabilidad, y w hereda la propiedad de que la suma
de sus coordenadas es 1.
Finalmente, si w 0 es otro vector tal que la suma de sus coordenadas es 1 y
w P = w 0 , tenemos
0
w 0 = w 0 P = (w 0 )P = (w 0 P)P = w 0 (P 2 ) = (w 0 P)(P 2 ) = w 0 P 3 = · · · ,
de donde w 0 W = w 0 . Pero como las columnas de W son constantes, la coordenada j

de w 0 debe ser X X
w 0j = (w 0 W ) j = w i0 Wi j = w j w i0 = w j ,
i i
pues suponemos que las coordenadas de w 0 suman 1. ,
10. El comportamiento asintótico de cadenas de Mar-

kov
Terminamos haciendo un breve comentario sobre las matrices correspondientes
a cadenas absorbentes y regulares. En ambos casos vimos que P s tiende a un límite
cuando s → ∞.
En el caso de las cadenas regulares, si (esquemáticamente) ponemos

I 0
P= ,
R Q
(16)
Esta última parte de la demostración es «técnica» y no aporta mucho a la idea.
28 Apéndice A Apéndice A Pág. 29
3 2
Figura10.1:
Figura 7: Una
Unacadena
cadenacı́clica.
cíclica.
vimos (teorema 7.7) que

y entonces P 4 = P y se repite cı́clicamente
I cada
0 3 iteraciones.

s
P −→ ,
Puede demostrarse que esencialmente
s→∞ N Reste 0 es el único comportamiento posi-
ble. Para hacer este estudio primero se piensa en una cadena auxiliar, donde los
mientras que en el caso de cadenas regulares acabamos de ver que
conjuntos ergódicos se “colapsan” a estados absorbentes, quedando una cadena
absorbente, y luego se hace el estudio,s ya como cadena ergódica, de los conjuntos
P −→ W.
ergódicos originales. Para un estudio s→∞
más detallado ver por ejemplo el libro de
Kemeny y Snell [KLS76].
De modo que en ambos casos el comportamiento «a la larga» o, más formalmente,
asintótico del proceso es como si hubiera una única matriz que lo describe.
Podemos quedarnos con la idea de que esto sucederá para cualquier cadena de
Apéndice A. Algunas soluciones
Markov, pero el ejemplo de la figura 10.1 muestra que pueden haber comportamien-
tos cíclicos.
A.1. Problema 7.8
En este caso la matriz correspondiente es
Queremos verificar que, con lasnotaciones  de la Sección 7, la suma de las
filas de N R es 1. 0 0 1
Recordemos que N = (I − Q) = ∈1R(m−n)×(m−n)
P −1 0 0 , y que R ∈ R(m−n)×m , por
 
lo que N R ∈ R (m−n)×m 0 1 0
. Llamando n a las entradas de N y r a las entradas
ij ij
de R, debemos tomar un estado transiente ui y evaluar la suma
por lo que
  !  
0 1 0s = n r , 1 0 0 (A.1)
ik kj
P 2 = 0 0 1 j,ky P 3 = 0 1 0  ,
   
1 0 0 0 0 1
donde la suma es sobre todos los ı́ndices k correspondientes a estados transientes
yy entonces 4
= P y jsecorrespondientes
todos losPı́ndices repite cíclicamente cada 3 iteraciones.
a estados absorbentes.
Puede demostrarse que esencialmente este es el único comportamiento posible.
Como la matriz P original es de probabilidad, sabemos que para todo ı́ndice
Para hacer este estudio primero se piensa en una cadena auxiliar, donde los conjuntos
!, debe ser
ergódicos se «colapsan» a estados absorbentes,
n quedando una cadena absorbente, y
!
luego se hace el estudio, ya como cadena ergódica,
p!h = 1, de cada uno de los conjuntos
ergódicos originales. Para un estudio h=1más detallado ver, por ejemplo, el libro de
Kemeny y Snell [KLS76].
de modo que podemos reagrupar los términos en la ecuación (A.1) para obtener
! ! ! " ! #
Apéndice A. s =Algunas
nik kj = nik 1 −
rsoluciones pk! ,
k j k !
A.1. Problema 7.8

donde ahora los ı́ndices ! corresponden a estados transientes, es decir pk! = qk!
—laQueremos
entrada k! de Q—que,
verificar porconlo que
las notaciones de la sección 7, la suma de las filas
de N R es 1. ! " ! # "! # "! #
Recordemoss= que N n=ik(I1−−Q)−1q∈k!R(m−n)×(m−n)
= nik y−que R ∈ Rq(m−n)×m
nik k! . , por lo(A.2)
que
N R ∈ R(m−n)×m . Llamando
k ni j a las
! entradas de
k N y ri j a las
k,! entradas de R, debemos
tomar un estado transiente ui y evaluar la suma

X
s= nik rk j , (A.1)
j,k
donde la suma es sobre todos los índices k correspondientes a estados transientes y

todos los índices j correspondientes a estados absorbentes.
Como la matriz P original es de probabilidad, sabemos que para todo índice `,
debe ser
Xn
p`h = 1,
h=1
de modo que podemos reagrupar los términos en la ecuación (A.1) para obtener
X X X X
s= nik rk j = nik 1 − pk` ,
k j k `
donde ahora los índices ` corresponden a estados transientes, es decir pk` = qk` —la
entrada k` de Q— por lo que
X X X X
s= nik 1 − qk` = nik − nik qk` . (A.2)
k ` k k,`
Como N y I − Q son inversas, tomando δi` como 1 si i = ` y 0 si i =

6 `, si i y `
son índices correspondientes a estados transientes debe ser
X
δi` = nik (δk` − qk` ),
k
es decir, X X
nik qk` = −δi` + nik δk` = −δi` + ni` .
k k
Reemplazando en la ecuación (A.2), queda

X XX
s= nik − nik qk` =
k ` k
X X X X
= nik − (−δi` + ni` ) = nik + 1 − ni` = 1. ,
k ` k `
A.2. Problema 8.10

Aquí queremos verificar que si ai está dado por la ecuación
1
ai = para i = 0, 1, . . . , m − 1,
p m−i
entonces
(a0 , a1 , . . . , am−2 , am−1 ) · (I − Q) = (1, 0, . . . , 0).
30 A.3. Problema 8.12
Para la primer columna ( j = 0),

m−1
X 1 q m−2
X
p (1/p) − q
m
(1/p) m−i
= − (1/p)i =
i=1
p m−1 p i=0
1 q (1/p)m−1 − 1
= − = 1.
p m−1 p 1/p − 1
Para las otras columnas ( j = 1, . . . , m − 1),

1 1
(−p) + = 0. ,
p m−( j−1) p m− j
A.3. Problema 8.12

Nos preguntamos si la matriz
 
1 p p (1 + p) p (1 + p)2 ... p (1 + p)n−2
0 1 p p (1 + p) ... p (1 + p)n−3 
 
. 
. ,
. 
0 ... 0 1 p
 

0 ... 0 1
es la inversa de la matriz I − Q dada por

 
1 −p −p . . . −p −p
0 1 −p . . . −p −p
 
. 
. .
. 
0 ... 1 −p
 
0 ... 1
Al considerar la entrada (i, j) del producto de N con I −Q, donde i, j = 0, . . . , n−

1, tenemos que hacer el producto interno entre los vectores
i
(0, . . . , 0, 1, p, p (1 + p), . . . , p (1 + p)n−2−i )
y
j
(−p, −p, . . . , −p, 1, 0, . . . , 0),
de modo que la entrada es 0 si i > j, 1 si i = j, y
j−1
X
−p + p (1 + p)k−i−1 (−p) + p (1 + p) j−i−1 =
k=i+1
j−i−2
X
= −p − p2 (1 + p)k + p (1 + p) j−i−1 =
k=0
(1 + p) j−i−1 − 1
= −p − p2 + p (1 + p) j−i−1 =
(1 + p) − 1
= −p − p (1 + p) j−i−1 − 1 + p (1 + p) j−i−1 = 0,

si i < j (cuando j = i + 1, la suma del medio no existe).

Otra forma de verlo es resolver el sistema
    
1 0 0 0 ... 0 a0 1
−p 1 0 0 . . . 0  a1  0
    
 .  .  .
 .  .  = .
 .  .  .
−p . . . −p 1 0 an−2  0
    

−p ... −p 1 an−1 0
donde (a0 , a1 , . . . , an−2 , an−1 ) es la primer fila de N (correspondiente a i = 0).

Como la matriz de este sistema es triangular, podemos ver que
a0 = 1, y ak = p sk−1 para k = 1, . . . , n − 1,
Pk
donde sk = j=0 a j . En realidad es más fácil determinar primero sk pues s0 = 1 y
sk = sk−1 + p sk−1 = (1 + p)sk−1 para k = 1, . . . , m − 1,
i.e., sk = (1 + p)k , por lo que para k ≥ 1,
ak = sk − sk−1 = (1 + p)(1 + p)k−1 − (1 + p)k−1 = p (1 + p)k−1 ,
que es el resultado que teníamos. ,
Apéndice B. Fórmulas relacionadas con el problema

del cumpleaños
Tratamos ahora de encontrar fórmulas para describir varias de las ecuaciones
que aparecieron en la sección 8.4 al estudiar el problema de dos con el mismo
cumpleaños.
Para n entero no-negativo y x ∈ R, definimos la función ϕ como(17)
Z∞
ϕ(n, x) = e x t n e−t d t.
x
Observemos que
ϕ(0, x) = 1 (B.1)
y
Z ∞ Z ∞
n −t
∞
ϕ(n, x) = e x
dt = e x
−t n e−t x +n t n−1 e−t d t =

t e
x x (B.2)
= x + n ϕ(n − 1, x).
n
Siguiendo de la misma forma, usando las ecuaciones (B.2) y (B.1),

ϕ(n, x) = x n + n ϕ(n − 1, x) =
= x n + nx n−1 + n(n − 1) ϕ(n − 2, x) = · · · =
n (B.3)
X xk
= n! .
k=0
k!
(17)
ϕ(n, x) está relacionada con la función Γ incompleta, ϕ(n, x) = e x Γ(n + 1, x).
32 Apéndice B
Así, ϕ(n, x) puede considerarse como una notación para el último término: lo
importante es la relación de recurrencia (B.2) junto con la condición inicial (B.1).
Para x, y ∈ R, usando (B.3) y (B.2),
n n n n n−1 k
X xk X xk X xk X xk X x
( y − k) =y − k =y −x =
k=0
k! k=0
k! k=1 k! k=0
k! k=0
k!
ϕ(n, x) ϕ(n − 1, x)
=y −x =
n! (n − 1)! (B.4)
ϕ(n, x) 1 ϕ(n, x) − x n
=y −x =
n! (n − 1)! n
y−x x n+1
= ϕ(n, x) + .
n! n!
En el caso particular x = y = n queda
n n−1
X nk X nk nn+1
(n − k) = (n − k) = ,
k=0
k! k=0 k! n!
de donde se obtiene la ecuación (8.17) en la que se suman las probabilidades en el

caso del cumpleaños:
n−1
n! X ni
(n − i) = 1.
nn+1 i=0 i!
Recordando ahora la ecuación (8.15), la reescribimos en términos de ϕ:

n
n! X nk n! nϕ(n, n) ϕ(n, n)
E= (n − k)(n + 1 − k) = n+1 = ,
nn+1 k=0 k! n n! nn
Si x, y, z ∈ R, usando (B.4) y (B.2) tenemos

n n n
X xk X xk X xk
( y − k)(z − k) =y (z − k) − k(z − k) =
k=0
k! k=0
k! k=1 k!
n n−1
X xk X xk
=y (z − k) −x (z − 1 − k) =
k=0
k! k=0
k!
ϕ(n, x) x n+1
= y (z − x) + −
n! n!
ϕ(n − 1, x) xn
− x (z − 1 − x) + =

(n − 1)! (n − 1)!
x n+1 ϕ(n, x)
= ( y − n) + y(z − x) −
n! n!
1 ϕ(n, x) − x n
− x(z − 1 − x) =
(n − 1)! n
x n+1 ϕ(n, x)
= ( y + z − 1 − x − n) + ( y − x)(z − x) + x .
n! n!
Poniendo y = x = n y z = n + 1, obtenemos la ecuación (8.15).
Para la esperanza en (8.18), donde n = 365, podemos usar (B.3) con x = n,

obteniendo el mismo resultado: ϕ(n, n)/nn . ,
Es interesante mirar estas fórmulas en casos más familiares como tirar dados o
monedas. Por ejemplo, la esperanza de tirar monedas hasta que se repita alguna es
ϕ(2, 2) 5
E= = = 2.5,
22 2
mientras que la esperanza de tirar dados hasta que alguno se repita es
ϕ(6, 6) 1223
E= = ≈ 3.77469.
66 324
Observación. El uso de ϕ es sólo una conveniencia. La forma con exponenciales

e integrales es más que nada una curiosidad para lo que hacemos (x ∈ N). Por
ejemplo, las esperanzas que consideramos son números racionales (como puede
verse en la ecuación (B.3)). ,
Apéndice C. Programas en Pascal

En este apéndice bosquejamos algunos programas, usando el lenguaje Pascal,
para hacer simulaciones numéricas de algunos problemas que hemos mencionado.
Sólo indicamos la parte principal, dejando detalles de interacción con el usuario
para el lector interesado.
Como en todos ellos usamos números aleatorios, pero en Pascal no están defini-
dos, suponemos una función aleatorio que da un número aleatorio (uniformemen-
te distribuido) en (0, 1], con la variante aleatorio(m) que da un número entero
entre 1 y m. En Turbo Pascal aleatorio es la sentencia random y debe aplicarse
previamente la sentencia randomize.
La implementación de los programas es una parte importante del aprendizaje,
y esperamos que el lector extienda estos programas para los otros problemas que
hemos mencionado, por ejemplo el problema del Número de Oro (problema 1.1) o
el problema de la REM (problema 8.6).
En todos los programas la variable entera n es la cantidad de veces que se realiza
la simulación, la variable real veces es el número de veces que se ha realizado la
experiencia («tirado el dado»). Al terminar, veces/n indica el promedio de «tiros»
realizado hasta obtener m consecutivos. Ponemos veces de tipo real pues podría ser
muy grande (dependiendo del problema).
Al hacer las primeras pruebas, es conveniente tomar n chico, n = 1 o 10, y una
vez que se sabe que el programa funciona, tomar n más grande, 1000 o tal vez
10000.
C.1. (Programa para el problema 8.1 de m consecutivos). Aquí tenemos

p, real: la probabilidad de suceso favorable, 0 ≤ p ≤ 1.
m, entero: el número consecutivo de veces que debe aparecer el resultado favora-
ble.
contador, entero: cuenta cúantos favorables consecutivos se han obtenido.
34 Apéndice C
veces := 0;
for i := 1 to n do begin
contador := 0;
repeat
veces := veces + 1;
if (aleatorio < p) then contador := contador + 1
else contador := 0
until (contador = m)
end;
C.2. (Programa para el problema 8.2 de sumar hasta una cifra dada). Acá
suponemos que sacamos números enteros entre 1 y k (k = 6 para dados).
m, entero: el objetivo al cual debe llegar la suma.
suma, real: la suma de los números obtenidos. La tomamos como real pues puede
ser muy grande.
veces := 0;
suma := 0;
repeat veces := veces + 1; suma := suma + aleatorio(k)
until (suma >= m)
end;
C.3. (Programa para el problema 8.3 de sumar hasta 1). Es una variante del
anterior, donde ahora m = 1, y los números aleatorios están entre 0 y 1:
veces := 0;
suma := 0;
repeat veces := veces + 1; suma := suma + aleatorio
until (suma >= 1)
end;
C.4. (Programa para el problema 8.4 del cumpleaños). Aquí usamos:

m, entero: la cantidad de posibilidades, en el problema del cumpleaños tomaríamos
m = 365.
a, arreglo «booleano»: inicialmente en false, cambia a true cuando ha llegado
alguien con esa «fecha de cumpleaños».
seguir, «booleana»: si dejamos que sigan entrando personas al cine.
veces := 0;
for j := 1 to m do a[j] := false;
seguir := true;
repeat
veces := veces + 1;
j := aleatorio(m);
if (a[j]) then seguir := false else a[j] := true
until (not seguir)
end;
C.5. (Programa para el problema 8.5 del paseo). En este caso ponemos:
inic, entero: la posición (esquina) inicial.
pos, entero: la posición (esquina) en la que estamos.
veces := 0;
pos := inic;
repeat
veces := veces + 1;
if (aleatorio > .5) then pos := pos - 1
else pos := pos + 1
until ((pos = 0) or (pos = m))
end;
Bibliografía
[Fel57] W. FELLER: An Introduction to Probability Theory and its Applications, vol.
1, 3.a ed. J. Wiley & Sons, 1957. (págs. 1 y 4)
[KLS76] J. G. KEMENY, J. LAURIE SNELL: Finite Markov Chains, Springer-Verlag,

1976. (págs. 1, 2, 26 y 28)
[REM02] D. PENAZZI: Problemas para resolver, en Revista de Educación Matemática,

UMA, vol. 17, n.o 2, pág.46, 2002. http://www.union-matematica.
org.ar/publicaciones/index.html (pág. 13)
[Rob76] F. S. ROBERTS: Discrete mathematical models. With applications to social,
biological, and environmental problems. Prentice-Hall, 1976. (pág. 1)

Cadenas de Markov

Cargado por

Copyright:

Formatos disponibles

Cadenas de Markov

Cargado por

Información del documento

Derechos de autor

Formatos disponibles

Compartir este documento

Compartir o incrustar documentos

Opciones para compartir

¿Le pareció útil este documento?

¿Este contenido es inapropiado?

Copyright:

Formatos disponibles

Cadenas de Markov

Cargado por

Copyright:

Formatos disponibles

Cadenas de Markov

por Néstor Aguilera†

Versión revisada, 7 de octubre de 2009‡

3. Usando grafos dirigidos 5

5. Clasificación de estados y cadenas 7

7. Cadenas absorbentes: resultados teóricos 10

Apéndice A: Algunas soluciones 28

Apéndice B: Fórmulas relacionadas con el problema del cumpleaños 31

Apéndice C: Programas en Pascal 33

1.1. Problema. Tres jugadores, A, B y C, arrojan alternativamente —en ese orden—

O, un ejercicio muy común de los cursos de programación como:

En estas notas, basadas en un curso dado en la Reunión de Educación Matemática

2.1. Ejemplo (El clima en la Tierra de Oz). Según el cuento, en la Tierra de Oz

p bb = 0 de un buen día a un buen día,

Es conveniente ordenar estos datos en una tabla o matriz,

5. que sólo puede depender del estado inmediatamente anterior,

2.2. Ejemplo (Paseando por la peatonal). La peatonal de mi pueblo tiene 6

2.3. Problema. Supongamos que decido no terminar el juego, y en cambio seguir

2.4. Problema. Supongamos que en el ejemplo 2.1, las probabilidades dependen

A veces se trata de una cadena de Markov «disfrazada»:

2.7. Problema (Teoría de Mendel). En 1866 el monje agustino Gregor Mendel

1 1!2 1!2 1!2 1!2 1!2 1

recesivos), y hacer que las entradas pi j representen la probabilidad de que un

3.1. Problema. Hacer el digrafo correspondiente al clima en la Tierra de Oz (ejem-

Pensar en digrafos ayuda a pensar en la estructura de la cadena de Markov. Por

Pág. 6 Figura 2: Árbol de posibilidades.Cadenas de Markov

• Para llegar a 1 tengo que llegar3 primero a 2 (con probabilidad 1/2) y

4.1. Problema. Ver que P (2) es una matriz de probabilidad. $

4.2. Problema. Ver que P r es una matriz de probabilidad para r ∈ N. $

5. Clasificación de estados y cadenas

Figura 4: Un digrafo “no conexo”. Los nodos 1, 2 y 3 forman una componente

salgan— pero puedo

Ası́ como es conveniente considerar sólo componentes conexas, es conveniente

por lo que la probabilidad de que salga exactamente en el paso n es el producto de

Para calcular la última suma podemos usar el siguiente truco: consideramos

que tiene como derivada a

Podemos poner entonces:

6.2. Resultado. Si en cada paso hay una probabilidad constante p de obtener un

7. Cadenas absorbentes: resultados teóricos

7.1. Teorema. En toda cadena de Markov absorbente, la probabilidad de absorción

Eventualmente renumerando los estados, podemos escribir la matriz de transi-

En este caso, si hay n estados, de los cuales m son absorbentes y n − m transientes,

7.5. Teorema. En una cadena absorbente, si se empieza en el estado transiente ui ∈ T ,

Como ui es transiente y u j absorbente, pi j es la entrada correspondiente de la

de donde sigue el resultado pues I − Q es inversible con inversa N . ,

8. Problemas de dados y monedas

Un nuevo jugador, C, entra en el juego. Él ganará si sale una cruz seguida de

La mayoría de estos problemas son suficientemente sencillos como para resolver-

Las probabilidades de transición son (en el caso de los dados):

pk,k+i = p para i = 1, 2, . . . , 6, k = 0, 1, . . . , si k + i < m,

Finalmente, en el problema 8.3 donde los números obtenidos en cada paso

En el apéndice C bosquejamos algunos programas en Pascal para los proble-

8.1. El problema de repetir hasta obtener m consecutivos

No es difícil intuir cuál será el caso general: tendremos una probabilidad p m

obtuve resultados favorables en las primeras m − 1 pero desfavorable en la siguiente

Para continuar debemos evaluar las sumas «internas». Es sencillo calcular la

8.1.2. Con cadenas de Markov

 0 1 2 ... m−2 m−1

Podemos encontrar la primer fila de la matriz N correspondiente —que es lo

(a0 , a1 , . . . , am−2 , am−1 ) · (I − Q) = (1, 0, . . . , 0),