The Distribution of the Combined Length of Spanned Cycles in a Random Permutation
Yannai A. Gonczarowski
Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem
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.
Pages: 9 pages
Date: 2013-11
References: Add references at CitEc
Citations: View citations in EconPapers (1)
Downloads: (external link)
http://ratio.huji.ac.il/sites/default/files/publications/dp650.pdf (application/pdf)
Our link check indicates that this URL is bad, the error code is: 404 Not Found (http://ratio.huji.ac.il/sites/default/files/publications/dp650.pdf [302 Moved Temporarily]--> https://ratio.huji.ac.il/sites/default/files/publications/dp650.pdf)
Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.
Export reference: BibTeX
RIS (EndNote, ProCite, RefMan)
HTML/Text
Persistent link: https://EconPapers.repec.org/RePEc:huj:dispap:dp650
Access Statistics for this paper
More papers in Discussion Paper Series from The Federmann Center for the Study of Rationality, the Hebrew University, Jerusalem Contact information at EDIRC.
Bibliographic data for series maintained by Michael Simkin (menahem.simkin@mail.huji.ac.il).