1. A Markov chain (Xn)n>0  with state space S = {1, 2, 3, 4} has transition matrix

P =     、．

 ．． .

(a) Find f(X3 = 1, X1 = 2|X0 = 2).

(b) If the initial distribution is uniform on {1, 2, 3, 4}, find f(X3 = 1, X1 = 2).

(c) Write down the communication classes of the chain.

(d) Find the period of each communicating class.

(e)  Determine which classes are essential.

(f)  Classify each essential communicating class as transient or positive recurrent or null recurrent.

(g)  Describe the long run behaviour of the chain (including deriving long run probabilities where appropriate).

(h) Find the expected number of steps taken for the chain to first reach state 1, given the chain starts at state 4.

[16 marks]

Ans.

(a)  (2 marks)

p22p  )1(2) = /  、  / 、 =  .

(b)  (2 marks)

 pi2p =  /  + 、  / 、 =  .

(c)  (1.5 marks) Inspection of a transition diagram gives S1 = {1, 2} and S2 = {3, 4}.

(d)  (1.5 marks) Both classes have a loop and so have period 1.

(e)  (1.5 marks) S1  is essential (can’t leave) and S2  is non-essential (can get to state 1 from state 3.

(f)  (1.5 marks) The essential communicating class is positive recurrent since it is finite.

(g)  (3 marks) The chain will eventually end up in the essential communicating class S1 and since it is aperiodic and positive recurrent, it is ergodic. The long run probabil- ities are given by the stationary distribution solving πP = π, which is easily found to be

π = (6/11, 5/11, 0, 0).

(h)  (3 marks) We use first step analysis.  Let ei  = 时 [inf{n ≥ 1 : Xn = 1}|X0 = i].  We then have

e4 = 1 + e4 + e3

e3 = 1 + e4 + e3 ,

and solving yields e4 = 7.

2. A Markov chain (Xt)t>0  with state space S = {1, 2, 3} has generator

A =  ╱ 一21   1一4     2(0)   、

．   0      1     一1 ． .

(a)  Given the chain is in state 2 right now, what is the expected amount of time until the chain jumps to a new state?

(b)  Given the chain is in state 2 right now, what is the probability that the next time the chain jumps, it jumps to state 1?

(c) Find the stationary distribution of the chain.

(d)  Derive a differential equation for p2,2 (t) := P (Xt = 2|X0 = 2), and show that p2,2 (t) =  + e-5t .

(e)  Calculate p1,2 (t) := P (Xt = 2|X0 = 1) for t ≥ 0.

[14 marks]

Ans.

(a)  (2 marks) Since a22  = 一4, the time spent in state 1 before jumping is exponential rate 4 having mean 1/4.

(b)  (2 marks) From state 2, the chain jumps to states 1 and 3 with the same rate 2 so the chance of jumping to state 1 is 1/2 (also the same as 一a2,1 /a2,2 ).

(c)  (3 marks) We need to solve πA = 0.  By symmetry and the fact that ←iπi  = 1, π 1 = π3 = (1 一 π2 )/2. Using this and that (πA)2 = 0:

π 1 一 4π2 + π3 = 0,

we easily find π = (2/5, 1/5, 2/5).

(d)  (4 marks) In the usual notation, we can use the forward equations P(t) = P(t)A to find

p2(/) ,2 (t) = p2,1 (t) 一 4p2,2 (t) + p2,3 (t).

Using symmetry and that ←ip2,i(t) = 1, we have p2,1 (t) = p2,3 (t) = (1 一 p2,2 (t))/2, so the above equation reduces to

p2(/) ,2 (t) = (1 一 p2,2 (t)) 一 4p2,2 (t) = 1 一 5p2,2 (t).            We can easily solve this with the boundary condition p2,2 (0) = 1, to find

p2,2 (t) =  + e-5t .

(e)  (3 marks) In order to be at state 2 at time t, starting from state 1, we must jump away from 1 before time t.  But then the chain always jumps to state 2, so we can condition on the time of the jump and use the Markov property to find

p1,2 (t) = (0t e-sp2,2 (t 一 s)ds = (0t e-s  /  + e-5(t-s)、ds =  /1 一 e-5t、.

3. A factory worker is assigned tasks one at a time. The amount of hours it takes to complete tasks are i.i.d. with (gamma) density 100te-10t , t > 0. The worker is given a new task as soon as they finish one.

(a)  State from formulas  (or compute) the mean and variance of the time it takes to complete a task.

(b)  On average, about how many tasks does the worker complete over a 40 hour work week?

(c)  Give a symmetric interval around your estimate from (b) that will have a 95% chance of covering the true number of tasks completed over the 40 hour work week.  Note

that

  e-xA /2dx = 0.95.

(d) What would you estimate to be the mean of the time to completion of the task the worker is currently working on?

(e) Now assume that each task is  “easy” with probability 1/4  (independently among tasks), in which case it is completed in an exponential with rate 10 (per hour) dis- tributed time. In this new setting, about how many tasks does the worker complete over a 40 hour work week?

You may find the following formula useful for this problem: for a, b > 0

(0 o ta e-btdt =  .

[15 marks]

Ans. We model the system as a renewal process with inter-arrival distribution gamma as above.

(a)  (2 marks) Using formulas for gamma distributions, the inter-arrival variable τ has µ := E[τ] = 1/5,   σ2  := Var(τ) = 1/50.

(b)  (3 marks) For t in hours, Nt/t → 1/E[τ] = 5 as t → &, and so in 40 hours we expect the worker to complete about 40 * 5 = 200 tasks.

(c)  (3 marks) The renewal CLT says that N40 ≈ Normal(40/µ, 40σ2 /µ3 ) = Normal(200, 100), and so there is approximately a 95% chance that the number of tasks the worker com-      pletes will fall in the interval

200 士 (1.96)10 = 200 士 19.6.

(d)  (4 marks) Defining the renewal times Tk  = ←i(k)=1 τi, we know that for large t, Yt  := TNt+1 一 t roughly has density

1 一 µ(F)(t) = 5e  10t- (10t + 1),   t > 0.

(0 o 5te-10t(10t + 1)ds =  .

(e)  (3 marks) Now the inter-arrival distribution is a mixture of the exponential and gamma, as described in the problem. Thus the new mean is

µ/ = 1  1  + 3  2  =  7 

and so we expect that the number of tasks the worker will complete in 40 hours is

about

N4(/)

4. Let (Nt)t>0 be a Poisson process with rate λ, and (Mt)t>0 be the “thinned” process where each arrival in N is added to M with probability p > 0.  Your answers to the questions below should be simple and tidy formulas in terms of λ and p.

(a) What is the expected time of the first arrival of N that occurs after the tenth arrival of M?

(b) What is the chance that there are no arrivals of M in the interval (2, 5)?

(c) What is the expected time until the first arrival of either M or (N 一 M)?

(d) What is the expected time between the first arrivals of N and M?

(e) What is the probability that in the time interval (0 , 1), the number of arrivals of N and M are the same?

(f)  Given there are 10 total arrivals of N in the interval (0, 1), what is the chance that exactly 5 of these are in M?

(g)  Given that N10 = 3, what is the chance that N3 = 1?

(h)  Given that N10 = 3, what is the chance that M3 = 1?

(i) What is the variance of N1 + M1?

[19 marks]

Ans. We use below, from the thinning theorem, that the M process is a Poisson process rate λp, independent of the N 一 M Poisson process with rate λ(1 一 p).

(a)  (2 marks) Since any arrival in M is an arrival of N, the time until the next arrival of the N process after any arrival of the M process is exponential rate λ, which has mean 1/λ.  The tenth arrival of the M process has mean 10/(λp) and so the total time until the first arrival of N after the tenth arrival of M is

10 + 1

(b)  (2 marks) M5 一 M2  is Poisson mean 3pλ and so

P (M5 一 M2 = 0) = e-3pλ .

(c)  (2 marks)The first arrival of M or N 一 M is just the first arrival of N which is exponentially distributed with rate λ and hence mean 1/λ .

(d)  (2 marks) With probability p, the first arrivals of N and M coincide. Otherwise the first arrival is in N but not in M, and the process starts anew, so the time to the next arrival of M is exponential with rate pλ, having mean 1/(pλ).  Thus the difference has mean  .

(e)  (2 marks) This probability is the same as f(N1 一 M1 = 0) = e-λ(1-p) .

(f)  (2 marks) Directly from the thinning description, given N1 = 10, M1 has the binomial distribution with parameters 10 and p. Thus

f(M1 = 5|N1 = 10) = / 5(10)、p5 (1 一 p)5 .

(g)  (3 marks) Given N10  = 3, the positions of these 3 arrivals in the interval  (0 , 10) are uniform and independent.  Thus the chance any particular one lands in (0 , 3) is 3/10 and since there are three points, the number landing in (0 , 3) is binomial with parameters 3 and 3/10. The probability this binomial is equal to one is

/ 、  /1(3) 、2  / 、 = 0.441.

(h)  (2 marks) Continuing from the previous part, the chance any particular point of N is both thinned to M and in the interval (0, 3) is (3/10)p, each point independently. Thus, given N10  = 3, the number of points of M landing in (0, 3) is binomial with parameters 3 and (3/10)p and the probability this binomial is 1 is

3 / 、  /1 一 、2 .

(i)  (2 marks) Write N1 + M1  = (N1 一 M1) + 2M1; the summands are independent by the thinning theorem. Thus

Var(N1 + M1) = Var(N1 一 M1) + 4Var(M1) = λ(1 一 p) + 4λp.

5. In a certain computer queuing system, jobs arrive according to a Poisson process with rate 4. There are two servers that process jobs: Server A works at exponential rate 3 and Server B at exponential rate 2. Since Server A is faster than Server B, the system works as follows.  When an arriving job finds the system empty, Server A always processes the job. If only one server is free, then an arriving job goes immediately into service with the free server. When both servers are busy, jobs queue in an infinite buffer.

(a)  Model the number of jobs in the system  (including those being worked on) as a continuous time Markov chain (Xt)t>0  with appropriate state space, and specify its generator.

(b) Find the stationary distribution of the Markov chain.

(c) What proportion of time is Server B idle?

(d) What is the average number of jobs in the system?

(e) What is the average number of jobs waiting in the queue (that is, in the system but not in service)?

(f) What is the average amount of time an arriving job waits for service in the queue? (g) What is the average amount of time an arriving job is in the system?

You may find the following formula useful for this problem: for 0 < a < 1

L jaj  = (1 a一a)2 .

[17 marks]

Ans.

(a)  (3 marks) We view the system as a CTMC with states {0, (1, 0), (0, 1), 2, 3, . . .}, where (1, 0) means the Server A is busy and Server B is not, and (0 , 1) means Server B is busy and Server A is not; note in both these cases the number of jobs in the system is 1. The generator is

╱ 一34   4一  、

A =  ．(．)    0      2      3     一9    4      0     0   ．．．   ．(．) ,

where it continues for j ≥ 3 as a birth-death process.  (The chain is irreducible and ergodic since the maximum service rate is greater than the arrival rate.)

(b)  (4 marks) To determine the stationary distribution of this system, we solve πA = 0. For j ≥ 3, the equations are

9πj  = 4πj -1 + 5πj+1 ,

which can be solved in the usual way using way (solution of the form πj  = uj ) to find for j ≥ 2, and some constants a, b,

πj  = a + b(4/5)j .

The a coefficient must be zero, since←j>3 πj  < 1, so that for j ≥ 2, πj  = π2 (4/5)j -2 .

Now for states 0, (1, 0), (0, 1), the equations are

4π0 = 3π (1,0)+ 2π (0,1) ,

7π (1,0) = 2π2 + 4π0 ,

6π (0,1) = 3π2 .

Solving these in terms of π2 , we have

π0 = (13/16)π2 ,

π (1,0) = (3/4)π2 ,

π (0,1) = (1/2)π2 .

Since←j>0 πj  = 1, we find

π0 =  13 

πj  =  /  、 j -2 ,   j ≥ 2.

(c)  (2 marks) From the work above,  Server B  is idle in states 0, (1, 0), in which the system spends a proportion of time equal to

π0 + π (1,0) =  .

(d)  (2 marks) The average number of jobs in the system is

L = π (0,1)+ π (1,0)+L jπj  =  .

j>2

(e)  (2 marks) The average number of people in the queue is

Lq  = L(j 一 2)πj  =  .

j>2

(f)  (2 marks) By Little’s law,  λW  = Lq, where λ  = 4 is the arrival rate,  W is the expected time for an arriving job to wait for service, and Lq  is the expected number of jobs in the queue, which we just computed. Thus

W = Lq/λ =  .

(You can also compute this directly, W =  ←j>2(j 一 1)πj.)

(g)  (2 marks) By Little’s law, λD = L, where λ = 4 is the arrival rate, D is the expected time for an arriving job to leave the system, and L is the average number of jobs in the system, which we just computed. Thus

D = L/λ = 125