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
|
= |
æ ç ç ç ç
ç ç ç è
|
|
| |
ö ÷ ÷ ÷ ÷
÷ ÷ ÷ ø
|
. |
| (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
and
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
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.