Cadenas de MarkovInvestigación de Operaciones 2

Cadenas de Markov

“Cuando, conociendo el pasado y el presente, el comportamiento

probabilístico del futuro inmediato sólo depende del estado presente”

Cadena de Markov

› En honor al matemático ruso Andrei Andreyevich Markov,

› 1856 - 1922

Cadenas de Markov

› Las cadenas de Markov y los procesos de Markov son un tipo especial de procesos estocásticos que poseen la siguiente propiedad:

› Propiedad de Markov: Conocido el estado del proceso en un momento dado, su comportamiento futuro no depende del pasado. Dicho de otro modo, “dado el presente, el futuro es independiente del pasado”

Definiciones de las Cadenas de Markov› Las cadenas de Markov son una herramienta para

analizar el comportamiento de determinados procesos estocásticos, estos procesos evolucionan de forma determinística a lo largo del tiempo en torno a un conjunto de estados.

› En las cadenas de Markov la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este tipo tienen memoria. " Recuerdan" el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Markov de las series de eventos independientes, como tirar una moneda al aire o un dado.

Glosario› Pruebas del proceso: eventos que disparan transiciones de un estado a otro. 

En muchas aplicaciones, periodos de tiempo sucesivos.

› Probabilidad de transición: dado que el sistema está en estado i durante un periodo, la probabilidad de transición pijes la probabilidad de que el sistema este en el estado j durante el siguiente periodo.

› Probabilidad de estado: es la probabilidad de que el sistema esté en cualquier estado particular.

› Probabilidad de estado estable: La probabilidad de que el sistema esté en cualquier estado particular después de un número elevado de transiciones.  Una vez  alcanzado este estado la probabilidad de estado no cambia de un periodo a otro.

› Estado de absorción: se da cuando la probabilidad de que ocurra una transición de este estado es cero.  Por lo que una vez que el sistema a hecho una transición a un estado de absorción, quedará ahí.

› Matriz fundamental: Matriz necesaria para el cómputo de probabilidades asociadas con el estado de absorción de un proceso de Markov.

….definiciones

› Es una serie de eventos, en la cual la probabilidad de que ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este tipo tienen memoria. “ Recuerdan” el último evento y esto condiciona las posibilidades de los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de Markov de las series de eventos independientes, como tirar una moneda al aire o un dado.

› Una cadena de Markov es una secuencia X1, X2, X3, … de variables aleatorias.

› El rango de estas variables, es llamado espacio estado o transición de estados, el valor de Xn es el estado del proceso en el tiempo n. Si la distribución de probabilidad condicional de Xn+1 en estados pasados es una función de Xn por sí sola

Diagrama de transición de estados

› El diagrama de transición de estados (DTE) de una CM es un grafo dirigido cuyos nodos son los estados de la CM y cuyos arcos se etiquetan con la probabilidad de transición entre los estados que unen. Si dicha probabilidad es nula, no se pone arco.

i j

qi

j

Probabilidades de Transición

pi,j(n) = la probabilidad de que el proceso,

estando en el estado i en el tiempo n,

pase al estado j en el instante

siguiente

Cuando pi,j(n) = pi,j (esto es, no depende de n) se

dice que las probabilidades de transición son

estacionarias. Lo supondremos de ahora en

adelante.

Matriz de Transición

Las probabilidades de transición definen la matriz P = [pij] que satisface

1) pij 0 para todo i, j

2)

para todo i

1pj

ij

Matriz de Transición: ejemplo

.

Tiempo n+1

Estado 0 Estado 1 Estado 2 Estado 3

Estado 0 0,20 0,65 0,15 0

Tiempo n

Etado 1 0 0,60 0 0,40

Estado 2 0,15 0,15 0,30 0,40

Estado 3 0 0 0 1

Las filas

deben de

sumar 1

Ejemplo: línea telefónica (matriz transiciones)

Sea una línea telefónica de estados ocupado=1 y desocupado=0. Si en el instante t está ocupada, en el instante t+1 estará ocupada con probabilidad 0,7 y desocupada con probabilidad 0,3. Si en el instante t está desocupada, en el t+1 estará ocupada con probabilidad 0,1 y desocupada con probabilidad 0,9.

Ejemplo: línea telefónica

7,03,0

1,09,0Q

0 10,9

0,1

0,3

0,7

E0

E1

Ejemplo 2: Matriz de transiciones

› El nivel de negocio de la Bolsa puede considerarse cada día alto (A) o bajo (B). Para un periodo de 5300 días se dispone de la secuencia BAABBA..., y que nos permite representar la alternancia mediante el cuadro adjunto:

B A

B 3077 543

A 588 1092B A

B 0.85 0.15

