estocastcos

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 )!

3 4

8

P( X = 1) = p
P( X = 2) = (1 − p) p
L
P( X = n)= (1 − p) n−1 p = q n−1 p

n=22, k=7
1

Separación entre eventos: sea X= número de pruebas
hasta el primer éxito

13

15

21
1

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

3 4

8

15

21

X=n

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

P ( X = n, X > n0) P ( X = n)
=
=
P ( X > n0 )
P ( X > n0 )

q n −1 p
∞

∑q

k −1

=
p

k = n0 +1

=
5 48
48

13

n0

X=n

Aplicación: Proceso de Bernoulli como modelo
de flujo ATM

09/11/2003

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

q n −1
∞

∑q

i = n0

=
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 Markov y 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 )!

34

8

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

09/11/2003

13

1− k / n
pn (k + 1)
p n−k
a
a
=
⋅
=
⋅
n
→
→∞
1− p k +1 1− a / n k +1
pn (k )
k +1
a
pn ( k )
k +1
p(0) = lim pn (0) = lim (1 − p) n = lim (1 − a / n) n = e −a

pn (k + 1) =
n →∞

n=22, k=7
1

Variable de Poisson: Si p0/ πij(n)>0.

•Comunicantes: los estados i y j comunican si son accesibles entre
sí. Se escribe 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 él en 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 deEstados
•

•

•
•

Cerrada: Si desde un estado interior no se puede
alcanzar ningún estado exterior a la 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.
Dosclases distintas deben ser disjuntas, pues si
existe algún elemento común, los estados de una
clase se pueden comunicar con los de la otra, y así
resultan ser de la misma clase.

09/11/2003

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

Clase reducible
Clase cerrada

Estados absorbentes

Clase irreducible

17

Clases de Cadenas
•

Irreducible. Definiciones...