Our moment matching algorithms have broad applicability in computer science, engineering, operations research, etc., where the performance evaluation or optimization in stochastic environment is needed. For example, in this thesis, a moment matching algorithm is used to model a multiserver system as a (multidimensional) Markov chain, as well as in a key step of the analysis of the multidimensional Markov chain via dimensionality reduction. Furthermore, many optimization problems in stochastic environment can be formulated as Markov decision problems [159] by mapping general (input) probability distributions into PH distributions.
Our moment matching algorithms can also be used as a building block to
construct a solution with additional properties. For example, the
Positive solution can be used as a building block for yet
another solution, ZeroMatching, that not only matches the first
three moments of the input distribution but also matches the mass
probability at zero. Consider a distribution whose mass
probability at zero is
. Then,
can be expressed as a mixture
of
(the distribution of a random variable
) and a
distribution
that does not have mass probability at zero. The
Positive solution can be used to match the first three moments
of
by an extended EC distribution,
. Now, a mixture of
and
, whose distribution function is
, matches
the first three moments and mass probability at zero of
. Observe
that the ZeroMatching solution uses at most
phases.
Beyond proving the minimality of the number of phases used in our
moment matching algorithms, our characterization of set
via set
is found to be useful in developing
our moment matching algorithms, since the characterization of
allows us to determine how close our PH distribution is to
the minimal PH distribution, and provides intuition for coming up with
improved algorithms. Another benefit of characterizing
is that some existing moment matching algorithms, such as
Johnson and Taaffe's nonlinear programming approach
[90], require knowing the number of phases,
, in
the minimal PH distribution. The current approach involves simply
iterating over all choices for
[90], whereas
our characterization would immediately specify
.
In developing moment matching algorithms, we have introduced various
theoretical concepts such as the normalized moments, -value, sets
and
, function
, and the EC
distribution, and have proved their properties. These new concepts
and their properties are found to be quite useful in developing
moment matching algorithms, and they have recently stimulated
the research in this area.
For example, Bobbio, et al. [22] have recently used the
normalized moments to provide exact characterizations of sets
and
, where
is the
set of distributions that can be well-represented by an
-phase
acyclic PH distribution and
is the set of
distributions that can be well-represented by an
-phase acyclic PH
distribution with no mass probability at zero.
Bobbio, et al. use their exact
characterization of
to construct a minimal
acyclic PH distribution that well-represents any distribution in
. The PH distributions to which an input distribution
is mapped in [22], the Exp-Erlang distribution and the
Erlang-Exp distribution, are similar to (but simpler than) the
EC (Erlang-Coxian) distribution and the extended EC distribution
introduced in this chapter. In fact, the EC distribution is reduced
to the Exp-Erlang distribution by setting
and
(see Figure 2.2), and the extended
EC distribution is reduced to the Erlang-Exp distribution by setting
,
, and
(see Figure 2.3).
Since the work by Bobbio, et al.
builds upon the results in this chapter,
we summarize their main results in Appendix B.
In response to increased request, the closed form solutions developed in this chapter have been largely implemented, and the latest implementation of the solutions is made available at an online code repository: