I'm given an exercise where we are to simulate a thief escaping from an officer. The thief (let's call him/her T for simplicity) and an officer (O) have four cities to be in.
Let's call the cities A, B, C and D. There is a road between A and B, B and C and C and D. The roads can be traveled in both directions, so there is an opportunity to travel between city D and A as well (etc.).
There is a 90% probability to move to the next city and a 10% probability to just stay in the current city. If C and T end up in the same city, the O arrests T, and T's escape route ends here. O does NOT catch T if they are crossing roads in different directions (e.g. if O travels from B to C and T travels from C to B, T is still on the run).
We are considering this as a stocastic process and want to use a Markov chain to model it. So, firsly, we are to find a suitable transition matrix. My attempt is this, and i assume it is correct:
$$ \begin{bmatrix} 0.1 & 0.45 & 0 & 0.45 \\ 0.45 & 0.1 & 0.45 & 0 \\ 0 & 0.45 & 0.1 & 0.45 \\ 0.45 & 0 & 0.45 & 0.1 \end{bmatrix} $$
Secondly, our task is to find the eqvivalence classes for this matrix, and then state and explain why they are recurrent or transient. I'm finding this part a bit hard!
Furthermore, we are supposed to find the expected "escape time" for T (i.e. the number of times T and O move before they end up in the same city). We consider one movement as one hour. I also struggle with that part.
Lastly, we want to find the probability that O and T never are located in cities next to eachother (if O is in city A, T can't be in city B or D and so on). I'm stuck here as well.
I know this turned out to be more of a novel, but I really need some advice/help here. So, I beg you guys! Please help me (^__^)'
Hint Try and be systematic and encode everything about your problem into your state matrix. That is; combination of thief and agent position into each position. This can be done with Kronecker product $\otimes$:
If $\bf P$ is your matrix above, then $\bf P\otimes P$ will then be a simultaneous transmission matrix - taking both thief and agent to their new positions at once. In this new state space, probability for each combination will have it's own index, so you can easily sum out those probabilities by scalar products with masked 1 vectors.
This vector of interesting combinations can be found by doing (element-wise) $$([1,1,1,1]^T \otimes [1,2,3,4]^T) = ([1,2,3,4]^T \otimes [1,1,1,1]^T)$$