Cops and Robbers is a classic game played on graphs that has many applications. Well consider the following probabilistic version. Here are the rules: (i) Given a graph (a set of vertices and edges connecting them), a cop and a robber are placed on random (different) vertices. The cop tries to catch the robber by being on the same vertex. (ii) Each move in the game consists of one of the following, chosen randomly by a spinner: 1/3 of the time, the cop moves one vertex closer to the robber. If there is more than one possible move that accomplishes this, the cop chooses randomly between them. 1/3 of the time, the robber moves one vertex further away from the cop, if possible. If there is more than one possible move, the robber chooses randomly. If there is no way to move further away from the cop, the robber stays on their current vertex (this still counts as a move in the game). 1/6 of the time, the cop makes a random move (this variation is called the tipsy cop theyve had a few too many and are stumbling around). 1/6 of the time, the robber makes a random move (this variation is called the drunken robber). (iii) The game continues until the cop and robber are on the same vertex, at which point the cop has caught the robber. Well investigate the game played on the Petersen graph, a well-known graph in which the distance between any two different vertices is 1 or 2. Heres a picture taken from the paper Markov Models for the Tipsy Cop and Robber Game on Graphs by Bardenova, Ciarcia, and Insko that was published in July of this year in the Open Journal of Discrete Mathematics: In the first graph, the cop (blue double circle) and the robber (red single circle) are on the same vertex (so the game has ended). In the middle graph the distance between them is 1, and the distance is 2 in the third graph. You should convince yourself of two things: (1) 2 is the maximum distance between any two vertices. (2) Because of the graphs symmetry, if the distance between the cop and robber is 2, in terms of game play it doesnt matter which two vertices theyre on (any pair of vertices that are distance two apart are just like any other two vertices that are distance two apart). The same is true for any vertices that are distance one apart. So to model this game with a Markov process, we just need three states: a distance 0 state, a distance 1 state, and a distance 2 state. Here are the first two columns of the transition matrix: A = 1 4/9 0 0 0 5/9 The (1, 1) entry is 1 since if were in the distance 0 state the game ends and we stay in that state. To see where the entries in the second column come from, consider what can happen when the game is in the distance 1 state. The (1, 2) entry of A is the probability of moving from the distance 1 state to the distance 0 state, the (2, 2) entry is the probability of starting in the distance 1 state and staying there, and the (3, 2) entry is the probability of moving from the distance 1 state to the distance 2 state. Now, if we start in the distance 1 state, heres what happens: 1/3 of the time the cop moves to the same vertex as the robber. This is moving from the distance 1 state to the distance 0 state. 1/3 of the time the robber moves distance two away from the cop. This is moving from the distance 1 state to the distance 2 state. 1/6 of the time the cop moves randomly. If the cop and robber are distance 1 apart and move randomly, one of the three moves available for the cop decreases the distance to 0, and other two increase the distance to 2 (take a look at the graphs above to convince yourself of this). 1/6 of the time the robber moves randomly. As with the cop, one of the three moves available for the robber decreases the distance to 0, and other two increase the distance to 2. So the (1, 2) entry of A, representing the probability of moving from the distance 1 state to the distance 0 state, is 1/3 + (1/6)(1/3) + (1/6)(1/3) = 4/9 and the (3, 2) entry (representing the probability of moving from the distance 1 state to the distance 2 state) is 1/3 + (1/6)(2/3) + (1/6)(2/3) = 5/9. The (2, 2) entry is 0 since we never stay in the distance 1 state. Wow, that was a long set up! Heres what you actually have to do: (a) Determine the third column of A. Clearly explain how you obtain each entry. (c) Check your answer to part (b) using Matlab. Enter A into Matlab and compute Akx0 until you find the smallest k such that the probability of being in the 0- distance state (which ends the game) is at least 95%, for x0 equal to (0, 1, 0)T and (0, 0, 1)T . Report the k values here, and state how they match up (or dont) with your conjecture. Again, if your conjecture was wrong thats fine, you wont lose points. (d) What happens over time? Does the probability that the game will terminate go to 1? Conjecture an answer by calculating Ak for some large values of k for both x0s from part(c). Report what you did here. (e) What if we start with a probability vector (the entries add to 1) besides (0, 1, 0)T or (0, 0, 1)T ? Does the same thing happen over time as in part (d)? (f) The answers to (d) and (e) should be able to be explained by eigenvalues and eigenvectors. Compute the eigenvalues and eigenvectors of A in Matlab with the command [X,D]=eig(A) (this puts the eigenvectors in the columns of X and the corresponding eigenvalues on the diagonal in D). Report the eigenvalues and eigenvectors here. (g) Lets call the eigenvectors v1, v2, and v3, where v1 corresponds to = 1. Note that v1, v2, and v3 are linearly independent, so any initial vector x0 can be written as a linear combination of v1, v2, and v3. Use this fact to explain why Akx0 converges to a steady state vector as k gets large, for any initial vector x0. (h) Use the fact that Ak = XDkX1 to find Akx0 for an arbitrary x0 = (a, b, c) T with a + b + c = 1. Then show that Akx0 goes to (1, 0, 0)T as k gets large. This proves that (1, 0, 0) is indeed the steady state vector, and indicates that the game will eventually terminate with high probability.