Poisson approximations of the number of fixed points in random multiset permutations

Abstract

For ordinary permutations on $n$ letters, the distribution of the number of fixed points of random permutations is well known to approach the Poisson$(1)$ distribution in total variation distance as $n\to \infty$ super-exponentially quickly. We use Stein's method to get related results for the number of fixed points of random permutations of multisets. Given a sequence of multisets on $n$ letters whose expected number of fixed points converges to a constant $c$, we must have $c\ge 1$ and the distribution of number of fixed points converges to the $\mathrm{Poisson}(c)$ distribution as $n\to \infty$. If $c>1$, then the rate of convergence in total variation distance can be as slow as $n^{-1/2}$.

13 pages, minor additions