[math] \newcommand{\NA}{{\rm NA}} \newcommand{\mat}[1]{{\bf#1}} \newcommand{\exref}[1]{\ref{##1}} \newcommand{\secstoprocess}{\all} \newcommand{\NA}{{\rm NA}} \newcommand{\mathds}{\mathbb}[/math]

(from Pittel) Telephone books, [math]n[/math] in number, are kept in a stack. The probability that the book numbered [math]i[/math] (where [math]1 \le i \le n[/math]) is consulted for a given phone call is [math]p_i \gt 0[/math], where the [math]p_i[/math]'s sum to 1. After a book is used, it is placed at the top of the stack. Assume that the calls are independent and evenly spaced, and that the system has been employed indefinitely far into the past. Let [math]d_i[/math] be the average depth of book [math]i[/math] in the stack. Show that [math]d_i \le d_j[/math] whenever [math]p_i \ge p_j[/math]. Thus, on the average, the more popular books have a tendency to be closer to the top of the stack. Hint: Let [math]p_{ij}[/math] denote the probability that book [math]i[/math] is above book [math]j[/math]. Show that [math]p_{ij} = p_{ij}(1 - p_j) + p_{ji}p_i[/math].

Notes