3
$\begingroup$

The cycle containing $1$ of a uniform permutation has length which is uniformly distributed. I was wondering if the converse is true:

Suppose $\sigma$ is a permutation on $\{1,\dots,n\}$ and let $u \in \{1,\dots,n\}$ be a uniformly chosen random variable, independent of $\sigma$. Let $V$ be the size of the cycle of $\sigma$ containing $u$. If $V$ is uniformly distributed on $\{1,\dots,n\}$ then is it true that $\sigma$ must be a uniform permutation?

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ It seems to me that there are $n!$ variables -- the probabilities for each permutation -- but only $n^2+1$ equations. So for large $n$, surely this is false? (Of course the probabilities have to be non-negative ...) $\endgroup$
    – Lucia
    Commented Sep 1, 2014 at 16:23
  • 1
    $\begingroup$ @Lucia: That indicates a more stringent condition, that for any $u$, the size of the cycle containing $u$ is uniformly distributed, is also not enough to guarantee a uniform distribution. As an example, take then uniform distribution on $S_n$, then map each permutation to the lexicographically first permutation in its conjugacy class, then conjugate by a uniformly random power of $(1 2 ... n)$. For $n \ge 3$ this is not uniformly distributed on $S_n$ but for each $u$, the cycle containing $u$ has a uniformly distributed length. $\endgroup$
    – Douglas Zare
    Commented Sep 2, 2014 at 9:56

1 Answer 1

Reset to default
3
$\begingroup$

Observe that the distribution of $V|\sigma$ depends only on the lengths of the cycles in $\sigma$. Therefore, the distribution of $V$ does not change if we replace the random variable $\sigma$ with $f(\sigma)$, where $f:S_n\to S_n$ is any function that maintains the lengths of the cycles.

Example: let $\sigma$ be the identity permutation with probability $1/6$, $(12)$ with probability $3/6$, and $(123)$ with probability $2/6$.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .