# Cycle lengths of θ-biased random permutations

2014

## Document Type

Open Access Senior Thesis

## Degree Name

Bachelor of Science

## Department

Mathematics

Nicholas Pippenger

Michael Orrison

## 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 mth moment of the rth longest cycle of a random permutation is Θ(nm), 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 mth moments of the rth shortest cycle of a random permutation is Θ(nm−θ/(ln n)r−1) when θ < m, Θ((ln n)r) when θ = m, and Θ(1) when θ > m. The exponent of cycle lengths at the 100qth percentile goes to q with zero variance. The exponent of the expected cycle lengths at the 100qth percentile is at least q due to the Jensen’s inequality, and the exact value is derived.

## Source Fulltext

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

COinS