Cycle lengths of θ-biased random permutations

Author

Tongjia Shi, Harvey Mudd CollegeFollow

Graduation Year

2014

Document Type

Open Access Senior Thesis

Degree Name

Bachelor of Science

Department

Mathematics

Reader 1

Nicholas Pippenger

Reader 2

Michael Orrison

Terms of Use & License Information

This work is licensed under a Creative Commons Attribution-Noncommercial-Share Alike 3.0 License.

Rights Information

© 2014 Tongjia Shi

Abstract

Consider a probability distribution on the permutations of n elements. If the probability of each permutation is proportional to θ^K, where K is the number of cycles in the permutation, then we say that the distribution generates a θ-biased random permutation. A random permutation is a special θ-biased random permutation with θ = 1. The m^th moment of the r^th longest cycle of a random permutation is Θ(n^m), regardless of r and θ. The joint moments are derived, and it is shown that the longest cycles of a permutation can either be positively or negatively correlated, depending on θ. The m^th moments of the r^th shortest cycle of a random permutation is Θ(n^m−θ/(ln n)^r−1) when θ < m, Θ((ln n)^r) when θ = m, and Θ(1) when θ > m. The exponent of cycle lengths at the 100q^th percentile goes to q with zero variance. The exponent of the expected cycle lengths at the 100q^th percentile is at least q due to the Jensen’s inequality, and the exact value is derived.

Recommended Citation

Shi, Tongjia, "Cycle lengths of θ-biased random permutations" (2014). HMC Senior Theses. 65.
https://scholarship.claremont.edu/hmc_theses/65

Source Fulltext

http://www.math.hmc.edu/~tshi/thesis/permutations.pdf