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
    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
    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$

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.