Hostname: page-component-cd9895bd7-fscjk Total loading time: 0 Render date: 2024-12-23T05:09:31.418Z Has data issue: false hasContentIssue false
  • English
  • Français

Kronecker-Based Infinite Level-Dependent QBD Processes

Part of: Markov processes Physiological, cellular and medical topics

Published online by Cambridge University Press:  30 January 2018

TuǦrul Dayar  and
M. Can Orhan
TuǦrul Dayar*
Affiliation:
Bilkent University
M. Can Orhan*
Affiliation:
Bilkent University
*
∗ Postal address: Department of Computer Engineering, Bilkent University, TR–06800 Bilkent, Ankara, Turkey.
∗ Postal address: Department of Computer Engineering, Bilkent University, TR–06800 Bilkent, Ankara, Turkey.
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the ‘Save PDF’ action button.

Markovian systems with multiple interacting subsystems under the influence of a control unit are considered. The state spaces of the subsystems are countably infinite, whereas that of the control unit is finite. A recent infinite level-dependent quasi-birth-and-death model for such systems is extended by facilitating the automatic representation and generation of the nonzero blocks in its underlying infinitesimal generator matrix with sums of Kronecker products. Experiments are performed on systems of stochastic chemical kinetics having two or more countably infinite state space subsystems. Results indicate that, even though more memory is consumed, there are many cases where a matrix-analytic solution coupled with Lyapunov theory yields a faster and more accurate steady-state measure compared to that obtained with simulation.

Keywords

Markov processnumerical analysissimulationbiologyqueues: theory

MSC classification

Primary: 60J22: Computational methods in Markov chains
Secondary: 60J28: Applications of continuous-time Markov processes on discrete state spaces 92C45: Kinetics in biochemical problems (pharmacokinetics, enzyme kinetics, etc.) 92D25: Population dynamics (general)
Type
Research Article
Information
Journal of Applied Probability , Volume 49 , Issue 4 , December 2012 , pp. 1166 - 1187
Copyright
© Applied Probability Trust 

References

