Each day one of n possible elements is requested, the ith one with probability P., i1,2" P, = 1 These elements are at all times arranged in an ordered list that is revised as follows, the element selected is moved to the front of the list with the relative positions of all the other elements remaining unchanged Define the state at any time to be the list ordering at that time.

(a) Argue that the above is a Markov chain.

(b) For any state i,.,i (which is a permutation of 1, 2, ..., n) let (ii) denote the limiting probability Argue that P (ii) P - '2 1- P - P