On Rate Matrix R of G=M=1-type Markov Process

Abstract

In this paper we establish an upper bound for absolute value of the determinant of rate matrix R used in matrix-geometric solution for steady-state probabilities of a structured G=M=1-type Markov process. This result, although being mostly theoretical, may be useful to establish bounds for the geometrical decay of steady-state probabilities useful in many practical problems.

Introduction

In this short paper we address a particular problem related to matrix-analytic method (MAM) of stochastic simulation. The MAM is widely used to study Markov processes of special structure, with many successful applications to stochastic models of queueing systems [11,8]. Practical applications of MAM cover many areas in modern computing and communication systems, such as Internet of Things [7], high-performance [13] and distributed [4] computing systems.

The key component of the MAM analysis of a G=M=1-type system in stationary regime is obtaining a minimal nonnegative matrix R solving the following matrix series equation or (if motivated by the model) the following matrix polynomial equation of power N > 2 which we focus our attention on: P (R) :=

N X RiA(i) = 0: i=0 In general, the solution R may be obtained either numerically [2], or by invariant subspaces approach [10], and nally, by spectral decomposition [6]. However, ( 1 ) apart from componentwise non-negativity, not many properties of the key matrix R are known in general [5].

In this paper we obtain an upper bound for the absolute value of determinant of R in terms of determinants of the submatrices of in nitesimal generator matrix of Markov process, considered to be known in advance from the model properties. The corresponding theorem is proven in Section 2. In Section 3 we discuss the applicability of this theoretical result to practical problems, and give some conclusions. 2

