This is just a preliminary version of the software and of the documentation.
A lot of features are missing and that, I hope,
will be added soon.
Full use is permitted for academic purposes. In order to obtain source files contact
the author.
1 Introduction
The MOnocyclic Markovian Identifier (MOMI) is the numerical implementation of the
results presented in [3]. The idea is to find highly sparse representations
for general phase-type distributions. Given a finite absorbing Markov chain characterized by
the initial probability distribution vector a and the transition matrix T,
the p.d.f. of the hitting time distribution and its Laplace-Stieljes transform are obtained as:
f(t)=aetT(-Te),
f(s)=a(sI-T)-1(-Te),
We focus on the Laplace-Stieljes transform expression which is a rational function,
with some specific properties ([4], [5]).
The problem that we try to solve is :
given the Laplace-Stieljes transform of a phase-type distribution,
find out a representation, i.e
a Markov chain that could generate this phase-type distribution.
A general approach in order to construct the representation (a , T)
of a phase-type distribution is provided in [2].
Our goal here is to find a representation with a highly sparse transition matrix.
When the Laplace-Stieljes transform has only real poles we can always find Coxian representations
([1] [6] [7]).
Such representations are bi-diagonal.
We generalize the results presented in [6] for the general case, when
there are also complex poles of the Laplace-Stieljes transform.
The details are provided in [3].
The representation that we find is quasi-bi-diagonal with a number of backward transitions that equals
the number of complex pole pairs. Each state of the Markov chain can belong
at most to one cycle of the chain. Inside a cycle all transition rates are equal
We call such a representations a Mixture of Monocyclic Erlang distributions (MME).
2 The algorithm
We assume that the user is familiar with the technique and the notations
used in [6].
Our technique is very similar.
We write down a MME generator Q such that the pole of
the Laplace-Stieljes transform
are among the eigenvalues of the generator.
We compute the initial probability vector a
We compute the residual life trajectory Rtµ, t³ 0
We compute T such that RTµÎ PH(Q)
For computational purposes we try to optimize T such that
we maximize the minimal value of the elements of ae(-TQ)
We compute the approximants of the trajectory as in [6], [3]
We write down the final generator ([6], [3]), and we compute the initial probability
vector
3 How it works
The input data are the values of the poles and zeros of the
Laplace-Stieljes transform. For the moment there are only file based input.
1. Create a file having the following structure
number of real poles
number of complex pole pairs
number of real zeros
number of complex zero pairs
values of the real poles
values of real and complex part of complex pole pairs
values of the real zeros
values of real and complex part of complex zero pairs
Don't name the file as out.dat or reprez.dat. These names are internally used
by the program.
2. In the program select File|Open then select your file. The values of the
parameters will be displayed
3. Select Run|Step 1. The generator and the initial vector will be
computed and displayed. If the initial vector is not positive
the residual life trajectory will be also computed and the values for T (minimal and
optimal) will also be displayed.
4. If the initial vector is not positive select Run|Step 2. The final
representation will be computed.
The file out.dat is overriden each time with the
following data: the order of the initial representation, the optimal value
for T the initial vector and the initial generator,
The file reprez.dat will contain the final representation (i.e. the initial vector
and the generator).
4 Missing features and bugs
I'm not a Windows programming guru, so if you encounter problems,
the most probably they are
graphical interface related.
The graphical interface definitly needs a lot of work.
There are not
a working Save feature in the menu, then you need to manually retrive the
representation from the reprez.dat file.
The trajectory is computed even when not needed (this is a bug).
The distributions with a multiple dominant pole are not fully handled (it works but
the numeric implementation does not explicitly carry out this situation).
There is still no help.
You can't compute representations for values of T other than the optimal value
(unless you manually change the value for T in the out.dat file between Step1 and Step2
- this is moreover a cheat than a feature)
Large representations cannot be properly displayed (you must retrive the full
representation in the reprez.dat file)
5 Instalation and requirements
You need Windows95 installed on your computer. Download the binary executable
here.
Some sample data files are available here
You are strongly encouraged to report bugs, observations, missing features to
Stefan Mocanu.
I will be very gratefull for any user reports (data files, results files)
If you want to be announced about new versions of the program send e-mail to
Stefan Mocanu with subject ``subscribe''.
References
[1]
Aldo Cumani.
On the canonical representation of homogenous markov processes
modelling failure-time distributions.
Microelectronics and reliability, 22(3):583--602, 1982.
[2]
Robert S. Maier.
The algebraic construction of phase-type distributions.
Commun. Stat., Stochastic Models, 5(2):573--602, 1991.
[3]
Stefanita Mocanu and Christian Commault.
Sparse representations of phase-type distributions.
subnitted to Commun. Stat., Stochastic Models, 1998.
[4]
Marcel Neuts.
Matrix-Geometric Solutions in Stochastic Models. An Algorithmic
Approach.
The John Hopkins University Press, Baltimore and London, 1981.
[5]
Colm Art O'Cinneide.
Characterization of phase-type distributions.
Commun. Stat., Stochastic Models, 6(1):1--57, 1990.
[6]
Colm Art O'Cinneide.
Phase-type distributions and invariant polytopes.
Adv. Appl. Probab., 23(3):515--535, 1991.
[7]
Colm Art O'Cinneide.
Triangular order of triangular phase-type distributions.
Commun. Stat., Stochastic Models, 9(4):507--529, 1993.