×

Kronecker-based infinite level-dependent QBD processes. (English) Zbl 1268.60099

A Markovian system is considered with the state space formed by a Cartesian product of a countably infinite set \(n_I\) and a finite set \(n_F\). In the considered biochemical examples, the countable coordinates correspond to metabolits and the finite ones to the control unit. The authors propose a Kronecker product representation for such systems which allows reduction to an infinite level-dependent quasi-birth-and-death process. Lyapunov function approach is used to obtain the values of lower- and higher-level numbers between which a specified percentage of the steady-state probability mass \(\pi\) of the system lies. Then \(\pi\) can be computed approximately by a matrix-analytic method. The approach is compared to the stochastic simulation results. The authors conclusion is that the memory requirement of their approach is incompatibly large, but the accuracy of the results is much higher and the time to obtain the solution is much smaller compared to that of simulation.

MSC:

60J22 Computational methods in Markov chains
60J28 Applications of continuous-time Markov processes on discrete state spaces
92C45 Kinetics in biochemical problems (pharmacokinetics, enzyme kinetics, etc.)
92D25 Population dynamics (general)
PDFBibTeX XMLCite
Full Text: DOI Euclid

References:

[1] Baumann, H. and Sandmann, W. (2010). Numerical solution of level dependent quasi-birth-and-death processes. Procedia Comput. Sci. 1, 1561-1569.
[2] 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. · Zbl 0837.60081 · doi:10.1080/15326349508807357
[3] Buchholz, P. (1994). A class of hierarchical queueing networks and their analysis. Queueing Systems 15, 59-80. · Zbl 0789.60067 · doi:10.1007/BF01189232
[4] Dayar, T. (2006). Analyzing Markov chains based on Kronecker products. In Markov Anniversary Meeting , eds A. N. Langville and W. J. Stewart, Boson Books, Raleigh, NC, pp. 279-300.
[5] Dayar, T. and Orhan, M. C. (2011). LDQBD solver version 2. Available at http://www.cs.bilkent.edu.tr/\~tugrul/ software.html.
[6] 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. · Zbl 1265.60148 · doi:10.1002/nla.795
[7] 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. · Zbl 1233.60042 · doi:10.1239/aap/1324045696
[8] Gans, D. (1969). Transformations and Geometries . Appleton-Century-Crofts, New York. · Zbl 0182.23301
[9] Gillespie, D. T. (1977). Exact stochastic simulation of coupled chemical reactions. J. Phys. Chem. 81, 2340-2361.
[10] 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. · Zbl 1170.68389 · doi:10.1214/074921708000000381
[11] Grassman, W. K. (ed.) (2000). Computational Probability . Kluwer, Norwell, MA.
[12] Grassman, W. K. and Stanford, D. (2000). Matrix analytic methods. In Computational Probability , ed. W. K. Grassman, Kluwer, Norwell, MA, pp. 153-204.
[13] Hanschke, T. (1999). A matrix continued fraction algorithm for the multiserver repeated order queue. Math. Comput. Modelling 30, 159-170. · Zbl 1042.60539 · doi:10.1016/S0895-7177(99)00139-9
[14] Kurtz, T. G. (1972). The relationship between stochastic and deterministic models for chemical reactions. J. Chem. Phys. 57, 2976-2978.
[15] Latouche, G. and Ramaswami, V. (1999). Introduction to Matrix Analytic Methods in Stochastic Modeling . SIAM, Philadelphia, PA. · Zbl 0922.60001 · doi:10.1137/1.9780898719734
[16] 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. · Zbl 1167.65366 · doi:10.1007/s00607-008-0015-6
[17] 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.
[18] Loinger, A. and Biham, O. (2007). Stochastic simulations of the repressilator circuit. Phys. Rev. E 76, 051917.
[19] McQuarrie, D. A. (1967). Stochastic approach to chemical kinetics. J. Appl. Prob. 4, 413-478. · Zbl 0231.60090 · doi:10.2307/3212214
[20] Neuts, M. F. (1981). Matrix-Geometric Solutions in Stochastic Models . Johns Hopkins University Press, Baltimore, MD. · Zbl 0469.60002
[21] Orhan, M. C. (2011). Kronecker-based infinite level-dependent QBDs: matrix analytic solution versus simulation. Masters Thesis, Department of Computer Engineering, Bilkent University.
[22] 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.
[23] Plateau, B. and Stewart, W. J. (2000). Stochastic automata networks. In Computational Probability , ed. W. Grassmann, Kluwer, Norwell, MA, pp. 113-152. · Zbl 0945.65010
[24] 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.
[25] 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. · Zbl 0846.60086 · doi:10.1080/15326349608807377
[26] Sanft, K. R. et al. (2011). Stochkit2: software for discrete stochastic simulation of biochemical systems with events. Bioinformatics 11, 2457-2458.
[27] 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. · Zbl 0053.40801
[28] 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. · doi:10.1007/s00791-006-0045-6
[29] Stein, S. K. and Barcellos, A. (1992). Calculus and Analytic Geometry . McGraw-Hill, New York.
[30] Stewart, W. J. (1994). Introduction to the Numerical Solution of Markov Chains . Princeton University Press, Princeton, NJ. · Zbl 0821.65099
[31] Thattai, M. and van Oudenaarden, A. (2001). Intrinsic noise in gene regulatory networks. Proc. Nat. Acad. Sci. USA 98, 8614-8619.
[32] Tweedie, R. L. (1975). Sufficient conditions for regularity, recurrence and ergodicity of Markov processes. Math. Proc. Camb. Phil. Soc. 78, 125-136. · Zbl 0331.60047 · doi:10.1017/S0305004100051562
[33] Van Kampen, N. G. (1992). Stochastic Processes in Physics and Chemistry . North-Holland, Amsterdam. · Zbl 0511.60038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.