Citation:
Gonczarowski, Yannai A. . “Distribution Of The Combined Length Of Spanned Cycles In A Random Permutation, The”. Discussion Papers 2013. Web.
Abstract:
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.