In the list example of Section 3.6.1 suppose that the initial ordering at time 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 . Hint: To compute Ple, precedes

e, at time r] condition on whether or not either

e, or

e, have ever been requested prior to t.