pith. sign in

arxiv: 1901.03386 · v3 · pith:DWPDJBV5new · submitted 2019-01-10 · 🧮 math.PR

How Uniform is the Uniform Distribution on Permutations?

classification 🧮 math.PR
keywords permutationsuniformdistributiondotsapproximateconfigurationfavorablenegligible
0
0 comments X
read the original abstract

For large $q$, does the (discrete) uniform distribution on the set of $q!$ permutations of the vector $(1,2,\dots,q)$ closely approximate the (continuous) uniform distribution on the $(q-2)$-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,\dots,q)$ is not the most favorable configuration for approximate spherical uniformity of permutations. Unlike the permutations of $(1,2,\dots,q)$, the normalized surface area of the largest empty spherical cap among the permutations of the most favorable configuration approaches 0 as $q\to\infty$. Several open questions are posed.

This paper has not been read by Pith yet.

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.