The Distribution of the Combined Length of Spanned Cycles in a Random Permutation
Yannai A. Gonczarowski · RePEc: Research Papers in Economics · 2013
For a random permutation π on {1, 2, …, n} for fixed n, and for M⊆{1, 2, …, n}, we analyse the distribution of the combined length L=L(π, M) of all cycles of π that contain at least one element of M. We give a simple, explicit formula for the probability of every possible value for L (backed by three proofs of distinct flavours), as well as closed-form formulae for its expectation and variance, showing that less than 1/(|M|+1) of the elements 1, …, n are expected to be contained in cycles of π that are disjoint from M, with low probability for a large deviation from this fraction. We furthermore give a simple explicit formula for all rising-factorial moments of L. These results are applicable to the study of manipulation in matching markets.