Placing books in order so as to minimize search time This is problem 2.7.15 from Probability and Random Processes by Grimmett and Stirzaker:
It is required to place in order $n$ books $B_1, B_2, \ldots, B_n$ on a library shelf in such a way that readers searching from left to right waste as little time as possible on average. Assuming that each reader requires book $B_i$ with probability $p_i$, find the ordering of the books which minimizes $\mathbb{P}(T \geq k)$ for all $k$, where $T$ is the (random) number of titles examined by a reader before discovery of the required book.
Intuitively, it seems to me that the books should be placed in order so that the books which are the most popular (i.e. have the highest probability of being taken from the shelf) appear first. But how do I start to go about proving this? Any hints would be appreciated.
As requested by user uniquesolution, here is my argument for $n = 2$:
Let $p_1$ be the probability that $B_1$ is required, and $p_2 = 1 - p_1$ be the probability that $B_2$ is required. No matter how the books are placed, $\mathbb{P}(T \geq 1) = 1$. So we only need to minimize $\mathbb{P}(T \geq 2)$. Now, if we place $B_1$ first then,
\begin{eqnarray}
\mathbb{P}(T \geq 2) &=& \mathbb{P}(T \geq 2|B_1) \mathbb{P}(B_1) + \mathbb{P}(T \geq 2|B_2) \mathbb{P}(B_2) \\
& = & 0 . p_1 + 1 . p_2 \\
& = & p_2
\end{eqnarray}
If we place book 2 first then,
\begin{eqnarray}
\mathbb{P}(T \geq 2) &=& \mathbb{P}(T \geq 2|B_1) \mathbb{P}(B_1) + \mathbb{P}(T \geq 2|B_2) \mathbb{P}(B_2) \\
& = & 1 . p_1 + 0 . p_2 \\
& = & p_1
\end{eqnarray}
Suppose that $B_1$ is the most popular book. Then $p_1 \geq p_2 = 1 - p_1$. So to minimize the search time we should place $B_1$ first. Similarly we should place $B_2$ first if that is the most popular book.
How can I generalize this argument to $n > 2$?
 A: Based on hints from uniquesolution and Aravind here is my solution:
$\textbf{Proof:}$
Suppose that the books are ordered $B_1, B_2, \ldots, B_n$. And the probability of a reader wanting $B_i$ is $\mathbb{P}(B_i) = p_i$. Then the probability that the number of titles examined by a reader is greater than or equal to $k$ when they search for a book they want is given by
\begin{eqnarray}
\mathbb{P}(T \geq k) &=& \sum_{i = 1}^n \mathbb{P}(T \geq k|B_i)\mathbb{P}(B_i) \\
& = & \sum_{i = 1}^{k - 1} \mathbb{P}(T \geq k|B_i)\mathbb{P}(B_i) + \sum_{i = k}^{n} \mathbb{P}(T \geq k|B_i)\mathbb{P}(B_i) \\
& = & \sum_{i = 1}^{k - 1} 0.\mathbb{P}(B_i) + \sum_{i = k}^{n} 1.\mathbb{P}(B_i) \\
& = & \sum_{i = k}^{n} p_i
\end{eqnarray}
Now suppose that $k_1 < k_2$ and $p_{k_1} < p_{k_2}$. If we swap the books at positions $k_1$ and $k_2$ then from the calculation above, $\mathbb{P}(T \geq k)$ does not change for all $k \leq k_1$ and all $k > k_2$. However, for $k_1 < k \leq k_2$, the probability decreases by $p_{k_2} - p_{k_1}$. So to decrease $\mathbb{P}(T \geq k)$ for all $k$ we should swap the books.
Now relabel the books so that they are again ordered as $B_1, B_2, \ldots, B_n$. As $k_1$ and $k_2$ were arbitrary in the argument above we can repeat the procedure and swap books if we find another pair $k_1$ and $k_2$ such that $k_1 < k_2$ and $p_{k_1} < p_{k_2}$. Doing this repeatedly we obtain a sequence of configurations of books for which the average search time becomes progressively smaller. The procedure stops when all the books are ordered from the most the popular to the least popular and this is the configuration for which $\mathbb{P}(T \geq k)$ for all $k$ is minimized. $\square$
