3
$\begingroup$

For $w$ a permutation, let $c(w)$ denote the total number of cycles and $c_i(w)$ denote the number of $i$-cycles. The Ewens measure is a one-parameter probability distribution on permutations where the permutation $w \in S_n$ has probability $$ \frac{\theta^{c(w)}}{n! \cdot \binom{n+\theta-1}{\theta-1}} $$ of occurring. Here, the weight of $w$ is $\theta^{c(w)}$ while the denominator is the normalizing constant. Let $X^\theta_n$ denote a permutation in $S_n$ sampled from the Ewens measure with parameter $\theta$.

A result of Watterson shows that as $n \to \infty$, we have $$c_i(X^\theta_n) \xrightarrow{d} Poi(\theta/i),$$ where $\xrightarrow{d}$ denotes convergence in distribution. A proof with specific rates of convergence appears here.

Note for fixed $n$ if $\theta \to 0$ that the Ewens measure converges to the uniform measure on cyclic permutations, while if $\theta \to \infty$ it converges to the atomic measure on the identity permutation (all fixed points). I am interested in the case where $\theta$ is treated as a function of $n$, denoted $\theta(n)$. When $\theta(n) \to 0$ or $\theta(n) \to \infty$, the limiting behavior now depends on rates of convergence.

Question: Has anyone studied cycle counts for the Ewens measure when $\theta$ is a function of $n$?

I am especially interested in understanding the (normalized) distribution when $\theta(n) \to \infty$. For example, in this case, when is $$ \mathbb{E}\left[c_1(X^{\theta(n)}_n)\right] = o(n)? $$ Naively, the Poisson convergence might suggest this holds for $\theta(n) = o(n)$, but I don't know an easy way to see what should actually be true.

$\endgroup$
3
  • $\begingroup$ Oh, I swapped $\infty$ and 0 on the limiting distributions. Fixed $\endgroup$
    – Zach H
    Apr 25, 2022 at 20:53
  • $\begingroup$ Also with respect to the convergence of the $c_i$ to Poisson random variables: really the most interesting thing is that they converge jointly to (independent) Poisson random variables. $\endgroup$ Apr 25, 2022 at 22:58
  • $\begingroup$ I agree joint convergence is the most interesting part. Perhaps you can say something similar for sufficiently small values. $\endgroup$
    – Zach H
    Apr 26, 2022 at 1:22

1 Answer 1

4
$\begingroup$

For $w \in S_n$ let $\mathrm{wt}(w) := \theta^{c(w)}$. Thus the probability of $X^{\theta}_n = w$ is $\frac{\mathrm{wt}(w)}{n! \cdot \binom{n+\theta-1}{\theta-1}}$.

Recall that by the exponential formula, we have $$ \sum_{n \geq 0} \frac{1}{n!}x^n \sum_{w \in S_n} t_1^{c_1(w)}t_2^{c_2(w)} t_3^{c_3(w)}\cdots = e^{t_1 \frac{x}{1} + t_2\frac{x^2}{2} + t_3\frac{x^3}{3}+\cdots}$$ so that $$ \sum_{w\in S_n} c_1(w) \cdot \mathrm{wt}(w) = [\frac{1}{n!}x^n] (\partial/\partial t \; e^{t\theta \frac{x}{1} + \theta\frac{x^2}{2} + \theta\frac{x^3}{3} + \cdots } )\mid_{t=1} \\ = [\frac{1}{n!}x^n] (\partial/\partial t \; e^{(t-1)\theta x} \cdot (\frac{1}{1-x})^{\theta})\mid_{t=1} \\ = [\frac{1}{n!}x^n] \theta x (\frac{1}{1-x})^{\theta} \\ = [\frac{1}{n!}x^n] \sum_{n\geq 1} \theta \binom{n+\theta-2}{n-1} x^n \\ = n! \cdot \theta \cdot \binom{n+\theta-2}{n-1} $$

Thus $\displaystyle \mathbb{E}[c_1(X^{\theta}_n)] = n! \cdot \theta \cdot \binom{n+\theta-2}{n-1} \cdot \frac{1}{n!\binom{n+\theta-1}{\theta-1}} = \theta \cdot \frac{n}{n+\theta-1}$.

As you guessed, this quantity is $o(n)$ for $\theta(n) = o(n)$.

EDIT: Using this exponential generating function technique you can similarly obtain exact formulas for all the moments of all the $c_i(X^{\theta}_n)$. Then there is some analysis you have to do if you want to understand their (individual) behavior when taking various limits. It might also be possible to understand joint convergence by computing the mixed moments in the same way.

$\endgroup$
1
  • 2
    $\begingroup$ It’s a nice sanity check to plug in theta equals 1, 0, and infinity to that last formula. $\endgroup$ Apr 25, 2022 at 19:51

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.