Applications of character estimates to statistical problems for the symmetric group

Let g,h in S_n be chosen at random. Using character estimates we show that in various aspects the elements gh^i behave like independent random variables. As application we show that almost surely the Cayley graph determined by g and h has diameter O(n^3 log n), and the directed Cayley graph has almost surely diameter O(n^4 log n). Further we desribe an algorithm for the black-box-recognition of the symmetric group, and show that for each element g moving a positive proportion of all points, the number of cycles of a random element h and of gh are nearly independent.

http://ift.tt/2thiOhn