Stochastic Couplings and Bijections from the Symmetric Group to Itself

Abstract

Inspired by the Stochastic processes described by the Feller Coupling and Chinese Restaurant Processes, we create four different bijections from words in the set $[1]\times [2]\times \cdot \times [n]$ to $S_n$. We then compose these maps with their inverse to obtain a toal of six bijections $S_n\to S_n$. Following that, we investigate the fixed points ($1$-cycle) and higher $k$-cycles of these maps. We characterized some of their properties completely as well as empirically showing the complexity of the higher $k$-cycle structures for these maps.

13 pages