Skip to content
Tutorials Center
My learning

Topics

Lesson 27 of 38 · M/G/1 and Variability

Phase-Type Service: Erlang and Hyperexponential

Build service-time models with less or more variability than exponential: Erlang-k (cs² = 1/k) and hyperexponential mixtures, with M/G/1 waiting times.

The exponential distribution has cs² = 1. Real service times are often smoother (a task done in several fixed steps) or wilder (a mix of quick and very slow jobs). We can build such distributions from exponential pieces, called phases. They are easy to simulate, and the P-K formula needs only their first two moments.

Erlang-k: less variable than exponential

An Erlang-k service time is the sum of k independent exponential stages, each with rate kμ. Think of a job that must pass through k identical steps.

  • Mean: k · 1/(kμ) = 1/μ
  • Variance: k · 1/(kμ)² = 1/(k μ²)
  • cs² = 1/k

With k = 1 you get the exponential. As k grows, cs² shrinks toward 0, approaching deterministic service. So Erlang-k lets you tune variability between exponential and deterministic while keeping the mean fixed.

Python Erlang-k and the M/Ek/1 waiting time

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The wait falls from 4.0 (exponential) toward 2.0 (deterministic) as k increases. Most of the improvement comes from the first few phases.

Hyperexponential: more variable than exponential

A hyperexponential distribution picks one of m exponential servers at random. With probability p_i the job is exponential with rate μ_i. This models a population made of different job types, for instance quick questions and long investigations.

  • E[S] = Σ p_i / μ_i
  • E[S²] = Σ 2 p_i / μ_i²
  • cs² = E[S²]/E[S]² - 1, which is always at least 1 for a hyperexponential.

Two classes of jobs with very different sizes give a large cs².

Python Moments of a hyperexponential and its M/G/1 wait

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Two jobs types with the same mean of 1 time unit give a wait several times higher than exponential service.

Balanced means and fitting a distribution

Often you know only the mean and cs² of real data and want a model. Standard choices:

  • If cs² < 1, use Erlang-k with k ≈ 1/cs² (round to an integer; mixtures of two Erlangs fit any value in between).
  • If cs² > 1, use a two-phase hyperexponential. A common choice is balanced means: p_1/μ_1 = p_2/μ_2 = E[S]/2, which gives:
Text
p_1 = (1 + √((cs² - 1)/(cs² + 1))) / 2,   p_2 = 1 - p_1
μ_1 = 2 p_1 / E[S],                        μ_2 = 2 p_2 / E[S]
Python Fit a balanced-means H2 to a target mean and cs²

Press Run (or Ctrl + Enter) to see the result here.

Program input · what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The fitted moments reproduce your targets exactly. Remember that matching two moments does not make the shapes identical, but M/G/1 mean values depend only on those two moments.

Only M/G/1 means depend on two moments alone. Tail probabilities (the chance of a very long wait) and multi-server queues are sensitive to the actual shape, so two models with the same cs² can still differ there.

Check your understanding

Quick check · 4 questions

of 4 answered You scored / 4 · perfect!

  1. 1. What is cs² of an Erlang-5 service time?

    cs² = 1/k = 1/5 = 0.2.
  2. 2. A hyperexponential distribution always has cs² that is

    Mixing exponentials spreads values out, so the variability is at least that of a single exponential.
  3. 3. Which M/G/1 service model has the smallest wait at the same mean and utilization?

    Deterministic has cs² = 0, so the factor (1 + cs²)/2 is the smallest possible (0.5).
  4. 4. In an Erlang-k with total mean 1/μ, each stage has rate

    k stages of mean 1/(kμ) each add up to a mean of 1/μ.

Summary

  • Erlang-k: cs² = 1/k, between exponential and deterministic.
  • Hyperexponential: random mixture of exponentials, cs² ≥ 1.
  • P-K needs only E[S] and E[S²], so fitting the mean and cs² is enough for M/G/1 mean values.
  • Balanced-means H2 gives a quick fit for cs² > 1.

Next: Kingman's Formula for the G/G/1 Queue