Comparacion numerica de algoritmos para calcular distribuciones estacionarias de cadenas de Markov finitas
Tóm tắt
En este trabajo se estudia la eficiencia de un conjunto de algoritmos, exactos e iterativos, para el problema de obtener la distribución estacionaria de una cadena de Markov homogénea, irreducible y finita. Se presentan los resultados computacionales obtenidos al resolver problemas de diferentes tipos y tamaños, aleatoriamente generados, así como el tratamiento estadístico realizado sobre los mismos. Se ha comparado la estabilidad de estos algoritmos frente a la pérdida de irreducibilidad y la existencia de estados transitorios mediante su aplicación a 26 problemas test. El trabajo concluye con una discusión del comportamiento de los diversos algoritmos.
Tài liệu tham khảo
COURTOIS, P. J. (1977):Descomposability: Queueing and computer system applications, Nueva York, Academic Press.
GRASSMANN, W. K. (1990): «Computational methods in probability theory»,Handbook in OR & MS, Vol. 2 (D. P. Heyman y M. J. Sobel, eds.), North-Holland, Elsevier Science Publisher B. V., 199–254.
GRASSMANN, W. K.; TAKSAR, M. I., y HEYMAN, D. P. (1985): «Regenerative analisys and steady state distributions for Markov chains»,Operations Research, 33, 1107–1116.
GROSS, D., y HARRIS, C. M. (1985):Fundamentals of queueing theory (2.a ed.), Nueva York, Wiley.
HARROD, W. J., y PLEMMONS, R. J. (1984): «Comparison of some direct methods for computing stationary distributions of Markov chains»,SIAM J. Sci. Stat. Comput. 5, 453–469.
KOURY, R.; McALLISTER, D. F., y STEWART, W. J. (1984): «A numerical comparison of block iterative methods with aggregation for computing stationary probability vectors for nearly completely descomposable Markov Chains»,SIAM J. Algebraic Disc. Method., 5, 164–186.
LOPEZ, A. (1990):Comparación de algunos métodos para calcular distribuciones estacionarias de cadenas de Markov, Memoria de Licenciatura, Universitat de València.
PRESS, W. H.; FLANNERY, B. P.; TEUKOLSKY, S. A., y VETTERLING, W. T. (1986):Numerical Recipes: The art of scientific computing, Cambridge: Cambridge University Press.
SEELEN, L. P. (1986): «An algorithm for Ph/Ph/c queues»,European J. Operat. Res., 23, 118–127.
SHANTHIKUMAR, J. G., y SARGENT, R. G. (1984): «An algorithmic approach for a special class of Markov chains»,Operations Research Letters, 3, 81–83.
SHESKIN, T. J. (1985): «A Markov chain partitioning algorithm for computing steady state probabilities»,Operations Research, 33, 228–235.
TIJMS, H. C. (1986):Stochastic modelling and analysis, Nueva York, Wiley.