Problem 1. (20 points) Suppose that we are given n records Ri, kept in some arbitrary ordering. Rn and that the records are originally Consider the move-to-front heuristic where the most recently accessed record moves to the front of the ist. The cost to access a record i at location j in the list j For example, if we access R3 in the list R1, Rs, R2, R4, then the resulting list is Rs, Ri, R2, R4 and the cost is 2. You can think of this as similar to a lookup in a linked list that moves the requested node to the head of the list. Suppose that at each step record Ri is accessed with probability p 0 and k1. Then this forms a Markov chain where each ordering of records is a state and the transitions go between orderings where one of the records moves to the front (a) Compute the stationary distribution of this Markov chain (b) Compute the expected cost per access Note: the expectation should be computable in time that is polynomial in n, given the pi's