Next: Concluding remarks Up: Moment matching algorithm Previous: Characterizing phase type distributions   Contents

EC distribution

The purpose of this section is twofold: to provide a detailed characterization of the EC distribution, and to discuss a narrowed-down subset of the EC distributions with only five free parameters ( is fixed) which we will use in our moment matching algorithms. Both results are summarized in Theorem 3.

To motivate the theorem in this section, suppose one is trying to match the first three moments of a given distribution, , to a distribution, , which is the convolution of exponential distributions (possibly with different rates) and a two-phase Coxian PH distribution. If has sufficiently high second and third moments, then a two-phase Coxian PH distribution alone suffices and we need no exponential distributions (recall Theorem 2). If the variability of is lower, however, we might try appending an exponential distribution to the two-phase Coxian PH distribution. If that does not suffice, we might append two exponential distributions to the two-phase Coxian PH distribution. Thus, if has very low variability, we might be forced to use many phases to get the variability of to be low enough. Therefore, to minimize the number of phases in , it seems desirable to choose the rates of the exponential distributions so that the overall variability of is minimized. One could express the appending of each exponential distribution as a function'' whose goal is to reduce the variability of yet further.

Definition 12   Let be an arbitrary distribution. Function maps to such that , the convolution of and , where is an exponential distribution whose rate, , is chosen so that the normalized second moment of is minimized. Also, refers to the distribution obtained by applying function to for integers , where .

Observe that, when is a -phase PH distribution, is a -phase PH distribution.

In theory, function allows each successive exponential distribution which is appended to have a different rate. Surprisingly, however, the following theorem shows that if the exponential distribution being appended by function is chosen so as to minimize the normalized second moment of (as specified by the definition), then the rate of each successive is always the same and is defined by the simple formula shown in the theorem below. The theorem also characterizes the normalized moments of .

Theorem 3   Let , and let be the rate of the exponential distribution for . Then,
 (2.1)

for . The normalized moments of are:

Proof:We first characterize , where is an arbitrary distribution with a finite third moment and is an exponential distribution. The normalized second moment of is

where . Observe that is minimized when , namely when
 (2.2)

Observe that when is set at this value, the normalized moments of satisfy:

We next characterize for . By the above expression on and , the second part of the theorem on the normalized moments of follow from solving the following recurrence equations (where we use to denote and to denote ):

The solutions for these recurrence equations are

for all . These solutions can be verified by substitution. This completes the proof of the second part of the theorem.

The first part of the theorem on is proved by induction. When , (2.1) follows from (2.2). Assume that (2.1) holds for . Let . By the second part of the theorem, which is proved above,

Thus, by (2.2),

width 1ex height 1ex depth 0pt

Corollary 1   If is in set , then is in set .

Proof:By Theorem 3, is a continuous and monotonically increasing function of . Thus, the infimum and the supremum of are given by evaluating at the infimum and the supremum, respectively, of . When , . When , .     width 1ex height 1ex depth 0pt

Corollary 1 suggests the number, , of times that function must be applied to to bring into a desired range, given the value of .

Subsections

Next: Concluding remarks Up: Moment matching algorithm Previous: Characterizing phase type distributions   Contents
Takayuki Osogami 2005-07-19