MVE170/MSG800 Basic Stochastic Processes Course Mail 5

Skickat: den 5 december 2013 13:23

Hello!

Having not sent any emails at all to you more or less during a long
initial part of the course the email action is now picking up as you 
can see ... .

1) Today I gave a crash course on Chapter 9 in Hsu using just 20 min-
utes or so to cover the material based on the fact that queues are
just special cases of birth-and-death processes (see Section 6.11 in
G&S) started according to their stationary distribution with

lambda_n = lambda for n<=K-1 and lambda_n=0 for n>=K

mu_n = n mu for 1<=n<=s and mu_n = s mu for s<n<=K

where s is the number of servers (with s>=1 always finite) and K (pos-
sibly = oo) is the total number of available places in the queueing
system (the number of servers plus the number of queueing places to
wait for service (possibly infinite) ...).

Using Eq 6.11.2 in G&S this gives the stationary distribution pi_n for
0 <= n <= K for the queue (labeled p_n in Hsu).

For the quantities L, L_q, L_s, W, W_q and W_s (defined in Section 9.2
in Hsu) we must now have

L=L_q+L_s, W=W_q+W_s

L = Sum_{n=0}^K n pi_n, W_s=1/u

L=W lambda, L_q=W_q lambda, L_s=W_s lambda for K=oo

L=W lambda (1-pi_K), L_q=W_q lambda (1-pi_K),
L_s=W_s lambda (1-pi_K) for K<oo

where one of the three last equations always follows from the two others
(either if K=oo or K<oo), so that we have six equations for six unknown
making everything solved and setteled ... :) .

NOTE that there is one serious error in Hsu in Chapter 9 which is deta-
iled in the Errata list for the book - please make adjustments for that 
when reading Hsu's queueing material ... .

2) As I have now in principle lectured on everyting I am supposed to it
will not really bother me to use some of the lecture time next Wednesday
11 December to finish doing the exercises in Chapter 6 in G&S (which I
did not manage to do today during exercise time (: ... . Then I will talk
more about Chapter 9 in Hsu (to the extent I have time left). And then I 
will contnue with doing exercises in Chapters 6 and 9 in Hsu Thursday 12 
December.

HOWEVER, as the computational problems of Exercise Sessions 5 and 6 have 
complete solutions available through the course web page, I will not talk 
about them anthing (unless urged by students to do so ...).

3) When I talked about Exercises 6.9.9 and 6.9.10 in G&S today I left out
some computational details claiming that we had already done these details 
as part of doing Exercise 6.8.2 - let me explain how that goes:

In 6.9.9 we are dealing with a transient state i of a continuous time Mar-
kov chain so that the probability f_i to come back to i if we start there 
has f_i<1. As we know that we spend an exp(-g_{ii})-distributed time in i 
before switching value we conclude that the PDF for the total time spent 
in i (the item searched for in the exercise) has PDF f(x) given by

f(x) = 
Sum_{n=1}^oo ((n-1)!)^{-1} x^{n-1} (-g_{ii})^n e^{-(-g_{ii})x} f_i^{n-1} (1-f_i)

because we are doing n-1 repeated failed attempts to leave state i forever
each having probability f_i and then we leave at attempt n with probability 
1-f_i and given that this is so we use a sum of n independent exp(-g{ii})-
distributed times in state i which equals a Gamma(n,-g_{ii})-distribution 
- see Chapter 2 in Hsu - with PDF 

((n-1)!)^{-1} x^{n-1} (-g_{ii})^n e^{-(-g_{ii})x} 

... and from calculating the above sum we readily get

f(x) = (-g_{ii}) exp(-(1-f_i)(-g_{ii})x)

that is, and exp((1-f_i)(-g_{ii}))-PDF, so that we spend an 
exp((1-f_i)(-g_{ii}))-distributed time in state i if we start there before 
we leave i forever ... .

In 6.9.10 we just have a special case of this with a continuous time random
walk for which the probability f_{10} that ever getting back to 0 when star-
ting at 1 must satisfy

f_{10} = mu/(lambda+mu) + lambda/(lambda+mu) f_{10}^2

     => f_{10} = mu/lambda

making f_0 = same thing = mu/lambda so that as g_{00}=-lambda we get an 
exp((1-f_0)(-g_{00})) = exp((1-mu/lambda) lambda) = exp(lambda-mu)-
distributed time totally spent at 0 when starting there ... .

Similarly, we have (by analogy) for r>=1

f_r = mu/(lambda+mu) + lambda/(lambda+mu) f_{10} = 2 mu/(lambda+mu)

so that as g{rr}=-(lambda+mu) we get an

exp((1-f_r)(-g_{rr})) = exp((1-2mu/(lambda+mu))(lambda+mu)) = exp(lambda-mu)

distributed time totally spent at r when starting there ... . SAA-DE-SAA!!!!!

Best regards, Patrik Albin