Directional Statistics on Permutations

Distributions over permutations arise in applications ranging from multi-object tracking to ranking. The difficulty of dealing with these distributions is caused by the size of their domain, which is factorial in the number of entities $(n!)$. The direct definition of a multinomial distribution over permutation space is impractical for all but a very small $n$. In this work we propose an embedding of all $n!$ permutations for a given $n$ in a surface of a hypersphere defined in $\mathbb{R}^{(n-1)^2}$. As a result, we acquire the ability to define continuous distributions over a hypersphere with all the benefits of directional statistics. We provide polynomial time projections between the continuous hypersphere representation and the $n!$-element permutation space. The framework provides a way to use continuous directional probability densities and the methods developed thereof for establishing densities over permutations. As a demonstration of the benefits of the framework we derive an inference procedure for a state-space model over permutations. We demonstrate the approach with applications and comparisons to existing models.