Diseño de sistemas de ingenieria usando cadenas de Markov Chains

Se realiza un análisis de la trayectoria que sigue una matriz de probabilidades de transición a un estado estable, cuando se aplica una perturbación a uno o a varios de sus elementos. Este análisis general se aplica a procesos estocásticos de tiempo discreto y con espacio de estados finito, investigando las propiedades a largo plazo de las cadenas de Markov.

Introduccion

Para el modelado los procesos y sistemas reales probabilísticos donde hay variación en la condición de operación de una maquina o las características de realización de un experimento, y aun en las políticas de un proceso de decisión, se debe tomar en cuenta que las probabilidades pueden ir cambiando en el transcurso del tiempo y mantener los parámetros estáticos. Este es el caso cuando se están analizando procesos estocásticos, que modelados a través de matrices en los cuales los parámetros siguen las leyes de probabilidad y que además son sujetos a pequeñas perturbaciones conforme transcurre el tiempo.

En este trabajo las matrices de transición de probabilidad, no consisten en arreglos fijos, sino que tienen una variación en el tiempo (Feller, 1973). Aquí se aborda el caso cuando dentro una matriz de elementos fijos puede haber uno o varios elementos variando en el tiempo, en este caso se esta hablando de tiempo en el sentido de los pasos sucesivos que usando calculo numérico, que se requieren para llevar una matriz a estado estable. Otras formas de pertubacion de matrices estocasticas es como el que se utiliza en (Borkar, 2004), donde solo se toman terminos lineales. En la teoría de matrices estocásticas se han estudiado varios casos particulares de acuerdo al arreglo espacial que resulta de analizar un problema particular y que teniendo interés práctico se puede además resolverse en forma analítica el problema de cálculo de estado estable. Algunos de estos casos son: Caminatas aleatorias con barreras absorbentes o con barreras reflejantes, el Modelo de difusión de Ehrenfest, etc. (Hillier et. al. 2002). En este trabajo la única restricción sobre la matriz estocástica es que la suma de los elementos de cada uno de los renglones de la matriz sume la unidad, considerando de esta forma matrices reales de probabilidad de transición.

El interés de estudiar los procesos estocásticos es describir el comportamiento de un sistema en operación durante algunos periodos (Hillier et. al. 2002). En este trabajo la principal cuestión que se analiza es obtener una heurística acerca del número o proporción de elementos variantes que caracterizan las probabilidades de transición no estacionarias que puede tener una matriz de transición que se lleva a estado estable, y obtener una métrica que nos indique si una matriz con elementos perturbados ha variado significativamente de la correspondiente matriz de elementos puramente estáticos o fijos correspondientes a las probabilidades de transición estacionarias, llevada durante el mismo proceso a tal estado estable.

Es importante y es útil poder sacar conclusiones de un modelo en el que se considere esta perturbación en los elementos o parámetros del sistema, debido a que en la mayoría de los casos reales se tiene un sistema donde se tienen varios elementos dentro de un proceso de producción que varían con el tiempo o sufren variaciones o deterioro en el desempeño y se quiere saber, como evolucionara ese sistema a largo plazo o equivalentemente en estado estable, en el caso en que no se tome alguna acción o decisión en tiempo presente.

El Modelo

El sistema a analizar en este trabajo son matrices estocásticas P correspondientes a probabilidades de transición donde hay elementos de matriz con valor fijo f de probabilidad de transición esto es estacionarias, y otros elementos v que a partir de su valor inicial se perturban de manera aleatoria de acuerdo a una distribución normal y se trata de llevar estas matrices a estado estable. El lo sucesivo, a la matriz con solo elementos fijos le llamaremos matriz estacionaria F, y a la que tiene elementos variantes o con perturbación matriz perturbada V. El número de elementos variantes se elige como un parámetro a analizar. La forma de llevar una matriz de transición a estado estable mediante calculo numérico es aplicar a si misma dicha matriz, o en otras palabras, pre-multiplicar o pos-multiplicar n-veces dicha matriz por si misma hasta que se llega a una situación donde los elementos de cada una de las columnas de la matriz resultante coinciden en un mismo valor a este se le llama estado estable. La variación de los elementos designados a ser perturbados se realiza en cada paso de aplicación de la matriz o sea cada vez que se multiplica P sucesivamente, lo cual equivale a una variación de algunas de las características del sistema real en el tiempo. A la matriz resultante se le puede llamar matriz de transición de n pasos.

Un caso particular de una matriz estocástica con las modificaciones que se están proponiendo P={ pij | pij = f, v } es:

(1)

