EEL6507sp09L34

From BoykinWiki

Jump to: navigation, search

Contents

EEL6507 Spring 2009, Lecture 34, Friday 2009/04/10 (Notes created by Nathan Blythe)

  • Moments of waiting time distribution
  • Ex. M/M/1 system time
  • Ex. M/M/1 waiting time
  • Ex. M/D/1 waiting time

In the previous lecture we derived some results for the waiting time distribution of the M/G/1 queue. In this lecture we applied these results to various ends. Some of this lecture was spent discussing more philosophical aspects of mathematics and looking at some alternate derivations of the concepts presented in previous lectures. This was informally presented and not included in these notes.

Moments of waiting time distribution

In the previous lecture we found that W^*(s) = \frac{1 - \rho}{1 - \rho \hat{B}^*(s)} where \hat{B}^*(s) = \frac{1 - B^*(s)}{\bar{X} s} is the characteristic equation for residual life on the distribution b(x).

From the form of W * (s) we can see that W(k) = (1 - \rho) \sum_{k = 0}^{\infty} \rho^k \hat{B}^{*k}(s).

We define b_k(y) = \mathcal{L}^{-1}\lbrace \hat{B}^{*k}(s) \rbrace. Then w(y) = (1 − ρ)ρkbk(y). This last expression is the PDF of the waiting time distribution.

The kth moment of the waiting time distribution can be found from the kth derivative of the generating function, as in E[W^k] = (-1)^k (\frac{d}{ds})^k \lbrace W^*(s) \rbrace_{s = 0}. We can then expand this to E[W^k] = \frac{\lambda}{1 - \rho} \sum_{i = 1}^{k} (k \choose i) \frac{E[X^{i - 1}]}{i + 1} E[W^{k - i}].

We know that E[W0] = 1 (E[W0] = E[1] = 1). Using the above result we can write E[W^1] = \frac{\lambda}{1 - \rho} \frac{E[X^2]}{2} E[W^0] = \frac{\lambda}{1 - \rho} \frac{E[X^2]}{2}.

We can continue on in this fashion to produce any of the moments. For example, E[W^2] = \frac{\lambda}{1 - \rho} \sum_{i = 1}^{2} (2 \choose i) \frac{E[X^{i + 1}]}{i + 1} E[W^{2 - i}] which yields E[W^2] = \frac{\lambda}{1 - \rho} \left( E[X^2] E[W] + \frac{E[X^3]}{3} \right).

Ex. M/M/1 system time

For M/M/1 queues we have b(x) = μe − μx. Then B^*(s) = \frac{\mu}{s + \mu} and E[X] = \frac{1}{\mu}.

From our work in previous lectures, S^*(s) = \frac{B^*(s)(1 - \rho) s}{s - \lambda + \lambda B^*(s)}. Substituting our definition of B * (s) and simplifying we have S^*(s) = \frac{\mu (1 - \rho)}{s + \mu (1 - \rho)}. We identify this as an exponential and write S(y) = μ(1 − ρ)e − μ(1 − ρ)y.

The expected value of an exponential is just the inverse of its parameter: E[S] = \frac{1}{\mu (1 - \rho)}.

Ex. M/M/1 waiting time

Referring to our expression for W * (s) we write (using the same definitions as for the previous example) W^*(s) = \frac{s (1 - \rho)}{s - \lambda + \lambda B^*(s)} = \frac{s (1 - \rho)}{s - \lambda + \frac{\lambda \mu}{s + \mu}}. With a lot of algebra we find that W^*(s) = (1 - \rho) + \rho \frac{\mu (1 - \rho)}{s + \mu (1 - \rho)}. Here we see two components: a delta function and an exponential. We write W(y) = (1 − ρ)δ(y) + ρμ(1 − ρ)e − μ(1 − ρ)y.

The delta term corresponds to the case in which the system is not busy. The exponential corresponds to the case in which the system is busy (at which point the waiting time is independent of the number in the system).

Ex. M/D/1 waiting time

We started this problem, enough to see where the solution lies. For the queue with deterministic service, b(x) = \bar{X} and so B^*(s) = e^{-s \bar{X}}.

Then we can write (again using the result for W * (s)) W^*(s) = \frac{s (1 - \rho)}{s - \lambda + \lambda e ^{-s \bar{X}}}. We conclude that taking derivatives of this function would be difficult and evaluating at s = 0 would yield continuing applications of L'Hopital's rule, and so we left the solution at this point. This agrees with our notion that mixing deterministic distributions with non-deterministic distributions yields difficult mathematics.

Lecture Voice Recording

lecture_recording

Retrieved from "http://boykin.acis.ufl.edu/wiki/index.php/EEL6507sp09L34"