84. In the list example of Section 3.6.1 suppose that the initial ordering at time t = 0 is determined completely at random; that is, initially all n! permutations are equally likely. Following the front-of-the-line rule, compute the expected position of the element requested at time t.

Hint: To compute P {ej precedes ei at time t} condition on whether or not either ei or ej has ever been requested prior to t.