A 0.35 0.653077 ÷ (3077 +

543)

Ejemplo 2: juego aleatorio

En el tiempo 0 tengo Q2 y en los tiempos 1,2,3,... participo en un juego en el que apuesto Q1. Gano el juego (y gano Q1) con probabilidad p y lo pierdo (perdiendo lo apostado) con probabilidad 1-p. Mi meta es aumentar mi capital hasta Q4 y tan pronto lo logre me salgo del juego. También salgo cuando me arruine (capital Q0).

Ejemplo 2 (cont)

- Xn : mi capital inmediatamente después del juego n

- Estados del proceso = {0,1,2,3,4}

- Matriz de transición:

1

p

0

0

0

0

0

p

0

0

0

p1

0

p

0

0

0

p1

0

0

0

0

0

p1

1

P

Ejemplo 3: un modelo para el desplazamiento poblacional

Para efectos de una investigación, en un determinado país, una familia puede clasificarse como habitante de zona urbana, rural o suburbana. Se ha estimado que durante un año cualquiera, el 15% de todas las familias urbanas se cambian a zona suburbana y el 5% a zona rural. El 6% de las familias suburbanas pasan a zona urbana y el 4% a zona rural. El 4% de las familias rurales pasan a zona urbana y el 6% a zona suburbana.

Cadenas de Markov: ejemplo 3

Tendremos la siguiente matriz de transición

Urbana Suburbana. Rural.

900060040

040900060

050150800

,,,

,,,

,,,

P

Cadenas de Markov

Urb Surb. Rural

0,15 0,04

0,05

0,04

0,06

0,06

0,80,90

0,90

Ejemplo 4

› 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.

Como quedarían las probabilidades ?› De un buen día a un buen día BB = 0

› De un buen día a un día lluvioso BL = ½

› De un buen día a un día con nieve BN = ½

› De un día lluvioso a un día lluvioso LL = ½

› De un día lluvioso a un buen LB= ¼

› De un día lluvioso a un día con nieve LN = ¼

› De un día con nieve a un día con nieve NN = ¼

› De un día con nieve a un día con lluvia NL = ¼

› De un día con nieve a un buen día NB = ½

B L NB 0 ½ ½L ¼ ½ ¼N ¼ ¼ ½

Ejemplo 5Un ratón cambia de habitáculo cada minuto con igual probabilidad a las salas adyacentes

Salón 1

Habitación 2 Cocina 3Entra

da

4

Matriz de probabilidades de transición :

0 1/3 1/3 1/3

1/2 0 1/2 0

1/3 1/3 0 1/3

1/2 0 1/2 0

P =

S E

H C

1/2

1/2

1/2

1/2

1/3

1/3

1/3

1/3

1/3

1/3

Hoja de trabajo

›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 escudo. Y continúo este juego hasta salir de la peatonal, ya sea hacia el norte o hacia el sur.

Los estados en una Cadena de Markov

Tipos de Estados› Estados Transitorios

Los estados que pueden sucederse a sí mismos y, además, es posible alcanzar, por lo menos, alguno de los restantes desde ellos se llaman estados transitorios.

Estados Absorbentes

Un estado tal que si el proceso entra en él permanecerá indefinidamente en este estado (ya que las probabilidades de pasar a cualquiera de los otros son cero), se dice estado absorbente.

BIEN CON SECUELAS

MUERTO

0.6 0.6

0.2

0.2

3 estados (1 absorbente, 2 transitorios)

3 estados (1 absorbente, 2 transitorios)

S1 S2

S1 1/2 1/2

S2 1/2 1/2

Está claro que el sistema completo nunca estará completamente "atrapado" en un estado, así que la cadena es regular.

S1 S2 S3

S1 0 3/4 1/4

S2 1/2 0 1/2

S3 1/4 3/4 0 Siempre es posible moverse de un estado a cualquier otro, en cualquier paso siendo los movimientos no‑cíclicos. Así la cadena y la matriz son regulares.

S1 S2 S3

S1 ½ 1/4 1/4

S2 0 1/3 1/3

S3 0 1/4 1/4

Después de n pasos la cadena entrará (con probabilidad 1 cuando n tiende a ∞) en S2 o en S3. Una vez situada en uno de estos estados nunca podrá pasar a S1. Por lo tanto S1 es un estado transitorio y así la cadena es no regular y por lo tanto no‑ergódica, aunque el conjunto [ S2, S3 ] sea un conjunto ergódico.

S1 S2 S3

S1 0 0 1

S2 1 0 0

S3 0 1 0

La cadena se mueve con período 3 a través de los conjunto cíclicos [ S1 ] [ S2 ] y [ S3 ]. Es por lo tanto una cadena cíclica ergódica y no una cadena regular.