Shift-generated random permutations and the M/D/1 queue

Abstract

We consider a simple shift procedure which transforms any mapping f : {0,...,n} --> {0,..., n} into a permutation of 0,...,n. We study this shift under the assumption that the values f(0),...,f(n) are uniformly and independently chosen random numbers in {0,...,n}. The exact and asymptotic distributions of the required shift sizes are derived, and a connection to queueing theory is exhibited.