Consider two independent random walkers A and B on the 5-cycle with vertices = {1, 2, 3, 4, 5}. They walk independently clockwise or anticlockwise with probability 1 2 . Consider the graph distance between A and B, i.e., the length of the shortest path joining the two. For example, if A is at 1 and B is at 5, the graph distance is 1 and not 4. In particular the graph distance can only take values {0, 1, 2}. (a) Let Xt denote the graph distance between the two walkers at time t. Show that Xt is a Markov chain by describing its transition probabilities. (b) Suppose, at time zero, walker A start at 2 while walker B starts at 5. Find the expected number of steps after which they are at the same vertex