unidad 4 IOS 2
-
Upload
shaka-de-loera -
Category
Documents
-
view
222 -
download
0
Transcript of unidad 4 IOS 2
-
7/24/2019 unidad 4 IOS 2
1/13
CADENAS DE MARKOV
Introduccin
Un proceso o sucesin de eventos que se desarrolla en el tiempo en el cual el resultado en
cualquier etapa contiene algn elemento que depende del azar se denomina proceso aleatorio
o proceso estocstico. Por ejemplo, la sucesin podra ser las condiciones del tiempo en
Paran en una serie de das consecutivos: el tiempo cambia da a da de una manera que en
apariencia es algo aleatoria. O bien, la sucesin podra consistir en los precios de las acciones
que cotizan en la bolsa en donde otra vez interviene cierto grado de aleatoriedad. Un ejemplo
simple de un proceso estocstico es una sucesin de ensaos de !ernoulli, por ejemplo, una
sucesin de lanzamientos de una moneda. "n este caso, el resultado en cualquier etapa es
independiente de todos los resultados previos #esta condicin de independencia es parte de la
de$inicin de los ensaos de !ernoulli%. &in embargo, en la maora de los procesos
estocsticos, cada resultado depende de lo que sucedi en etapas anteriores del proceso. Por
ejemplo, el tiempo en un da determinado no es aleatorio por completo sino que es a$ectado en
cierto grado por el tiempo de das previos. "l precio de una accin al cierre de cualquier dadepende en cierta medida del comportamiento de la bolsa en das previos. "l caso ms simple
de un proceso estocstico en que los resultados dependen de otros, ocurre cuando el resultado
en cada etapa slo depende del resultado de la etapa anterior no de cualquiera de los
resultados previos. 'al proceso se denomina proceso de (ar)ov o cadena de (ar)ov #una
cadena de eventos, cada evento ligado al precedente% "stas cadenas reciben su nombre del
matemtico ruso *ndrei *ndreevitc+ (ar)ov #-/0122%. 3omo mencionamos antes, estas
cadenas tiene memoria, recuerdan el ltimo evento eso condiciona las posibilidades de los
eventos $uturos. "sto justamente las distingue de una serie de eventos independientes como el
+ec+o de tirar una moneda. "ste tipo de proceso presenta una $orma de dependencia simple,
pero mu til en muc+os modelos, entre las variables aleatorias que $orman un proceso
estocstico. &e utilizan, por ejemplo, para analizar patrones de compra de deudores morosos,para planear necesidades de personal, para analizar el reemplazo de un equipo, entre otros.
Definicin
Una cadena de (ar)ov es una sucesin de ensaos similares u observaciones en la cual cada
ensao tiene el mismo nmero $inito de resultados posibles en donde la probabilidad de cada
resultado para un ensao dado depende slo del resultado del ensao inmediatamente
precedente no de cualquier resultado previo.
Propiedad de (ar)ov: 4ada una secuencia de variables aleatorias...... , , , 5 52 56 , tales que
el valor de 5n es el estado del proceso en el tiempo n. &i la distribucin de probabilidadcondicional de 5n7 en estados pasados es una $uncin de 5n por s sola, entonces:
4onde i 8 es el estado del proceso en el instante i.
-
7/24/2019 unidad 4 IOS 2
2/13
Matriz de transicin
*l trabajar con cadenas de (ar)ov, a menudo es til pensar la sucesin de ensaos como
e8perimentos e$ectuados en cierto sistema $sico, cada resultado dejando a este sistema en
cierto estado. Por ejemplo, consideremos una sucesin de elecciones polticas en cierto pas: el
sistema podra tomarse como el pas mismo cada eleccin lo dejara en cierto estado, es
decir en el control del partido ganador. &i slo +a dos partidos polticos $uertes, llamados *
!, los que por lo regular controlan el gobierno, entonces podemos decir que el pas se
encuentra en el estado * o ! si el partido * o ! ganara la eleccin. 3ada ensao #o sea cada
eleccin%, coloca al pas en uno de los dos estados * o !. Una sucesin de 9 elecciones
podra producir resultados tales como los siguientes: *, !, *, *, !, !, !, *, !, ! a primera
eleccin en la sucesin deja en el poder al partido *, la segunda $ue ganada por el partido !,
as sucesivamente, +asta que la d;cima eleccin la gane el partido !. &upongamos que las
probabilidades de que el partido * o ! ganen la pr8ima eleccin son determinadas por
completo por el partido que est en el poder a+ora. Por ejemplo podramos tener las
probabilidades siguientes: < &i el partido * est en el poder, e8iste una probabilidad de = que el
partido * ganar la pr8ima eleccin una probabilidad de > de que el partido ! gane laeleccin siguiente. < &i el partido ! est en el poder, +a una probabilidad de ?6 de que el
partido * gane la eleccin siguiente una probabilidad de 2?6 que el partido ! permanezca en
el poder. "n tal caso, la sucesin de elecciones $orman una cadena de (ar)ov, dado que las
probabilidades de los dos resultados de cada eleccin estn determinadas por el resultado de
la eleccin precedente. o descrito anteriormente puede representarse gr$icamente usando la
siguiente red:
a in$ormacin probabilstica que se acaba de dar se puede representar de manera
conveniente por la siguiente matriz:
-
7/24/2019 unidad 4 IOS 2
3/13
Probabilidad de transicin estacionaria de n pasos
as ecuaciones de 3+apman0@olmogorov proporcionan un m;todo para calcular estas
probabilidades de transicin de n pasos :
"stas ecuaciones simplemente seAalan que al ir de un estado i al estado j en n pasos, elproceso estar en algn estado ) despu;s de e8actamente m # menor que n% pasos. *s,
"s solo las probabilidad condicional de que, si se comienza en el estado i, el proceso vaa alestado ) despues de m pasos despu;s al estado j en n0 m pasos.
os casos especiales de mB mBn0 conducen a las e8presiones
Para toda i, j, n de lo cual resulta que las probabilidades de transicin de n pasos sepueden obtener a partir de las probabilidades de transicin de un paso de manera recursiva.
Para nB2, estas e8presiones se vuelven :
Cote que las son los elementos de la matriz P#2%, pero tambi;n debe de observarse que
estos elementos, se obtienen multiplicando la matriz de transicin de un paso por smismaD esto es , P#2%B P E P B P2.
"n t;rminos ms generales, se conclue que la matriz de probabilidades de transicin de npasos se puede obtener de la e8presin : P#n%B P E P .... P B PnB PPn0B Pn0P.
"ntonces, la matriz de probabilidades de transicin de n pasos se puede obtener calculandola n0;sima potencia de la matriz de transicin de un paso. Para valores no mu grandes de n, lamatriz de transicin de n pasos se puede calcular en la $orma que se acaba de describir, perocuando n es grande, tales clculos resultan tediosos , ms an, los errores de redondeopueden causar ine8actitudes.
-
7/24/2019 unidad 4 IOS 2
4/13
E!e"plo #
Una tienda de cmaras tiene en almac;n un modelo especial de cmara que se puedeordenar cada semana. &ean 4, 42, ... las demandas de esta cmara durante la primera,segunda, ... , semana, respectivamente. &e supone que las 4ison variables aleatoriasindependientes e id;nticamente distribuidas que tienen una distribucin de probabilidad
conocida. &ea 59el nmero de cmaras que se tiene en el momento de iniciar el proceso, 5 elnmero de cmaras que se tienen al $inal de la semana uno, 5 2el nmero de cmaras al $inalde la semana dos, etc. &uponga que 59B 6 . "l sbado en la noc+e la tienda +ace un pedidoque le entregan el lunes en el momento de abrir la tienda. a tienda +ace un pedido que leentregan el lunes en el momento de abrir la tienda. a tienda usa la siguiente poltica # s,&%para ordenar : si el nmero de cmaras en inventario al $inal de la semana es menor que sB #no +a cmaras en la tienda%, ordenar #+asta% &B6. 4e otra manera, no coloca la orden #sise cuenta con una o ms cmaras en el almac;n, no se +ace el pedido%. &e supone que lasventas se pierden cuando la demanda e8cede el inventario. "ntonces, F5G para t B 9, , .. esun proceso estocstico de la $orma que se acaba de describir. os estados posibles del procesoson los enteros 9, , 2, 6 que representan el nmero posible de cmaras en inventario al $inalde la semana.
*s, dado que tiene una cmara al $inal de una semana, la probabilidad de que no +aa
cmaras en inventario dos semanas despu;s es 9.2-6D es decir, 4e igualmanera, dado que se tienen dos cmaras al $inal de una semana, la probabilidad de que +aa
tres cmaras en el almac;n dos semanas despu;s es 9.91HD esto es,
a matriz de transicin de cuatro pasos tambi;n se puede obtener de la siguiente manera :
P#I%B PIB P#2%E P#2%
*s, dado que queda una cmara al $inal de una semana, 9.2-2 es la probabilidad de que no
+aa cmaras en inventario I semanas ms tardeD es decir, 4e igual manera,
-
7/24/2019 unidad 4 IOS 2
5/13
dado que quedan dos cmaras en el almac;n $inal de una semana, se tiene una probabilidad
de 9.H de que +aa tres cmaras en el almac;n I semanas despu;sD esto es,
Estado estable
os estados son la caracterizacin de la situacin en que se +alla el sistema en un instantedado, de dic+a caracterizacin puede ser tanto cuantitativa como cualitativa.
"l estado de un sistema en un instante t es una variable cuos valores solo pueden pertenecer
al conjunto de estaos en el sistema. "l sistema modelizado por la cadena, por lo tanto, es una
variable que cambia con el valor del tiempo, cambio al que llamamos transicin.
Estado estable#&e puede decir que el estado estable es la distribucin de probabilidades que
en cierto punto quedar $ija para el vector P no presentar cambios en periodos posteriores.
-
7/24/2019 unidad 4 IOS 2
6/13
&e dice que una 3adena de (ar)ov en tiempo discreto admite una distribucin estacionaria en
la medida que las probabilidades de largo plazo e8isten es independiente de la distribucin
inicial #$9%.
"n este sentido se deben veri$icar ciertos requisitos para la e8istencia de esta distribucin de
probabilidades de largo plazo: la cadena debe ser irreducible sus estados deben ser
recurrentes positivos aperidicos. &e recomienda revisar en detalle la clasi$icacin de
estados antes del clculo de la distribucin estacionaria.
a distribucin estacionaria se obtiene a trav;s de la solucin nica del siguiente sistema de
ecuaciones:
"jemplo clculo distribucin estacionaria de una 3adena de (ar)ov
-
7/24/2019 unidad 4 IOS 2
7/13
3onsidere la siguiente matriz de transicin de probabilidades para un proceso mar)oviano en
tiempo discreto:
3alcule la probabilidad de encontrarse en cada uno de los estados en el largo plazo.
4esarrollo: Para veri$icar la e8istencia de una distribucin estacionaria debemos analizar si la
cadena es irreducible #es decir, e8iste una nica clase de estados% los estados que la
componen son recurrentes positivos aperidicos. Para $acilitar este proceso se recomienda
utilizar una representacin gr$ica o gra$o:
"l estado 2 es accesible desde el estado , es decir, e8iste una probabilidad no nula quecomenzando en el estado se pueda llegar al estado 2 al cabo de n etapas #no
necesariamente esto debe ser al cabo de una etapa%. 'ambi;n se puede veri$icar que el estado
es accesible desde el estado 2, por tanto se conclue que el estado 2 se comunican.
3abe destacar que 2 estados que se comunican pertenecen a una misma clase de estados.
*dicionalmente se puede demostrar que el estado 6 es accesible desde el estado 2 el estado
2 es accesible desde el estado 6. Por tanto el estado 2 6 se comunican por transitividad el
estado 6 se comunican. &e conclue entonces que e8iste una sola clase de estados que
contiene a F,2,6G por tanto la cadena es irreducible.
os estados , 2 6 son recurrentes dado que la cadena tiene una cantidad $inita de estados
se puede a$irmar que ;stos son recurrentes positivos.
Jinalmente los estados son aperidicos, es decir, no e8iste una secuencia de pasos tal para
que comenzando en uno de ellos se pueda volver sobre si mismo #con probabilidad no nula% al
cabo de un cierto nmero de pasos o etapas.
-
7/24/2019 unidad 4 IOS 2
8/13
Una vez que se +an veri$icado las condiciones necesarias para la e8istencia de una distribucin
estacionaria se $ormula el sistema de ecuaciones que permitir encontrar las probabilidades de
estado de largo plazo. "n nuestro ejemplo el sistema queda de$inido por:
a resolucin del sistema anterior permite encontrar que:
&e conclue que en el largo plazo la probabilidad de estar en el estado es de un 2K la
probabilidad de estar en el estado 2 6 es de un 6H,K.
ES$ADOS A%SOR%EN$ES
&e dice que un estado es absorbente si es cero la probabilidad de +acer una transicin $uera de
ese estado. Por tanto, una vez que el sistema +ace una transicin +acia un estado absorbente,
permanece en el siempre
MA$RI& '(NDAMEN$A)
a matriz $undamental es mu til para el anlisis solucin de situaciones en las cuales
aparecen estados absorbentes.
a metodologa para obtener la matriz $undamental es la siguiente:
. Obtener la matriz de transicin en la $orma usual, incluendo los estados absorbentes.
-
7/24/2019 unidad 4 IOS 2
9/13
2. Ldenti$icar de la matriz de transicin los renglones correspondientes a la matriz
absorbente
6. 4e lo que +a quedado de la matriz de transicin en el paso anterior, dividirlo en dos
partes: C que ser la parte no absorbente * que contendr los estados absorbentes
I. Obtenemos la matriz U mediante la siguiente $rmula:
UBL0C
4onde L es la matriz identidad.
. Jinalmente, se obtiene la matriz identidad de la siguiente manera:
5BU0
4onde 5 representa la inversa de U, la cual se obtiene por algunos m;todos como el Mauss0
Nordan.
eamos el siguiente ejemplo en el cual e8plicaremos algunos conceptos importantes:
Una empresa emplea a tres tipos de ingenieros: principiantes, con e8periencia socios.
4urante un aAo determinado +a una probabilidad de 9. que un ingeniero principiante sea
ascendido a ingeniero con e8periencia una probabilidad de 9.9 que deje la empresa sin ser
socio. 'ambi;n +a una probabilidad de 9.29 que un ingeniero con e8periencia sea ascendido a
socio una probabilidad de 9.9 que deje la empresa sin ser socio. 'ambi;n +a una
probabilidad de 9.9 de que un socio deje la empresa. 4etermine:
a% 3ul es la duracin promedio de un ingeniero reci;n contratadoQ
b% cul es la probabilidad de que un ingeniero principiante llegue a ser socioQ
c% 3ul es la duracin promedio que pasa un socio en la empresaQ
Primero, determinamos la matriz de transicin en la cual se observa que +a dos estados
absorbentes: el ingeniero deje la empresa sin ser socio que un socio deje la empresa
-
7/24/2019 unidad 4 IOS 2
10/13
4onde LPB LCM"CL"RO PRLC3LPL*C'"
L"B LCM"CL"RO 3OC "5P"RL"C3L*
L& B LCM"CL"RO &O3LO
L4&B LCM"CL"RO 4"N* * "(PR"&* &L"C4O &O3LO
L4&&B LCM"CL"RO 4"N* * "(PR"&* &LC &"R &O3LO
uego +allamos la matriz L0C, donde L es la matriz de identidad C la matriz no absorbente
identi$icada en el paso anterior.
-
7/24/2019 unidad 4 IOS 2
11/13
uego a trav;s de Mauss0Nordan, +allamos la matriz inversa como se muestra a continuacin.
Para responder la primera pregunta debemos tener presente un nuevo concepto que es el valor
esperado que es el tiempo en que un estado demora antes de ser absorbido. "ste valor
esperado se obtiene a trav;s de la matriz inversa. 4e esta $orma, la duracin promedio de un
reci;n contratado seria:
-
7/24/2019 unidad 4 IOS 2
12/13
Para +allar la probabilidad de que un ingeniero principiante llegue a ser socio se debe
multiplicar la matriz inversa por la matriz absorbente, de la siguiente manera:
Obs;rvese que esta probabilidad es igual a 9..
4e igual manera como en la primera parte, la duracin promedio de un socio en la empresa es:
(so de soft*are
Modelado y Anlisis de Sistemas Complejos
Software de anlisis de Markov es una interfaz visual que permite a los fabricantespara construir un diagrama de transicin de estados para modelar sistemas
complejos !ado que estos sistemas estn dise"ados con una amplia gama de
redundancia# interdependencia y fracasos dependientes de secuencia# sus
necesidades de anlisis superar el mbito# las $erramientas de modelado estndar
basadas en la serie
Con sus $erramientas de creacin de diagramas de transicin de estado slido y la
interfaz intuitiva# %&C 'indc$ill Markov permite a los usuarios crear
representaciones y modelos de estados de sistemas complejos gr(cos y susintercone)iones asociadas Mediante el aprovec$amiento de cada diagrama# es
posible calcular las m*tricas de rendimiento del sistema# incluyendo la capacidad#
(abilidad y disponibilidad de los diferentes estados
-
7/24/2019 unidad 4 IOS 2
13/13
%&C 'indc$ill Markov Caracter+sticas y ,ene(cios
-tilice las $erramientas de creacin de diagramas de transicin de estados para
representar estados complejos y sus intercone)iones
Sistemas de modelos de la ms alta complejidad# incluyendo sistemas con m.ltiples
mecanismos complejos
Cuenta con mecanismos de conmutacin# las prioridades de reparacin# de
reparacin de recursos limitados y secuencia de error de dependencias
Considere los costos asociados en t*rminos de la moneda# la funcionalidad o el
rendimiento
/mplear una amplia gama de clculos# incluyendo M&,0 1tiempo medio entre
fallos2# M&&0 1tiempo medio de 0alla2 y M&&3 1tiempo medio de reparacin2
0uncionalidad de edicin gr(ca interactiva permite actualizaciones fciles a
modelos y medidas del sistema rpido de reclculo
Referencias#
+ttp:??SSS.bioingenieria.edu.ar?academica?catedras?metestad?3adenasK29deK29(ar)ov0.pd$
+ttp:??SSS.gaatlacomulco.com?tutorials?investoper2?temaIH.+tm
+ttp:??SSS.ingenieria.unam.m8?industriales?descargas?documentos?catedra?invop.pd$
+ttp:??SSS.virtual.unal.edu.co?cursos?sedes?manizales?I9I9IH?descargas?ejemplos6.pd$
+ttp:??SSS.investigaciondeoperaciones.net?distribucionTestacionariaTmar)ov.+tml
+ttp:??invoperaciones20ingindustrial.blogspot.m8?29?9?estados0absorbentes.+tml
+ttp:??SSS.ptc.com?product0li$eccle0management?Sindc+ill?mar)ov
http://www.bioingenieria.edu.ar/academica/catedras/metestad/Cadenas%20de%20Markov-1.pdfhttp://www.gayatlacomulco.com/tutorials/investoper2/tema47.htmhttp://www.ingenieria.unam.mx/industriales/descargas/documentos/catedra/invop.pdfhttp://www.virtual.unal.edu.co/cursos/sedes/manizales/4040147/descargas/ejemplos3.pdfhttp://www.investigaciondeoperaciones.net/distribucion_estacionaria_markov.htmlhttp://invoperaciones2-ingindustrial.blogspot.mx/2011/05/estados-absorbentes.htmlhttp://www.ptc.com/product-lifecycle-management/windchill/markovhttp://www.gayatlacomulco.com/tutorials/investoper2/tema47.htmhttp://www.ingenieria.unam.mx/industriales/descargas/documentos/catedra/invop.pdfhttp://www.virtual.unal.edu.co/cursos/sedes/manizales/4040147/descargas/ejemplos3.pdfhttp://www.investigaciondeoperaciones.net/distribucion_estacionaria_markov.htmlhttp://invoperaciones2-ingindustrial.blogspot.mx/2011/05/estados-absorbentes.htmlhttp://www.ptc.com/product-lifecycle-management/windchill/markovhttp://www.bioingenieria.edu.ar/academica/catedras/metestad/Cadenas%20de%20Markov-1.pdf