ON THE APPLICATION OF MATRIX SCALING AND POWERING METHODS OF SMALL STATE SPACES FOR SOLVING TRANSIENT DISTRIBUTION IN MARKOV CHAIN

  • Olanrewaju Agboola Nigerian Army University Biu
  • Ali S. Nehad Sejong University Seoul 05006, Korea
Keywords: infinitesimal generator, linear combination, matrix-powering, matrix scaling, Padé approximants, uniformization method

Abstract

The iterative solution methods for transient distribution in Markov chain is the computation of state probability distributions at an arbitrary point of time, which in the case of a discrete-time Markov chain means, finding the distribution at some arbitrary time step   denoted , a row vector whose  component is the probability that the Markov chain is in state  at time step . In this study, the solutions of transient distribution in Markov chain using matrix scaling and powering methods for small state spaces which produce a significantly more accurate response in less time for some types of situations and also, tries to get to the end result as quickly as possible has been investigated, in order to provide some insight into the solutions of transient distribution of Markov chain. Our goal is to compute solutions and algorithms for tiny state spaces utilizing matrix scaling and powering approaches, which begin with an initial estimate of the solution vector and then comes closer and closer to the true solution with each step or iteration. With the help of several existing Markov chain laws, theorems, and formulas, matrices operations such as multiplication with one or more vectors, Padé variant of the matrix-powering and scaling technique are used. While the algorithms are explained, the transient distribution vector’s   Padé approximants , and a backward error analysis of the Padé approximation are obtained for certain illustrative examples..

Author Biography

Ali S. Nehad, Sejong University Seoul 05006, Korea

Department of Mechanical Engineering, Senior Lecturer

References

Agboola, S. O. (2022). The Decomposition and Aggregation Algorithmic Numerical Iterative Solution Methods for the Stationary Distribution of Markov Chain, Journal of Scientific and Engineering

, 9(1): 116 - 123. CODEN (USA): JSERBR. www.jsaer.com.

Agboola, S. O. (2021). Direct Equation Solving methods Algorithms Compositions of Lower -Upper Triangular Matrix and Grassmann–Taksar–Heyman for the stationary distribution of Markov chains, International Journal of Applied Science and Mathematics (IJASM), Volume 8, Issue 6, pp. 87 – 96. www.ijasm.org.

Agboola, S. O. (2016). Repairman problem with multiple batches deterministic repairs, Unpublished Ph.D. Thesis, Obafemi Awolowo University, Ile-Ife, Nigeria, 256pp.

Agboola, S. O. and Ayoade, A. A. (2021). On the Analysis of Matrix Geometric and Analytical Block Numerical Iterative Methods for Stationary Distribution in the Structured Markov Chains, International Journal of Contemporary Applied Researches (IJCAR), Vol. 8, No. 11, pp. 51 – 65, Turkey, http://www.ijcar.net

Agboola, S. O. and Ayinde, S. A. (2021). The Performance Measure Analysis on the States Classification in Markov Chain, Dutse Journal of Pure and Applied Sciences (DUJOPAS), Faculty of Science Journal, Federal University Dutse, Jigawa State. Vol. 7 No. 04b, pp. 19 -29, 2021. https://fud.edu.ng/dujopas.

Agboola, S. O. and Badmus, N. I. (2021). Application of Renewal Reward Processes in Homogeneous Discrete Markov Chain, FUDMA Journal of Sciences (FJS), Faculties of Earth Science and Physical Science Journal, Federal University DutsinMa. Vol. 5 No. 4, pp 210 – 215. https://fjs.fudutsinma.edu.ng

Azizah, A., Welastica, R., Nur, F., Ruchjana, B. and Abdullah, A. (2019). An application of Markov chain for predicting rainfall data at West Java using data mining approach, Earth and Environmental Science, 303(1): 203 – 216.

Baker, A. (1975). Essentials of Padé Approximants. Academic Press, New York,

Clemence. T. (2019). Markov chain modelling of HIV, Tuberculosis, and Hepatitis B transmission in Ghana, Hindawi, Interdisciplinary Perspective on Infectious Disease, 27(1): 204 – 214.

Dayar., T. (1998). Permuting Markov chains to nearly completely decomposable form. Technical Report BU-CEIS-9808, Department of Computer Engineering and Information Science, Bilkent University, Ankara, Turkey. pp. 18 – 31.

Moler, C. and Van Loan, C (1978). Nineteen dubious ways to Compute the Exponential of a Matrix. SIAM Review, Vol. 20, No. 4, pp. 801–836.

Pesch, T., Schroder, S., Allelein, H. and Hake, J. (2015). A new Markov chain-related statistical approach for modelling synthetic wind power time series, New Journal of Physics, Deutsche Physikalische, 35(2): 64 – 85.

Philippe, B. and Sidje, B. (1993) Transient Solution of Markov Processes by Krylov Subspaces, Technical Report, IRISA—Campus de Beaulieu, Rennes, France. pp. 11 - 24.

Ramaswami, V. (1988). A Stable Recursion for the Steady State Vector in Markov chains of M/G/1 type. Communication in Statist. Stochastic Models, 4(1): 183–188.

Ramaswami, V. and Neuts, M. F. (1980). Some explicit formulas and computational methods for infinite server queues with phase-type arrivals. Journal of Applied Probability, 17(1): 498–514.

Romanovsky, V.I. (1970). Discrete Markov Chains, Wolters-Noord off, Groningen, Netherlands. pp. 23 – 44.

Saff, E. (1973). On the Degree of the Best Rational Approximation to the Exponential Function. Journal of Approximation Theory, Vol. 9, pp. 97–101, 1973.

Stewart, W. J. (1994). Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton, N.J. pp. 14 – 38.

Stewart, W. J. (2009). Probability, Markov Chain, Queues and Simulation, Princeton University Press, United Kingdom. pp. 1- 42.

Uzun, B. and Kiral, E. (2017). Application of Markov chain-fuzzy states to the gold price, Science Direct. ELSEVIER, 120(1): 365 – 371.

Vermeer, S. And Trilling, D. (2020): Toward a better understanding of a new user journey: A Markov chain approach. Journalism Journal, 21(1): 879 – 894.

Ward, R (1977). Numerical Computation of the Matrix Exponential with Accuracy Estimate, SIAM

Journal on Numerical Analysis, Vol. 14, No. 4, pp. 600–610.

Zakaria, N. N., Mahmod, O., Rajalmgan, S., Hamita, D., Lazim, A. and Evizal, A. (2019). Markov chain model development for forecasting air pollution index of Miri, Sarawak, Sustainability 11(1): 5190 -5202.

Published
2022-03-31
How to Cite
AgboolaO., & NehadA. S. (2022). ON THE APPLICATION OF MATRIX SCALING AND POWERING METHODS OF SMALL STATE SPACES FOR SOLVING TRANSIENT DISTRIBUTION IN MARKOV CHAIN . FUDMA JOURNAL OF SCIENCES, 6(1), 135 - 140. https://doi.org/10.33003/fjs-2022-0601-849