How Uniform is the Uniform Distribution on Permutations?

Tech Report Number

For large q, does the (discrete) uniform distribution on the set of q! permutations of the vector (1, 2, . . . , q) closely approximate the (continuous) uniform distribution on the (q2)-sphere that contains them? These permutations comprise the vertices of the regular permutohedron, a (q 1)-dimensional convex polyhedron. Surprisingly to me, the answer is emphatically no: these permutations are confined to a negligible portion of the sphere, and the regular permutohedron occupies a negligible portion of the ball. However, (1,2,...,q) is not the most favorable configuration for approximate spherical uniformity of permutations. Unlike the permutations of (1, 2, . . . , q), the normalized surface area of the largest empty spherical cap among the permutations of the most favorable configuration approaches 0 as q ! 1. Several open questions are posed.

Published Date