Question 1 [50 marks]
Three processing units – Units 1, 2, and 3 – deal with requests until they are either classified as ‘resolved’ or ‘dismissed’. All requests initially go to Unit 1. You may assume that the process {Xn;n ≥ 0}, describing the location of the request at time n (i.e. at unit 1, 2 or 3, or resolved (R), or dismissed (D)) is a Markov chain with state-space S = {1, 2, 3, R, D} and transition matrix
02/3 0 1/3 0
0 0 1/21/2 0 P = 0 1/4 1/4 1/3 1/6 .
0 0 0 1 0 00001
(a) Write down the initial distribution for {Xn; n ≥ 0}. [1]
(b) Find the irreducible classes of intercommunicating states, classifying them as positive recurrent, null recurrent or transient. State their periodicity and whether they are ergodic. [4]
(c) Without performing any calculations, state whether:
(i) an invariant distribution exists for {Xn; n ≥ 0}, clearly stating your reasoning in one sentence; [2]
(ii) an equilibrium exists for {Xn;n ≥ 0}, clearly stating your reasoning in one sentence. [2]
(d) Assuming that each attempt at resolution takes 1 unit of time, what is the probability that the request stays active in the system (i.e. is not resolved or dismissed) for more than 4 units of time? [5]
(e) Compute the expected time until the request is resolved or dismissed, again assuming that each attempt at resolution takes 1 unit of time. [3]
(f) Compute the expected number of times that unit 3 attempts to resolve a request. [4]
Now assume that at time 2, the request is being dealt with by unit 3 (i.e. X2 = 3).
(g) Compute the probability of the request ever returning to unit 3 (i.e. Xu = 3 for u > 2) given that X2 = 3. [4]
(h) State the distribution of the number of times the process visits state 3 in total, given X2 = 3. (You should count the fact that X2 = 3 as one visit.) [2]
(i) Compare the mean of the distribution you gave in part (h) with your solution to part (f) and explain in one sentence why they are either the same or different (whichever applies). [2]
Turn Over
Page 3
A system upgrade means that if a request reaches state 3, the system sends a warning message to the administrator. However, the warning mechanism is faulty: it sends N warning messages each time the request reaches state 3 where N has a Poisson distribution with some parameter λ > 0.
(j) Find the probability generating function of the total number of warning messages the system sends before the request is resolved or dismissed, under the assumption that X2 = 3. [8]
(k) Compute the probability that the system sends no warning message for a particular request, either because it never reaches state 3 or because when it does the system sends no messages. Note here that the assumption of X2 = 3 has been removed. [6]
A further malfunction means the following changes to the system. Updated transition prob- abilities are given below where, for example, pij denotes the one-step transition probability from state i to j.
Unit 3 can no longer resolve requests or send them to Unit 2, so that p3R = 0 and p32 = 0.
Once a request reaches Unit 3 it either stays there with probability 1/4 or classifies it as dismissed, i.e. p33 = 1/4 and p3D = 3/4.
Once labelled as dismissed the request immediately returns to Unit 3, so that pD3 = 1.
Engineers trying to resolve the issue have built a system that tracks a request, emitting a signal of ‘1’, ‘2’ or ‘3’ if the request is in unit 1, 2 or 3 respectively, and a signal of ‘4’ if the request is either in state D or state R. Let Yn denote the signal emitted from the tracking system at time n, again assuming that each attempt at resolution takes 1 unit of time. For example,ifY2 =3thenweknowthattherequestiswithUnit3attime2,orifY5 =4then we know that the request is in state D or R at time 5.
(l) Is the process {Yn;n ≥ 0} Markov? If it is, justify your answer. If it is not, give an example of where the Markov property fails. [7]
Continued
Page 4
Question 2 [50 marks]
Consider the following simple model of a population of N individuals. A virus is thought not to be transmissable between individuals, but they can contract it by other means (e.g. from their environment). Let Xt denote the number of individuals in the population with the virus at time t. Once infected, individuals eventually recover but can be re-infected at any time at the same rate as those who have not previously been infected. The distribution of the length of time an individual is infected for is the same regardless of how many times they’ve contracted the virus in the past.
You can assume that {Xt;t ≥ 0} is a continuous-time, time-homogeneous, Markov process with state-space S = {0,1,2,…,N}, defined by the following transition rates where these transitions are possible,
qn,n−1 = nλ
qn,n+1 = (N − n)λ
andqi,j =0whenj<(i−1)orj>(i+1).
(a) Write down the generator matrix, Q, for {Xt; t ≥ 0}. [3]
(b) Does an equilibrium distribution exist for {Xt;t ≥ 0}? Explain your answer in no more than one sentence. [2]
(c) Define the vector α = (α0, …, αN ) to be the solution to αQ = 0. Find an expression for αk (for some k = 1, …, N ) in terms of α0 and any other constants required. [4]
(d) The virus has been circulating in the population according to the model described for many years. Find the probability distribution of the number of infected individuals at some large time t. You should name the distribution and find its parameters. [6]
(e) In one sentence, explain what the (embedded) jump chain {Yn;n ≥ 0} of the process {Xt; t ≥ 0} would describe. [1]
(f) Write down the transition matrix of {Yn; n ≥ 0}. [2]
(g) What happens to {Yn;n ≥ 0} in the long run? Does P(Yn = i) converge as n → ∞,
for i = 0, …, N ? Justify your answer in no more than two sentences. [4]
(h) There is one infected person in the population at time t = 0. Compute the expected
time until we have two infected individuals in the population for the first time. [6]
Now consider a different population of N individuals who are dealing with a virus – known as Covoid – which is only transmissable between individuals (cannot contract from the en- vironment). An individual with the virus has probability αh + o(h) of passing it to another individual in any time interval of length h, where h is very small. If an individual is infected, the distribution of the length of time they remain infected is exponential with some param- eter μ > 0, and individuals eventually recover but can become re-infected at any time. The length of time they are infected is not related to whether they have had the virus before.
Page 5
Turn Over
(i) What happens to the virus Covoid if, at some time t, there is nobody in the population with the virus? [1]
(j) Write the the generator matrix of the process describing the number of individuals in the new population infected with Covoid. [3]
(k) It is not known how many individuals have the virus Covoid at a given time t. Under what conditions does Covoid die out? Justify your answer, for example by considering the probability of Covoid becoming extinct conditional on all N individuals being infected simultaneously. [7]
Now assume that the size of this new population is infinite, rather than having N individuals.
(l) Again, it is not known how many individuals in this infinite population have Covoid. Under what conditions is Covoid guaranteed to die out when we assume an infinite population? [2]
(m) A vaccine has been manufactured that protects individuals against Covoid with prob- ability 0.9. The Government cannot immunise everyone in the population. By consid- ering different relative magnitudes of μ and α, propose the minimum proportion of the population that need to be vaccinated in order for Covoid to die out with probability 1. You should justify your proposal by computing relevant quantities. [9]
End of Paper
Page 6