R help - Dec 2017 - Curiously short cycles in iterated permutations with the same seed

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

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

Landau's function gives the maximum cycle length of a permutation.
See.,e.g.,
http://mathworld.wolfram.com/LandausFunction.html.

Bill Dunlap
TIBCO Software
wdunlap tibco.com

On Thu, Dec 7, 2017 at 9:34 PM, Eric Berger <ericjberger at gmail.com>
wrote:
> 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]]
>
> ______________________________________________
> 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]]