UNIVERSIDAD MAYOR DE SAN SIMÓN
Facultad de Ciencias Económicas
Ingeniería Comercial
CADENAS DE MARKOV
Investigación Operativa II
Estudiantes:
Buergo Camacho Luis Sebastian
Monzón Pilco Daniel Marcelo
Ordóñez Alejandro Jhasir Noel
Seleme Trigo Monica Romina
Docente: Mgr. Ademar Marcelo Vargas Antezana
Grupo: 01
09 de noviembre de 2022
Cochabamba – Bolivia
ii
Resumen
La materia de Investigación Operativa II contempla el tema de “Cadenas de
Markov” la cual desarrolla una amplia gama de soluciones y gráficas prácticas aplicables
dentro el rubro para el cual requieren ser comprendidas en esencia y complementadas con
diferentes teorías y herramientas según se precise.
Se presenta el desarrollo del marco teórico y estructura que el autor Andréi Markov
establece propuso en 1906 junto con aportaciones a la fecha de elaboración, concluyendo
en un ejercicio práctico de grupo como indicador de comprensión.
iii
Tabla de Contenidos
Introducción.....................................................................................................................................
Cadenas de Marcov..........................................................................................................................
Concepto......................................................................................................................................
Definición....................................................................................................................................
Demostración...............................................................................................................................
Ejemplo....................................................................................................................................
Probabilidades de transición absolutas y de n paso.....................................................................
Ejemplo....................................................................................................................................
Clasificación de los estados en una cadena de Markov...............................................................
Probabilidades de estado estable y tiempos de retorno medios de cadenas ergódicas..............
Ejemplo:.................................................................................................................................
Tiempo del primer paso.............................................................................................................
Ejemplo:.................................................................................................................................
Análisis de los estados absorbentes...............................................................................................
Conclusión.....................................................................................................................................
Apéndice........................................................................................................................................
Lista de referencias....................................................................................................................
1
Introducción
Andréi Andréyevich Márkov (en ruso, Андре́й Андре́евич Ма́рков; 14 de junio
de 1856-20 de julio de 1922) fue un matemático ruso conocido por sus trabajos en la
teoría de los números y la teoría de probabilidades.
En un primer artículo de 1906 A. A. Markov definió la "cadena simple" como
"una secuencia infinita x1, x2, ..., xk, xk+1, ..., de variables conectadas de tal modo que
xk+1 para cualquier k es independiente de x1, x2, ..., xk−1, en el caso de que xk sea
conocida”.
En la práctica, esta forma de evaluar y moldear los problemas cotidianos,
considerando el cómo se hacen las cosas, para la comprensión en el presente de un evento
futuro con el propósito de dar la mayor certidumbre o respaldo fundamentado a la toma
de decisiones así poder evitar desde una simple falla hasta un caos total en las
operaciones, dependiendo la magnitud del problema.
2
Cadenas de Marcov
Concepto
Una cadena de Markov es una serie de eventos, en la cual la probabilidad de que
ocurra un evento depende del evento inmediato anterior. En efecto, las cadenas de este
tipo tienen memoria, "Recuerdan" el ultimo evento y esto condiciona las posibilidades de
los eventos futuros. Esta dependencia del evento anterior distingue a las cadenas de
Markov.
Definición
“Una herramienta es útil cuando significa un beneficio tangible y amplía los
límites del conocimiento humano.
Sin lugar a dudas lo es el aporte del científico ruso Andréi Markov a la Teoría de la
probabilidad conocido como:
Cadena de Markov. Este operador permite conocer el estado probable futuro de un
proceso, a partir de sólo su probable estado actual.”
(Polanco & Castañón González, 2015)
3
Demostración
Sea Xi una variable aleatoria que caracteriza el estado del sistema en
puntos discretos en el tiempo t = 1, 2… . La familia de variables aleatorias {Xi} forma un
proceso estocástico con una cantidad finita o infinita de estados.
Proceso de Markov.
Un proceso estocástico es un proceso de Markov si un estado futuro
depende sólo del estado inmediatamente anterior. Esto significa que dados los tiempos
cronológicos t0, t1,…, tn, la familia de variables aleatorias { Xtn } = {x1, x2, Á , xn} es
un proceso de Markov si
P{Xtn = xn {Xtn - 1 = xn-1, Á , Xt0 = x0} = P{Xtn = xn ƒXtn - 1 = xn-1}
Markoviano con n estados exhaustivos y mutuamente excluyentes, las
probabilidades en un punto específico del tiempo t 5 0,1,2,… se definen como:
pij = P{Xt = jIXt-1 = i}, i = 1, 2, ……… , n, j = 1, 2, ……. , n, t = 0, 1, 2, ……….. , T
4
Esto se conoce como probabilidad de transición en un paso al ir del
estado i en el instante t -1 al estado j en el instante t. Por definición, tenemos
∑ Pij=1 ,i=1 , 2 ,… .. , n
j
Pij≥0,(i, j) = 1, 2, …….. , n
La notación utilizada en la matriz es una forma conveniente de resumir
las probabilidades de transición en un paso:
( )
p 11 p 12 p 13 … … p 1 n
P= 21 p 22 p 23 … … p2 n
p
::::
pn 1 pn 2 pn 3 … … . pnn
La matriz P define una cadena de Markov. Tiene la propiedad de que
todas sus probabilidades de transición pij son estacionarias e independientes a lo largo del
[Link] una cadena de Markov puede incluir un número infinito de estados.
Ejemplo
Cada año, durante la temporada de siembra de marzo a septiembre, un jardinero
realiza una prueba química para verificar la condición de la tierra. Según el resultado de
la prueba, la productividad en la nueva temporada puede ser uno de tres estados: (1)
buena, (2) regular y (3) mala. A lo largo de los años, el jardinero ha observado que la
5
condición de la tierra del año anterior afecta la productividad del año actual y que la
situación se describe mediante la siguiente cadena de Markov:
Las probabilidades de transición muestran que la condición de la tierra puede
o deteriorarse o permanecer como está pero nunca mejorar. Por ejemplo, si la condición
de la tierra es buena en este año (estado 1) hay 20% de que no cambie el año siguiente,
50% de probabilidad de que sea regular (estado 2), y 30% de probabilidad de que se
deteriorará a una condición mala (estado 3). El jardinero modifica las probabilidades de
transición P utilizando un fertilizante orgánico. En este caso, la matriz de transición se
vuelve
6
El uso de fertilizante puede conducir a mejorar las condiciones del suelo
Probabilidades de transición absolutas y de n paso
Dada la matriz de transición P de una cadena de Markov y el vector de
probabilidades iniciales a(0)={aj (0 ) , j=1,2 … … n }, las probabilidades absolutas
(n) (n )
a ={aj , j=1,2 … … n} después de n(> 0) transiciones se calculan como sigue:
( 1) (0 )
a =a P
a (2)=a(1 ) P=a(0 ) PP=a(0 ) P2
( 3) (2 ) (0 ) 2 (0 ) 3
a =a P=a P P=a P
a (n)=a(0 ) Pn
7
La matriz P n se conoce como la matriz de transición de n pasos. A partir de
estos cálculos, podemos ver que:
Pn=P n−1 P
Y
n n−m m
P =P P , 0<m<n
Éstas se conocen como ecuaciones de Chapman-Kolomogorov.
Ejemplo
La siguiente matriz de transición es aplicable al problema del jardinero con
fertilizante
8
La condición inicial de la tierra es buena, es decir a(0) 5 (1,0,0). Determine las
probabilidades absolutas de los tres estados del sistema después de 1,8 y 16 temporadas
de siembra.
Por lo tanto, las probabilidades absolutas requeridas se calculan como
9
Las filas de P8 y el vector de probabilidades absolutas a(8) son casi idénticos.
El resultado es más evidente para P16. Ello demuestra que, a medida que la cantidad de
transiciones aumenta, las probabilidades absolutas se vuelven independientes del a(0)
inicial. Las probabilidades resultantes se conocen como probabilidades de estado estable.
Clasificación de los estados en una cadena de Markov
Los estados de una cadena de Markov se clasifican con base en la probabilidad de
transición pij de P.
1. Un estado j es absorbente si está seguro de regresar a sí mismo en una transición; es
decir, pij
Definición.- Un estado absorbente o estacionario es aquel que tiene una probabilidad de
ser abandonado igual a cero, o sea que, una vez comenzado es imposible dejarlo igual a
cero y el proceso o se detiene completamente o se detiene para luego comenzar a partir de
algún otro estado
Una cadena de Markov es absorbente si:
Tiene por lo menos un estado absorbente
Es posible ir desde cada estado no absorbente hasta por lo menos un estado absorbente
2. Un estado j es transitorio si puede llegar a otro estado pero no puede regresar desde
otro estado.
Definición.- Un estado transitorio o no estacionario es aquel estado de sistema donde los
valores de las variables involucrados en su estudio cambian a lo largo del tiempo, es
decir, son dinámicas. Estos van de un estado a otro, no se quedan en el mismo
10
3. Un estado j es recurrente si la probabilidad de ser revisitado desde otros estados es 1.
Esto puede suceder si, y sólo si, el estado no es transitorio.
Definición.- Un estado recurrente puede volver a si mismo o puede ser revisitado
4. Un estado j es periódico con periodo de t . 1 si es posible un retorno sólo en t, 2t, 3t, etc.
pasos. Esto significa que cuando n no es divisible entre t.
Todos los estados de un conjunto cerrado deben comunicarse, lo cual significa que es
posible ir de cualquier estado a cualquier otro estado del conjunto en una o más
transiciones.
Una cadena de Markov es ergódica si todos los estados son recurrentes y aperiódica (no
periódica)
Probabilidades de estado estable y tiempos de retorno medios de cadenas ergódicas
Partiremos diciendo: Que una cadena es ergódica cuando tiene el mismo
comportamiento promedio en el tiempo como promedio durante el espacio de todos los
estados del sistema. define la probabilidad de encontrar el sistema en el estado j, después
de un gran número de transiciones y tiende a ser constante e independiente del estado
inicial.
En una cadena ergódica, las probabilidades de estado estable se definen como:
11
Estas probabilidades, las cuales son independientes de {aj(0)} , se pueden
determinar de las ecuaciones.
Lo que dice es que las probabilidades p permanecen sin cambiar después
de una transición adicional, y por esta razón representan la distribución de estado estable.
Esto se conoce como tiempo medio del primer retorno o tiempo medio de recurrencia, y
se calcula en una cadena de Markov de n estados como:
Ejemplo:
Para determinar la distribución de probabilidad de estado estable del problema del
jardinero con fertilizante, tenemos:
12
Esto quiere decir que, en promedio, se requerirán aproximadamente 10 emporadas
de siembra para que la tierra regrese a un buen estado, 2 temporadas para que regrese al
estado regular, y 3 temporadas para que regrese a un estado malo.
Tiempo del primer paso
Las probabilidades de estado estable para calcular mij, el tiempo medio del primer
retorno para el estado j. En esta sección nos interesa el tiempo medio del primer paso mij,
definido como el número esperado de transiciones para llegar por primera vez al estado j
desde el estado i.
Los cálculos tienen su origen en la determinación de la probabilidad de al menos
un paso del estado i al estado j, definido como:
13
es la probabilidad del primer paso del estado i al estado j en n transiciones.
Ejemplo:
Considere una vez más la cadena de Markov del jardinero con fertilizantes
14
Para demostrar el cálculo del tiempo del primer paso a un estado específico desde
todos los demás, considere el paso de los estados 2 y 3, (regular y malo) al estado 1
(bueno).Por lo tanto, j = 1 y
De modo que:
Por lo tanto, se requerirán 12.5 temporadas en promedio, para pasar la tierra
regular a tierra buena, y 13.34 temporadas para ir de la tierra mala a la tierra buena.
Análisis de los estados absorbentes
En el problema del jardinero, sin fertilizante la matriz de transición se da como.
Los estados 1 y 2 (condiciones de tierra buena y regular) son transitorios, y el
estado 3 (condición de tierra mala) es absorbente, porque una vez que llega a ese estado
el sistema permanecerá allí por tiempo indefinido. Una cadena de Markov puede tener
más de un estado absorbente. Por ejemplo, un empleado puede permanecer con la misma
15
compañía hasta su retiro o renunciar antes (dos estados absorbentes). En estos tipos de
cadenas, nos interesa determinar la probabilidad de llegar a la absorción y el número
esperado de transiciones para llegar a ella, dado que el sistema se inicia en un estado
transitorio específico. Por ejemplo, en la cadena de Markov antes dada, si actualmente la
tierra es buena, nos interesará determinar el promedio de temporadas de siembra hasta
que la tierra se vuelva mala, e igualmente la probabilidad asociada con esta transición. El
análisis de las cadenas de Markov con estados absorbentes puede realizarse de forma
conveniente con matrices. En primer lugar, la cadena de Markov se particiona como
sigue:
La disposición requiere que todos los estados absorbentes ocupen la esquina
sureste de la nueva matriz. Por ejemplo, considere la siguiente matriz de transición:
La matriz P puede reacomodarse y particionarse como
16
En este caso, tenemos
Dada la definición de A y N y el vector columna unitario 1 (de todos los
elementos 1), se puede demostrar que:
Tiempo esperado en el estado j iniciado en el estado i = elemento (i,j) de
Tiempo esperado para la absorción =
Probabilidad de la absorción =
17
RENTARÁS Y SERÁS FELIZ CON ELLO
¿Algún día tendrás tu propia casa?
Considerando el estimado de 544.318 estudiantes en el departamento de
Cochabamba en universidades privadas y de estado se cuenta con 9.801 abandonos al año
2021, por lo cual a priori se considera que los estudiantes titulados promedio representan
5.454 anuales según [Link] por lo tanto la probabilidad de la relación de titularse o
abandonar en Cochabamba es de 64% de abandonar y de 36% de titularse. Para fines
prácticos mantendremos una relación de 2/3 y 1/3 respectivamente.
“El 47% de los egresados de las universidades de Bolivia no consigue trabajo en los
primeros 18 meses, y la mitad de ellos sí lo hace después de ese tiempo, según el CEDLA
y un estudio de empleabilidad realizado por la Fundación para la Producción”
Verónica Zapana S. / La Paz
Sacamos dos relaciones respecto a la obtención de empleo de 1/2 de conseguir empleo
antes de los 18 meses, 1/4 de probabilidad de conseguirlo posterior los 18 meses.
Desarrollo
1/3 UNIVERSITARIO 2/3
TITULARSE NO TITULARSE
1/2
1/2
TRABAJO NO TRABAJO
1/2
MEJOR RETIRO PEOR RETIRO
1/5 4/5
BUEN
FREELANCE
TRABAJO
SEGURO
DE SALUD BIENES:
AUTOMOVIL
CASA PROPIA
ACCIDENTE
18
Conclusión
En síntesis, podemos decir que el uso de la suposición dentro el argumento
separado que pueda demostrarse matemáticamente pone a nuestra disposición la
“seguridad técnica” y la mayor certidumbre al momento de tomar decisiones.
Además de la necesidad del uso de esta herramienta para el seguimiento de
acontecimientos contemporáneos jamás antes vistos desarrollando un vistazo a las
necesidades actuales para abordar y visibilizar los problemas reales.
19
Apéndice
Proceso estocástico. Concepto matemático que sirve para usar magnitudes aleatorias que
varían con el tiempo o para caracterizar una sucesión de variables aleatorias que
evolucionan en función de otra variable (tiempo).
Propiedad de Markov. Un proceso estocástico es un proceso de Markov si un estado
futuro depende sólo del estado inmediatamente anterior.
Matriz de probabilidades de transición. La información de probabilidad de transición
para una cadena de Markov de tiempo discreto se resume en forma de matriz además que
la probabilidad de transición permite ir de un estado actual a un estado futuro.
La movilidad social se refiere al aumento equitativo de las oportunidades de las personas
en salud, educación e ingreso a lo largo de su vida y entre generaciones.
Un freelancer es un tipo de autónomo. En lugar de ser empleados de una empresa, los
freelancers suelen trabajar como autónomos, proporcionando sus servicios por contrato o
proyecto.
20
Lista de referencias
Polanco, Carlos; González, Jorge Alberto Castañón (2015). Cadenas de Markov un
vistazo al futuro Archipiélago. Revista Cultural de Nuestra América; Ciudad de
México Tomo 23 N.º 90: 27.
Taha, Hamdy A. (2012). Cadenas de Markov. Investigación de operaciones 9 edición,
571–592.
Bini, D., E. Harold, y J. Palacios, Numerical Methods for Structured Markov Chains,
Oxford University Press, Nueva York, 2005.
Cyert, R., H. Davidson, y G. Thompson, “Estimation of the Allowance for Doubtful
Accounts by Markov Chains”, Management Science, vol. 8, núm. 4, págs. 287-
303, 1963.
Pfifer, P., y R. Cassaway, “Modeling Customer Relations with Markov Chains”, Journal
of Interactive Marketing, vol. 14, núm. 2, págs. 43-55, 2000.
Grimmet, G., y D. Stirzaker, Probability and Random Processes, 2a. ed., Oxford
University Press, Oxford, Inglaterra, 1992.
Pliskin, J., y E. Tell, “Using Dialysis Need-Projection Model for Health Planning in
Massachusetts”, Interfaces, vol. 11, núm. 6, págs. 84-99, 1981.
Stewart, W., Introduction to the Numerical Solution of Markov Chains, Princeton
University Press, Princeton, NJ, 1995.
Tijms, H., A First Course in Stochastic Models, Wiley, Nueva York, 2003.
Dirección general de planificación equipo de investigación sectorial, indicadores y
análisis educativo, 2021.
CEDLA, estudio de empleabilidad, La paz; Fundación para la Producción (FUNDAPRO)
