lunes, 6 de junio de 2011

CADENAS DE MARKOV


 

Condiciones generales:
 
Si P [Sj(k) / Sa(k-1), Sb(k-2), Sc(k-3).....] = P[Sj(k) / Sa(k-1)] para todo k, j,a, b, c,..... Entonces el sistema es un estado discreto de discretas transiciones de procesos de Markov. La implicación de esta condición es que la historia anterior del sistema a su llegada en (a) no tiene efecto en la transición a (j). En otras palabras, el sistema no tiene memoria.


Para una cadena de Markov, se definen las probabilidades de transición como:
pij  = P[Sj(k) / Si(k-1)]     1<= i,j <= m
y las pij  son independientes de (k). Estas probabilidades pueden ser incluidas en una matriz de transición,


P11
P12
........................
P1m
P21
P22
........................
P2m
P=
.
.
.
.
.
.
.
.
Pm1
Pm2
........................
Pmm




También note que las transiciones de probabilidad satisfacen
0<=pij<=1
y


 m
S pij =1,      i = 1,2,3...........,m
.j=1




Debido a que los estados son mutuamente excluyentes y colectivamente exhaustivos.
La matriz P, proporciona una completa descripción del proceso de Markov el cual se usara para responder numerosas preguntas sobre un sistema. Por ejemplo,

