PROCESOS MARKOV

1. PROCESOS MARKOV

1.1. ESTADOS DEL SISTEMA:

Un modelo de Markov consiste en un conjunto de estados discretos. Este conjunto es exhaustivo y describe todos los posibles estados donde el sistema puede estar. La transición del estado i a j ocurre con una probabilidad pij

Podemos pensar en un modelo de Markov como una simple línea de transferencia.

Se puede pensar en dos máquinas y en un inventario. Cada máquina es descrita por su tiempo de operación, su tiempo para la falla y su tiempo para la reparación. El tiempo de proceso se refiere a la cantidad de tiempo en que demora hacer una parte. El tiempo para la falla, es el tiempo que ocurre entre la ultima reparación y el siguiente daño. El tiempo para reparación, es el tiempo que transcurre entre el ultimo daño y el momento en que la máquina esta disponible para operar. Estas cantidades pueden ser deterministicas, en estos casos se obtienen estados discretos y una cadena de Markov con transiciones discretas(o tiempos discretos en la cadena de Markov). También puede ser continuo con variables aleatorias.

Se asume que la primera máquina nunca deja de ser alimentada y la ultima maquina nunca es bloqueada.

Se modela para una maquina y así tener una idea básica de la cadena de Markov. En este caso el estado de la maquina se describe por su estatus, Wi, donde:

Wi = 1 máquina disponible

0 máquina en reparación

M1

Inventario

M2

La cadena se puede representar así:

Donde de 0 a 1 se da la probabilidad de repararse.

Donde de 1 a 0 se da la probabilidad de falla.

0

1

Estas probabilidades se obtienen al observar las máquinas en operación por un largo periodo de tiempo. Estos datos se pueden recopilar para determinar que porcentaje de tiempo la máquina esta siendo reparada e igual para el porcentaje de tiempo que la máquina esta disponible para el trabajo.

Ahora los estados de este proceso consisten en el estatus de cada máquina más la cantidad de material presente en el sistema. Específicamente, el estado del sistema es:

S=(n,W1,W2),

Donde :

.n= # de piezas en inventario + # piezas en la máquina 2 0<=n<=N

Ya que n, W1 y W2 son enteros, el sistema es descrito por un conjunto de estados mutuamente excluyentes y colectivamente exhaustivos S1, S2,......., Sm. Entonces el sistema puede estar solo en uno de estos estados en algún instante de tiempo dado.

El sistema puede experimentar un cambio de estado(o una transición de estado) en un instante de tiempo discreto de acuerdo a un conjunto de probabilidades. Permitamos que P[Si(k)]= probabilidad que el sistema este en el estado Si en el tiempo k.

Ahora se puede decir que un cambio de estado ocurrirá con probabilidad, P[Sj(k)]/Sa(k-1), Sb(k-2), Sc(k-3).......] 1<=j,a,b,c<=m k = 1,2,3....

Lo anteriores denota como la probabilidad de transición. Note que (j) podrá ser igual a (a), para el caso en que no cambie de estado.

1.2. LA CONDICIÓN DE MARKOV:

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.

1.3. PROBABILIDADES DE TRANSICIÓN:

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

 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 el sistema. Por ejemplo,

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

Si se escriben todos las m, se puede representar en forma matricial y obtener:

(P[S1(k+1)] P[S2(k+1)]……….P[Sm(k+1)])

P11 P12 ................. P1m

P21 P22 ................. P2m

=(P[S1(k+1)] P[S2(k+1)]……….P[Sm(k+1)]) . . ................. .

. . ................. .

Pm1 Pm2 ................. Pmm

O de la siguiente forma:

P(k+1) = P(k)P , k=0,1,2......

Para responder a la pregunta Q1 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......

Por ejemplo si se tiene la siguiente cadena de Markov de dos estados

De los estados del diagrama tenemos la siguiente matriz:

0.5 0.5

0.4 0.6

P=

Para encontrar P(k), se necesita Pk, que puede ser encontrada con una técnica como la de Cayley-Hamilton(este modelo es aplicado para una matriz 2x2, no se sabe cual es el modelo para otro tipo de matriz).

Pk= ((0.1)k-1-1)I + (10-(0.1) k-1)P

9 9

Donde I es la matriz identidad. Pk puede ser evaluada para un k especifico, entonces :

P(k) = P(0)Pk

En un caso de interés particular es en el que k tiende al infinito. Para este ejemplo:

4/9 5/9

4/9 5/9

Pk=

Con k tendiendo al infinito.

Claramente, Pk llega a una constante. Esto conlleva a otra propiedad la que puede ser vista con el rotulo de P(0)=(1 0). Entonces Pk=[4/9 5/9] con k tendiendo al infinito. Similarmente, si P(0)=(0

...