Marcov chains
MA636/MA836/19Ass2 UNIVERSITY OF KENT FACULTY OF SCIENCES Assessment 2 STOCHASTIC PROCESSES MA636 students should do questions 1, 2, 3, 4, 5, 6 and 7 while MA836 students should do questions 1, 2, 3, 4, 5, 7 and 8. Students are advised to show their working on their scripts. Marks might then be allocated for use of a correct method, even if the numerical or algebraic result is incorrect. Please hand-in your work to the SMSAS Recep- tion before 4pm on the 12nd December Thursday, 2019. Turn over MA636/MA836/19Ass2 2 SECTION A 1. Let X = (Xn : n ∈ N0) be a time-homogenous Markov chain on state space S = {−1, 0, 1} with transition probability matrix P = 0 1/2 1/21/2 0 1/2 1/2 1/2 0 . (a) Calculate P(X2 = a|X0 = b) for a, b ∈ S. [ 2 marks ] (b) Calculate E[X1|X0 = b] and E[X2|X0 = b] for b ∈ S. [ 5 marks ] (c) If P(X0 = −1) = P(X0 = 0) = P(X0 = 1), calculate E[X1] and E[X2]. [ 3 marks ] 2. Let Y = (Yt : t ≥ 0) denote a time-homogeneous, continuous-time Markov chain with state space S = {1, 2, 3} and the corresponding generator matrix G = −1 a b6 −9 3 9 10 −19 , where a, b 6= 0. (a) Let X = (Xn : n ∈ N0) denote the embedded Markov chain of Y with P(X1 = i|X0 = i) = 0, i ∈ S. Derive the transition matrix of X . [ 4 marks ] (b) If E[X1|X0 = 1] = 2.5, determine the values of a and b. [ 4 marks ] (c) Calculate the mean holding time of Y in state 2. [ 2 marks ] 3. Consider a time-homogeneous Markov chain X = (Xn : n ∈ N0) on state space S = {0, 1, 2} with transition probability matrix P = 1/3 1/6 1/21/4 1/3 5/12 1/2 1/4 1/4 , (a) Draw a transition diagram for X . [ 2 marks ] (b) Determine the communication classes for X and show whether they are recurrent or transient. [ 4 marks ] (c) Find a stationary distribution for X . [ 4 marks ] 3 MA636/MA836/19Ass2 4. Demands on a first aid facility in a certain location occur according to a time homogeneous Poisson process denoted by (Nt : t ≥ 0) with rate λ = 3. (a) Write down the transition probability function pij(t)=̂P(Nt+1 = j|N1 = i), i, j = 0, 1, 2, ... Calculate E[Nt+1|N1 = 0]. [ 4 marks ] (b) Show that the above process satisfies the Markov property. [ 4 marks ] (c) Calculate the generator matrix for the above process and show that its stationary distri- bution does not exist. [ 2 marks ] 5. Let Xn denote the health state of a person at day n ≥ 0, which can be classified as L,M,H. Suppose that (Xn : n ≥ 0) follows a Markov chain with the transition probability matrix P = 0 1/2 1/21/3 1/4 5/12 2/3 1/4 1/12 and initial distribution P(X0 = L) = 0.1, P(X0 = M) = 0.4, and P(X0 = H) = 0.5. (a) Calculate P(X0 = L,X2 = M,X3 = H). [ 4 marks ] (b) Justify the existence of the limit of P(Xn = L|X0 = L) as n tends to infinity and calculate it. [ 6 marks ] Turn over MA636/MA836/19Ass2 4 SECTION B 6. (a) Let X = (Xn : n ∈ N0) be a time homogenous Markov chain on state space S = {1, 2, 3, 4, 5} with transition probability matrix P = 2/3 1/3 0 0 0 1/2 1/2 0 0 0 0 0 2/3 0 1/3 0 1/3 0 1/3 1/3 0 0 0 1/2 1/2 . (i) Draw a transition diagram for X and determine its communication classes. Which of them are recurrent and which are transient? Explain your choices. [ 7 marks ] (ii) For i, j, k ∈ S, prove the following statement: if j is accessible from i and k is accessible from j, then k is accessible from i. [ 5 marks ] (b) Let Y be a random walk with barrier at zero. Its state space is S = N0 and the transition probabilities are given by p00 = 1− q, p01 = q and pij = { q, j = i+ 1 1− q, j = i− 1 . for all i ≥ 1, where 0 < q="">< 1.="" (i)="" show="" that="" y="" is="" irreducible.="" [="" 5="" marks="" ]="" (ii)="" determine="" its="" stationary="" distribution="" when="" q="">< 1/2. [ 8 marks ] 5 ma636/ma836/19ass2 7. (a) define the terms irreducible continuous time markov chain, positive recurrent continuous markov chain and aperiodic continuous time markov chain . [ 3 marks ] (b) the maintenance record of a hitting system can be classified as “condition green” (g) if no issues have arisen, “condition yellow” (y) if minor issues have arisen, “condition orange” (o) if there are major maintenance issues or “condition red” (r) if it requires immediate maintenance. the product handbook provides the following information for the system. after maintenance the system is in condition green and remains there for an exponentially distributed length of time with mean 400 hours, after which it has probability 90% of transitioning to condition yellow, probability 10% of transitioning to condition orange. the system in condition yellow remains in that state for an average of 100 hours, then moves to condition orange with 98% probability, or to condition red otherwise. the average holding time for condition orange and condition red are 10 hours and infinite respectively. the transition probabilities from condition orange to conditions orange and red are 70% and 30% respectively. condition red is an absorbing state. (i) let x(t) denote the maintenance state of the system at time t. assuming that (x(t) : t ≥ 0) can be modelled as a continuous time markov chain, write down the generator matrix. [ 4 marks ] (ii) let pij(t) denote the probability that a process which starts in state i at time 0 is in state j at time t, where i, j ∈ s = {g, y,o,r}. write down the kolmogorov forward equation for pij(t) and identify the solutions for pii(t), i ∈ s. [ 8 marks ] (c) consider an ordered sequence of random letters sampled from 4-alphabet letters: a, c, g, t. we obtained the following frequencies of changes between the above letters: a c g t a 100 50 50 0 c 50 0 50 0 g 0 200 100 100 t 0 0 0 100 . (i) fit a discrete-time markov chain, say x = (xn : n ∈ n0), to the data by estimating the transition probability matrix. [ 2 marks ] (ii) draw the transition diagram for x . [ 1 marks ] (iii) determine the communication classes for x and show which of them are recurrent and which of them are transient by using the first step decomposition technique. [ 3 marks ] (iv) determine the stationary distributions for x . [ 3 marks ] (v) for j ∈ {a,c,g, t}, calculate lim n→∞ p(xn = a|x0 = j). [ 1 marks ] turn over ma636/ma836/19ass2 6 8. (a) airplanes arrive at a runway at random times, according to a poisson process, with a rate of 10 airplanes per hour. the taxiing time an airplane spends is an exponential random variable, independent of the arrival time, with the average of 2 minutes per airplane. the taxiing times of these airplanes are independent with identical distribution. (i) provide a model for this queueing system in terms of a continuous-time markov chain. determine the generator matrix. [ 4 marks ] (ii) express the transition probability pij(t) between states i and j in terms of the generator matrix. [ 2 marks ] (iii) calculate a stationary distribution for the above continuous-time markov chain. [ 6 marks ] (iv) calculate the average number of taxiing airplanes on the runway when the system is stationary. [ 4 marks ] (v) determine the transition probability matrix p = (pij) of the embedded markov chain for the above continuous-time markov chain, assuming pii = 0, i ∈ n0. [ 4 marks ] (b) the so-called ehrenfest model can be described as follows: imagine two boxes containing a total ofm identical balls. at each step a ball is selected at random (with uniform probability) from among the totality of m balls, and the selected ball is taken out of its box and placed into the other box. model the number of balls in one box by a discrete time markov chain. determine its transition probability matrix and show that it is irreducible. [ 5 marks ] 1/2.="" [="" 8="" marks="" ]="" 5="" ma636/ma836/19ass2="" 7.="" (a)="" define="" the="" terms="" irreducible="" continuous="" time="" markov="" chain,="" positive="" recurrent="" continuous="" markov="" chain="" and="" aperiodic="" continuous="" time="" markov="" chain="" .="" [="" 3="" marks="" ]="" (b)="" the="" maintenance="" record="" of="" a="" hitting="" system="" can="" be="" classified="" as="" “condition="" green”="" (g)="" if="" no="" issues="" have="" arisen,="" “condition="" yellow”="" (y)="" if="" minor="" issues="" have="" arisen,="" “condition="" orange”="" (o)="" if="" there="" are="" major="" maintenance="" issues="" or="" “condition="" red”="" (r)="" if="" it="" requires="" immediate="" maintenance.="" the="" product="" handbook="" provides="" the="" following="" information="" for="" the="" system.="" after="" maintenance="" the="" system="" is="" in="" condition="" green="" and="" remains="" there="" for="" an="" exponentially="" distributed="" length="" of="" time="" with="" mean="" 400="" hours,="" after="" which="" it="" has="" probability="" 90%="" of="" transitioning="" to="" condition="" yellow,="" probability="" 10%="" of="" transitioning="" to="" condition="" orange.="" the="" system="" in="" condition="" yellow="" remains="" in="" that="" state="" for="" an="" average="" of="" 100="" hours,="" then="" moves="" to="" condition="" orange="" with="" 98%="" probability,="" or="" to="" condition="" red="" otherwise.="" the="" average="" holding="" time="" for="" condition="" orange="" and="" condition="" red="" are="" 10="" hours="" and="" infinite="" respectively.="" the="" transition="" probabilities="" from="" condition="" orange="" to="" conditions="" orange="" and="" red="" are="" 70%="" and="" 30%="" respectively.="" condition="" red="" is="" an="" absorbing="" state.="" (i)="" let="" x(t)="" denote="" the="" maintenance="" state="" of="" the="" system="" at="" time="" t.="" assuming="" that="" (x(t)="" :="" t="" ≥="" 0)="" can="" be="" modelled="" as="" a="" continuous="" time="" markov="" chain,="" write="" down="" the="" generator="" matrix.="" [="" 4="" marks="" ]="" (ii)="" let="" pij(t)="" denote="" the="" probability="" that="" a="" process="" which="" starts="" in="" state="" i="" at="" time="" 0="" is="" in="" state="" j="" at="" time="" t,="" where="" i,="" j="" ∈="" s="{G," y,o,r}.="" write="" down="" the="" kolmogorov="" forward="" equation="" for="" pij(t)="" and="" identify="" the="" solutions="" for="" pii(t),="" i="" ∈="" s.="" [="" 8="" marks="" ]="" (c)="" consider="" an="" ordered="" sequence="" of="" random="" letters="" sampled="" from="" 4-alphabet="" letters:="" a,="" c,="" g,="" t.="" we="" obtained="" the="" following="" frequencies="" of="" changes="" between="" the="" above="" letters:="" a="" c="" g="" t="" a="" 100="" 50="" 50="" 0="" c="" 50="" 0="" 50="" 0="" g="" 0="" 200="" 100="" 100="" t="" 0="" 0="" 0="" 100="" .="" (i)="" fit="" a="" discrete-time="" markov="" chain,="" say="" x="(Xn" :="" n="" ∈="" n0),="" to="" the="" data="" by="" estimating="" the="" transition="" probability="" matrix.="" [="" 2="" marks="" ]="" (ii)="" draw="" the="" transition="" diagram="" for="" x="" .="" [="" 1="" marks="" ]="" (iii)="" determine="" the="" communication="" classes="" for="" x="" and="" show="" which="" of="" them="" are="" recurrent="" and="" which="" of="" them="" are="" transient="" by="" using="" the="" first="" step="" decomposition="" technique.="" [="" 3="" marks="" ]="" (iv)="" determine="" the="" stationary="" distributions="" for="" x="" .="" [="" 3="" marks="" ]="" (v)="" for="" j="" ∈="" {a,c,g,="" t},="" calculate="" lim="" n→∞="" p(xn="A|X0" =="" j).="" [="" 1="" marks="" ]="" turn="" over="" ma636/ma836/19ass2="" 6="" 8.="" (a)="" airplanes="" arrive="" at="" a="" runway="" at="" random="" times,="" according="" to="" a="" poisson="" process,="" with="" a="" rate="" of="" 10="" airplanes="" per="" hour.="" the="" taxiing="" time="" an="" airplane="" spends="" is="" an="" exponential="" random="" variable,="" independent="" of="" the="" arrival="" time,="" with="" the="" average="" of="" 2="" minutes="" per="" airplane.="" the="" taxiing="" times="" of="" these="" airplanes="" are="" independent="" with="" identical="" distribution.="" (i)="" provide="" a="" model="" for="" this="" queueing="" system="" in="" terms="" of="" a="" continuous-time="" markov="" chain.="" determine="" the="" generator="" matrix.="" [="" 4="" marks="" ]="" (ii)="" express="" the="" transition="" probability="" pij(t)="" between="" states="" i="" and="" j="" in="" terms="" of="" the="" generator="" matrix.="" [="" 2="" marks="" ]="" (iii)="" calculate="" a="" stationary="" distribution="" for="" the="" above="" continuous-time="" markov="" chain.="" [="" 6="" marks="" ]="" (iv)="" calculate="" the="" average="" number="" of="" taxiing="" airplanes="" on="" the="" runway="" when="" the="" system="" is="" stationary.="" [="" 4="" marks="" ]="" (v)="" determine="" the="" transition="" probability="" matrix="" p="(pij)" of="" the="" embedded="" markov="" chain="" for="" the="" above="" continuous-time="" markov="" chain,="" assuming="" pii="0," i="" ∈="" n0.="" [="" 4="" marks="" ]="" (b)="" the="" so-called="" ehrenfest="" model="" can="" be="" described="" as="" follows:="" imagine="" two="" boxes="" containing="" a="" total="" ofm="" identical="" balls.="" at="" each="" step="" a="" ball="" is="" selected="" at="" random="" (with="" uniform="" probability)="" from="" among="" the="" totality="" of="" m="" balls,="" and="" the="" selected="" ball="" is="" taken="" out="" of="" its="" box="" and="" placed="" into="" the="" other="" box.="" model="" the="" number="" of="" balls="" in="" one="" box="" by="" a="" discrete="" time="" markov="" chain.="" determine="" its="" transition="" probability="" matrix="" and="" show="" that="" it="" is="" irreducible.="" [="" 5="" marks="">