The Distribution of the Combined Length of Spanned Cycles in a Random Permutation
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.
Year of publication: |
2013-11
|
---|---|
Authors: | Gonczarowski, Yannai A. |
Institutions: | Center for the Study of Rationality, Hebrew University of Jerusalem |
Saved in:
freely available
Saved in favorites
Similar items by person
-
A Stable Marriage Requires Communication
Gonczarowski, Yannai A., (2014)
-
Cascading to Equilibrium: Hydraulic Computation of Equilibria in Resource Selection Games
Gonczarowski, Yannai A., (2014)
-
Good, Better, Best! — Unbeatable Protocols for Consensus and Set Consensus
Castaneda, Armando, (2013)
- More ...