1. Cuál es la probabilidad que el sistema este en Si después de k transiciones si el estado en k=0 es conocido?
Se puede responder la pregunta así:
P[Sj(k+1)]=P[S1(k)p1j+P[S2(k)]p2j+......+P[Sm(k)]pmj,
Donde P[Sj(k+1)]=probabilidad que el sistema este en el estado Sj en el tiempo k+1.
En la ecuación anterior, j=1,2,.....,m. O de la siguiente forma:
P(k+1) = P(k)P , k=0,1,2......
Para responder a la pregunta 1 por inducción


P(1) =
P(0)P
P(2)=
P(1)P=
P(0)P2
.
.
.
.
.
.
P(k) =
P(0)Pk
k=0,1,2......


Clasificación de los estados:

1. Límite de las probabilidades de estado:
Si k tiende a infinito, P(k) llega a una constante, entonces el limite de las probabilidades de estado existe y son independientes de la condición inicial.
Si p es un vector 1 x m  definido como,
Limkàinfinito P(k)= p
Entonces p puede satisfacer  p =pP.
Para el ejemplo, esta ecuación se puede ser resueltacon la restricción
Sim pi =1  para obtener (p1       p2)

2. Estado transitorio
Si  es un estado transitorio si se puede dejar el estado pero nunca retornar a él.

3. Estado absorbente
Si es un estado absorbente si el sistema entra al estado y permanece ahí. Y el límite de la probabilidad de estado es 1. este estado es conocido también como estado trampa.

4. Cadena recurrente
Una cadena recurrente es un conjunto de estados de los que el sistema no puede salir. Un estado transitorio conduce al sistema dentro de este conjunto de estados. El sistema hace saltos dentro de este conjunto indefinidamente. La cadena recurrente es también llamada subcadena de Markov irreducible o de clases recurrentes.

Datos claves de la cadena de markov:

o   Cada cadena de Markov debe tener al menos una cadena recurrente
o   Una cadena recurrente es un estado absorbente generalizado
o   Un proceso de Markov que tiene una cadena recurrente será completamente ergódica desde dondequiera que el inicie finalizara en cadena recurrente
o   Si un proceso tiene dos o más cadenas recurrentes, entonces la propiedad ergódica no se mantiene en el tiempo
o   Un estado transitorio es un estado que ocupa el sistema antes de convertirse en una cadena recurrente

Comportamiento a largo plazo de una cadena regular

La notación X(n)=(x1(n),.....,xk(n))t representa la probabilidad de que una cadena se encuentre en cada uno de los estados en la etapa n.
Xc=Lim nàinfinito X(n)=LX(0) donde L=Lim nàinfinitoTn.

El vector Xc caracteriza el comportamiento a largo plazo de la cadena, ya que nos informa de la probabilidad de que la cadena se encuentre en cada uno de los estados cuando ha transcurrido un número grande de etapas. Al vector Xc se le llama distribución estacionaria de la cadena. El límite no siempre existe debido a la existencia de periodos.

"Se dice que una cadena de Markov con matriz de probabilidades de transición T (esta matriz es la transpuesta de la original) es regular si todos los elementos de matriz Tn son estrictamente positivos para algún valor de n."
Es decir, una cadena de Markov es regular si existe un número de etapas n tal que la probabilidad de la transición en n etapas entre cualquier par de estados es estrictamente positiva.

Cadenas ergódicas:

Si existe un n>0 tal que Pijn >0, i, j=0,1,2....m. la cadena de Markov, con esta propiedad, se llama ergódica. Entonces, Pijn = Sk=0 (Pikn * Pkj), luego pj =  Sk=0 (pk * Pkj) y como Sj=0 Pijn = 1, entonces Sj=0 pj =1

Teorema. Para una cadena de Markov ergódica, pj =Lim nàinfinito Pijn existe y pj (j pertenece {0,..,m}) es la única solución no negativa de pj. Entonces:
pj =  Sk=0 (pk * Pkj) y Sj=0 pj =1.

Límites ergódicos en la cadena de markov:

La relación fundamental en una cadena de Markov es: Pn =Mn P0. Y si nuestro interés es el comportamiento asintótico de Pn, es decir Lim nàinfinito Pn entonces el problema es encontrar las condiciones para que este límite exista y en caso de existir, ¿dependerá del estado inicial del sistema?
Bajo condiciones de “regularidad” la distribución asintótica existe y bajo estas condiciones la distribución en el límite será independiente de la distribución inicial.

Clasificación de los estados:



Recurrentes:
Si i=j y  Sinfn=1 fiin =1
·         Absorbentes si pii =1
·         Recurrentes nulos uii = inf
·         Recurrentes positivos uii < inf
·         Ergódico: recurrente positivo aperiódico
Transitorio o transiente: si hay alguna probabilidad positiva de no volver allí,  Sinfn=1 fiin <1
Estados
Efímero: no puede ser alcanzado desde ningún otro estado
 J es  Accesible, si pijn >0
Comunicados
Si i es accesible desde j
Si j es accesible desde i
Pertenecen a una clase: cadena irreductible
Periódico: tiene periodo
Aperiódico: no tiene periodo


Mostrando las entradas más recientes con la etiqueta CADENAS DE MARKOV Mostrar las entradas más antiguas
Mostrando las entradas más recientes con la etiqueta CADENAS DE MARKOV Mostrar las entradas más antiguas

viernes 3 de junio de 2011

CADENAS DE MARKOV


Las cadenas de markov reciben este nombre debido al matemático Andrei Andreevitch Markov  y consisten en un proceso discreto en el cual la probabilidad de que se lleve a cabo un evento es dependiente del evento inmediatamente anterior. Por lo tanto, la característica más destacada de esta herramienta es la capacidad de " recordar" el último evento y esto condiciona las posibilidades de los eventos futuros

Para llevar a cabo el desarrollo de la cadena de markov se requiere tener fundamentos matemáticos en:

1. Operaciones con matrices
  • Suma y resta
  • Multiplicación
  • Traspuesta
  • Inversa- Gauss-Jordan 
 2.    Probabilidad


Propiedad de Markov: "si se conoce la historia del sistema hasta su instante actual, su estado presente resume toda la información relevante para describir en probabilidad su estado futuro".

ELEMENTOS DE LA CADENA DE MARKOV

Estado: Una cadena de Markov es una secuencia X1, X2, X3, … de variables aleatorias, el rango de estas variables, es llamado espacio -estado, el valor de Xn es el estado del proceso en el tiempo n. Cuando un estado es igual a cero, significa que no hay vía directa de un estado a otro.

Matriz de transición: Es la matriz que representa la probabilidad de una población de moverse de un estado a otro.  Cumple con las siguientes condiciones:
  •   La matriz de transición debe ser cuadrada.
  •   La suma de las probabilidades por fila debe ser igual a 1.
Composición actual (Po): Representa la distribución actual de la distribución de la población, a partir de esta matriz se describen las probabilidades de su estado fututo.  El número de renglones de Po debe ser igual número de elementos del vector columna T.

Para comprender a cabalidad lo expresado anteriormente, desarrollaremos un ejemplo en el cual se reconozca la importancia de las cadenas de markov y los elementos que la conforman. 

EJEMPLO NO.1

Actualmente, en Colombia la distribución de la población según su operador celular se encuentra representada de la siguiente forma: el 40% está dominado por  Comcel, mientras que Tigo y Movistar presentan un porcentaje de participación en el mercado de 30% cada uno. Además se obtiene la presente información:
  
a)      Los individuos que están en Movistar tienen una probabilidad de 30% de quedarse en la misma operadora, una de 50% de cambiar a Tigo, y una de 20% para pasarse a Comcel.

