[R] Curiously short cycles in iterated permutations with the same seed

[Eric Berger]

Hi Boris,
Do a search on "the order of elements of the symmetric group". (This search
will also turn up homework questions and solutions.) You will understand
why you are seeing this once you understand how a permutation is decomposed
into cycles and how the order relates to a partition of n (n=10 in your
case).

Enjoy!
Eric


On Fri, Dec 8, 2017 at 6:39 AM, Boris Steipe <boris.steipe at utoronto.ca>
wrote:

> I have noticed that when I iterate permutations of short vectors with the
> same seed, the cycle lengths are much shorter than I would expect by
> chance. For example:
>
> X <- 1:10
> Xorig <- X
> start <- 112358
> N <- 10
>
> for (i in 1:N) {
>   seed <- start + i
>   for (j in 1:1000) { # Maximum cycle length to consider
>     set.seed(seed)    # Re-seed RNG to same initial state
>     X <- sample(X)    # Permute X and iterate
>     if (all(X == Xorig)) {
>       cat(sprintf("Seed:\t%d\tCycle: %d\n", seed, j))
>       break()
>     }
>   }
> }
>
> Seed:   112359  Cycle: 14
> Seed:   112360  Cycle: 14
> Seed:   112361  Cycle: 8
> Seed:   112362  Cycle: 14
> Seed:   112363  Cycle: 8
> Seed:   112364  Cycle: 10
> Seed:   112365  Cycle: 10
> Seed:   112366  Cycle: 10
> Seed:   112367  Cycle: 9
> Seed:   112368  Cycle: 12
>
> I understand that I am performing the same permutation operation over and
> over again - but I don't see why that would lead to such a short cycle (in
> fact the cycle for the first 100,000 seeds is never longer than 30). Does
> this have a straightforward explanation?
>
>
> Thanks!
> Boris
>
> ______________________________________________
> R-help at r-project.org mailing list -- To UNSUBSCRIBE and more, see
> https://stat.ethz.ch/mailman/listinfo/r-help
> PLEASE do read the posting guide http://www.R-project.org/
> posting-guide.html
> and provide commented, minimal, self-contained, reproducible code.
>

	[[alternative HTML version deleted]]