Algunas consideraciones a tomar en cuenta durante los cálculos numéricos con este sistema se derivan de cálculos previos exploratorios del problema como en (Sausedo-Solorio). Cabe hacer notar que de acuerdo a tales cálculos, se ha observado que con 4 elementos variantes dentro de una matriz con 10×10 (100 elementos), o sea una densidad de elementos variantes de 4.0%, los valores de las columnas en la matriz de n pasos se modifican por completo respecto de la misma matriz llevada a estado estable sin modificar alguno de sus elementos.

También se debe distinguir los casos donde el o los elementos variantes permanecen en un posición fija, y el caso en que tales elementos pueden también variar en sus posiciones lo cual es un problema más complejo para su análisis aunque también corresponde al caso real en donde en un proceso, una maquina puede variar en su estado y después de un tiempo variar otra en un orden aleatorio. El caso que será considerado en este trabajo en que los elementos variantes están en una posición fija.

Las matrices estocásticas que serán consideradas en este trabajo son de dimensión 30×30. Se ha elegido este tamaño de acuerdo a los resultados que exponen a continuación.

El numero de iteraciones para el cual empieza a definirse un comportamiento o tendencia en el valor hacia el cual tiende cada columna es muy variable, la estadística correspondiente se presenta en la sección IV. En algunos casos, desde las primeras iteraciones los valores de las columnas convergen rápidamente a su valor de estado estable, mientras que en otras la convergencia es demasiado lenta y el número de iteraciones hasta llegar a estado estable pude ser de decenas o centenas, esto depende por supuesto de la conformación inicial de la matriz estocástica.

El proceso general de cálculo se realiza partiendo de una matriz estocástica inicial Pf, de esta matriz se forma una segunda matriz PV que constara de los mismos elementos que Pf pero con uno o varios de sus elementos modificados en base a una pequeña perturbación generada con la distribución normal N(0, ?).donde el valor de ? se elige de simulaciones previas que se presentan mas abajo. Las posiciones de los elementos a ser modificados se eligen de manera aleatoria y antes de empezar las iteraciones que llevan a la matriz Pf a estado estable. Una vez iniciado el proceso de cálculo, los elementos variantes se van actualizando de acuerdo a la distribución normal, alrededor de su valor actual. Así el mismo número de iteraciones se aplican a las dos matrices a la par, pero la terminación esta controlada cuando la matriz Pf llega a estado estable.

Para mantener la condición que los renglones de la matriz de variantes sea matriz de probabilidades entre cada aplicación, la suma de los elementos de cada renglón de la matriz se deben sumar la unidad, esto se logra haciendo un escalamiento por renglón en tal matriz.

Calculos preliminares

Para establecer un criterio que indique el grado de similitud de una matriz con su contraparte, se ha elegido un primer método que es el de calcular un parámetro para medir el comportamiento de las desviaciones que tiene la matriz perturbada respecto de la matriz estacionaria. El estadístico a utilizar consiste en medir el promedio de las diferencias al cuadrado de las parejas de matrices elemento a elemento en su camino a estado estable. Para cada pareja muestra k, se calcula la suma de las diferencias al cuadrado elemento a elemento usando la ecuación:

(2)

donde y son los elementos de las matrices perturbada y estacionaria respectivamente, y las sumas se realizan sobre los renglones y columnas de estas matrices cuadradas.

La figura 1 muestra la estadística del promedio de la raíz cuadrada de las diferencias al cuadrado elemento a elemento entre las matrices. Los puntos corresponden a la media del estadístico mk, y las barras al error típico definido en la ecuación (1) para las matrices estocásticas en estado estable y su dependencia del número de elementos variantes. Cada promedio se ha hecho sobre 500 muestras de parejas de matrices de dimensión 30×30, la barra vertical es la desviación estándar correspondiente del estadístico mk, para cada número de elementos variantes.

Como se puede ver de la figura 1, a medida que se aumenta el número de elementos variantes el error asociado en la medición del estadístico también crece como es de esperarse, además este estadístico no sigue un comportamiento consistente para valores del nV mayores de 15. Esta manera de calcular las variaciones de la matriz perturbada proporciona la información de bulto o macroscópica de las desviaciones de la matriz perturbada, da además una guía para la formulación y comparación de otros estadísticos que sean aptos para analizar este problema.

Fig. 1 Medias (puntos) y desviaciones estándar (barras de error) de la raíz cuadrada de las diferencias al cuadrado elemento a elemento de las parejas de matrices de dimensión 30×30.

El cálculo de los valores de probabilidad de estado estable se realiza mediante la solución de las ecuaciones de Chapman-Kolmogorov

