91Ó°ÊÓ

Let's define \(L\) as a list of elements, with length \(n\). Let \(E(L)\) be the expected position of the element requested in the list L, if list L has elements ordered in a certain way. We can calculate the expected position of the element requested as follows: \( E(L) = \sum_{i=1}^{n} P_{i} \cdot i \) where \(P_{i}\) is the probability of the element at position i being requested, and i is the position of the element.

Now let's consider two elements, \(a\) and \(b\), at positions \(i\) and \(j\) respectively, with probabilities \(P_{a}\) and \(P_{b}\). Assume that \(i < j\) and \(P_{a} < P_{b}\), meaning element a is before b in the list, but has a lower probability.

Let's call the current list L and the list obtained by swapping elements a and b as L'. We want to compare the expected values of these two orderings, \(E(L)\) and \(E(L')\). For L, the expected value is: \( E(L) = \sum_{k=1}^{n} P_{k} \cdot k = \cdots + P_{a} \cdot i + \cdots + P_{b} \cdot j + \cdots \) For L', the list with elements a and b swapped, the expected value is: \( E(L') = \sum_{k=1}^{n} P_{k} \cdot k^{'} = \cdots + P_{a} \cdot j + \cdots + P_{b} \cdot i + \cdots \) Now let's find the difference between the expected values of these two orderings: \( E(L) - E(L') = (P_{a} \cdot i + P_{b} \cdot j) - (P_{a} \cdot j + P_{b} \cdot i) \) \( E(L) - E(L') = (P_{a} - P_{b}) \cdot (j - i) \) Since \(P_{a} < P_{b}\) and \(i < j\), the difference \((P_{a} - P_{b}) \cdot (j - i)\) is negative. This means that: \( E(L) - E(L') < 0 \) or \( E(L') > E(L) \)

We showed that the expected value of the list L', where elements a and b are swapped, is greater than the expected value of the original list L. Therefore, the list with the elements in decreasing order of their probabilities has a smaller expected value than any other ordering, and it is the best ordering in the sense of minimizing the expected position of the element requested.