Shift-Generated Random Permutations and The M/D/1 Queue

We consider a simple shift procedure which transforms any mappingf:{0, ..., n}{0, ..., n} into a permutation of 0, ..., n. Westudy this shift under the assumption that the values f(0),..., f(n) are uniformly and independently chosen random numbersin {0, ..., n}. The exact and asymptotic distributions of therequired shift sizes are derived, and a connection to queueingtheory is exhibited. 1991 Mathematics Subject Classification60C05, 60K25.