I. CADENAS DE MARKOV PROCESOS ESTOCSTICOS Sonprocesosquedescribenfenmenosdinmicosdecomportamientoaleatorio.Es decir, a medida que se recorre un parmetro (que a menudo es el tiempo), el sistema avanza de un estado a otro en forma impredecible. Una o ms variables aleatorias representan una caracterstica mensurable del estado del sistema, y pueden ser de naturaleza: -DISCRETA por ejemplo, la cantidad de automviles esperando o recibiendo una atencin en una estacin de servicio -CONTINUA, como ser la presin de salida del vapor en una caldera Cuandoelestadodelsistemaquedadefinidoporvariablesdiscretas,elprocesode denominaprocesomarkoviano.Estetipodeprocesossepuedenestudiarconlas denominadasCADENASDEMARKOV,llamadasasenhonoralmatemticorusoque desarroll el mtodo en 1907, Andrei Adreyevich Markov. Amedidaqueelsistemaoperasobreelparmetrot,serealizanobservacionesala variable. Las mismas se pueden verificar: En forma permanente, por ejemplo la medicin de la temperatura de un fluido. En este caso el proceso se llama de parmetro continuo. Demaneradiscreta.Lospuntosdeobservacineneltiempopuedenestarigualmente espaciados(comoseraenelcasodelaobservacindelniveldestockdeunrepuestoa frecuenciamensual)ono(observacindeunniveldestockcuandosealcanzaelpuntode pedido).Puedeocurrirquelaobservacinserealiceporlaverificacindeuneventoque Parmetro t Parmetro t VARIABLE DISCRETA VARIABLE CONTINUA H.ROJO, M. MIRANDA 2 modifiqueelestadodelsistema(porejemplo,laefectivizacindelaventadeunproducto determinado).Encualquieradeestoscasos,sedicequeelprocesoesdeparmetro discreto. En lo sucesivo nos limitaremos a estudiar procesos de estas caractersticas. Losprocesosmarkovianospuedenserdeprimerordenodeordensuperior.Sonde primer orden cuando el estado del sistema en el instante t depende nicamente del estado del mismo en el instante t-1 y no de cmo evolucion para llegar a l. En este caso se dice quelacadenatieneunamemoriadeprimerorden,yaquerecuerdasolamenteelsuceso anterior. Sin, en cambio, el estado del sistema depende adems de otros sucesos en instantes anteriores, se dice que el proceso (o la cadena) es de orden superior. Cuando el conjunto de estados posibles que puede adoptar el sistema es finito, la cadena se llama finita. Nuestro estudio se limitar al anlisis de cadenas de Markov de primer orden, finitasydeparmetrodiscreto,lasquedescribenunagrancantidaddeprocesosfsico-econmicos de la realidad, como ser: anlisis de comportamientos de compra y lealtad a una marca (brand switching), estudio de reemplazo de equipos, planeamiento de necesidades de personal, anlisis de inventarios, anlisis de crditos, estudio de sistemas de colas, etc. Paso o transaccin: Eselavancedelprocesocuandoelsistemapasadeunestadoaotro.Elpasotiene asociada una probabilidad para cada transicin a los estados que el proceso puede seguir. Llamaremos: ijp : a la probabilidad condicional de que el sistema se encuentre en el estado j dado que en el paso anterior se encontraba en el estado i (o probabilidad de transicin de i a j en un paso). ) n (ijp : a la probabilidad condicional de que el sistema se encuentre en el estado j dado que n pasos atrs se encontraba en el estado i (o probabilidad de transicin de i a j en n pasos). En lo sucesivo supondremos que las probabilidades de transicin de un estado a otro, en un paso, no cambian con el tiempo; es decir, son estacionarias. Llamaremos adems: ijV : al vector probabilidad (o vector distribucin) en un paso. Cada elemento de este vector representa la probabilidad de pasar del estado i a cada uno de los estados que el proceso puede seguir: | |in ij 3 i 2 i 1 i ijp ... p .... p p p V = ) n (iV :alvectorprobabilidad(ovectordistribucin)ennpasos.Estevectorenumeralas probabilidadescondicionalesdepasaralosdiferentesestadosennpasos,dadoqueel estado actual es i: | |) n (in) n (ij) n (3 i) n (2 i) n (1 i) n (ip ... p .... p p p V =P:Matrizdetransicin(omatrizestocstica)deunpaso.Cadaelementodelamatriz representa la probabilidad de desplazarse de un estado a otro en una transicin: CADENAS DE MARKOV 3 N j 2 1S ... S ... S SP =Ni21S...S...SS(((((((((

) n (NN) n (Nj) n (2 N) n (1 N) n (iN) n (ij) n (2 i) n (1 i) n (N 2) n (j 2) n (22) n (21) n (N 1) n (j 1) n (12) n (11p p p p...p p p p...p p p pp ... p ... p p = (((((((((

) n (N) n (i) n (2) n (1V...V...VV Lasprobabilidadesdetransicinenunpasodebenserconocidas;esdecir,son parmetrosdelproblema. Unacadenaquedadefinidacuandose conocen las probabilidades de transicin, el nmero de estados y el estado actual del sistema. Representacin grfica: Las cadenas de Markov se pueden representar mediante grafos. Supongamos el siguiente ejemplo:unprocesopuedeadoptarsolamentetresestados(S1,S2yS3).Sielprocesose encuentraenelestadoS1,laprobabilidaddemantenerseenelestado1esde0,5,la probabilidad de pasar al estado S2 es de 0,3 y de pasar al estado S3, de 0,2. Por su parte, si el procesoseencuentraenelestadoS2,laprobabilidaddepasaralestadoS1esde0,1,lade mantenerse en el mismo estado S2 es d de 0,6, y la de pasar al estado S3 es de 0,3. Finalmente si el sistema se encuentra en el estado S3, la probabilidad de pasar al estado S1 es de 0,2, de pasar al estado S2 es de 0,4y de mantenerse en el mismo estado S3 es de 0,4.La matriz de transicin ser:

3 2 1S S SP =321SSS((((

4 , 0 4 , 0 2 , 03 , 0 6 , 0 1 , 02 , 0 3 , 0 5 , 0 Enlarepresentacingrfica,cadaestadoserepresentaconunnodo,mientrasquelas transicionesdeunpasoseindicanmedianteflechas,indicndoselaprobabilidadde transicin arriba de la misma. Para el ejemplo, el grafo correspondiente ser:

S1

S2

S3 0,3 0,5 0,1 0,2 0,3 0,4 0,2 0,6 0,4 H.ROJO, M. MIRANDA 4 Anlisis del rgimen transitorio: UnestudiointeresantequesepuedehacerconlascadenasdeMarkoveselpronstico delestadodelsistemadentrodeunacantidaddepasosoperodosdetiempo.Cuandose enfocaunlapsorelativamentecortodetiempo,elanlisissobreelsistemaseconocecomo transitorio o transiente. Supongamosunprocesosimplequepuedeadoptarsolamentedosestados(E1yE2)en dondelasprobabilidadesdeestadoenunpasoestndadasporlasiguientematrizde transicin: 2 1E E2 E1 E((

75 , 0 25 , 05 , 0 5 , 0

Este sistema se puede representar con el grafo siguiente: Si,ademsconocemoselestadoactualdelproceso,tendremosdefinidatotalmentela cadena. Esto significa que se pueden conocer la probabilidad de que el sistema se encuentre encualquieradelosestadosquepuedeasumirluegodeunnmerodeterminadode transacciones. Supongamosquesedeseanconocerlasprobabilidadesdeque,luegodedospasos,el sistemaseencuentreencadounodesusdosestadosE1yE2.Esteinterrogantesepodra responder a travs de la teora clsica de la probabilidad de la siguiente forma: Si el estado actual es E1: LaprobabilidaddequeelsistemaseencuentreenelestadoE1luegodedos transacciones dado que el estado actual es E1, es decir ) 2 (11p , es igual alaprobabilidaddequeelsistemaseencuentreen elestadoE1luegodelprimerpasoy que en el segundo paso la transicin E1 E1, es decir que haya cambio de estado, o E1 E2 E2 E1 E1 E2 E1

E1

E2 0,25 0,5 0,5 0,75 CADENAS DE MARKOV 5 laprobabilidaddequeelsistemaseencuentreenelestadoE2luegodelaprimera transaccin y que en el segundo paso la transaccin sea E2 E1, es decir, que haya cambio de estado. Matemticamente: 375 , 0 25 , 0 5 , 0 5 . 0 5 , 0 p p p p p21 12 11 11) 2 (11= + = + =De la misma forma, la probabilidad de que el sistema se encuentre en el estado E2 luego de dos pasos, dado que el estado actual es E1, es decir ) 2 (12p , es:625 , 0 75 , 0 5 , 0 5 . 0 5 , 0 p p p p p22 12 12 11) 2 (12= + = + =Si el estado actual es E2: La probabilidad de que, luego de dos pasos el sistema se encuentre en E1 es igual a3125 , 0 25 , 0 75 , 0 5 . 0 25 , 0 p p p p p21 22 11 21) 2 (21= + = + =Y, la probabilidad de que se encuentre en E2 es:6875 , 0 75 , 0 75 , 0 5 . 0 25 , 0 p p p p p22 22 12 21) 2 (22= + = + =Deestaforma,hemosdescritotodaslasprobabilidadesasociadasacadaunodelos estadosdelsistemaluegodedospasos.Estainformacinsepuederesumirenlamatrizde transicin de dos pasos: ((

+ + + + =((

=22 22 12 21 21 22 11 2122 12 12 11 21 12 11 11) 2 (22) 2 (21) 2 (12) 2 (11 ) 2 (p p p p p p p pp p p p p p p pp pp pPCadafiladeestamatrizes,comoyahemosdefinido,unvectordeprobabilidadesde transicin en dos pasos, es decir: ((

=) 2 (2) 2 (1 ) 2 (VVPEl vector | |22 12 12 11 21 12 11 11) 2 (1p p p p p p p p V + + =contiene las probabilidades de transicin en dos pasos cuando el estado actual es E1, mientras que el vector | |22 22 12 21 21 22 11 21) 2 (2p p p p p p p p V + + =enuncia las probabilidades de transicin en dos pasos cuando el estado actual es E2. E2 E2 E2 E1 E1 E2 E1 H.ROJO, M. MIRANDA 6 Estosvectores,querespondenalosinterrogantesplanteados,puedencalcularse fcilmentehaciendoelproductodelvectordetransicindeunpasoporlamatrizde transicin ) 2 (1) 1 (1V P V = Es decir: | | | |22 12 12 11 21 12 11 1122 2112 1112 11p p p p p p p pp pp pp p + + =((

En nuestro ejemplo: | | | | 625 , 0 375 , 075 , 0 25 , 05 , 0 5 , 05 , 0 5 , 0 =((

Por su parte, ) 2 (2) 1 (2V P V = Es decir: | | | |22 22 12 21 21 22 11 2122 2112 1122 21p p p p p p p pp pp pp p + + =((

En nuestro ejemplo: | | | | 6875 , 0 3125 , 075 , 0 25 , 05 , 0 5 , 075 , 0 25 , 0 =((

De manera ms sencilla an, se puede responder a los interrogantes de nuestro problema calculando directamente la matriz P(2) que, como se observa, es P2: ((

+ + + + =((

((

= =22 22 12 21 21 22 11 2122 12 12 11 21 12 11 1122 2112 1122 2112 11 2 ) 2 (p p p p p p p pp p p p p p p pp pp pp pp pP PEs decir, cada elemento enuncia la probabilidad de transicin en dos pasos para los dos estados y para cada estado inicial. Siquisiramoshallarlasprobabilidadesasociadasacadaestadoluegodetrespasos, cuando el estado actual es E1, la respuesta se puede obtener, ya sea mediante el producto del vector de transicin en dos pasos por la matriz de transicin: ) 3 (1) 2 (1V P V = (1) obienmultiplicandoelvectordetransicinenunpasoporlamatrizdetransicinendos pasos: ) 3 (1) 2 (1V P V = (1') En efecto, el primer producto, para nuestro ejemplo, es: | | | |22) 2 (12 12) 2 (11 21) 2 (12 11) 2 (1122 2112 11 ) 2 (12) 2 (11p p p p p p p pp pp pp p + + =((

CADENAS DE MARKOV 7 es decir: | | | | 65625 , 0 34375 , 075 , 0 25 , 05 , 0 5 , 0625 , 0 375 , 0 =((

y el segundo producto es: | | | |) 2 (22 12) 2 (12 11) 2 (21 12) 2 (12 11) 2 (22) 2 (21) 2 (12) 2 (1112 11p p p p p p p pp pp pp p + + =((

es decir: | | | | 65625 , 0 34375 , 06875 , 0 3125 , 0625 , 0 375 , 05 , 0 5 , 0 =((

Delmismomodo,parahallarlasprobabilidadesasociadasacadaestadocuandoel estado actual es E2 lo podemos hacer mediante: ) 3 (2) 2 (2V P V = (2) o bien ) 3 (2) 2 (2V P V = (2') En efecto, el primer producto es: | | | |22) 2 (22 12) 2 (21 21) 2 (22 11) 2 (2122 2112 11 ) 2 (22) 2 (21p p p p p p p pp pp pp p + + =((

o sea: | | | | 671875 , 0 328125 , 075 , 0 25 , 05 , 0 5 , 06875 , 0 3125 , 0 =((

y el segundo producto es: | | | |) 2 (22 22) 2 (12 21) 2 (21 22) 2 (11 21) 2 (22) 2 (21) 2 (12) 2 (1122 21p p p p p p p pp pp pp p + + =((

es decir: | | | | 671875 , 0 328125 , 06875 , 0 3125 , 0625 , 0 375 , 075 , 0 25 , 0 =((

Laexpresiones(1)y(2),osusequivalentes(1')y(2')sonlasdenominadasecuaciones de Chapman-Kolmogorov. A los mismos resultados se puede arribar en forma ms sencilla hallando la matriz P(3): P P P P2 3 ) 3 ( = =En efecto: ((

+ + + + =((

((

22) 2 (22 12) 2 (21 21) 2 (22 11) 2 (2122) 2 (12 12) 2 (11 21) 2 (12 11) 2 (1122 2112 11) 2 (22) 2 (21) 2 (12) 2 (11p p p p p p p pp p p p p p p pp pp pp pp p H.ROJO, M. MIRANDA 8 Para el ejemplo: ((

=((

((

671875 , 0 328125 , 065625 , 0 34375 , 075 , 0 25 , 05 , 0 5 , 06875 , 0 3125 , 0625 , 0 375 , 0 Siguiendo el procedimiento, podemos extender este anlisis para un paso n cualquiera aplicando las ecuaciones de Chapman-Kolmogorov, cuyas expresiones generales son:) 1 n (i) n (iV V= (3) o) 1 n (1niP V V = (3') Estos productos matriciales nos dicen que la probabilidad de pasar de un estado i a un estado j en n pasos para un proceso de Markov de M estados viene dada por alguna de las siguientes expresiones: = =M0 k) 1 n (kj ikp p) n (ijp(4) o = =M0 kkj) 1 n (ikp p) n (ijp (4') Endefinitiva,paraconocerlaprobabilidadde que elprocesose encuentre enelestado jdespusdenperodos,cuandoenlaactualidadseencuentreenelestadoi,debe calcularse simplemente la matriz P(n): n ) n (P P =(5) es decir, la matriz que se indica a continuacin en forma genrica: n11 11 1111 11 1111 11 11) n (MM) n (2 M) n (1 M) n (M 2) n (22) n (21) n (M 1) n (12) n (11p ... p p... ... ... ...p ... p pp ... p pp ... p p... ... ... ...p ... p pp ... p pP(((((

=((((((

=Volviendo al ejemplo, para calcular las probabilidades asociadas a cuatro pasos, debera calcularse la matriz P(4 )= P4: ((

=6680 , 0 3320 , 06641 , 0 3359 , 0P4 Estoes,sielestadoinicialesE1,laprobabilidaddequeelprocesoseencuentreenel mismo estado E1 luego de 4 pasos es 0,3359, y que se halle en el estado E2 es 0,6641. Si en cambioelestadoinicialesE2,laprobabilidaddequeseencuentreenE1luegode4 transacciones es 0,3320 y de que se encuentre en E2, es de 0,6680. CADENAS DE MARKOV 9 CLASIFICACIN DE LOS ESTADOS DE UNA CADENA DE MARKOV 1. Estados accesibles Un estado Sj es accesible desde un estado Si si se cumple que para algn paso n 1 se cumple que0 p) n (ij> , y se escribe: Si Sj La accesibilidad es una propiedad transitiva, es decirsiSi SjySj SkSi Sk Tomemosunejemplodeunacadena,indicandoconunaxunvalordepij>0,en donde la matriz de transicin es: 4 3 2 1(((((

xxx xx x4321 El estado 3 es accesible desde 2 porque desde 2 se puede ir a 1 y de 1 a 3. El estado 2, sin embargo no es accesible desde 3. 2. Estados comunicantes Dos estados Si y Sj se comunican si Sj es accesible desde Si y si Si es accesible desde Sj, y se escribe: Si Sj Enelejemploanterior,losestados1y2soncomunicantes.Losestados1y3,en cambio, no lo son. La comunicacin es una propiedad transitiva, es decir siSi SjySj SkSi Sk 3. Estados recurrentes UnestadoSiesrecurrentesi,unavezqueelprocesoloalcanza,regresaral.Por ejemplo:

1 2

3

4 H.ROJO, M. MIRANDA 10 6 5 4 3 2 1654321(((((((((

x x xx xxx xxx x x Losestados4,5y6sonrecurrentes.Elestado3,encambio,esnorecurrente(o transitorio) ya que existe una posibilidad de que no se regrese nunca a l. Uncasoespecialdeestadorecurrenteeseldenominadoestadoabsorbente,quees aquelalque,sielprocesoloalcanza,laprobabilidaddeabandonarloescero.Esdecir,un estado Si es absorbente si la probabilidad de transicin en un paso pii = 1. En el ejemplo, el estado 2 es absorbente. 4. Clase y ciclo Los estados que se comunican pertenecen a una misma clase. En el ejemplo anterior, los estados 4, 5 y 6 forman una clase. Unaclasepuede consistirenunsoloestado.Porejemplo, elestado1forma unaclase, como as tambin ocurre con los estados 2 y 3 que forman una clase cada uno. Esto es, en el ejemplo, la cadena tiene cuatro clases. Un conjunto de estados recurrentes y que se comunican forman un ciclo. Los estados 4, 5 y 6 constituyen un ciclo. El ciclo tiene la particularidad de que, una vez que se alcanza uno de sus estados, el proceso se queda definitivamente en l. 5. Estados sin retorno Unestadoquenosecomunicaconningnotroestado,nisiquieraconsigomismo,se llama sin retorno. En el siguiente ejemplo, el estado 3 es un estado sin retorno:

1 2

3

4

5 6 CADENAS DE MARKOV 11 Elestadosinretornoesuncasoparticulardeestadotransitorioendonde,unavez alcanzado, la probabilidad de que el proceso no regrese nunca a l es igual a 1. La matriz de transicin de este ejemplo es: 5 4 3 2 154321(((((((

x xx x1x x xx x CLASIFICACIN DE LAS CADENAS DE MARKOV 1. Cadenas reducibles o separables UnacadenadeMarkovesreduciblecuandonotodossusestadossoncomunicantes(o sea, cuando hay por lo menos un estado sin retorno) . Esto significa que se la puede reducir o separar en clases comunicantes y/o estados sin retorno. Enelejemploanterior,lacadenasepuedereducirendosclases(1,2)y(4,5),yenel estado sin retorno (3).La clase (4,5) constituye un ciclo. Generalmente, las cadenas reducibles se encierran en ciclos, como ocurre en el ejemplo. 2. Cadenas irreductibles o ergdicas Son aquellas en las que todos sus estados se comunican, tal como ocurre en el siguiente ejemplo:

1 2

3

4

5 H.ROJO, M. MIRANDA 12 Indicando con x los elementos positivos, tendremos que la matriz de transicin tiene la siguiente configuracin: 6 5 4 3 2 1654321(((((((((

x xx x xx xx xx x xx x Losestadosdeunacadenairreductiblesontodosrecurrentes.Estascadenassellaman as porque forman una sola clase comunicante (se pueden reducir nicamente a una clase). RGIMEN PERMANENTE Unapropiedadquetienelascadenasergdicasesqueluegodeinfinitastransacciones, lasposibilidadesseestabilizanenvaloreslmites,independientementedesuestadoinicial. Por ejemplo, la siguiente cadena:

S1

S2

S3 0,5 0,5 1 0,6 0,2 0,2

1

2

6

5

3

4 CADENAS DE MARKOV 13

3 2 1S S SP =321SSS((((

16 , 0 2 , 0 2 , 05 , 0 5 , 0 es irreductible. Observando las distintas potencias de la matriz de transicin: P2 =((((

50 , 0 50 , 012 , 0 14 , 0 74 , 030 , 0 35 , 0 35 , 0 P4 =((((

2100 , 0 2450 , 0 5450 , 02388 , 0 3386 , 0 4226 , 01470 , 0 3215 , 0 5315 , 0 P8 =((((

1827 , 0 3096 , 0 5077 , 01931 , 0 3090 , 0 4979 , 01858 , 0 3158 , 0 4985 , 0 P16 =nn19 18P... P P1875 , 0 , 03125 5000 , 01875 , 0 3125 , 0 5000 , 01875 , 0 3125 , 0 5000 , 0 = = = =((((

Vemosque,amedidaqueaumentan, loselementos ) n (ijp tiendenaunlmitefijo,de maneraquecadavector niV esigualparacadai.Esdecir,paraunvectorden suficientemente grande se cumple que: * 1 n n 1 niniV V V V V = = = =+ + Cadaelementodeestevector(V*)representalasproporcionesdelaspermanenciadel proceso en los distintos estados de la cadena luego de un perodo largo de tiempo, lo que se conoce con el nombre de distribucin de estados lmites. Estetipodecadenassepresentanenunagrandiversidaddeprocesosfsicos-econmicos,ysondegranintersenelestudiodelrgimenpermanentedeesossistemas, como se ver ms adelante. Las cadenas ergdicas se pueden clasificar en aperidicas (tambin llamadas regulares) y peridicas. UnacadenadeMarkovesregularsi algunadelas potenciasdesu matrizdetransicin contiene slo elementos positivos; por ejemplo: H.ROJO, M. MIRANDA 14 P = (((((((

x xx x xx xx x xx x x xP2 = (((((((

x x x x xx x x xx x x xx x x x xx x x x xP4 = (((((((

x x x x xx x x x xx x x x xx x x x xx x x x x Unacadena,esperidicacuandonopuedeencontrarseunapotenciadePparalacual todos los elementos sean positivos. Por ejemplo, la siguiente cadena es peridica: P = (((((

x xx xx xx x P2 = (((((

x xx xx xx xP3 = (((((

x xx xx xx xP4 = (((((

x xx xx xx x en donde se cumple que P = P3 =P5 = Pn(para n impar),y P2 = P4 =P6 = Pm(para m impar). Sibienenlascadenasperidicasnopuedenalcanzarsevaloreslmites,albuscar potencias den,elprocesoseestabiliza envaloresdeprobabilidades lmitesalargoplazo que,comoenelcasoanterior,representanporcentajesdetiempoenlosqueelproceso permanece en cada estado. En definitiva, en cadenas de Markov ergdicas, a medida que se progresa lo suficiente, lasprobabilidadesseestabilizanenvaloreslmites,independientementedelestadoinicial. Una vez alcanzada esta situacin, se dice que se ha llegado al rgimen permanente. Elclculodelasprobabilidadesenrgimenpermanenteparacadenasnoperidicasse puedehacersimplementecalculandounapotenciagrandedelamatrizdetransicin.Por ejemplo, tal como hemos visto ms arriba la matriz P =((((

16 , 0 2 , 0 2 , 05 , 0 5 , 0

elevada a una potencia n grande nos daba como resultado:Pn =((((

1875 , 0 , 03125 5000 , 01875 , 0 3125 , 0 5000 , 01875 , 0 3125 , 0 5000 , 0 Esto significa que, en estado de rgimen permanente, la probabilidad de que el sistema se encuentre en el estado E1 es del 50%, en el estado E2, de 31,25%, y en E3, del 18,75%. Vemos que, en rgimen permanente, cada vector niV , para n grande, tiende a hacerse igual para todos los estados i: 1 niniV V+=CADENAS DE MARKOV 15 Pero, como adems, por Chapman-Kolgomorov (3), tenemos que P V Vni1 ni =+ resulta que existir un vector V* tal que P V V* * = (5) ElvectorV*contienelasprobabilidades,encondicionesdergimenpermanente asociadasacadaestadodelprocesos.Enformageneral,paraunacadenadeNestados, tendremos: | | ) N ( p ... ) j ( p ... ) 2 ( p ) 1 ( p V*=Para hallar sus elementos, planteamos el siguiente sistema de ecuaciones: = ==1 ) i ( pP V VN1 j* * es decir: | | | |= + + + += 1 ) N ( p ... ) j ( p ... ) 2 ( p ) 1 ( p) N ( p ... ) j ( p ... ) 2 ( p ) 1 ( p P ) N ( p ... ) j ( p ... ) 2 ( p ) 1 ( p Expandiendoelproductomatricial,obtendremosunsistemadeN+1incgnitas,porlo que se puede eliminar cualquiera de las primeras N ecuaciones para resolver. La ecuacin que establece que la suma de las probabilidades es igual a 1 no se puede eliminar, ya que las primeras satisfacen la solucin trivial. Tomemos el ejemplo anterior: P =((((

16 , 0 2 , 0 2 , 05 , 0 5 , 0

En rgimen permanente, tendremos: | | | |= + +=((((

1 ) 3 ( p ) 2 ( p ) 1 ( p) 3 ( p ) 2 ( p ) 1 ( p16 , 0 2 , 0 2 , 05 , 0 5 , 0) 3 ( p ) 2 ( p ) 1 ( p(6) Realizando el producto matricial y eliminando una ecuacin: = + += + = + + 1 ) 3 ( p ) 2 ( p ) 1 ( p) 2 ( p 2 , 0 ) 2 ( p 5 , 0 ) 1 ( p) 1 ( p ) 3 ( p 2 , 0 ) 2 ( p 5 , 0 ) 1 ( p La solucin de este sistema de 3 ecuaciones con 3 incgnitas es: H.ROJO, M. MIRANDA 16 ===1875 , 0 ) 3 ( p3125 , 0 ) 2 ( p5000 , 0 ) 1 ( p Esto es, el vector de probabilidades lmite en rgimen permanente es: | | 1875 , 0 3125 , 0 5000 , 0 V*=Elsistema(6)sepuedeformularenformasimplificadaincluyendolaecuacindela sumadeprobabilidadesenlamatrizdetransicin.Paraellosereemplazaunvector cualquieradelamatrizporunvectordeelementos1,yenelvectorfilaresultadodel productomatricialsereemplazapor1elelementocorrespondiente.Suponiendoquese elige anular la ecuacin correspondiente al estado 3, el sistema (6) quedara formulado como sigue: | | | | 1 ) 2 ( p ) 1 ( p1 11 2 , 0 2 , 01 5 , 0 5 , 0) 3 ( p ) 2 ( p ) 1 ( p =((((

(6') Si la cadena es peridica, el lmite Pn (para n ) no existe pero, sin embargo, existen probabilidades lmite de estado estacionario que se calculan con el procedimiento visto. Por ejemplo, la matriz ((

=11Pes peridica, ya que n 6 4 2P ... P P11P = = =((

=para n par, y m 5 3P ... P P11P = = =((

=para m impar. Planteandoelsistemadeecuacionesdelproductomatricial,comohemosvisto, eliminandounadeestasecuacionesyagregandolaecuacinqueestablecequelosestados son mutuamente excluyentes, tendremos: | | | |= +=((

1 ) 2 ( p ) 1 ( p) 2 ( p ) 1 ( p11) 2 ( p ) 1 ( p(7) = += + 1 ) 2 ( p ) 1 ( p) 1 ( p 1 ) 2 ( p 0 ) 1 ( p Cuya solucin es p(1)=0,5 y p(2)=0,5 Comomencionamosanteriormente,elsistema(7)sepudohaberformuladoenforma simplificada, como sigue: CADENAS DE MARKOV 17 | | | | 1 ) 1 ( p1 11) 2 ( p ) 1 ( p =((

(7') Esimportantedestacarqueenlascadenasperidicaslaprobabilidaddetransicindel estadoialjencualquierpasonsiguesiendopij.Lasprobabilidadeslmitesp(i) representan el porcentaje del tiempo que, a largo plazo, el sistema permanece en cada estado i. MTODO DE SUMA DE FLUJOS Otra forma de plantear el sistema de ecuaciones para el rgimen estacionario en cadenas de Markov ergdicas es a travs del denominado mtodo de suma de flujos. Este mtodo est basado en el balance de los nodos que representan los estados. Para que el sistema est en equilibrio, condicin que se cumple a largo plazo (es decir en rgimen permanente), debe verificarsequeelflujodeprobabilidadesqueconcurrenaunnodoseaigualalflujode probabilidades que de l emergen. Es decir, para un estado i cualquiera: = kkijijp ) k ( p p ) i ( pendondejrepresentaelconjuntodeestadosalosqueelprocesopuedepasardesdeel estado i en un paso, y k el conjunto de estados desde los que puede acceder al estado i en un paso. Tomemos el ejemplo planteado con anterioridad: Los balances de los nodos son: BALANCE EN NODO S1:1 ) 3 ( p 2 , 0 ) 2 ( p 5 , 0 ) 1 ( p + = BALANCE EN NODO S2:| | 5 , 0 ) 1 ( p 6 , 0 2 , 0 ) 2 ( p = + BALANCE EN NODO S3:| | 5 , 0 ) 1 ( p 6 , 0 2 , 0 ) 2 ( p = + Obviamente,enunnodocualquieraelflujoprobabilsticodelaprobabilidadde permanecerenelmismonodoseanula.PorejemploenelcasodelnodoS1habrunflujo saliente p(1)0,5 que se anula con el flujo entrante p(1)0,5. Endefinitiva,elsistemadeecuacionesquedaplanteadoeliminandocualquieradelas ecuaciones anteriores y agregando la de la suma de probabilidades de estado. Por ejemplo: = + += + = + + 1 ) 3 ( p ) 2 ( p ) 1 ( p) 2 ( p 2 , 0 ) 2 ( p 5 , 0 ) 1 ( p) 1 ( p ) 3 ( p 2 , 0 ) 2 ( p 5 , 0 ) 1 ( p

S1

S2

S3 0,5 0,5 1 0,6 0,2 0,2 H.ROJO, M. MIRANDA 18 Cuya resolucin es | | 1875 , 0 3125 , 0 5000 , 0 V*=Veamos otro caso para ejemplificar el mtodo de suma de flujos aplicado a una cadena peridica: P =((((

15 , 0 5 , 01

cuya representacin grfica es: El sistema de ecuaciones se puede plantear balanceando, por ejemplo, los nodos 1 y 3: = + + = = 1 ) 3 ( p ) 2 ( p ) 1 ( p5 , 0 ) 2 ( p 1 ) 3 ( p5 , 0 ) 2 ( p 1 ) 1 ( p que nos lleva al siguiente resultado: | | 25 , 0 50 , 0 25 , 0 V*= Ejemplo 1: Serequieredeterminarlasprobabilidadesdeestadoenrgimenpermanenteparaun sistemadecolasdeunsolocanalyqueadmiteunsololugardeespera,conprocesosde arribo de clientes Poisson (con media =8 cl/h) y de servicio de clientes en el canal tambin Poisson (con media =10 cl/h). La poblacin de clientes puede considerarse infinita. Resolucin: La representacin grfica de este sistema de colas es la siguiente:

1

2

3 1 0,5 0,5 1 CADENAS DE MARKOV 19 Llamando: n a la tasa de ingreso de clientes al sistema, dado que la velocidad media de llegadas es y que el estado del sistema es n, y n a la tasa de egreso de clientes del sistema, dado que la velocidad media de atencin es y que el estado del sistema es n.Dado que se trata de un sistema que no admite ms de un lugar en cola, tendremos que los valores de n sern: == = 2 n para 01 , 0 n paran y, dado que se trata de un sistema con un solo canal de atencin tendremos que = == 2 , 1 n para0 n para 0n Laprobabilidadesdequeunclientequearribaalsistemaingreseenlydequeun clientequeseestatendiendoenelcanalegresedelsistema,enunintervalodetiempode tiempotmuypequeo(tantocomoparasuponerquenosepuedeproducirmsdeun evento) estn dadas, respectivamente, por: p(ingreso) = nt p(egreso) = nt dado que los procesos son poissonianos. En consecuencia: Si el sistema se encuentra en el estado 0, tendremos que: la probabilidad de que se mantenga en el mismo estado 0 en un intervalo de tiempo t(muychico),correspondienteaunpasodelprocesomarkoviano,ser igualala probabilidad de que no haya ningn ingreso, es decir:p(0,0) = 1-t mientras que la probabilidad de que pase al estado 1 es la probabilidad de que haya un ingreso, o sea: H.ROJO, M. MIRANDA 20 p(0,1) = t. Si el estado es 1, tendremos que la probabilidad de pasar al estado 0 es igual a la probabilidad de que en ese intervalo se produzca un egreso (t) y ningn ingreso (1-t): ( ) t t 1 t ) 0 , 1 ( p = =dadoqueelintervaloteslosuficientementechicocomoparasuponerquet2es igual a cero. la probabilidad de permanecer en el propio estado 1 es igual a la probabilidad de que no haya ningn ingreso ni ningn egreso( ) ( ) t t 1 t 1 t 1 ) 1 , 1 ( p = =y la probabilidad de pasar al estado 2 es igual a la probabilidad de que haya un ingreso a la vez que no se produzca ningn egreso: ( ) ( ) t t 1 t 1 t ) 2 , 1 ( p = =Finalmente,Si el estado del sistema es 2: laprobabilidaddepasaralestado1enunpasoesigualalaprobabilidadde quese produzca un egreso t ) 1 , 2 ( p =yla probabilidad de permanecer en el mismo estado 2 es igual a la probabilidad de que no se produzca un egreso: ( ) t 1 ) 2 , 2 ( p = En definitiva, la matriz de transicin para el sistema ser la siguiente: 2 1 0210P =((((

t 1 tt t t 1 tt t 1 En rgimen permanente se cumple que: | | | | ) 2 ( p ) 1 ( p ) 0 ( pt 1 tt t t 1 tt t 1) 2 ( p ) 1 ( p ) 0 ( p =((((

Realizando el producto matricial de dos vectores tendremos: ( ) ) 0 ( p t ) 1 ( p t 1 ) 0 ( p = + CADENAS DE MARKOV 21 0 ) 0 ( p t ) 1 ( p t ) 0 ( p ) 0 ( p = + 0 t ) 1 ( p t ) 0 ( p = + = ) 0 ( p ) 1 ( p( ) ) 2 ( p t 1 ) 2 ( p t ) 1 ( p = + ) 2 ( p t ) 2 ( p ) 2 ( p t ) 1 ( p = + = ) 1 ( p ) 2 ( p2) 0 ( p ) 2 ( p||.|

\| =Llamando = yconsiderandolaecuacincorrespondientealasumadelas probabilidades, tendremos: 1 ) 2 ( p ) 1 ( p ) 0 ( p = + +1 ) 0 ( p ) 0 ( p ) 0 ( p2= + +| | 1 1 ) 0 ( p2= + + 211) 0 ( p + +=Para los datos del problema (=8 cl/h y =10 cl/h), tendremos el siguiente resultado: 4098 , 08 , 0 8 , 0 11) 0 ( p2 =+ +=3278 , 0 8 , 0 ) 0 ( p ) 1 ( p = =2623 , 0 8 , 0 ) 0 ( p ) 2 ( p2= =Como hemos podido observar, los valores de t se simplifican al plantear las ecuaciones de estado para el rgimen permanente, por lo que se podran obviar al formular los planteos delasprobabilidadesdetransicin.Elsistemadeecuacionesdelproblema,expresadoen formasimplificada,considerandoestecomentarioyteniendolasconsideracionesexpuestas ms arriba, quedara: | | | | 1 ) 1 ( p ) 0 ( p11 11 1) 2 ( p ) 1 ( p ) 0 ( p =((((

Sepodrahaberarribadoalmismosistemadeecuaciones,anenformamssencilla, aplicando el mtodo de suma de flujos: H.ROJO, M. MIRANDA 22 NODO 0: = ) 1 ( p ) 0 ( p = ) 0 ( p ) 1 ( pNODO 2: = ) 1 ( p ) 2 ( p 2 = = ) 0 p( ) 1 ( p ) 2 ( pSUMA:1 ) 2 ( p ) 1 ( p ) 0 ( p = + + 211) 0 ( p + += 3. Cadenas absorbentes: Una cadena de Markov es absorbente si tiene por lo menos un estado absorbente, y si esposibleaccederdesdecadaestadonoabsorbentehastaporlomenosunestado absorbente (no necesariamente en un paso). Recordemosqueunestadoabsorbenteesunestadoquenopuedeserabandonado;es decir,unavezalcanzadoesimposibledejarlo,porloqueelprocesotermina,obiense detiene para comenzar nuevamente a partir de otro estado. Unestadojabsorbenteseidentificaporquetieneunaprobabilidadunitariapjjenla matriz de transicin. Por ejemplo, el estado 3 de la siguiente cadena es absorbente: 3 2 1P = 321((((

15 , 0 5 , 03 , 0 7 , 0 Ejemplos de estados absorbentes, en donde el proceso se termina (o se detiene) una vez alcanzados, pueden ser:

1 2

3 0,7

0,3

0,5

0,5

1

0

1

2 t1-t tt 1-t t 1-t-t CADENAS DE MARKOV 23 el pago de una factura la realizacin de un contrato, la venta de un activo fijo, el despido de un empleado, etc. A menudo, las caractersticas que interesa conocer en este tipo de procesos son: el nmero promedio de pasos que tarda el proceso en absorberse, y laprobabilidaddequeelprocesoseaabsorbidoporunestadodeterminadocuandoel sistema tiene varios estados absorbentes. Una matriz absorbente puede reagruparse en cuatro submatrices, lo que se conoce como formacannica.Supongamosunprocesodeaestadosabsorbentesynestadosno absorbentes. La matriz cannica tiene la siguiente estructura: en donde: I (a x a):Matrizidentidad.Cadaelementorepresentalaprobabilidaddepermanecer enun estado absorbente en un paso. 0 (a x n):Matriznula.Cadaelementorepresentalaprobabilidaddepasardeunestado absorbente a uno no absorbente en un paso. A (n x a):Matriz de estados absorbentes. Cada elemento representa la probabilidad de pasar de un estado no absorbente a uno absorbente en un paso. N (n x n):Matrizdeestadosnoabsorbentes.Cadaelementorepresentalaprobabilidadde pasar de un estado no absorbente a otro no absorbente en un paso. Tomemos por ejemplo, la siguiente cadena que tiene dos estados absorbentes (el 1 y el 4): La matriz de transicin correspondiente es:

1 3

2 0,5

0,25

0,5

0,75

1 4

1 I 0 A N a estadosn estados a estados n estados H.ROJO, M. MIRANDA 24 4 3 2 1P = 4321(((((

175 , 0 25 , 0150 , 0 50 , 0 Reagrupando a la matriz cannica correspondiente: 3 1 4 2

3142(((((

25 , 0 75 , 050 , 0 50 , 011 Este formato de la matriz de transicin nos permitir determinar: 1.El nmero de pasos (o transacciones) promedio que transcurren hasta que el proceso se absorbe. 2.Elnmeropromediodevecesqueelprocesopasaporcadaestadoantesde absorberse. 3.La probabilidad de que el proceso se absorba en un estado determinado. 1.Determinacindelnmerodepasospromedioquetranscurrenhastaqueelprocesose absorbe, comenzando en un estado i no absorbente. Llamemosnal vector que indica la cantidad esperada de transacciones requeridas hasta que el proceso se absorbe, dado que se encuentra en un estado no absorbente particular. | | 1 ... A N 4 A N . 3 A N 2 A n3 2 + + + + =Elvector1 A indicalasprobabilidaddequeelprocesoseabsorbaenunpaso,para cada estado no absorbente. Por su parte, el vector1 A N muestra la probabilidad de que el procesonoseabsorbaenunaprimeratransaccinysienlasegunda.Delmismomodo, 1 A N2 seala la probabilidad de que el proceso no se absorba en los dos primeros pasos y que s se absorba en el tercero; y as sucesivamente. Dado que A = I N, siendo I una matriz unitaria (n x n), reemplazando en la expresin anterior, tendremos: | | 1 ... ) N I ( N 4 ) N I ( N 3 ) N I ( N 2 ) N I ( n3 2 + + + + =Luego: | | 1 ... N N 4 N N 3 N 2 N 2 N I n4 3 3 2 2 + + + + =Entonces: | | 1 ... N N N N N n4 3 2 1 0 + + + + + = (8) LosvaloresdeloselementosdelamatrizNestncomprendidosentre0y1,yaque constituyen probabilidades. Por lo tanto, a medida que aumenta la potencia de n, la matriz CADENAS DE MARKOV 25 Nntiende aseruna matriznula.Unaseriede matricescomolaque est comprendida enel corchete de la expresin (8) se comporta como una serie numrica de un valor x menor a 1: x 11x0n=

DemaneraquelaseriematricialdeN,siemprequesuselementospijseanmenoresa uno, como efectivamente sucede al constituir probabilidades de no absorcin en un paso: 10n) N I (N IIN == Reemplazando,entonces,en(8)tendremoslaexpresindelvectordeprobabilidades buscado: 1 ) N I ( n1 =(9) Para el ejemplo planteado arriba, tendremos: A = ((

75 , 05 , 0N = ((

25 , 05 , 0 I-N = ((

=((

((

1 25 , 050 , 0 125 , 05 , 011 ((

= 1429 , 1 2857 , 05714 , 0 1429 , 1) N I (1 ((

=((

((

= 4286 , 17143 , 1111429 , 1 2857 , 05714 , 0 1429 , 11 ) N I (1 Es decir, que si el proceso comienza en el estado 1, har en promedio 1,71 transacciones antesdeabsorberse.Si,encambio,empiezaenelestado3,tardar1,43pasospara absorberse. 2.Determinacin del nmero promedio de veces que el proceso pasa por cada estado antes de absorberse, comenzando en un estado i no absorbente. Estos valores se obtienen de la matriz 1) N I ( . Sielprocesocomienzaenelestado1,elnmeropromediodevecesquepasaporel estado1es,aproximadamente,1,14veces,yelnmeropromediodevecesquepasaporel estado 3 es, aproximadamente, 0,57 veces. Si,encambio,elprocesocomienzaenelestado3,pasarenpromedio(y aproximadamente) 0,29 veces por el estado 1 y 1,14 veces por el estado 3. 3.Clculodelaprobabilidaddeterminarenunestadojabsorbente,comenzandoenun estado i no absorbente. Este valor es igual a la probabilidad de ir de i a j en un paso, ms la probabilidad de hacerlo en dos pasos, ms la probabilidad de hacerlo en tres, y as sucesivamente: P(j) = p(ij en un paso) + p(ij en dos pasos) + H.ROJO, M. MIRANDA 26 P(j) = A + NA + N2A + N3A + = IA + NA +N2A + N3A + .. = (I + N + N2 + N3 + ..)A Es decir, A ) N I ( ) j ( P1 = Para el ejemplo anterior, tendremos: ((

=((

((

8571 , 0 1429 , 04286 , 0 5714 , 075 , 050 , 01429 , 1 2857 , 05714 , 0 1429 , 1 Esto significa que: Comenzandoenelestado1,laprobabilidaddeterminarenelestado2es0,57yde absorberse en el estado 4 es 0,43 (aproximadamente).Si,encambio,secomienzaenelestado3,laprobabilidaddeterminarelprocesoenel estado 2 es de 0,14 y de absorberse en el estado 4 es de 0,86 (aproximadamente). Extensin para cadenas no absorbentes Paradeterminarelnmerodepasosnecesarios(enpromedio)paraalcanzarunestado cualquieraj,seprocededeigualformaalavistaparaunprocesoabsorbentesuponiendo que el estado j es absorbente. Por ejemplo, para el siguiente proceso: cuya matriz de transicin es: 3 2 1S S S321SSSP =((((

6 , 0 4 , 03 , 0 5 , 0 2 , 03 , 0 3 , 0 4 , 0 Paraaveriguar elnmero promediodetransaccionesquese realizan hastaalcanzarpor ejemploelestadoS3porprimeravez,sedebeconsideraralestadoS3comosifuera absorbente, de manera que la nueva matriz de transicin sera:

S1

S2

S3 0,3 0,4 0,6 0,3 0,5 0,2 0,4 0,3 CADENAS DE MARKOV 27 3 2 1S S S321SSSP =((((

13 , 0 5 , 0 2 , 03 , 0 3 , 0 4 , 0 Luego, se pasa al formato estndar: 2 1 3S S S S3 1 P =S1 0,30,40,3 S2 0,30,20,5 La matriz I-N es entonces: ((

=((

((

= 5 , 0 2 , 03 , 0 6 , 05 , 0 2 , 03 , 0 4 , 011N Iy su inversa: ( )((

= 50 , 2 82 , 025 , 1 08 , 2SSN I21 1 El vectornser entonces: ( )((

=((

((

= =32 , 333 , 31150 , 2 82 , 025 , 1 08 , 2SS1 N I n21 1 Esdecir,partiendodel estadoS1, elnmerodeocasionesquetranscurrenenpromedio antesdellegaralestadoS3es3,33.Porsuparte,sielestadoinicialesS2,elnmero promedio de pasos que transcurren antes de alcanzar el estado S3 es igual a 3,32. Ampliacin a cadenas cclicas Talcomosehavistoanteriormente,uncicloesuncaminocerradoentreestados recurrentes.Demaneraque,cuandoelprocesoalcanzaaunestadodelciclo,todaslas transacciones futuras se realizan entre estados del mismo ciclo.Lascadenascclicassonaquellasquetienenporlomenosuncicloalqueesposible acceder. Por ejemplo, la siguiente cadena es cclica: H.ROJO, M. MIRANDA 28 3 2 1S S S321SSSP =((((

113 , 0 2 , 0 5 , 0 Esta no es una cadena ergdica, ya que es reducible en dos clases: [S2,S3] y [S1]. Como podemos observar, la clase [S2,S3] constituye un ciclo. Enelcortoplazo(rgimentransiente),sepuededeterminarelnmerodepasos promedio que se realizan hasta alcanzar el ciclo. Es clculo se puede hacer suponiendo que el ciclo es un estado absorbente, y proceder luego como se explic anteriormente. La matriz de transicin se transforma entonces en:

3 2 1S S S 3 21S SS((

150 , 0 50 , 0 y su cannica:

3 2 1S S S 13 2SS S ((

50 , 0 50 , 01 Por lo tanto: IN = [1] [0,50] = [0,50] ( ) | | 2 N I1= ( ) | | | | | | 2 1 2 1 N I1= = Es decir, se requieren 2 pasos en promedio para alcanzar el ciclo. En el largo plazo (rgimen permanente) el sistema es cclico, y el tiempo que el proceso pasaencadaestadodelciclosecalculaconelprocedimientoyavistoparargimen permanente.Paraelejemplo,elsistemadeecuacionesquenospermitedeterminarlas probabilidadesdeestadoenrgimenpermanentesepuedeplantearmedianteelsiguiente producto matricial:

S2

S3

S1 1 0,5 0,2 1 0,3 CADENAS DE MARKOV 29 | | | | ) 3 ( p ) 2 ( p ) 1 ( p1 111 2 , 0 5 , 0) 3 ( p ) 2 ( p ) 1 ( p =((((

cuyo resultado es p(1) = 0 p(2) = 0,50 p(3) = 0,50 Ejemplo 2:Lademandasemanaldeunrepuestoenunprocesoproductivotienelasiguiente distribucin de probabilidad: Si el stock inicial es de 3 unidades, y la observacin del nivel de inventarios se realiza al finalizar cada semana:a.cul es la probabilidad de que al cabo de dos semanas se haya agotado el stock? b.culeslaprobabilidaddequealcabodecuatrosemanashayadosomsdedos repuestos en stock? c. Determinar el nmero promedio de semanas que transcurren hasta agotar el stock. d.Calcularelcostototaldealmacenamientoparacadaciclodecompra,sielcosto unitario semanal es de $10. Llamaremos: S0: ninguna unidad en stock al finalizar una semana S1: una unidad en stock al finalizar una semana S2: dos unidades en stock al finalizar una semana S3: tres unidades en stock al finalizar una semana La matriz de transicin es: 0 1 2 3S S S SP = 0123SSSS(((((

14 , 0 6 , 01 , 0 3 , 0 6 , 01 , 0 3 , 0 6 , 0 y la representacin grfica: dp 00,6 10,3 20,1 30 H.ROJO, M. MIRANDA 30 Los estados S3, S2 y S1 son transitorios. El estado S0 es absorbente. a)El estado actual es S3. Para hallar la probabilidad de que en dos semanas se haya agotado el stock se calcula el cuadrado de la matriz de transicin: 0 1 2 3S S S SP2 = 0123SSSS(((((

164 , 0 36 , 028 , 0 36 , 0 36 , 007 , 0 21 , 0 36 , 0 36 , 0 Luego: % 7 07 , 0 p) 2 (0 , 3= = b)Laprobabilidaddequeal cabode cuatrosemanashayadosomsrepuestosenstockes ) 4 (3 , 3) 4 (2 , 3p p + . Para determinarla se calcula la matriz de transicin en cuatro pasos: 0 1 2 3S S S SP4 = 0123SSSS(((((

187 , 0 23 , 029 , 0 26 , 0 13 , 032 , 0 29 , 0 26 , 0 13 , 0 Por lo tanto: % 39 39 , 0 13 , 0 26 , 0 p p) 4 (3 , 3) 4 (2 , 3= = + = + c) Se reagrupa la matriz de transicin P para llevarla a la forma cannica:

S3

S2

S1 0,3 0,6 0,3 0,6 0,6 0,1 0,4 0,1

S0 1 CADENAS DE MARKOV 31

1 2 3 0S S S S1230SSSS(((((

6 , 0 4 , 03 , 0 6 , 0 1 , 01 , 0 3 , 0 6 , 01 N = ((((

6 , 03 , 0 6 , 01 , 0 3 , 0 6 , 0I-N = ((((

4 , 03 , 0 4 , 01 , 0 3 , 0 4 , 0 ( )((((

= 50 , 2875 , 1 50 , 2781 , 0 875 , 1 50 , 2N I1 ((((

=((((

((((

=50 , 2375 , 4156 , 511150 , 2875 , 1 50 , 2781 , 0 875 , 1 50 , 2SSSn123 En consecuencia, el nmero promedio de semanas que transcurren hasta agotar el stock es 5,156. d)Asumiendo que cada ciclo comienza con 3 unidades y termina cuando se agotan las tres unidades,elnmerodesemanaspromedioqueelsistemaestenelestadoS3(tres unidades en existencias) es 2,50, en el estado S2 (dos unidades en stock), 1,875y en el estado S1 (1 unidad en stock) es 0,781. Luego el costo de almacenamiento por ciclo es: ciclo$93 , 85sem un$10ciclosem781 , 0 un 3ciclosem875 , 1 un 2ciclosem50 , 2 un 1 =((

+ + Ejemplo 3: Asumir que en un mercado particular de computadoras personales laptop solo hay tres modelosdisponibles:COMPAQ,APPLEySONY.Lascompaasfabricantesdecada computadora tienen los siguientes datos con respecto a compras de clientes. MARCA ACTUAL Siguiente compra % que compra COMPAQ% que compra APPLE % que compra SONY COMPAQ203050 APPLE403030 SONY204040 1.CuleslaprobabilidaddequeunposeedordeunaCOMPAQadquieraunaAPPLE dentro de dos compras? H.ROJO, M. MIRANDA 32 2. Cul es la probabilidad de que el dueo de una APPLE siga con una APPLE dentro de dos compras, y cul en tres compras? 3.Alargoplazoculeslaprobabilidaddequeunclientecomprecadaunadelastres marcas? 4.Determinarelnmeroesperadodecomprasantesdequeelahoradueodeuna COMPAQ adquiera una SONY. Resolucin: LlamandoalosestadosC,AySalosestadosCOMPAQ,APPLEySONY, respectivamente, la matriz de transicin en un paso del problema es: S A C((((

=40 , 0 40 , 0 20 , 030 , 0 30 , 0 40 , 050 , 0 30 , 0 20 , 0SACPy el grafo correspondiente: 1. Para un cliente actual de COMPAQ, el vector de transicin en dos pasos, aplicando la ecuacin de Chapman-Kolmogorov, es: S A C| | | | 39 , 0 35 , 0 26 , 040 , 0 40 , 0 20 , 030 , 0 30 , 0 40 , 050 , 0 30 , 0 20 , 050 , 0 30 , 0 20 , 0 P V V) 1 (C) 2 (C=((((

= =Luego, la probabilidad de permanecer en C luego de dos pasos es35 , 0 p) 2 (C = . Otraforma,dehallarestaprobabilidadesapartirdelcuadradodelamatrizde transicin:

A

S

C 0,4 0,2 0,3 0,3 0,5 0,40,3 0,4 0,2 CADENAS DE MARKOV 33 S A C((((

=38 , 0 34 , 0 28 , 041 , 0 33 , 0 26 , 039 , 0 35 , 0 26 , 0SACP2 2. De la matriz P2 se observa que la probabilidad de que un cliente A permanezca en A luegode2comprasesdel26%.Parahallar,laprobabilidaddeque,alcabode3compras, siga teniendo una A, podemos aplicar Chapman-Kolmogorov: | | | | 393 , 0 341 , 0 266 , 040 , 0 40 , 0 20 , 030 , 0 30 , 0 40 , 050 , 0 30 , 0 20 , 041 , 0 33 , 0 26 , 0 P V V) 2 (A) 3 (A=((((

= =o tambin, con la matriz en tres pasos P(3) = P3: S A C((((

=394 , 0 338 , 0 268 , 0393 , 0 341 , 0 266 , 0391 , 0 339 , 0 270 , 0SACP3 3.Parahallarelporcentajedeparticipacinenelmercadodecadaunadelastres marcas, aplicamos el producto matricial para rgimen permanente: | | | | 1 ) A ( p ) C ( p1 40 , 0 20 , 01 30 , 0 40 , 01 30 , 0 20 , 0) S ( p ) A ( p ) C ( p =((((

que nos lleva a un sistema de 3 ecuaciones con 3 incgnitas, cuya solucin es la siguiente: p(C) = 0,268 p(A) = 0,339 P(S) = 0,393 Al mismo resultado, por supuesto, se habra arribado a partir del planteo de ecuaciones que surge del mtodo de suma de flujos. 4. Para hallar el nmero de compras que se requiere para que el dueo de una C pase a una S, debemos convertir al estado S en un estado absorbente: S A C((((

=1 0 030 , 0 30 , 0 40 , 050 , 0 30 , 0 20 , 0SACPLuego se formula la forma cannica de la matriz P: H.ROJO, M. MIRANDA 34 A C S((((

=30 , 0 40 , 0 30 , 030 , 0 20 , 0 50 , 00 0 1ACSPEn consecuencia: ((

=((

((

= 7 , 0 4 , 03 , 0 8 , 03 , 0 4 , 03 , 0 2 , 011N I Calculamos, entonces( )1N I , por ejemplo por Gauss Jordan: 818 , 1682 , 01010909 , 0 1 0591 , 1 0 15 , 0 55 , 0 025 , 1 375 , 0 10 7 , 0 4 , 01 3 , 0 8 , 0 Luego: ( )((

= 818 , 1 909 , 0682 , 0 591 , 1N I1 ((

=((

((

=727 , 2273 , 211818 , 1 909 , 0682 , 0 591 , 1CAnEntonces, el nmero promedio de compras que transcurre hasta que el propietario actual de una COMPAQ adquiera una SONY es 2,273. Ejemplo 4: Unafirmadeabogadosrealizaunestudiodenivelesdecategoraparaproveer promocionesadecuadasenelmomentooportuno,controlarelpagodehaberes,analizar necesidades de empleo, etc. Las categoras de los profesionales de la firma son JR (jnior), SS(semi-senior),SE(senior),AS(asociado)ySO(socio).Enbaseadatoshistricosse esperaque,anualmente,elporcentajedeempleadosdecadacategoraquesedandebaja por renuncias, despidos, jubilaciones o fallecimientos sea el siguiente: CADENAS DE MARKOV 35 REDEJUFA JR% 7 7 , 13% 5 5 , 153%1% SS12,57%10%4%2% SE13%% 6 6 , 65%2% AS5%2%10%3% O15%5% Actualmentehay103abogadosenlafirma(45JR,28SS,15SE,10AS,5SO),yla poltica de la firma es tomar solamente abogados jnior. 1.Averiguarqucantidaddeabogadosdeberncontratarseyqucantidaddebern promoverse en cada categora para mantener los niveles estables. 2.Determinarculeseltiempodepermanenciapromediodeunempleadoenla compaa (ndice de rotacin). 3. Calcular la probabilidad de que un empleado que recin ingresa a la firma llegue a la categora de socio, y la probabilidad de que sea despedido. Resolucin: Delascausasdebajas,interesadeterminarlosquedejanlaempresapordespidos,de manera que clasificaremos a los estados de bajas solamente en dos: DE y OB (otras bajas).En primer lugar se calcula el flujo de cada nodo a fin de calcular las probabilidades de transicin. Analizando el nodo de socios SO: Actualmente hay 5 socios. El 20% de ellos (es decir 1 socio) abandona la empresa, y el resto(80%)permanececomosocio.Demaneraquedebepromoverse1asociado(AS)a categora de socio por ao, es decir 1 sobre 10 (x = 0,10).

SO

OB 0,20 x 10,80

AS H.ROJO, M. MIRANDA 36 Paramantenerlacantidadde10asociados,teniendoencuentaqueabandonanesta categorauntotalde3abogados(1pasaasocioy2abandonan),sedebenpromoverdela categora inferior (SE) tambin un total de 3 abogados, es decir 3 sobre 15 (y = 0,20). El 70% permanece en la categora. Pasando ahora al nodo SE, tendremos: Se deben promover, entonces 7 semi-senior por ao, es decir 7 en 28 ( z = 0,25). Por su parte, analizando el nodo SS:

AS

OB z y = 0,20 1 3 5 , 0

SE

DE

SS 1 0,20 6 06 , 0

SO

OB y x = 0,10 1 0,70

AS

DE

SE 1 0,02 0,18 CADENAS DE MARKOV 37 Dadoquehay28semi-seniors,deloscuales5,2abandonan(18,58%),2,8son despedidos(10%)y7sonpromovidosalacategorasuperior(25%),sedebenpromover desdelacategorainferior15abogados,loquerepresentaun33,33%(w=3 3 , 0,)delos juniors. Finalmente, analizando el nodo JR: De los 45 empleados, 8 abandonan la firma (13,77%), 7 son despedidos (15,55%), y 15 sonpromovidos(33,33%).Estosignificaque15deellossemantieneenlacategorade jnior (33,33%) y, para mantener la misma dotacin, se deben contratar 15 abogados para esa categora. La matriz de transicin ser entonces:

SS

OB w =3 3 , 0 1

JR

DE 1 7 13 , 0 5 15 , 0

6 6 , 0

SE

OB w z = 0,25 1

SS

DE

JR 1 0,1858 0,4643 0,10 H.ROJO, M. MIRANDA 38 SO AS SE SS JR DE OBSOASSESSJRDEOB((((((((((

80 , 0 20 , 010 , 0 70 , 0 02 , 0 18 , 020 , 0 3 533 , 0 6 066 , 0 20 , 025 , 0 4643 , 0 10 , 0 1858 , 03 333 , 0 3 333 , 0 5 155 , 0 7 177 , 011 La matriz I-N es: (((((((

= 20 , 010 , 0 30 , 020 , 0 6 466 , 025 , 0 5357 , 03 333 , 0 6 666 , 0N I y su inversa: ( )(((((((

= 56667 , 1 3333 , 37143 , 0 4286 , 1 1429 , 23333 , 0 6667 , 0 1 8667 , 11666 , 0 3333 , 0 50 , 0 93333 , 0 50 , 1N I1 Para calcular el ndice de permanencia en la firma para un recin ingresado: (((((((

=(((((((

(((((((

=552858 , 48667 , 34333 , 31111156667 , 1 3333 , 37143 , 0 4286 , 1 1429 , 23333 , 0 6667 , 0 1 8667 , 11666 , 0 3333 , 0 50 , 0 93333 , 0 50 , 1ni Es decir, 3,4333 aos. Por su parte, observamos que un empleado recin promovido a la categoradesemi-seniorpermanecer,enpromedio,3,8667aos,mientrasquelostiempos esperados para los ascendidos a las categoras de senior, asociado y socio, sern 4,2858, 5 y 5 aos, respectivamente. Paradeterminarlaprobabilidaddequeunempleadoquereciningresallegueala mximacategora(esdecir,desocio)sedebeconsiderarelestadoSOcomounestado absorbente: CADENAS DE MARKOV 39 AS SE SS JR SO DE OBASSESSJRSODEOB(((((((((((

70 , 0 10 , 0 02 , 0 18 , 020 , 0 3 533 , 0 6 066 , 0 20 , 025 , 0 4643 , 0 10 , 0 1858 , 03 333 , 0 3 333 , 0 5 155 , 0 7 177 , 0111 La matriz (I-N) ser: ( )((((((

= 30 , 020 , 0 6 466 , 025 , 0 5357 , 03 333 , 0 6 666 , 0N I y su inversa: ( )(((((

= 3333 , 34286 , 1 1429 , 26666 , 0 1 8666 , 13333 , 0 50 , 0 9333 , 0 50 , 1N I1 Luego, el producto( ) A N I1 ser: (((((

=((((((

(((((

3333 , 0 0667 , 0 60 , 01429 , 0 1714 , 0 6857 , 00667 , 0 2667 , 0 6666 , 00333 , 0 3667 , 0 60 , 010 , 0 02 , 0 18 , 06 066 , 0 20 , 010 , 0 1858 , 05 155 , 0 7 177 , 03333 , 34286 , 1 1429 , 26666 , 0 1 8666 , 13333 , 0 50 , 0 9333 , 0 50 , 1 En consecuencia, la probabilidad de que un abogado jnior recin ingresado sea dado de bajaporrenuncia,jubilacinofallecimientoesdel60%,laprobabilidaddequesea despedido es del 36,67% y de que alcance la mxima categora (socio) es de 3,33%. Ejemplo 5: En un centro de mecanizado se procesan piezas en dos etapas (Mquina A, y Mquina B). Los tiempos promedio de mecanizado de cada pieza son de 3 horas en la Mquina A y de 2 horas en la B. El costo de la hora hombre es de $10. Luego de cada etapa de elaboracin se efecta una inspeccin de calidad, tal como se indica en el siguiente grfico. Los tiempos promedio del control de calidad son de 0,2 horas H.ROJO, M. MIRANDA 40 y 0,1 horas para los centros A y B, respectivamente, y el costo de la hora de los inspectores es de $15. Elcostodirectodelaspiezasquelleganalcentrodesdeelalmacndeproductos semielaborados es de $40. Si durante el mecanizado en las mquinas se estropea una pieza, se la desecha sin pasar por control de calidad. En los centros de Control de Calidad se pueden devolver las piezas para ser reprocesadas en las mquinas o se las puede considerar defectuosas y desecharlas. Losporcentajesdepiezasestropeadasenproceso,depiezasareprocesarydepiezas defectuosas a desechar, estn indicados en el grfico. El costo directo de cada pieza semielaborada que llega al Centro de Mecanizado es de $30, mientras que el costo de oportunidad del material desechado es de $25 por pieza. Se desea determinar a. la cantidad de piezas semielaboradas a enviar al centro a fin de producir 100 piezas buenas terminadas. b. el requerimiento de personal para cada pieza terminada. c. el costo directo esperado de cada pieza terminada que sale del centro productivo. MAQ. A MAQ. B CC A CC B De almacn de Semielaborados A almacn de Productos Terminados Etapa A Etapa B A Desechos 6% 4% 1% 3% 2% 5% CADENAS DE MARKOV 41 Resolucin: Los estados posibles para una pieza son: SE: en almacn de semielaborados MA: en procesamiento en mquina A CA: en control de calidad del sector A MB: en procesamiento en mquina B CB: en control de calidad del sector B PD: en depsito de piezas defectuosas PT: en almacn de piezas terminada El diagrama de la cadena markoviana correspondiente es: a) La matriz de transicin en un paso del problema es: CA 0,06 0,04 0,01 0,03 0,02 0,05 MA MB CB PT PD 0,98 0,92 0,99 0,90 SE 1 H.ROJO, M. MIRANDA 42 PT PD CB MB CA MA SEPTPDCBMBCAMASEP =((((((((((

1190 , 0 04 , 0 06 , 001 , 0 99 , 003 , 0 92 , 0 05 , 002 , 0 98 , 01 Reagrupando: CB MB CA MA SE PT PDCDMBCAMASEPTPD((((((((((

06 , 0 90 , 0 04 , 099 , 0 01 , 092 , 0 05 , 0 03 , 098 . 0 02 , 0111 Luego: (((((((

=06 . 099 . 092 . 0 05 . 098 . 01N (((((((

= 1 06 . 099 . 0 192 . 0 1 05 . 098 . 0 11 1N I Por lo tanto: CADENAS DE MARKOV 43 ( )(((((((

= 0632 , 1 0638 , 00525 , 1 0632 , 10182 , 1 0285 , 1 05152 , 1 0526 , 09978 , 0 0079 , 1 0305 , 1 0515 , 19978 , 0 0079 , 1 0305 , 1 0515 , 1 1N I1 Multiplicando esta matriz por la matriz de absorcin A, obtendremos la probabilidad de quelapiezatermineencadaestadoabsorbente(piezadefectuosaopiezaterminada)para cada estado no absorbente. En particular interesa saber dichas probabilidades desde el estado MA, que es el de una pieza ingresada desde el almacn de productos intermedios. ( )(((((((

(((((((

= 90 , 0 04 , 001 , 003 , 002 , 00632 , 1 0638 , 00525 , 1 0632 , 10182 , 1 0285 , 1 05152 , 1 0526 , 09978 , 0 0079 , 1 0305 , 1 0515 , 19978 , 0 0079 , 1 0305 , 1 0515 , 1 1A N I1= ( )((((((

= 9568 , 0 0432 , 09473 , 0 0527 , 09164 , 08981 , 00836 , 01019 , 08981 , 0 1019 , 0A N I1 Se puede observar, entonces, que la probabilidad de que se encuentra en el almacn de semielaboradosyquepasaalsectordemecanizadotieneunaprobabilidadde89,81%de terminarcomobuena.Porlotanto,elnmeroesperadodepiezasquedebenentrarenel proceso para obtener 100 piezas buenas es: 112 34 , 1118991 , 0100n = = b) De la matriz( )1N Ise puede extraer el nmero de veces que una pieza que entra en elcentroproductivopasaporcadaoperacin.Aestevalorselodebemultiplicarpor1,12 para obtener el nmero de veces que pasa una pieza terminada que sale del centro.DeestaformasepuedeobtenereltiempoenHHporcadapiezaterminaday,en consecuencia, el costo directo por cada pieza terminada, segn se indica en la tabla siguiente. H.ROJO, M. MIRANDA 44 Estado n(por pieza entrante) n(por pieza saliente) HH por pieza procesada HH por pieza terminada Costo ($/HH) Costo ($/pieza terminada) MA1,05151.17773,03,53311035,3310 CA1,03051,15420,20,2308153,4620 MB1,00791,12882,02,25761022,5760 CB0,99781,11750,10,1118151,6770 Costo total Mano de Obra ($) por pieza terminada63,0460

El costo total de material es: ada min ter pieza$60 . 33ada min ter piezaentrante pieza12 , 1entrante pieza$30 = La venta del material de rezago es: . term pieza$8532 , 2. term piezaentrante pieza12 , 1entrante pieza. defect pieza1019 , 0. defect pieza$25 = En consecuencia, para cada pieza terminada tendremos: Costo de Mano de Obra $ 63,0460 Costo de Materiales$ 33,6000 Venta de Defectuosos -$ 2,8532 Costo directo $ 93,7928 Ejemplo 6: Alfinaldecadadadeoperacinunamquinasepuedeencontrarenalgunodelos siguientes estados: E0: En perfectas condiciones de operacin E1: Condicin regular de operacin E2: Malas condiciones de operacin E3: Inoperable Los costos de operar la mquina al da siguiente, debido a su estado operativo son los siguientes: E0: $ 0 E1: $ 500 E2: $ 1.000 CuandolamquinaseencuentraenelestadoE3selareparaduranteeldasiguiente paradejarlaenperfectascondicionesdeoperacinparaelprximoda.Elcostode reparacin es de $2.000, incurrindose adems en un lucro cesante de $ 5.000 por piezas no producidas durante ese da. CADENAS DE MARKOV 45 Las probabilidades de transicin entre los estados son las siguientes: ESTADOE0E1E2E3 E00,20,40,30,1 E10,50,30,2 E20,40,6 Sedeseacalcularelcostopromedioesperadodiarioyelnmeroesperadodedas promedio de funcionamiento de la mquina. Resolucin: La matriz de transicin es la siguiente: 3 2 1 0E E E E(((((

=16 , 0 4 , 02 , 0 3 , 0 5 , 01 , 0 3 , 0 4 , 0 2 , 0EEEEP3210 Por lo tanto, en estado de rgimen: | | | | 1 ) 2 ( p ) 1 ( p ) 0 ( p1 11 4 , 01 3 , 0 5 , 01 3 , 0 4 , 0 2 , 0) 3 ( p ) 2 ( p ) 1 ( p ) 0 ( p =(((((

=Es decir: ) 0 ( p ) 3 ( p 2 , 0 ) 0 ( p = + ) 1 ( p 5 , 0 ) 1 ( p 4 , 0 ) 0 ( p = + ) 2 ( p 4 , 0 ) 2 ( p 3 , 0 ) 1 ( p 3 , 0 ) 0 ( p = + + 1 ) 3 ( p ) 2 ( p ) 1 ( p ) 0 ( p = + + +cuyo resultado es: p(0) =0.2857 p(1) =0.2286p(2) =0.2571 p(3) =0.2286 Enconsecuencia,paracalcularelcostopromediodiarioredeterminaelvaloresperado con la expresin: = ) i ( p c Costoi H.ROJO, M. MIRANDA 46 ESTADO Costo diario p(i) E000,28570 E1 500 0,2286114,3 E2 1.000 0,2571257,1 E3 7.000 0,22861.600,2 Costo promedio diario esperado1.971,6 Finalmente,paracalcularlacantidaddeciclosporda,suponemoselestadoE3 absorbente: 3 2 1 0E E E E2 1 0 3E E E E(((((

=16 , 0 4 , 02 , 0 3 , 0 5 , 01 , 0 3 , 0 4 , 0 2 , 0EEEEP3210 (((((

4 , 0 6 , 03 , 0 5 , 0 2 , 03 , 0 4 , 0 2 , 0 1 , 01EEEE2103 ((((

=4 , 03 , 0 5 , 03 , 0 4 , 0 2 , 0N ((((

= 6 , 03 , 0 5 , 03 , 0 4 , 0 8 , 0N I Calculando la matriz inversa: | |((((

= 6 66 , 11 2125 , 1 1 25 , 1N I1 | |((((

=((((

((((

= 6 66 , 13375 . 31116 66 , 11 2125 , 1 1 25 , 11 N I1 El tiempo esperado de cada ciclo operativo es, entonces, igual a 3,375 das. Ejemplo 7: El Departamento de Facturacin de una empresa determin la evolucin de los crditos de un mes a otro mediante porcentajes, tal como se muestra en la tabla. Suponiendo que se mantienen en el tiempo los niveles de crditos a. Determinar la probabilidad de que se cobre una factura en Cuenta Corriente. CADENAS DE MARKOV 47 b. Calcular el nmero de meses que transcurren en promedio hasta que se cobra una factura de cada uno de los dos tipos de crditos. CUENTA CORRIENTE CREDITOS DOCUMENTADOS MOROSOSCOBROINCOBRABLE CUENTA CORRIENTE 30%15%15%40% CRDITOS DOCUMENTADOS 50%10%40% MOROSOS20%60%20% Resolucin: IN CO MO CD CC(((((((

=1120 , 0 60 , 0 20 , 040 , 0 10 , 0 50 , 040 , 0 15 , 0 15 , 0 30 , 0INCOMOCDCCP Reordenando: MO CD CC IN CO(((((((

20 , 0 20 , 0 60 , 010 , 0 50 , 0 40 , 015 , 0 15 , 0 30 , 0 40 , 011MOCDCCINCO ((((

=20 , 010 , 0 50 , 015 , 0 15 , 0 30 , 0N ((((

= 80 , 010 , 0 5 , 015 , 0 15 , 0 70 , 0N I Calculando la matriz inversa: | |((((

= 25 , 125 , 0 23214 , 0 4286 , 0 4286 , 1N I1 Multiplicando esta matriz por la matriz de absorcin A: H.ROJO, M. MIRANDA 48 | |((((

=((((

((((

= 25 , 0 75 , 005 , 0 95 , 006 , 0 94 , 020 , 0 60 , 040 , 040 , 025 , 125 , 0 23214 , 0 4286 , 0 4286 , 1A N I1 Estosignificaquelaprobabilidaddequesecobreunafacturaqueactualmentese encuentra en cuentas corrientes es del 94%. Paracalcularelnmerodemesesquepasan,enpromedio,hastaqueseliquidauna cuenta, se procede a calcular el siguiente vector: | |((((

=((((

((((

= =25 , 125 , 218 , 211125 , 125 , 0 23214 , 0 4286 , 0 4286 , 11 N I n1i Se observa que la cantidad de meses que transcurren hasta que se cobra una factura en cuentacorrienteesde2,18,enpromedio,mientrasqueparaelcobrodeunafactura documentada se requieren 2,25 meses.