b)       Los individuos que están en Tigo tienen una probabilidad de 70% de quedarse en la misma operadora, una de 10% de cambiar a Movistar, y una de 20% para pasarse a Comcel.  

c)       Los individuos que están en Comcel  tienen una probabilidad de 50% de quedarse en la misma operadora, una de 30% de cambiar a Tigo, y una de 20% para pasarse a Movistar.

 
SOLUCIÓN

Primero procedemos a reconocer cuales son los estados de la matriz.

La matriz de composición actual:

Po = [Movistar   Tigo   Comcel]
Po = [0,3     0,3   0,4]
La matriz de transición:

M: Movistar;  T: Tigo;  C: Comcel

Para hallar la participación de las telefonías celulares transcurrido un año, procedemos a multiplicar la composición actual de los operadores existentes por la matriz de transición de la siguiente manera:


Obteniendo así:
P1 = [0,2    0,48   0,32]

Una participación del 20%, 48% y 32% para Movistar, Tigo y Comcel respectivamente.

Para calcular el siguiente año procedemos a:

De esta manera se generan los siguientes resultados y se analizan las proyecciones de participación de los operadores celulares en diferentes periodos:

P1 = [0,20        0,48            0,32]
P2 = [0,172      0,532          0,296]
P3 = [0,164      0,547          0,288]
P4 = [0,1617    0,5517       0,2866]
P5 = [0,161      0,553          0,286]

Al realizar el ejercicio aplicando la formula enunciada anteriormente se definió como regla general:

ESTADO ESTABLE


El estado estable representa las probabilidades, y se calculan matemáticamente cuando al hallar las proyecciones en n periodos los valores son iguales, es decir, dejan de variar, al transcurrir n tiempo. Para el anterior ejercicio el estado estable es cuando:

P5 = [0,161      0,553          0,286]

Lo cual corresponde a una participación del 16,1%, 55,3% y 28,6% para Movistar, Tigo y Comcel respectivamente.

Ahora, si cambiamos los valores iniciales de la matriz de composición actual Pde la siguiente manera:
P0 = [0,6    0,2   0,2] se generan los siguientes valores:

P1 = [0,24        0,50            0,26]
P2 = [0,174      0,548          0,278]
P3 = [0,163      0,554          0,2834]
P4 = [0,161    0,554            0,285]

                Nota: se llegó más rápido al estado estable cambiando los valores iniciales.

Podemos concluir que el valor del estado estable es independiente de los valores iniciales.

En el proceso de hallar el estado estable, también se hace uso del método de Gauss, Gauss-jordan, entre otros.

Empleando el método de Gauss-Jordan



   
Nuevamente observamos que los valores del estado estable son:

L = [0,161      0,5535          0,2857]

Lo cual corresponde a una participación del 16,1%, 55,3% y 28,6% aproximadamente para Movistar, Tigo y Comcel respectivamente.

CONCEPTOS IMPORTANTES EN LAS CADENAS DE MARKOV:

ESTADO RECURRENTE: Un estado es recurrente si después de haber entrado a un estado, en el proceso definitivamente regresará a ese estado. Por consiguiente, un estado es recurrente si y solo si no es transitorio.

ESTADO TRANSITORIO: Un estado es transitorio si después de haber entrado a un estado no regresa a él.

ESTADO ABSORBENTE: Un estado es absorbente si después de haber entrado a  un estado nunca saldra de él..