para j = 0, …, M

(3)

donde las probabilidades de estado estable se definen con Así, para una matriz de transición típica (Taha, 1998):

(4)

Numéricamente mediante la matriz de transición de 10-pasos ?=A(10),

se obtienen los valores de las probabilidades de estado estable: ?1=0.2352943, ?2=0.3529415 y ?3=0.4117650; y para propósito de comparación, resolviendo para la matriz A las ecuaciones (2) se obtiene: ?1=0.2352941, ?2=0.3529412 y ?3=0.4117647. Lo que se resume en la tabla I. Dada la similitud de los resultados se justifica el método que se sigue en este trabajo para el cálculo de las probabilidades de estado estable.

Para analizar el efecto que tienen los elementos variantes sobre el resto de los elementos de la matriz de transición en su camino hacia estado estable, se realizan los cálculos utilizando la matriz (5) con un solo elemento variante a; se eligió para propósitos de demostración una esquina como se muestra la matriz (6):

(5)

Realizando el calculo de la potencia 10 de la matriz B esto es B(10), de manera analítica manteniendo el elemento a como parámetro, en cada paso (iteración), el resto de los elementos de la matriz resultante en cada paso, va haciéndose dependiente de ese elemento variante como función polinomial de a, así a medida que se realizan mas iteraciones, el grado de los polinomios va aumentando. Para la matriz B(10) los polinomios de la segunda columna son:

P1 = 0.0286884 + 0.299629 a + 0.604980 a2 + 0.1855470 a3

P2 = 0.0672045 + 0.361023 a + 0.395508 a2 + 0.0507813 a3

P3 = 0.1000730 + 0.384888 a + 0.237793 a2 + 0.0078125 a3

Es importante observar que cualquier polinomio de una columna proporciona uno de los valores de la probabilidad de estado estable. Mientras que cualquiera de los polinomios de una misma columna tendrán el mismo valor al evaluarlos en a=1/2. Es obvio que no es equivalente el aplicar la perturbación a un elemento variante en cada paso que es el enfoque usado en este trabajo, que aplicarlo a los polinomios resultantes al final del calculo de la matriz de estado estable.

Tabla 1 Comparación de los valores probabilidad de estado estable obtenidos por tres diferentes medios.

4. Resultados

Ya se han presentado en la sección III resultados preliminares para medir el comportamiento de las desviaciones que tiene la matriz perturbada respecto de la matriz estacionaria; calculado en el bulto o de manera macroscópica, el grado de similitud de una matriz con su contraparte.

En este trabajo para realizar el análisis se propone un parámetro definido mediante el cálculo de la desviación media DMK de los promedios entre columnas de la matriz de variantes y estacionaria, para cada pareja muestra K de matrices:

(6)

donde y son los promedios por columna de las matrices perturbada y estacionaria respectivamente, resultando en un vector DM de dimensión N. Para cada vector correspondiente a cada pareja muestra, se calcula la media y el error típico Err(DM) sobre todas las muestras, esto proporciona un valor y su correspondiente error con que se forma la estadística para cada numero de variantes nV dentro de la matriz perturbada, a esta técnica la identificamos como el uso del parámetro de clasificación de la desviación media DM.

A manera de ilustración, en la figura 2 se muestra el comportamiento de los promedios por columna para una pareja de matrices V y F de dimensión 10×10; donde se observan las desviaciones que se presentan entre las columnas para una pareja de matrices estocásticas, para obtener este resultado solo se realizaron tres iteraciones o pasos de calculo hacia la matriz de estado estable con el objeto de poner de relieve las desviaciones entre los promedios de cada columna. Para cada numero de columna, la desviación entre el valor promedio que tiene la columna de la matriz estacionaria y el valor promedio de la columna de la matriz perturbada es evidente.

En la figura 3 se muestra el comportamiento del parámetro de clasificación DM; para su calculo se han variado los elementos seleccionados de la matriz perturbada de acuerdo a una perturbación normal N(0, 0.1), la dimensión de las parejas de matrices es de 30×30, y para cada numero de elementos variantes se ha tomado una muestra de 100 parejas de matrices.

Fig. 2 Comportamiento típico de las desviaciones medias entre columnas de las parejas de matrices. La línea punteada corresponde a los promedios por columna de la matriz estacionaria F, la línea llena es para la matriz perturbada, para tres iteraciones a la matriz perturbada se le ha colocado un solo elemento variante.

De la figura 3 se puede observar que para un número de elementos variantes mayor de 10, en una matriz de dimensión 30×30; el estadístico basado en la media de las desviaciones de las columnas pierde estructura. Para hacer comparaciones confiables se trabajara con un límite para un número máximo de de 10 variantes.

