Consider a sentry who guards one of two doors (D1 and D2) at time t. If he guard
ID: 2960455 • Letter: C
Question
Consider a sentry who guards one of two doors (D1 and D2) at time t. If he guards D1 at time t, he will guard D2 at time t + 1. If he guards D2 at time t, he will guard D1 at time t + 1 with probability 1/2 and guard D2 at time t + 1 with probability 1/2. Model the guarding process as a Markov chain, and define the state of the process Xt at time t to be the door the sentry is guarding at time t. Give the transition matrix for the chain, where D1 serves as state 1 and D2 serves as state 2. What is P|Xt+4 = 2 | Xt = 1 ]? Explain your answer.Explanation / Answer
If he guards D1 now, he has a zero chance of guarding D1 next and a 100% chance of guarding D2 next. so D1 D2 D1 0 1 If he guards D2 now, he has a 50:50 chance of guarding D2 next and a 50:50 chance of guarding D1 next. so D1 D2 D2 1/2 1/2 Right away we know that he will be guarding D2 more. Putting this into a matrix we have --- D1 D2 D1 0 1 D2 1/2 1/2 Now let's cycle through this a number of times (b) squaring the matrix twice yields ---- D1__ D2 D1 0.375__ 0.625 D2 0.3125__ 0.6875 Given that we are guarding door one now, we have a 62.5% chance of guarding D2 four times from now Let's check this with common sense. t 100% of guarding door 1 t+1 100% chance of guarding door 2 t+2 50% chance of guarding door 2 50% chance of guarding door one, write this as t+2 = 1/2D2 +1/2D1 Now break these up in t+3 t+3 1/2(1/2 D2 +1/2D1) + 1/2(1D2) Now continue these in t+4 t+4 1/2[1/2(1/2D2 + 1/2D1) +1/2D2] + 1/2(1/2D1 +1/2D2) Now add up all of the D2 coefficients 1/2[1/2(1/2D2) + 1/2D2] + 1/2(1/2D2) = 1/8 + 1/4 + 1/4 = 5/8 = 0.625 yes! we did it! as a second check let's add the coefficients of D1 1/2[1/2(1/2D1)] +1/2(1/2D1) = 1/8 + 1/4 = 3/8 = .375 yes! this also agrees. Note that this is the probability of guarding D2 in four turns given that we are guarding D1 right now. I know there is no part (c), but these are fun (c) if we keep going we get ----D1__D2 D1_1/3__2/3 D2_1/3__2/3 This shows us that no matter what door we started watching, after many cycles we have a 33% chance of guarding door 1 and a 67% chance of guarding door 2 Note: to multiply a 2x2 matrix 12 34 it is top left is 1*1+3*4 bottom left is 1*3+3*4 top right is 1*2+2*4 bottom right is 3*2+4*4 It is a lot faster on a computer.