Applications of character estimates to statistical problems for symmetric group (Q2448934): Difference between revisions

This paper studies the probabilistic behaviour of properties of randomly chosen permutations from the symmetric group \(S_n\) (\(n\) a natural number). Let \(\sigma\), \(\pi\) be random permutations from \(S_n\) not both in \(A_n\). Then it is proved that various aspects of elements \(\pi\sigma^i\) behave like independent variables. From this it follows with the probability tending to \(1\) (if \(n\) goes to infinity) that \(\{\pi,\sigma \}\) generates \(S_n\), the Cayley graph of \(\{\sigma,\pi\}\) has diameter \(\leq n^3\log n\) and the directed Cayley graph has almost surely diameter \(\leq n^4\log n\). If \(G\) is a black box group isomorphic to \(A_n\) or \(S_n\) then for every \(k<n^{\frac 1{64}}\) there exists a Las Vegas algorithm giving an effective isomorphism with probability \(1-O(k^{-1})\) which takes \(2\) random elements and \(kn\log n\) multiplications in \(G\). For a given \(\alpha>0\) and \(\tau\in S_n\) which moves at least \(\alpha n\) elements it is proved that if we choose \(\sigma\in S_n\) at random then the number of cycles of \(\sigma\) and \(\tau\sigma\) are nearly independent variables. A precise estimate of their dependency is given.