Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

In an exercise series from my Queueing Theory course I am asked to find $E(W)$, $P(W > 0)$ and $P(W > 1)$ where $W$ is the waiting time in a $M/G/1$ queue. In this exercise, the interarrival times $A$ are i.i.d. and exponentially distributed with arrival rate $\lambda$ and the service times $B$ are i.i.d. with cdf $F(t) = 1 - \frac{1}{2}e^{-2t} - \frac{1}{2}e^{-\frac{2}{3}t}$ (so we're dealing with a $M/H_2/1$ queue , where $H_2$ denotes a hyperexponential distribution). We are also given that $\rho = \lambda E(b) = \frac{1}{2}$.

By calculating $E(B) = 1$ and $E(B^2) = \frac{5}{2}$ and using that $E(W) = \frac{\rho}{1-\rho}\frac{E(B^2)}{2E(B)}$ I found $E(W) = \frac{5}{4}$.

To determine $P(W > 1) = 1 - P(W \leq 1) = 1 - F_{W}(t)$ I need to know the cdf of the random variable $W$. Since the Laplace-Stieltjes transform of $B$, which has a $H_2$ distribution with $p_1 = p_2 = \frac{1}{2}$, is $$\tilde{B}(s) = p_1\frac{\mu_1}{\mu_1 + s} + p_2\frac{\mu_2}{\mu_2 + s} = \frac{1}{2+s} + \frac{1}{2+3s}$$ I can use the Pollaczek - Khinchin formula $$\tilde{W}(s) = \frac{(1-\rho)s}{\lambda \tilde{B}(s) + s - \lambda}$$ which gives, after plugging in $\tilde{B}(s)$, $\lambda = \frac{1}{2E(B)} = \frac{1}{2}$ and $\rho = \frac{1}{2}$, that $$\tilde{W}(s) = \frac{s}{2(\frac{1}{2+s} + \frac{1}{2+3s}) + s - \frac{1}{2}}$$ My question: does calculating the inverse Laplace-Stieltjes transform of $\tilde{W}(s)$ give me the cdf of $W$ and if yes, how would I go about doing that? Since $\tilde{W}(s)$ has no nice partial fraction decomposition (as one can see here) I'm having a hard time computing the inverse Laplace-Stieltjes transform of this expression. Or maybe I'm not seeing a simpler way of finding $P(W > 1)$? Any hints are greatly appreciated.

edit I now see that I indeed need the inverse Laplace-Stieltjes transform of $W$, however I'm still not able to do that.

share|improve this question

1 Answer 1

up vote 3 down vote accepted

Before answering the question, I want to stress I consider this homework question as one of the (much too few) homework questions asked on this site whose author respects the recommendations for asking homework questions: mainly, to show what one has tried and where one is stuck.

In the present case, why is the OP stuck? My guess is that this is due to the conjunction of two facts:

(1) The OP made a mistake in the computations presented.

(2) The OP might not be aware of some automatic ways to deduce the distribution of a random variable from its Laplace transform when the Laplace transform is a rational fraction.

We start with the Pollaczek-Khinchin formula for $\tilde W(s)=E(\mathrm{e}^{-sW})$. Plugging the values of $\tilde B(s)$, $\lambda$ and $\rho$ the OP mentions into this formula yields a different expression than the one the OP computed, namely, $$ \tilde{W}(s) = \frac{\frac12s}{\frac12(\frac{1}{2+s} + \frac{1}{2+3s}) + s - \frac{1}{2}}. $$ We note that this formula for $\tilde{W}(s)$ passes a test the one proposed by the OP does not, namely that $\tilde{W}(s)$ does not degenerate when $s\to0$.

Unsurprisingly, we can simplify $\tilde{W}(s)$ and a factor $s$ appears in the denominator, which allows to get rid of the factor $s$ in the denominator. When the dust has settled, we get the key formula $$ \tilde{W}(s) = \frac{4+8s+3s^2}{4+13s+6s^2}. $$ We note that $\tilde{W}(0)=1$, as should be.

First use of the key formula: to compute the value of $P(W=0)$

When $s\to+\infty$, $\mathrm{e}^{-sW}\to\mathbb{1}_{W=0}$ hence $\tilde{W}(s)\to P(W=0)$. Keeping only the $s^2$ terms of the numerator and the denominator yields the value the OP computed, that is, $$ P(W=0)=\frac{3}{6}=\frac{1}{2}. $$

Second use of the key formula: to compute the value of $E(W)$

Classically $E(W)=-\tilde{W}'(0)$. Writing $\tilde{W}(s)$ as $\tilde{W}(s) = N(s)/D(s)$, we get the value the OP computed, that is, $$ E(W)=-\frac{N'(0)}{D(0)}+D'(0)\frac{N(0)}{D(0)^2}=-\frac{8}{4}+13\frac{4}{4^2}=\frac{5}{4}. $$

Third use (more involved) of the key formula: to compute the value of $P(W>1)$

As noted by the OP, there seems to be no other way than to compute the whole distribution of $W$. We already know this distribution has an atom $\frac12$ at $w=0$ and we can guess it has an absolutely continuous part described by a density $\frac12f(w)$ on $w>0$. Thus, we want $f$ such that for every $s$, $$ Q(s)=\int_0^{+\infty}\mathrm{e}^{-sw}f(w)\mathrm{d}w,\quad\mbox{where}\ Q(s)=2\tilde{W}(s)-2P(W=0). $$ Now, $Q(s)$ is a rational function in $s$. If this rational function has simple poles, sooner or later we will want to inverse expressions like $$ \frac1{s+c}=\int_0^{+\infty}\mathrm{e}^{-sw}f_c(w)\mathrm{d}w. $$ We should keep in mind the solution $f_c$ of this elementary case, which is simply $$ f_c(w)=\mathrm{e}^{-cw}. $$ From this point, our task is clear: to decompose $Q(s)$ into a linear combination of simple rational functions $1/(s+c)$ and to identify $f$ as the corresponding linear combination of functions $f_c$. If I am not mistaken, $$ Q(s)= \frac{4+3s}{4+13s+6s^2}=\frac{a}{s+c}+\frac{a'}{s+c'}, $$ where $(a,a',c,c')$ solves $$ a+a'=\frac12,\ ac'+a'c=\frac23,\ c+c'=\frac{13}6,\ cc'=\frac23. $$ Hence $$ f(s)=a\mathrm{e}^{-cs}+a'\mathrm{e}^{-c's}. $$ A last test to see if our computations went astray: since $f$ is the density of a measure of mass $1$, we should have $\displaystyle\frac{a}{c}+\frac{a'}{c'}=1$.

Finally, all this yields $$ P(W>1)=\frac12\left(a\frac{\mathrm{e}^{-c}}c+a'\frac{\mathrm{e}^{-c'}}{c'}\right), $$ and I think the numerical values needed to compute this are $$ a=\frac{u-3}{4u},\ a'=\frac{u+3}{4u},\ c=\frac{13+u}{12},\ c'=\frac{13-u}{12},\ u=\sqrt{73}, $$ hence, $$ P(W>1)=\frac14\mathrm{e}^{-13/12}\left(\left(1-7/u\right)\mathrm{e}^{-u/12}+\left(1+7/u\right)\mathrm{e}^{u/12}\right). $$

share|improve this answer
    
Thanks for the answer and for the input on my question. I always feel silly when it turns out I just miscalculated but it could be worse I guess. A well deserved check-mark for you, sir! :) –  Stijn May 2 '11 at 16:26

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.