# Statistics for random permutations

Let $S_n$ be the symmetric group on $n$ elements, let $d$ be the Cayley distance, and let $m$ be a Haar measure on $S_n$.

Let $s$ denote a random permutation with respect to $m$, i.e., $s$ is an $S_n$-valued random variable with law $m$. Let $\delta := d(s,0)$ be the Cayley distance from $s$ to $0$, i.e., the minimum number of transpositions to shuffle $s$ back to the origin. Since $\delta$ is an $\mathbb N$-valued random variable its expectation and variance are well-defined (and dependent on $n$).

What is the asymptotic behavior of $\mathbb E[\delta]$ and $\operatorname{var}(\delta)$ as $n \to \infty$?

• Just to verify my cursory Googling: is Cayley distance the same as Kendall-tau distance? Also, what's known about $\nu$? Commented Feb 3, 2014 at 16:31
• @JonathanY: I don't believe that Kendall-tau is the same as Cayley distance. Since these are finite groups, the two metrics are probably equivalent in the sense that there exist constants $c_n$, $C_n$ so that $c_n d_{\mathrm K \tau} \le d_{\operatorname{Cayley}} \le C_n d_{\mathrm K \tau}$. I would expect the asymptotics of the expectations to be similar (or the same), with possibly different variances. What do you mean, "what is known about $\nu$"? Haar measures are the natural analogues of uniform measures on groups. What do you want to know about $\nu$? Commented Feb 4, 2014 at 3:39
• TomLaGatta, I'll take $\nu$ to be $m$, then. Also, why do you expect the assymptotics to be similar (e.g. are the constants invariant in $n$?)? Can you clarify the definition of $d$, to distinct it from what (I think) I know about K-$\tau$? Commented Feb 4, 2014 at 8:43
• @JonathanY. Oops, that was a typo. I thought you were asking a different question. Sorry about that! I edited the post to replace $\nu$ with $m$. Commented Feb 4, 2014 at 17:37
• The distance $d(s,0)$ is defined as the minimum number of transpositions to shuffle $s$ back to the origin. i.e., there exist transpositions $t_1, \cdots, t_d$ so that $(t_d \cdots t_1) s = 0$. Commented Feb 4, 2014 at 17:37