--------------050702030803030800070704
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
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://en.wikipedia.org/wiki/Random_permutation_statistics
It does go into cycle structure issues.
Regards,
David V.
--------------050702030803030800070704
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit
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://en.wikipedia.org/wiki/Random_permutation_statistics
It does go into cycle structure issues.
Regards,
David V.
--------------050702030803030800070704--
--- In 4D_Cubing@yahoogroups.com, David Vanderschel
>=20
> 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/
>=20
> 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.
>=20
I also have discovered this forum some time ago. Unfortunately, now it's al=
most dead. But 4-8 years ago it was very active. The most interesting for m=
e are attempts to describe different aspects of 4D world, but there are man=
y other interesting topics (including physics, geometry, philosophy, theolo=
gy and so on in different kinds of space).
--------------050004040003030107070301
Content-Type: text/plain; charset=ISO-8859-1; format=flowed
Content-Transfer-Encoding: 7bit
This is rather remotely related to cubing, so you may want
to skip it. It is a follow up, including a correction, on
my last post in this thread.
In my last message I quoted myself saying:
>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. ...
My statement that "the probability that all are moved is
1/n" is incorrect. The correct statement is that the
probability of an n-cycle is 1/n. (Permutations in which all
are moved are called derangements, and they are not so easy
to deal with.) It is true that the probability of a 5-cycle
is 2/5 for a random _even_ permutation of 5 things, since the
only way to get an even permutation for which all objects change
positions is a 5-cycle and the probability of a 5-cycle for
_any_ permutation is 1/5.
Regarding proving that the expected number of fixed positions
is 1, I wrote:
>..., 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.)
Now, I have _seen_ the proof! I emphasize "seen" because,
contrary to Melinda's beliefs about how I think, a proof
came to me by visualizing something. The proof in the
Mackay paper I cited is in terms of probability, which
struck me as a somewhat odd way of looking at a rather
finite problem. As I was pondering Mackay's proof, a simple
way to "see" it occurred to me:
Contemplating, "expected number of 1-cycles", one is
normally inclined to write something like
sum( k in [0,n] )( k*F(k) ) / n!,
where F(k) is the number of permutations for which k objects
are fixed. That line of reasoning gets you in trouble,
because F(k) is not very tractable. However, the sum that
is in the numerator can also be seen to be
sum( over all permutations p )( f(p) ),
where f(p) is the number of positions for which the
permutation p leaves the object in the position fixed, since
the number of occurrences of k=f(p) in the sum on p is F(k).
The thing that I visualized was an n! x n matrix of 1s and
0s in which the rows correspond to permutations and the
columns correspond to the possible positions of the objects
being permuted. For each permutation, there is a 1 in the
column corresponding to each position for which the
permutation is fixed (and 0s in any other columns). Thus
f(p) is the row-sum of the row for permutation p. Thus the
sum of the f(p) is the total number of 1s in the matrix.
The trick here is that it is much easier to count that
number of 1s if you do it by columns. For each position, it
is easy to see that there are (n-1)! permutations for which
that position is fixed (since we don't really care how many
other positions are fixed by any of those permutations). So
adding the column sums trivially yields n!.
The argument is almost the same when you are only doing it
for even permutations. The column sums are all (n-1)!/2,
and the overall denominator is n!/2.
Regards,
David V.
--------------050004040003030107070301
Content-Type: text/html; charset=ISO-8859-1
Content-Transfer-Encoding: 7bit