Upper bound on the determinant of key matrix R The system studied by MAM is usually modelled as a two-dimensional continuous time Markov chain f(X(t); Y (t)); t > 0g with countable state space E := f(0; j); j = 1; : : : ; m0g [ f(i; j); i > 1; j = 1; : : : ; mg, where the so-called phase Y (t) may take one of m (or m0 for boundary states) values and level X(t) may be increased/decreased at each transition. The state space E can be partitioned into levels with level n > 1 being the subset f(n; j); j = 1; : : : ; mg E. In many elds of interest, it is assumed that the level is increased by at most one, and decreased by at most N 1 (we focus on the case N < 1) units at each transition epoch. These models belong to the so-called structured G=M=1-type Markov processes, extensively studied in [11], with the natural example of such a process being the queue length process of an G=M=1 queue, embedded at arrival epochs. The in nitesimal generator matrix of a structured G=M=1-type process has the following block-multidiagonal representation where A(i); i = 0; : : : ; N are square matrices of order m, satisfying the balance equation

A1 = 0; where A :=

N X A(i); i=0 1 (0) is the vector of ones (zeroes) of corresponding dimension, A0;0 is a square matrix of order m0 and Ai;0; A0;1 are possibly rectangular matrices. (Recall that for these type of processes the o -diagonal elements of matrix Q, i.e. the rates of transitions of the chain, are nonnegative.) (2) (3)

The key component of the method is to obtain the steady-state probability vector = ( i;j ); i; j 2 E of the system states in the level-wise matrix-geometric form [11] (for more details on the method see e.g. [3,8]) where k = ( k;1; : : : ; k;m), and R is the minimal nonnegative (square matrix of order m) solution of nonlinear matrix equation ( 1 ), provided the stability condition holds [11] k = k 1R;

k > 1; A(0)1 <

1)A(k)1; N X(k k=2 A = 0 1 = 1: where the stochastic vector

is the solution of the linear system It is relatively easy to see (we refer to e.g. [5]) that the matrices R and A(0) have the same rank. Thus, we restrict the analysis to the case A(0) is nonsingular.

We de ne the generator function

It is easy to show that where and

N G( ) = X iA(i):

i=0 G( ) = ( I

R)J ( ; R);

N 1 J ( ; R) := X

iEi; Ei =

i=0 N X Rj i 1A(j): j=i+1 The derivation of (7) follows the Residual Theorem [9].

It follows from (3) that G( 1 )1 = 0. It is known, that in a stable system the spectrum sp(R) < 1 (i.e. the largest modulus eigenvalue, being simple, real and nonnegative, see e.g. [8]), and I R is nonsingular (which easily follows from diagonal dominance), hence it follows from (7) that Consider now J (1; R). It is easy to obtain from (8) that

J (1; R)1 = 0: J (1; R) = E0 + K(R); (4) (5) (6) (7) (8) (9) (10) We conventionally set 00 = 1 in E0.

Now consider G(0). By de nition, G(0) = A(0). However, noting that (8) provides J (0; R) = E0, we obtain from (7) (and also can see directly from ( 1 )) that

A(0) =

RE0: Thus, since A(0) is nonsingular, then E0 is nonsingular. Moreover, it follows from (9) that E0 = A( 1 ) PiN=2 Ri 1A(i), that is, E0 has positive diagonal elements and nonpositive o -diagonal elements. This means that E0 is the so-called M-matrix [12]. Hence, it is known that ( E0) 1 is by de nition a nonnegative matrix (the proof of this M-matrix de nition equivalence is given in [12]). Moreover, since K(R) is also nonnegative, then it follows from (10) and (11) that

( E0) 1K(R)1 = 1; that is, the matrix ( E0) 1K(R) is stochastic. Hence det ( E0) 1K(R) since for i = 1; : : : ; N 1, the matrices Rj i 1A(j); j > i + 2, are nonnegative. Thus, the matrix ( E0) 1 PN

i=2 A(i) is nonnegative and substochastic, which provides We have completed the proof of the following N j det A(0)j = j det Rjj det E0j > j det Rj det X A(i) : i=2 Theorem 1. If the minimal nonnegative solution R of ( 1 ) is nonsingular, then j det Rj 6

det A(0) det PN i=2 A(i) : (14) 3

Discussion

We stress that the upper bound for absolute value of the determinant j det Rj is given in terms of the matrices A(i); i = 0; : : : ; N known in advance. Note also that it immediately follows from sp(R) < 1 that j det Rj < 1. Thus, for practical purpose, one of these bounds may be used.

Let = sp(R) be the spectrum of R. Then it is easy to see that 6 j det Rj, which, together with (14), provides an upper bound for the spectrum. In particular we note that for a classical M/M/1 system, the inequality (14) becomes equality = = , where is the server load, is an arrival intensity, and is the service rate.

Let now j j be the absolute value of minimal (possibly complex) eigenvalue of rate matrix R. Then j det Rj > j jm, where, recall, m is the size of square matrix R. Thus it follows from (14) that j j 6

det A(0) det PN i=2 A(i) 1=m : This inequality may be used as an additional constraint when searching for numerically (some numerical methods of obtaining minimal eigenvalue, however, in M-matrix, can be found in [1]). Finally we note that the marginal probability of a level i > 0, i1, is known to asymptotically decrease approximately as i for i large. Then the upper bound (14) together with < j det Rj may be used to obtain a rough approximation for the level B such that B1 < " for given small constant ". However, we leave a detailed study of these practical applications for future research.

ACKNOWLEDGEMENTS The work of AR was carried out under state order to the Karelian Research Centre of the Russian Academy of Sciences (Institute of Applied Mathematical Research KRC RAS). This research is partially supported by RF President's grant MK-1641.2017.1 and RFBR, projects 18-07-00147, 18-07-00156, 18-3700094. Authors thank the referees for their suggestions that helped to improve the presentation. 2. Bini, D.A., Latouche, G., Meini, B.: Solving matrix polynomial equations arising in queueing problems. Linear Algebra and its Applications 340( 1 ), 225{244 (Jan 2002). https://doi.org/10.1016/S0024-3795(01)00426-8 3. Bladt, M., Nielsen, B.F.: Matrix-Exponential Distributions in Applied Probability, Probability Theory and Stochastic Modelling, vol. 81. Springer US, Boston, MA (2017), http://link.springer.com/10.1007/978-1-4939-7049-0, dOI: 10.1007/978-1-4939-7049-0 4. Chakravarthy Srinivas R., Rumyantsev Alexander: E cient Redundancy Techniques in Cloud and Desktop Grid Systems using MAP/G/c-type Queues. Open Engineering 8( 1 ), 17 (2018). https://doi.org/10.1515/eng-2018-0004, https://www.degruyter.com/view/j/eng.2018.8.issue-1/eng-2018-0004/ eng-2018-0004.xml 5. G. Latouche, Ramaswami, V.: Introduction to Matrix Analytic Methods in

Stochastic Modeling. ASA{SIAM, Philadelphia (1999) 6. Gail, H.R., Hantler, S.L., Taylor, B.A.: Spectral Analysis of M/G/1 and G/M/1 Type Markov Chains. Advances in Applied Probability 28( 1 ), 114 (Mar 1996). https://doi.org/10.2307/1427915, http://www.jstor.org/stable/ 1427915?origin=crossref 7. Garimella, R.M., Alexander, R.: On an exact solution of the rate matrix of G/M/1-type Markov process with small number of phases. Journal of Parallel and Distributed Computing 119, 172{178 (Sep 2018). https://doi.org/10.1016/j.jpdc.2018.04.013, http://linkinghub.elsevier.com/ retrieve/pii/S074373151830282X 8. He, Q.M.: Fundamentals of Matrix-Analytic Methods. Springer New York (2014) 9. Murthy, G.R.: Transient and equilibrium analysis of computer networks: Finite memory and matrix geometric recursions. Ph.D. thesis, Purdue University, West Lafayette (1989) 10. N. Akar, K. Sohraby: System theoretic approach to teletra c problems.

A unifying framework. In: Proceedings of GLOBECOM'96. 1996 IEEE Global Telecommunications Conference. vol. 1, pp. 163{167 vol.1 (Nov 1996). https://doi.org/10.1109/GLOCOM.1996.594353 11. Neuts, M.F.: Matrix-Geometric Solutions in Stochastic Models. Johns Hopkins

University Press, Baltimore (1981) 12. Plemmons, R.J.: M-matrix characterizations. I|nonsingular M-matrices. Linear

Algebra and its Applications 18(2), 175{188 (1977) 13. Rumyantsev, A., Morozov, E.: Stability criterion of a multiserver model with simultaneous service. Annals of Operations Research 252( 1 ), 29{39 (2017). https://doi.org/10.1007/s10479-015-1917-2, https://doi.org/10.1007/ s10479-015-1917-2

References

1. Alfa , A.S. , Xue , J. , Ye , Q. : Accurate computation of the smallest eigenvalue of a diagonally dominant M-matrix . Mathematics of Computation 71 ( 237 ), 217 { 237 (May 2001 ). https://doi.org/10.1090/S0025-5718-01-01325-4, http://www. ams.org/journal-getitem?pii= S0025 -5718-01-01325-4