next up previous contents
Next: Key idea Up: Overview Previous: Overview   Contents

Moment matching algorithms

A moment matching algorithm maps a general probability distribution, $G$, into a PH distribution, $P$. A PH distribution is a combination of exponential distributions with a certain structure. Examples of PH distributions include an exponential distribution, the convolution of exponential distributions, and a mixture of exponential distributions. More formally, a PH distribution is defined as the distribution of the time until absorption in a Markov chain (see Figure 2.1). Thus, essentially, a moment matching algorithm takes a general probability distribution, $G$, as an input, and outputs a Markov chain with an absorbing state together with the probability vector for the initial state, such that some moments of the distribution of the absorption time in the Markov chain (the PH distribution, $P$) agree with those of $G$. By convention, when the Markov chain has $n$ states, we say that the PH distribution has $n$ phases.

Figure 2.1: A PH distribution is shown as the distribution of the time until absorption in a continuous time Markov chain. At time 0, the Markov chain is in state $i$ with probability $\tau_i$ for $0\leq i\leq 3$, where state 0 denotes the absorbing state. The time that the Markov chain enters the absorbing state is said to have a PH distribution. See Section 2.2 for a more detailed explanation of the PH distribution.
\includegraphics[width=.6\linewidth]{fig/PH3_informal.eps}


Subsections
next up previous contents
Next: Key idea Up: Overview Previous: Overview   Contents
Takayuki Osogami 2005-07-19