Baumann, H. and Sandmann, W. (2010). Numerical solution of level dependent quasi-birth-and-death processes. Procedia Comput. Sci. 1, 1561–1569.CrossRefGoogle Scholar
Bright, L. and Taylor, P. G. (1995). Calculating the equilibrium distribution in level dependent quasi-birth-and-death processes. Commun. Statist. Stoch. Models 11, 497–525.CrossRefGoogle Scholar
Buchholz, P. (1994). A class of hierarchical queueing networks and their analysis. Queueing Systems 15, 59–80.CrossRefGoogle Scholar
Dayar, T. (2006). Analyzing Markov chains based on Kronecker products. In Markov Anniversary Meeting, eds Langville, A. N. and Stewart, W. J., Boson Books, Raleigh, NC, pp. 279–300.Google Scholar
Dayar, T. and Orhan, M. C. (2011). LDQBD solver version 2. Available at http://www.cs.bilkent.edu.tr/tugrul/software.html.Google Scholar
Dayar, T., Hermanns, H., Spieler, D. and Wolf, V. (2011). Bounding the equilibrium distribution of Markov population models. Numer. Linear Algebra Appl. 18, 931–946.Google Scholar
Dayar, T., Sandmann, W., Spieler, D. and Wolf, V. (2011). Infinite level-dependent QBD processes and matrix analytic solutions for stochastic chemical kinetics. Adv. Appl. Prob. 43, 1005–1026.Google Scholar
Gans, D. (1969). Transformations and Geometries. Appleton-Century-Crofts, New York.Google Scholar
Gillespie, D. T. (1977). Exact stochastic simulation of coupled chemical reactions. J. Phys. Chem. 81, 2340–2361.CrossRefGoogle Scholar
Glynn, P. W. and Zeevi, A. (2008). Bounding stationary expectations of Markov processes. In Markov Processes and Related Topics (Inst. Math. Statist. Collect. 4), Institute of Mathematical Statistics, Beachwood, OH, pp. 195–214.Google Scholar
Grassman, W. K. (ed.) (2000). Computational Probability. Kluwer, Norwell, MA.Google Scholar
Grassman, W. K. and Stanford, D. (2000). Matrix analytic methods. In Computational Probability, ed. Grassman, W. K., Kluwer, Norwell, MA, pp. 153–204.CrossRefGoogle Scholar
Hanschke, T. (1999). A matrix continued fraction algorithm for the multiserver repeated order queue. Math. Comput. Modelling 30, 159–170.Google Scholar
Kurtz, T. G. (1972). The relationship between stochastic and deterministic models for chemical reactions. J. Chem. Phys. 57, 2976–2978.Google Scholar
Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling. SIAM, Philadelphia, PA.Google Scholar
Lee, T. L., Li, T. Y. and Tsai, C. H. (2008). {HOM4PS-2.0}: a software package for solving polynomial systems by the polyhedral homotopy continuation method. Computing 83, 109–133.CrossRefGoogle Scholar
Li, H., Cao, Y., Petzold, L. R. and Gillespie, D. T. (2008). Algorithms and software for stochastic simulation of biochemical reacting systems. Biotech. Progress 24, 56–61.Google Scholar
Loinger, A. and Biham, O. (2007). Stochastic simulations of the repressilator circuit. Phys. Rev. E 76, 051917.Google Scholar
McQuarrie, D. A. (1967). Stochastic approach to chemical kinetics. J. Appl. Prob. 4, 413–478.Google Scholar
Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins University Press, Baltimore, MD.Google Scholar
Orhan, M. C. (2011). Kronecker-based infinite level-dependent QBDs: matrix analytic solution versus simulation. Masters Thesis, Department of Computer Engineering, Bilkent University.Google Scholar
Plateau, B. (1985). On the stochastic structure of parallelism and synchronization models for distributed algorithms. In Proc. {ACM SIGMETRICS 1985} (Austin, Texas), ACM, New York, pp. 147–154.Google Scholar
Plateau, B. and Stewart, W. J. (2000). Stochastic automata networks. In Computational Probability, ed. Grassmann, W., Kluwer, Norwell, MA, pp. 113–152.Google Scholar
Pollett, P. K. and Taylor, P. G. (1993). On the problem of establishing the existence of stationary distributions for continuous-time Markov chains. Prob. Eng. Inf. Sci. 7, 529–543.Google Scholar
Ramaswami, V. and Taylor, P. G. (1996). Some properties of the rate operators in level dependent quasi-birth-and-death processes with a countable number of phases. Commun. Statist. Stoch. Models 12, 143–164.Google Scholar
Sanft, K. R. et al. (2011). Stochkit2: software for discrete stochastic simulation of biochemical systems with events. Bioinformatics 11, 2457–2458.Google Scholar
Singer, K. (1953). Application of the theory of stochastic processes to the study of irreproducible chemical reactions and nucleation processes. J. R. Statist. Soc. B 15, 92–106.Google Scholar
Sjöberg, P. L., Lötstedt, P. and Elf, J. (2009). Fokker-Planck approximation of the master equation in molecular biology. Comput. Visualization Science 12, 37–50.CrossRefGoogle Scholar
Stein, S. K. and Barcellos, A. (1992). Calculus and Analytic Geometry. McGraw-Hill, New York.Google Scholar
Stewart, W. J. (1994). Introduction to the Numerical Solution of Markov Chains. Princeton University Press, Princeton, NJ.Google Scholar
Thattai, M. and van Oudenaarden, A. (2001). Intrinsic noise in gene regulatory networks. Proc. Nat. Acad. Sci. USA 98, 8614–8619.Google Scholar
Tweedie, R. L. (1975). Sufficient conditions for regularity, recurrence and ergodicity of Markov processes. Math. Proc. Camb. Phil. Soc. 78, 125–136.Google Scholar
Van Kampen, N. G. (1992). Stochastic Processes in Physics and Chemistry. North-Holland, Amsterdam.Google Scholar