Modelling with Quasi-Birth-and-Death Processes Modelling with Quasi-Birth-and-Death Processes

P.G. Taylor

Department of Applied Mathematics, University of Adelaide, South Australia 5005 (ptaylor@maths.adelaide.edu.au)

Abstract

Many models which arise in applied probability can be efficiently formulated using a matrix-analytic framework. In particular, many models can be formulated as quasi-birth-and-death processes (QBDs). These are discrete or continuous-time Markov chains which have a two-dimensional state space {(k,j):k ³ 0, 1 £ j £ M} and whose transition matrix is of the block partitioned form

^
P
 
= æ
ç
ç
ç
ç
ç
ç
ç
è
A(0)1
A0
0
0
¼
A2
A1
A0
0
¼
0
A2
A1
A0
¼
0
0
A2
A1
¼
:
:
:
:
···
ö
÷
÷
÷
÷
÷
÷
÷
ø
.
(1)

In (1981) and (1989), Neuts showed how QBDs can be analysed. In the discrete-time case, this analysis proceeds by attempting to solve the matrix quadratic equations

G = A2 + A1 G + A0G2
(2)
and
R = A0 + R A1 + R2A2.
(3)
The continuous-time case is similar. The minimal non-negative solutions of equations (2) and (3) have physical interpretations and can be used to derive many performance measures for QBDs. The most well-known of these is the matrix-geometric form of the stationary distribution x = (x0,x1,¼,) given by
xn = x0 Rn.
(4)

The set of level-dependent QBDs is a generalisation the set of classical QBDs with greater modelling power. Such processes have the structure (1) but transition rates are permitted to depend on the level of the process. In this case, the matrix quadratic equations (2) and (3) generalize to become the non-linear systems of equations,

Gk = A2(k) + A1(k) Gk + A0(k)Gk+1Gk
(5)
and
Rk = A0(k) + Rk A1(k+1) + RkRk+1A2(k+2)
(6)
respectively. As in the classical case, equations (5) and (6) can be shown to possess minimal non-negative solutions which have physical significance and which can be used to construct performance measures of interest.

In the first of the two talks, I shall introduce classical QBDs, give some examples of models which can be constructed using them and discuss how they can be analysed. In the second talk, I shall discuss the level-dependent extensions and their analysis and mention several interesting further questions involving solutions of (2), (3), (5) and (6) which are not the minimal non-negative solutions.


File translated from TEX by TTH, version 1.94.
On 27 Apr 1999, 16:03.