Otro parámetro que se puede usar para la caracterización de una matriz perturbada, es el número de iteraciones que se deben llevar a cabo para llevarla a estado estable. La figura 5 se muestra el diagrama de frecuencias que se requieren para un solo elemento variante, para una muestra de 1000 parejas de matrices. Es notable el hecho del buen comportamiento del estadístico que es unimodal aunque con una caída suave a la derecha, para valores grandes de nEE. La forma de uso de esta distribución es ver que tan lejos esta el numero de iteraciones nEE para una nueva matriz a caracterizar respecto del valor medio de la distribución: y aplicar el criterio: donde y es la media y la desviación estándar respectivamente de la distribución muestral. Así el criterio se establece en base a que si desviación de la media del numero de iteraciones necesario fue menor que una desviación estándar, la matriz no varia apreciablemente, si es mayor se establece que la matriz esta alejada de la matriz estacionaria en estado estable.

Fig. 3 Se presenta el promedio de la desviación media entre columnas, para un número de variantes mayor de 10 aproximadamente, el estadístico pierde estructura.

En la figura 5 se muestra un agregado de diagramas de frecuencias para varios valores del número de elementos variantes considerados en la matriz perturbada, se puede observar que al incrementarse el número de estos elementos, el máximo de las curvas sufre un corrimiento hacia la izquierda a la vez que va aumentando en altura y la curva se va haciendo mas centrada a la media modal, se puede ver como se van definiendo estos máximos conforme crece el número de elementos variantes.

Fig. 4 Diagrama de frecuencias donde se contabiliza el número de iteraciones que se requieren para llevar la matriz a estado estable con un solo elemento variante.

Fig. 5 Agregado de diagramas de frecuencias para diferentes valores del número de elementos variantes en la matriz perturbada.

Conslusiones

Cuando se aplica una perturbación a uno o a varios de los elementos de una matriz estocastica, los valores numericos que van apareciendo en su trayecotria a estado estable esto es cuando se calculan las probabilidades de estado estable, se puede establecer una metrica para determinar el grado de variacion de la matriz perturbada respecto de la matriz original llevada tambien a estado estable. Este análisis general se aplica a procesos estocásticos de tiempo discreto y con espacio de estados finito, en la determinacion de las propiedades a largo plazo de las cadenas de Markov. Se ha hecho un calculo numérico tomando una gran muestra para cada número de elementos variantes de la matriz perturbada y ver el porcentaje de matrices que se generan y que están dentro del rango de aceptación donde la esta matriz en estado estable no varia apreciablemente respecto de la matriz estacionaria correspondiente. El criterio que se ha tomado para aceptación es un intervalo que esta centrado en la media con un margen definido por el error típico. Conforme el número de variantes aumenta, el porcentaje de matrices generadas que están en la región de aceptación, va disminuyendo, lo que da una medida del grado de variabilidad respecto de este numero de elementos perturbados. Se ha encontrado una forma de clasificar los casos de las matrices con variantes, cuando están y cuando no están lejos del comportamiento de la matriz con solo elementos fijos correspondientes.

Referencias

Borkar,V.S., Ejov, V. and Filar, J.A., (2004) "Directed Graphs, Hamiltonicity and Doubly Stochastic Matrices", Random Structures and Algorithms, Vol. 25.

Feller, W. (1973), "Introducción a la Teoría de Probabilidades y sus aplicaciones", Ed. Limusa, Mexico.

Hillier, Frederick S., Lieberman, Gerald J., (2002), "Investigación de Operaciones", 7a. edición, Ed. McGraw-Hill, México.

Sausedo-Solorio, J. M. (In process), "Caracterización de estado estable en matrices estocásticas mediante la pendiente".

Taha, H. H., (1998), Investigación de Operaciones, Prentice Hall, México.

Fifth LACCEI International Latin American and Caribbean Conference for Engineering and Technology (LACCEI"2007)

"Developing Entrepreneurial Engineers for the Sustainable Growth of Latin America and the Caribbean:

Education, Innovation, Technology and Practice"

29 May – 1 June 2007, Tampico, México.

Autores: José Manuel Sausedo-Solorio Gilberto Pérez Lechuga

Enviado por:

Ing.+Lic. Yunior Andrés Castillo S.

"NO A LA CULTURA DEL SECRETO, SI A LA LIBERTAD DE INFORMACION"®

Santiago de los Caballeros,

República Dominicana,

2015.

"DIOS, JUAN PABLO DUARTE Y JUAN BOSCH – POR SIEMPRE"®