Message #1852

From: David Vanderschel <DvdS@Austin.RR.com>
Subject: Re: [MC4D] Random Permutations and some Interesting References
Date: Sun, 07 Aug 2011 18:47:43 -0500

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.