Skip to Content

Tongjia Shi

Thesis

Cycle Lengths of $\theta$-Biased Random Permutations

Advisor
Nicholas Pippenger
Second Reader(s)
Michael E. Orrison

Abstract

Consider a probability distribution on the permutations of $n$ elements. If the probability of each permutation is proportional to $\theta^K$, where $K$ is the number of cycles in the permutation, then we say that the distribution generates a $\theta$-biased random permutation. A random permutation is a special $\theta$-biased random permutation with $\theta=1$. The $m$th moment of the $r$th longest cycle of a random permutation is $\Theta(n^m)$, regardless of $r$ and $\theta$. 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 $\theta$. The $m$th moments of the $r$th shortest cycle of a random permutation is $\Theta(n^{m-\theta}/(\ln{n})^{r-1})$ when $\theta$ < $m$, $\Theta((\ln{n})^r)$ when $\theta = m$, and $\Theta(1)$ when $\theta$ > $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.

Proposal

$\theta$-Biased Permutations

Additional Materials

Poster