MATRIZ REGULAR: Una matriz es regular si en sus consignas no presenta ningún estado 0 y 1.

MATRIZ ERGÓDICA: Una matriz es ergódica si todos sus estados son nulos, no periodicos y recurrentes.



MATRIZ ABSORBENTE


Una matriz es absorbente si presenta estados absorbentes, es decir, que presente en sus consignas la probabilidad en la matriz T, de permanecer en el mismo estado a lo largo del tiempo (igual a 1).

Ejemplo No.1:

La Universidad Bolívar a estudiado la trayectoria de sus estudiantes y a descubierto que: 

A.       70% de los estudiantes de nuevo ingreso regresan al año sgte, de segundo año el 15% volvera como estudiante de nuevo ingreso y el resto no regresara.

B.      El 75% de los estudiantes de segundo año volverán al año siguiente como estudiantes de tercer año, el 15% volverán como estudiantes de segundo año y el resto no regresara.  

C.      El 80% de los estudiantes de tercer año regresaran al año siguiente como estudiantes de último año, 10% volverá como estudiante de tercer año y el resto no regresara.

D.      El 85% de los estudiantes de último año se graduaran, y el 10% volverá como estudiante de último año y el resto no regresara. 
 
Nota: Supongamos que la U no permite que un estudiante que se ha dado de baja, vuelva y tampoco permite que se cambie de curso a mitad de curso.

1) Escriba la matriz de transición de estos datos.
2) ¿Cuál es la probabilidad de que se gradúe un estudiante de nuevo ingreso?

SOLUCIÓN
Reconocimiento de los estados:

Estado 1: Primer año. (P)
Estado 2: Segundo año. (S)
Estado 3: Tercer año. (T)
Estado 4: Último año. (U)
Estado 5: Graduado. (G)
Estado 6: No regresan (NR)

Respuestas:
  • La probabilidad de que se gradúe un estudiante de nuevo ingreso es 61 % aproximadamente.

Ejemplo No.2.

Almacenes Julio Parts vende partes de automóviles y camiones a empresas que cuentan con flotas de vehículos. Cuando una empresa compra a Julio Parts se le otorgan 3 meses para pagar. Si las cuentas no se saldan en ese periodo, Julio Parts cancela la cuenta, la remite a una agencia de cobranza y da por terminada las transacciones. Por lo tanto Julio Parts, clasifica sus cuentas en: nuevas, de un mes de atraso, pagadas o incobrables.

Julio Parts estudió sus antiguos registros y descubrió que: 

a.       El 70% de las cuentas nuevas se pagan en un mes.

b.      El 60% de las cuenta con un mes de retraso se pagan al final del mes. 

c.       El 50% de las cuentas con dos meses de retraso se pagan al final del último mes. 

d.      El 60% de las cuentas con tres meses de retraso se remiten a una agencia de cobranza.

se requiere:
1) Formar la matriz de transición.
2) Determinar si esa matriz de transición es regular, absorbente.
3) ¿Cuál es la probabilidad de que una nueva cuenta se liquide?
4) ¿Cuál es la probabilidad que una cuenta de un mes de retraso se vuelva incobrable?
5) Si las ventas de Julio Parts son en promedio de $125.000 al mes, ¿cuánto dinero se aceptara como deuda incobrable cada mes y cada año?

SOLUCIÓN:

Reconocimiento de los estados:

Estado 1: Cuentas nuevas. (N)
Estado 2: Cuentas un mes de atraso. (1)
Estado 3: Cuentas dos meses de atraso. (2)
Estado 4: Cuentas tres meses de atraso. (3)
Estado 5: Cuentas pagadas. (P)
Estado 6: Cuentas incobrables (I)



 Respuestas:
  • La matriz de transición no es regular y si es absorbente.
  • La probabilidad de que una nueva cuenta se liquide es del 96%
  • La probabilidad que una cuenta de un mes de retraso se vuelva incobrable es de 12%
  • Se aceptaría como deuda incobrable al mes $4500 y al año $5400
 



REFERENCIA BIBLIOGRAFICA: consultas Medardo Gonzales
 

No hay comentarios:

Publicar un comentario