UNA EVALUACIÓN RECURRENTE PARA EL MARKOV CHAIN TREE THEOREM

Abstract

El Markov Chain Tree Theorem (MCTT) establece que la probabilidad en estado estacionario de que una Cadena de Markov Irreducible (CMI) se encuentre en uno de sus estados, es igual a la suma del peso de todos los árboles extendidos sobre el grafo asociado a la CMI cuya raíz es dicho estado, divido por una constante de normalización. En este teorema, el peso de un árbol se define como el producto de todas las tasas de transición de la CMI de parámetro continuo (o probabilidad de transición para el caso de una CMI de parámetro discreto) pertenecientes al árbol. Por otra parte, la constante de normalización es igual a la suma del peso de todos los árboles extendidos que se pueden formar sobre el grafo asociado a la cadena. Los métodos propuestos hasta ahora para implementar el MCTT generan y evalúan individualmente cada uno de los árboles extendidos sobre la CMI. En consecuencia, el costo temporal asociado a estos métodos es proporcional al número de árboles diferentes que se pueden formar sobre el grafo asociado a la CMI. En el peor caso, que corresponde a un grafo totalmente conexo, este número es O(|SS|<U+2212>1), donde |S| es el número de estados de la cadena. Este elevado costo temporal implica que estos métodos no se pueden usar para resolver CMI que posean más que unos cientos de estados. Esta es una gran limitación cuando se considera que los modelos de muchos sistemas corresponden a CMI de muchos miles de estados. Con el objeto de disminuir la dificultad recién descrita, en este trabajo se propone un nuevo método para evaluar el MCTT. El método consiste en transformar el MCTT en una ecuación que evalúa en forma recurrente la suma de los pesos de todos los árboles extendidos sobre el grafo asociado a la CMI que tienen la misma raíz. El costo temporal asociado a este nuevo método es O(|S|2 ? 3|S|). Consecuentemente, la evaluación del MCTT por medio del método propuesto en este trabajo es más eficiente que los métodos usados hasta ahora para evaluar dicho teorema. Posteriormente, en este trabajo se especializa el método propuesto para evaluar la probabilidad en estado estacionario de las cadenas Er/M/c/K y M/Er/1/K, obteniendo un método de solución más simple y rápido para dichas cadenas comparado con el método general. Adicionalmente, el método propuesto es levemente modificado para obtener un análisis de sensibilidad de cualquier CMI