Markov

Cadenas de Markov y Teoría de Colas
Carlos F. Belaustegui Goitia

Procesos y Cadenas de Markov
• • • • • • Variables binomial, geométrica y de Poisson. Procesos puntuales. Procesos de Markov. Cadenas de Markov. Clasificación de estados, clases de cadenas, estado estacionario. Teorema de Perron-Frobenius. Cadenas de Markov en tiempo continuo. Ecuaciones de balance global. Aplicaciones.09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

2

Variables Binomial y Geométrica
Variable Binomial: La probabilidad de que el evento A, cuya probabilidad es P(A) = p, ocurra k veces en n pruebas es n pn (k ) =   p k (1 − p) n−k ,   k   n n!  =  k  k!(n − k )!   Separación entre eventos: sea X= número de pruebas hasta el primer éxito P( X = 1) = pP( X = 2) = (1 − p) p L P( X = n) = (1 − p) n−1 p = q n−1 p
15 21 1 3 4 8 13 15 21

n=22, k=7
1 3 4 8 13

Distribución geométrica. X es el número de pruebas hasta el primer éxito en una secuencia de pruebas de Bernoulli.

1 3 4 8 13 15 21 1 2 4 5 11 19 20 3 5 6 7 12 17 20 ............... 4 6 8 9 16 21 22

 22    combinaciones 7  

X=n

n0

X=n
P ( X = n, X > n0 ) P ( X = n)= = P ( X > n0 ) P ( X > n0 ) q n −1 p
k = n0 +1

Propiedad “sin memoria” de la distribución geométrica
P ( X = n / X > n0 ) = q n −1
i = n0

Aplicación: Proceso de Bernoulli como modelo de flujo ATM
=
5 48 48
09/11/2003

∑q

∞

k −1

= p

∑q

∞

=
i

q n −1 = q n − n0 −1 p = P ( X = n − n0 ) n0 1 1− q − 1− q 1− q

53 bytes C.F. Belaustegui Goitia - Cadenas de Markovy Teoría de Colas 1 CC = 2.83 uSec @ 149.76 Mbps

3

Variables Binomial y de Poisson
Variable Binomial: La probabilidad de que el evento A, cuya probabilidad es P(A) = p, ocurra k veces en n pruebas es n pn (k ) =   p k (1 − p) n−k ,   k   n n!  =  k  k!(n − k )!   Variable de Poisson: Si p0/ πij(n)>0. Comunicantes: los estados i y j comunican si son accesibles entre sí. Seescribe i↔j. La comunicación es una relación de equivalencia: i↔j, j↔k ⇒ i↔k. Absorbente: Si es imposible abandonarlo: πii=1. Recurrente: El estado i es recurrente si la probabilidad de regresar alguna vez a él es 1. Periódico: Un estado es periódico con período d si sólo se puede regresar a él después de d, 2d, ..., nd pasos. Aperiódico o Ergódico: Periódico con período d=1. Se puede regresar a élen cualquier momento. Transitorio: La probabilidad de regresar al estado alguna vez es menor que 1.
09/11/2003 C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

Recurrente

• • • • •

f i = ∑ π ii (n) = 1
n =1

∞

Transitorio

f i = ∑ π ii (n) < 1
n =1

∞

16

Clases de Estados
• Cerrada: Si desde un estado interior no se puede alcanzar ningún estado exterior ala clase. Un estado absorbente es una clase cerrada con un único estado. Irreducible: Clase cerrada tal que ningún subclase propia es cerrada. En otros términos, la única clase cerrada es la de todos los estados. Dos estados pertenecen a un mismo conjunto si se comunican. Dos clases distintas deben ser disjuntas, pues si existe algún elemento común, los estados de una clase se pueden comunicarcon los de la otra, y así resultan ser de la misma clase.
Clase reducible Clase cerrada

•

• •

Estados absorbentes

Clase irreducible

09/11/2003

C.F. Belaustegui Goitia - Cadenas de Markov y Teoría de Colas

17

Clases de Cadenas
• Irreducible. Definiciones equivalentes: – – La que consiste en una única clase de equivalencia. El único conjunto cerrado es el de todos losestados.

En una cadena irreducible, todos los estados son recurrentes o son todos transitorios. En una cadena irreducible finita, no pueden ser todos los estados transitorios; luego, son todos recurrentes.

•

Reducible. Opciones:
1. 2. Tiene uno o más estados absorbentes. Tiene un subconjunto de estados S1 desde el cual no es posible alcanzar estados fuera de S1.

• • • •

Absorbente: la...