INSTITUTO TECNOLOGICO NACIONAL DE
MEXICO CAMPUS ATITALAQUIA
INGENIERIA INDUSTRIAL
Investigación de Operaciones II
Tema 4.1 “Introducción a las cadenas de
Markov”
JUAREZ URIBE OLIVER YAEL
5IA
Introducción
Los Procesos de Márkov o Cadena de Márkov, forman parte de los Procesos Estocásticos
como una herramienta que se basa en las probabilidades y es necesaria en la toma de
decisiones a nivel empresarial debido a que estudia la evaluación de ciertos sistemas de
ensayos repetitivos en un intervalo de tiempo dado. Esta toma decisiones se realiza en las
distintas áreas como Contabilidad, Administración, Marketing, Logística, Personal, entre
otros. Esta sucesión de observaciones con determinado número de resultados, cada uno
de los cuales tiene una probabilidad, depende sólo del resultado de la etapa
inmediatamente anterior. Este proceso en el que intervienen variables aleatorias indexadas
en el tiempo se denomina cadenas de Márkov, haciendo honor al matemático ruso Andrei
Andreyevich Márkov, quien creó este método. De esta forma la probabilidad de ocurrencia
de un evento depende del evento anterior.
Objetivo
Objetivo general
Emplear las cadenas de Márkov como una herramienta de resolución para situaciones
relacionadas con procesos estocásticos.
Objetivos específicos
• Reconocer las generalidades de una cadena de Márkov.
• Identificar las características de un proceso estocástico markoviano.
• Clasificar de forma general las cadenas de Márkov.
• Formular modelos soportados en cadenas de Márkov.
¿Qué es una cadena de Márkov?
Una cadena o modelo de Márkov es una herramienta para analizar procesos en que la
sucesión de variables aleatorias evoluciona en función de otra variable. Dichas variables o
conjunto de variables que tienen efectos aleatorios, reciben el nombre de proceso
estocástico. La inserción de este método a las matemáticas se le atribuye a Andrei
Andreyevich Márkov.
Una cadena de Márkov es una secuencia X1, X2, X3,… de variables aleatorias. El valor de
Xn es el estado del proceso en el tiempo n. De esta manera se obtiene la propiedad
markoviana:
Donde xi es el estado del proceso en el instante i.
¿Quién fue Andrei Márkov Andreyevich?
Andrei Márkov Andreyevich nació el 2 de junio de 1856 en Riazán, Rusia. Márkov fue uno
de los más famosos discípulos de Chebyshev y sus ideas se basaban en representar la
probabilidad como una ciencia matemática exacta y práctica. La introducción de la cadena
de Markov como un modelo para el estudio de variables aleatorias fue uno de los aportes
más representativos a las matemáticas. Markov también escribió un libro de texto de
estadística y probabilidad. Su obra influyó en muchos otros famosos matemáticos y
estadísticos, incluyendo SN Bernstein, Romanovsky VI, y Jerzy Neyman. Después de
contribuir en gran medida a la teoría de números, análisis, cálculo de diferencias finitas,
teoría de la probabilidad (con las cadenas de Markov) y las estadísticas, murió en
Petrogrado (San Petersburgo antes, ahora Leningrado), el 20 de julio de 1922.
Casos especiales (cadenas absorbentes, cadenas cíclicas).
Cadenas Absorbentes- Matriz Absorbente.
Una cadena de Markov con espacio de estados finito se dice absorbente si se cumplen las
dos condiciones siguientes:
1. La cadena tiene al menos un estado absorbente.
2. De cualquier estado no absorbente se accede a algún estado absorbente.
Si denotamos como A al conjunto de todos los estados absorbentes y a su complemento
como D, tenemos los siguientes resultados:
• Su matriz de transición siempre se puede llevar a una de la forma
donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0
es la matriz nula y R alguna submatriz.
Para describir procesos o sistemas que cesan (o vuelven a comenzar) después de alcanzar
determinadas condiciones se utiliza un caso especial de cadenas de Márkov. Por ejemplo,
después de hallar un número predeterminado de partes defectuosas o aceptables, se
suspende una inspección; después de un tiempo una cuenta se vuelve incobrable o pagada,
etc. Esos procesos pueden modelarse como una cadena de Márkov absorbente. Un estado
absorbente es aquel que tiene una probabilidad de ser abandonado igual a cero, es decir
que, una vez comenzado es imposible salir de él, y el proceso o se detiene completamente
o se detiene para luego comenzar a partir de algún otro estado.
Una cadena de Márkov es absorbente si:
1. Tiene por lo menos un estado absorbente.
2. Es posible ir desde cada estado no absorbente hasta por lo menos un estado
absorbente, no es necesario que esto se dé en un paso, ni es necesario que exista
la posibilidad de alcanzar cada estado absorbente a partir de cualquier estado no
absorbente.
Una cadena de Márkov se dice regular (también primitiva o ergódica) si existe alguna
potencia positiva de la matriz de transición cuyas entradas sean todas estrictamente
mayores que cero. Cuando el espacio de estados E es finito, si P denota la matriz de
transición de la cadena se tiene que:
donde W es una matriz con todos sus renglones iguales a un mismo vector de probabilidad
w, que resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas
regulares, este vector invariante es único.
Cadenas homogéneas y no homogéneas.
Una cadena de Márkov es homogénea si la probabilidad de ir del estado i al estado j en un
paso no depende del tiempo en el que se encuentra la cadena, es decir:
Si para alguna pareja de estados y para determinado tiempo n, la propiedad antes
mencionada no se cumple se puede decir que la cadena de Márkov es no homogénea.
Probabilidades y matriz de transición.
La probabilidad de ir del estado i al estado j en n unidades de tiempo está dada por:
En la probabilidad de transición, en un paso, se omite el superíndice y de esta forma se
obtiene:
Las probabilidades de transición en n pasos satisfacen la ecuación de Chapman-
Kolmogorov, es decir, para cualquier k tal que 0 < k < n se cumple que:
Donde E denota el espacio de estados.
Cuando la cadena de Márkov es homogénea, muchas de sus propiedades se pueden
obtener a través de su matriz de transición, definida, entrada a entrada, como:
En donde la entrada i, j corresponde a la probabilidad de ir del estado i a j en un paso.
De la misma manera se puede obtener la matriz de transición en n pasos como:
Una matriz de transición para una cadena de Márkov de n estados es una matriz de n X
n con todos los registros no negativos y con la propiedad adicional de que la suma de los
registros de cada columna (o fila) es 1.
Los Pij se agrupan en la matriz de transición de la cadena de Márkov, de tal forma que:
Representación gráfica de una matriz de transición
Las probabilidades de un estado a otro se pueden representar a través de un diagrama de
transición de estados, el cual es un grafo dirigido en donde los nodos son los estados de la
cadena de Márkov y cuyos arcos se deben etiquetar con la probabilidad de transición entre
los estados que unen. Si dicha probabilidad es cero, no se pone arco.
Propiedades:
• La suma de las probabilidades de los estados debe ser igual a 1.
• La matriz de transición debe ser cuadrada, es decir, debe tener el mismo
número de filas y columnas.
• Las probabilidades de transición deben estar entre 0 y 1.
A continuación, se desarrollarán varios ejemplos para comprender el significado de una
cadena de Márkov, una matriz de transición y las probabilidades de transición.
Ejemplo
Un agente comercial realiza su trabajo en tres ciudades: Bucaramanga, Cali y Pereira. Para
evitar desplazamientos innecesarios está todo el día en la misma ciudad y al día siguiente
se desplaza a otra ciudad, si no tiene suficiente trabajo. Después de estar trabajando un
día en Pereira, la probabilidad de tener que seguir trabajando allí al día siguiente es 0.4, la
de tener que viajar a Cali es 0.4 y la de tener que ir a Bucaramanga es 0.2. Si el viajante
duerme un día en Cali, con probabilidad de un 20%, tendrá que seguir trabajando en la
misma ciudad al día siguiente; en el 60% de los casos viajará a Pereira, mientras que irá a
Bucaramanga con probabilidad de 0.2. Por último, si el agente comercial trabaja todo un
día en Bucaramanga, permanecerá en esa misma ciudad al día siguiente con una
probabilidad de 0.1, irá a Cali con una probabilidad de 0.3 y a Pereira con una probabilidad
de 0.6.
a) Si hoy el viajante está en Pereira, ¿cuál es la probabilidad de que también tenga
que trabajar en el mismo lugar al cabo de cuatro días?
b) ¿Cuáles son los porcentajes de días en los que el agente comercial está en cada
una de las tres ciudades?
Solución
La matriz de transición P es la siguiente para el orden Bucaramanga, Cali y Pereira.
Para solucionar la primera pregunta se debe averiguar el término P433 , es decir, el término
que ocupa la tercera fila y la tercera columna de la matriz P4, lo cual se obtiene con la fila 3
y columna 3 de P4, cuyos valores son:
En la segunda pregunta, para hallar las probabilidades estacionarias, se debe proceder de
la siguiente manera:
Desarrollando resulta el sistema de ecuaciones lineales:
Se elimina y en las dos primeras -33 x + 12 z = 0 y se elimina y en las dos últimas: 12 z =
6; de ambas se deduce que x = 2/11 = 0.1818; y = 7/22 = 0.3181; z = 0.5, es decir:
• Bucaramanga = 18%
• Cali = 32%
• Pereira = 50%
Conceptos generales
Las cadenas de Márkov están caracterizadas por unos tiempos de entrada, recurrencia de
sus estados y una periodicidad, conceptos importantes que describen el comportamiento
del sistema.
Tiempos de entrada:
Si C ∁ E, se define el primer tiempo de entrada a C como la variable aleatoria
TC denota la primera vez que la cadena entra al conjunto de estados C.
Tipos de cadenas de Márkov
Cadenas irreducibles.
Una cadena de Márkov es irreducible si cumple con cualquiera de las siguientes
condiciones (equivalentes entre sí):
1. Desde cualquier estado de E se puede acceder a cualquier otro.
2. Todos los estados se comunican entre sí.
3. C(x)=E para algún x∈E.
4. C(x)=E para todo x∈E.
5. El único conjunto cerrado es el total.
Cadenas positivo-recurrentes.
Una cadena de Márkov es positivo-recurrente si todos sus estados son positivo-recurrentes.
Si la cadena es irreducible existe un único vector de probabilidad invariante y está dado por:
Cadenas regulares.
Una cadena de Márkov es regular (también primitiva o ergódica) si existe alguna potencia
positiva de la matriz de transición cuyas entradas sean todas estrictamente mayores que
cero.
Cuando el espacio de estados E es finito, si P denota la matriz de transición de la cadena
se tiene que:
Donde W es una matriz con todos sus renglones iguales a un mismo vector de probabilidad
w, que resulta ser el vector de probabilidad invariante de la cadena. En el caso de cadenas
regulares, este vector invariante es único.
Cadenas absorbentes.
Una cadena de Márkov con espacio de estados finito se llama absorbente si se cumplen
las siguientes condiciones:
1. La cadena tiene al menos un estado absorbente.
2. De cualquier estado no absorbente se accede a algún estado absorbente.
Si se denota como A al conjunto de todos los estados absorbentes y a su complemento
como D, se obtienen los siguientes resultados:
Su matriz de transición siempre se puede llevar a una de la forma:
Donde la submatriz Q corresponde a los estados del conjunto D, I es la matriz identidad, 0
es la matriz nula y R alguna submatriz.
Esto quiere decir que no importa en dónde se encuentre la cadena, eventualmente
terminará en un estado absorbente.
Ejercicios Resueltos de Cadenas de Markov
Una empresa está considerando utilizar Cadenas de Markov para analizar los cambios en
las preferencias de los usuarios por tres marcas distintas de un determinado producto. El
estudio ha arrojado la siguiente estimación de la matriz de probabilidades de cambiarse de
una marca a otra cada mes:
Si en la actualidad la participación de mercado es de 45%, 25% y 30%, respectivamente.
¿Cuáles serán las participaciones de mercado de cada marca en dos meses más?
En primer lugar, definimos la variable aleatoria X_{n} que representa la marca que adquiere
un cliente cualquiera en el mes n. Dicha variable aleatoria puede adoptar los valores 1,2,3
en el mes n=0,1,2,3,..
Adicionalmente conocemos cuál es la distribución inicial y la matriz de probabilidades de
transición en una etapa tal como se observa a continuación:
Luego para conocer la distribución de las participaciones de mercado al cabo de 2 meses
(2 etapas) podemos utilizar la fórmula fn=PT*f n-1:
Se concluye que las cuotas de mercado (participaciones de mercado) en dos meses ha
cambiado de un 45% a un 40.59%; de un 25% a un 33.91% y de un 30% a un 25.50%, para
las marcas 1,2 y 3 respectivamente.
Aplicaciones.
Las cadenas de Márkov tienen variadas utilidades en el mercado, por esta razón es una
herramienta importante para solucionar problemas en las empresas, como, por ejemplo, el
share de marcas, la dinámica de mantenimiento y la planeación de tareas administrativas.
Pero no sólo se emplean en las áreas de la industria, también son usadas para formular
modelos climatológicos, resolver problemas de estadística, termodinámica, realizar
simulaciones como el modelo M/M/1, para rankear las páginas web de Google, en los
juegos de azar y en diversos algoritmos de composición musical, entre otros.
Conclusión
Como conclusión las cadenas de Markov nos permite hacer análisis sobre el estudio de los
comportamientos de ciertos sistemas en ciertos periodos que pueden ser cortos o largos.
Además, se tiene una relación con las probabilidades absolutas. Pero sin embargo lo más
importante es el estudio del comportamiento sistemas a largo plazo, cuando el número de
transiciones tiene al infinito. Al conocer más o menos las probabilidades de un experimento,
esto a su vez nos permitirá conocer a corto plazo los estados en que se encontrarían en
periodos o tiempos futuros y tomar decisiones que afectarán o favorecerán nuestros
intereses, y tomar una decisión de manera consciente y no se comentan muchos errores.
Esto también nos proporcionara un tiempo estimado para que identifiquemos cada estado
y el periodo en que se encuentra con la implementación de un proceso, también se
establece las probabilidades como una herramienta más en las cadenas de Markov.
