Message #1850

From: David Vanderschel <DvdS@Austin.RR.com>
Subject: Random Permutations and some Interesting References
Date: Sat, 06 Aug 2011 16:13:10 -0500

In the MC2D state graph thread I wrote:
>Another interesting point is that, with 5 unplaced cubies,
>you can finish in only 2 steps whenever there are no stuck
>cubies. In a random permutation of n things, the expected
>number of unmoved things is 1 and the probability that all
>are moved is 1/n; so it is fairly common to wind up with a
>5-cycle when 5 cubies are unplaced. In my experience with
>the puzzles, it seems to be more common than one time out of
>five. (If that’s true, I think there may be an explanation
>of it in terms of the fact that an unmoved cubie may well be
>oriented correctly, but I have not figured out how to make the
>argument precise.) Except for S1111 (rare), when 4 cubies
>are unplaced, you can always finish in 2 steps.

After writing that, I kept thinking that my experience was
that I got a 5-cycle a lot more than 20% of the time. Then
it dawned on me that assuming a random permutation was very
wrong. It has to be even! :-[ For the fraction that are
5-cycles, this reduces the denominator by a factor of 2, so
you would expect a 5-cycle 40% of the time. I figured this
would skew the expected number of stuck cubies also, but it
doesn’t:

CLS number stuck expected-stuck

even
S11111 1 5
S221 15 1 1 = (1*5 + 15*1 + 20*2) / 60
S311 20 2
S5 24 0

odd
S41 30 1
S32 20 0 1 = (30*1 + 10*3) / 60
S2111 10 3

It is probably still not entirely appropriate to assume that
after lots of solving moves, then, when you get down to 5
unplaced cubies that their permutation is random even; but the
above numbers for even permutations are consistent with my
experience. (Not that I have been counting - just ‘feel’.)

Before doing the above analysis, I first searched on "random
even permutation" to see if someone else had already
analyzed the expected number of 1-cycles issue for random
even permutations. I did not find anything, but I was not
so interested in the general case, so I was satisfied with
the above enumeration. (And I think I now do know the
answer in general, but I have not seen the proof.)

In the above search, I did run across a site which will
probably interest many folks on the 4D_Cubing list:
http://teamikaria.com/hddb/

As you can see, there is a forum, a wiki, and a collection
of references to things 4D-related. ‘Team’ Ikaria is
actually a one-man show run by a guy who goes by Keiji. I
have not spent much time on Keiji’s site yet, but it looks
to me like it can be taken seriously.

On the general subject of statistics associated with random
permutations, the following paper is fairly tractable:
http://www.inference.phy.cam.ac.uk/mackay/itila/cycles.pdf

The following one is pretty esoteric, but it appears to have
been dumped whole into Wikipedia:
http://www.mathematik.uni-stuttgart.de/~riedelmo/papers/randperms.pdf
<http://www.mathematik.uni-stuttgart.de/%7Eriedelmo/papers/randperms.pdf>
http://en.wikipedia.org/wiki/Random_permutation_statistics
It does go into cycle structure issues.

Regards,
David V.