×

A novel computational method for solving finite QBD processes. (English) Zbl 0970.60079

The authors present a numerical method for finding the stationary probability distribution of finite quasi-birth-and-death (QBD) processes. If the QBD state space is defined in two dimensions with \(m\) phases and \(K+1\) levels, the paper follows a matrix-geometric approach and presents a simple and constructive proof for the mixed matrix-geometric form \(\pi_k=\nu_1 R_1^k+ \nu_2R_2^{K-k}\), \(0\leq k\leq K\), of the solution vector for level \(k\). \(R_1\) and \(R_2\) are solutions to two quadratic matrix equations which can be simultaneously obtained irrespective of \(K\) by finding arbitrary bases for the left- and right-invariant subspaces of a real matrix of size \(2m\). These bases are found either by Schur decomposition or by matrix-sign function iteration with quadratic convergence rate. The vectors \(\nu_1\) and \(\nu_2\) are determined using the boundary conditions and they are obtained by solving a linear matrix equation, which is constructed with a time complexity of \(O(m^3\log_2K)\). The proposed method is numerically efficient and stable. In the limiting case of \(K\to \infty\) it is shown to yield the well-known matrix-geometric solution \(\pi_k= \nu_1R_1^k\) for infinite QBD processes. The method is extended to the cases of level-dependent and noncanonical transitions. The method is illustrated with the example of a continuous-time voice/data multiplexer. Using this example, the numerical stability and CPU time requirements of the proposed method are examined in comparison with other well-known methods.

MSC:

60J10 Markov chains (discrete-time Markov processes on discrete state spaces)

Software:

LAPACK
PDFBibTeX XMLCite
Full Text: DOI