Each day, one of n possible elements is requested, the ith one with probability Pi, i 1,

n1 Pi = 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 and note that there are n! possible states.

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

(b) For any state i1, . . . , in (which is a permutation of 1, 2, . . . , n), let π(i1, . . . , in) denote the limiting probability. In order for the state to be i1, . . . , in, it is necessary for the last request to be for i1, the last non-i1 request for i2, the last non-i1 or i2 request for i3, and so on. Hence, it appears intuitive that

Verify when n = 3 that the preceding are indeed the limiting probabilities.

Transcribed Image Text:

Piz Pis (i,... in) = Pi Pi, 1 Pir Piz 1- 1 1 - Pi Pin- Pin-2