Unseparated pairs and fixed points in random permutations

August, 2013
Report Number: 
Persi Diaconis and Steven N. Evans and Ron Graham
In a uniform random permutation Π of [n] := {1, 2, . . . , n}, the set of elements k ∈ [n − 1] such that Π(k + 1) = Π(k) + 1 has the same distribution as the set of fixed points of Π that lie in [n−1]. We give three different proofs of this fact using, respectively, an enumeration relying on the inclusion-exclusion principle, the introduction of two different Markov chains to generate uniform random permutations, and the construction of a combinatorial bijection. We also obtain the distribution of the analogous set for circular permutations that consists of those k ∈ [n] such that Π(k + 1 mod n) = Π(k) + 1 mod n. This latter random set is just the set of fixed points of the commutator [ρ, Π], where ρ is the n-cycle (1, 2, . . . , n). We show for a general permutation η that, under weak conditions on the number of fixed points and 2-cycles of η, the total variation distance between the distribution of the number of fixed points of [η, Π] and a Poisson distribution with expected value 1 is small when n is large.