A new solution algorithm for skip-free processes to the left

• Claus Bauer ^[1]
  1. [1] Dolby Laboratories
• Localización: Cubo: A Mathematical Journal, ISSN 0716-7776, ISSN-e 0719-0646, Vol. 12, Nº. 2, 2010, págs. 169-187
• Idioma: inglés
• DOI: 10.4067/S0719-06462010000200011
• Enlaces
  • Texto completo
• Resumen
  • español

    Este artículo propone un nuevo algoritmo solución para modelos estado-steady describiendo procesos libres-salto para la izquierda donde todo nivel tiene una fase. La complejidad computacional del algoritmo es independiente del número de niveles del sistema. Si el parámetro de salto de los procesos libre-salto es significativamente pequeño respecto del número de niveles del sistema, nuestro algoritmo numérico supera algoritmos existentes para procesos libre-salto. El algoritmo propuesto se basa en un método reciente para aplicar series de Fibonacci generalizados para la solución de modelos-steady.

  • English

    This paper proposes a new solution algorithm for steady state models describing skip-free processes to the left where each level has one phase. The computational complexity of the algorithm is independent of the number of levels of the system. If the skip parameter of the skip-free process is significantly smaller than the number of levels of the system, our algorithm numerically outperforms existing algorithms for skip-free processes. The proposed algorithm is based on a novel method for applying generalized Fibonacci series to the solution of steady state models.

• Referencias bibliográficas
  • Adhikari, A. (1986). Skip free processes: Ph.D thesis.
  • Boyer, C. B. (1943). Pascal’s Formula for the Sums of Powers of the Integers. Scripta Math. 9. 237-244
  • Brockwell, P.J. (1985). The extinction time of a birth, death and catastrophe process and of a related diffusion model. Advances Applied Probability....
  • Chen, M.F. (1999). Single birth processes. Chinese Ann. Math. Ser. A. 20. 77-82
  • Gaver, D.P,Jacobs, P.A,Latouche, G. (1984). Finite birth-and-death models in randomly changing environments. Advances in Applied Probability....
  • Grassmann, W.K,Stanford, D.A. (2000). Matrix analytic methods. Computational Probability. 153-202
  • Guen, L,Makowski, A.M. (1987). Matrix-geometric solution for finite capacity queues with phasetype distributions. Performance’87,. 269-282
  • Hansen, E,Patrick, M,Rusnack, J. (1977). Some modifications of Laguere’s method. BIT. 17. 409-417
  • Hungerford, T. W. (1974). Algebra. Springer Publishing House.
  • Kelley, W.G,Peterson, A.C. (1991). Difference equations, An introduction with applications. Academic Press, Inc.
  • Jacobs, P.A,Gaver, D.P,Latouche, G. (1984). Finite markov chain models skip free in one direction. Naval Research Logistics Quarterly. 31....
  • Kuntz, E. (1991). Algebra. Vieweg Verlag. Braunschweig.
  • Latouche, G,Ramaswami, V. (1999). Introduction to matrix analytic methods in stochastic modeling. Society for Industrial and Applied Mathematics....
  • Neuts, M.F. (1981). Matrix-geometric solutions in stochastic models: An Algorithmic Approach. The John Hopkins University Press. Baltimore,...
  • Neuts, M.F. (1989). Structured stochastic matrices of M/G/1 type and their applications. Marcel Dekker. New York.
  • Pan, Y.V. Solving a polynomial equation: Some history and recent progress. Siam Rev., Vol. 39. 187-220
  • Prachar, K. (1978). Primzahlverteilung. Springer Verlag. Berlin, Heidelberg, New York.
  • Stewart, W.J,Perros, H,Pujolle, G. On the use of numerical methods for ATM model: Modeling and performance evaluation of ATM technology. 375-396
  • Wolfram, D.A.. Solving generalized Fibonacci recurrences. The Fibonacci Quarterly. 36. 129
  • Yan, S.J,Chen, M.F. (1986). Multidimensional Q-processes. Chin. Ann. Math. Ser. A,. 7. 90-110
  • Ye, J,Li, S.Q. (1994). Folding algorithm: A computational method for finite QBD processes with level dependent transitions. IEEE Transactions...
  • Zhang, J.K. (1984). Generalized birth-death processes. Acta Mathematica Sinica. 46. 241-259
  • Zhang, Y.H.. (2001). Strong ergodicity for single-birth processes. Journal of Applied Probability. 38. 207-277