# 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.