Matrix-Analytic Methods (butools.mam)

To load this package, either start the BuToolsInit script, or execute

addpath('butools/mam') in Matlab,
<<BuTools`MAM` in Mathematica,
from butools.mam import * in Python/Numpy.

Under Matlab, the SMCSolver package [1] (both for QBD and M/G/1,G/M/1 type Markov chains) must be in path as well.

Quasi Birth-Death Processes

Quasi Birth-Death Processes (QBDs, [2]) are discrete time or continuous time Markov chains. The state space is two dimensional, it is composed by the levels and the phases. QBDs have a block-tridiagonal generator.

\[\begin{split}Q=\begin{bmatrix}L_0 & F & &\\ B & L & F & \\ & B & L & F \\ & & \ddots & \ddots & \ddots \end{bmatrix}\end{split}\]

The matrix describing the transitions to the previous level is denoted by \(B\) (backward), the ones to the next level by \(F\) (forward), finally, transitions that are not accompanied by the change of the level are held by matrix \(L\) (local).

The QBDs have a matrix-geometrically distributed stationary distribution,

\[\pi_k=\pi_0 R^k,\]

where the \(i\) th entry of vector \(\pi_k\) is the stationary probability that the level is \(k\) and the phase is \(i\).

Matrix \(R\) is the solution of a matrix-quadratic equation.

BuTools has functions to determine both \(\pi_0\) and \(R\), thus all ingredients to easily calculate the stationary distribution of QBDs. Several functions are just wrappers to SMCSolver, so do not forget to give credit to [1] as well if you are using it.

M/G/1 and G/M/1 Type Markov Chains

M/G/1 and G/M/1 type Markov chains are more general than QBDs. They both have a block-triangular generator. For M/G/1 the structure of the generator is

\[\begin{split}Q=\begin{bmatrix}B_0 & B_1 & B_2 & B_3 & \dots \\ A_0 & A_1 & A_2 & A_3 & \dots \\ & A_0 & A_1 & A_2 & \dots \\ & & \ddots & \ddots & \ddots \end{bmatrix}\end{split}\]

while for G/M/1 type it is

\[\begin{split}Q=\begin{bmatrix}B_0 & A_0 \\ B_1 & A_1 & A_0 \\ B_2 & A_2 & A_1 & A_0 \\ \vdots & \ddots & \ddots & \ddots & \ddots \end{bmatrix}\end{split}\]

BuTools is able to calculate the stationary solution of such Markov chains. The corresponding functions are mostly wrappers of SMCTools, please cite [1] if you are using them.

Markovian Fluid Models

Markovian fluid models [3] are characterized by a continuous time Markov chain with generator \(Q\), and a diagonal matrix \(R\). The \(i\) th entry of the diagonal of \(R\) is the rate at which the fluid arrives to the fluid storage when the background Markov chain is in state \(i\) . Fluid rates can be positive (the fluid level increases), negative (the fluid level decreases) and can be zero as well (while being in these states the fluid level of the storage remains the same).

There is a class of Markovian fluid models, called canonical fluid models, which are much easier to hande technically. In canonical fluid models the fluid rates can be either 1 or -1, zero rates or rates other than these two are not allowed. Canonical fluid models are characterized by the blocks of the generator of the background Markov chain partitioned according to the sign of the associated fluid rate as

\[\begin{split}Q=\begin{bmatrix} Q_{++} & Q_{+-} \\ Q_{-+} & Q_{--} \end{bmatrix}\end{split}\]

The steady state solution of Markovian fluid models (both canonical and general ones) is matrix-exponential. The probability that the fluid level is exactly 0 while being in various states of the background process are denoted by vector \(p_m\), and the density vector corresponding to fluid level is \(x\) is expressed by

\[\pi(x)=\alpha e^{Kx} C,\]

BuTools provides functions to obtain the initial vector \(\alpha\), matrix \(K\) and closing matrix \(C\) both for canonical and general fluid models.

Functions to solve QBDs

QBDFundamentalMatrices Returns any combination of the R, G, and U matrices of a discrete or continuous time QBD
QBDSolve Returns the parameters of the matrix-geometrically distributed stationary distribution of a QBD
QBDStationaryDistr Returns the stationary distribution of a QBD up to a given level

Functions to solve M/G/1 and G/M/1 type Markov chains

MG1FundamentalMatrix Returns matrix G, the fundamental matrix of an M/G/1 type Markov chain
MG1StationaryDistr Returns the stationary distribution of an M/G/1 type Markov chain up to a given level
GM1FundamentalMatrix Returns matrix R, the fundamental matrix of a G/M/1 type Markov chain
GM1StationaryDistr Returns the stationary distribution of a G/M/1 type Markov chain up to a given level

Functions to solve Markovian fluid models

FluidFundamentalMatrices Returns any combination of the Psi, K, and U matrices of a canonical Markovian fluid model
FluidSolve Returns the parameters of the matrix-exponentially distributed stationary distribution of a canonical Markovian fluid model
GeneralFluidSolve Returns the parameters of the matrix-exponentially distributed stationary distribution of a general Markovian fluid model
FluidStationaryDistr Returns the cummulative distribution of the stationary fluid level of a Markovian fluid model

Refereces

[1](1, 2, 3) Bini, D. A., Meini, B., Steffé, S., Van Houdt, B. (2006, October). Structured Markov chains solver: software tools. In Proceeding from the 2006 workshop on Tools for solving structured Markov chains (p. 14). ACM.
[2]Latouche, Guy, Vaidyanathan Ramaswami. “Introduction to matrix geometric methods in stochastic modeling.” ASA-SIAM Series on Statistics and Applied Probability. SIAM, Philadelphia PA (1999).
[3]A da Silva Soares. “Fluid Queues.” PhD dissertation, de l’Université libre de Bruxelles, 2005.