Cadenas de markov

Clasificación de los estados en una cadena de Markov

Rafael Martínez González Daniel Héctor Stolfi Rosso
Modelos de evaluación del rendimiento de sistemas Curso 2009/2010

Índice
Estado alcanzable Conjunto cerrado Estado absorbente Conjunto irreducible Estado transitorio y recurrente Estado periódico y aperiódico Cadena ergódica Algunas propiedades Ejercicios Problemas
2

Estadoalcanzable
Dados dos estados i y j, una trayectoria de i a j es una secuencia de transiciones que comienza en i y termina en j, tal que cada transición en la secuencia tiene una probabilidad positiva de ocurrir. Un estado j es alcanzable desde el estado i si hay una trayectoria que conduzca de i a j.

D B A E

C

3

Conjunto cerrado
Un subconjunto no vacío C en una cadena de Markov S es unconjunto cerrado si y sólo si, para todo estado i de C y para todo estado j no perteneciente a C, j no es alcanzable desde i. Los subconjuntos C1 = {A, B} y C2 = {C, D, E} son cerrados, con C1 y C2 pertenecientes a la cadena de Markov S = {A, B, C, D, E}. D B A E

C

4

Estado absorbente
Un estado i es un estado absorbente si Pii = 1, es decir, para todo estado j distinto de i, Pij = 0.El estado B no es absorbente, ya que la probabilidad PBA es mayor que 0. El estado C sí es absorbente, ya que la probabilidad PCC = 1.

D B A E

C

5

Conjunto irreducible
Sea C un subconjunto cerrado de la cadena de Markov S. El conjunto C es irreducible si y sólo si no contiene ningún subconjunto propio cerrado. Una cadena de Markov S es irreducible si, para todo estado i, jperteneciente a S, j es alcanzable desde i. El subconjunto C1 = {A, B, C} es cerrado pero no irreducible, ya que C11 = {A, B} es cerrado. Si tuviéramos PCD > 0, el subconjunto C2 = {C, D, E} sería cerrado e irreducible. D B A E
6

C

Estado transitorio y recurrente
Un estado i es un estado transitorio si existe un estado j que es alcanzable desde i, pero el estado i no es alcanzable desde el estadoj. Si un estado no es transitorio, entonces es un estado recurrente. En la cadena de Markov inferior, el estado A es transitorio, mientras que los estados B, C, D y E son recurrentes. D B A E
7

C

Estado periódico y aperiódico
Un estado i es periódico con período k > 1 si k es el número más pequeño tal que las trayectorias que conducen del estado i de regreso al estado i tienen unalongitud que es un múltiplo de k. Si un estado recurrente no es periódico, entonces se denomina aperiódico. En la cadena de Markov inferior, todos los estados son periódicos con k = 3. A B E
8

C D

Cadena ergódica
Una cadena de Markov es ergódica si y sólo si es irreducible y todos sus estados son recurrentes y aperiódicos. La cadena de Markov S = {A, B, C} es ergódica; mientras tanto, lacadena de Markov T = {D, E, F, G} no es ergódica, ya que no es irreducible. A B D F

C

E

G
9

Algunas propiedades
Si un conjunto cerrado se compone de un único estado, entonces dicho estado es absorbente. Si un estado es absorbente, entonces también es recurrente. La implicación en el sentido contrario no se cumple.

A

B

C

E

D
10

Algunas propiedades
Si tenemos unacadena de Markov irreducible y finita, entonces todos sus estados son recurrentes. Si un estado j es alcanzable desde un estado i recurrente, entonces el estado j también es recurrente. B C

D A E
11

Ejercicios
Ejercicio 1: En el problema de la ruina del jugador, ¿cuál es el período de los estados 1 y 3? Solución: los estados 1 y 3 tienen período k = 2.

0

1

2

3

4

12Ejercicios
Ejercicio 2: Consideremos la cadena de Markov del problema de las familias españolas que viven en zonas urbanas, rurales o suburbanas. ¿Es dicha cadena de Markov ergódica? Solución: sí, porque la cadena es irreducible y sus tres estados son aperiódicos y recurrentes.

U S R
13

Ejercicios
Ejercicio 3: Sea la cadena de Markov que aparece debajo. Clasifica los estados según sean...