EconPapers    
Economics at your fingertips  
 

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).

 
Page updated 2025-01-08
Handle: RePEc:huj:dispap:dp650