crazybob pointed me to a discussion from MaryMaryQuiteContrary's blog related to an unfair random permutation generator:
import java.util.Random;
public class Puzz {
private static Random rnd = new Random();
public static void shuffle(Object[] a) {
for (int i = 0; i < a.length; i++)
swap(a, i, rnd.nextInt(a.length));
}
private static void swap(Object[] a, int i, int j) {
Object tmp = a[i];
a[i] = a[j];
a[j] = tmp;
}
}
The unfairness, as the discussion points out, should be obvious, because there are n! permutations and nn equally-likely possible outputs from the shuffle method. (n! does not divide nn unless n=2.)
One can naturally wonder just how unfair the shuffle method is. For example, how often does it produce the identity permutation? Somewhat out of nostalgia, this is just the kind of thing that I love to spend (i.e., waste) a little time on.
The first thing to do is to work some examples. For this kind of thing, there is a programming language called GAP, complete with an interactive shell, for working with permutations -- along with finite and infinite groups, rings, algebras, vector spaces, and combinatorial structures. (I used GAP and some other packages extensively for my PhD dissertation, and it definitely beat implementing the classic algorithms by hand...) One of the useful things about GAP is that it treats permutations and permutation groups as first-class constructs:
gap> (1,2,3)(4,5) * (4,5,6,7)(1,2);
(2,3)(4,6,7);
gap> g := SymmetricGroup(7);;
gap> s := Centralizer(g,Subgroup(g,[(1,2,3,4,5)]));
Group([ (6,7), (1,2,3,4,5) ])
gap> Size(s);
10
And this makes it relatively straightforward (if a bit brutish) to compute the probability that shuffle produces a trivial permutation:
gap> twocycleorid := function(i,j,n)
> if i=j then return Identity(SymmetricGroup(n));
> else return (i,j);
> end;
function ( i, j, n ) ... end
gap> f := function(n)
> local x,s;
> s := [];
> for i in Tuples([1..n],n) do
> x := Identity(SymmetricGroup(n));
> for j in [1..n] do
> x := x * twocycleorid(j,i[j],n);
> od;
> if x = Identity(SymmetricGroup(n)) then Add(s,i);fi;
> od;
> return s;
> end;
function( n ) ... end
gap>List([2..7], x -> Size(f(x)));
[ 2, 4, 10, 26, 76, 232]
GAP is a very useful tool, but silicon isn't as good as carbon for this sort of thing -- doing anything meaningful with a O(nn) computation will require (wo)man as opposed to machine. Even so, GAP and its ilk can still be useful as substitutes for hand computation when performing experiments. The key, of course, is to use the computer to do things some combination of faster, more accurately, or with more data than you could be hand; I do believe that the skills to compute by hand are the source of the intuition that creates assertions worth testing by machine... In regards to the current problem, consider the following simple obervation for n=7, which is the largest practical value for n on my PowerBook:
gap> g := function(x,y)
> return x and y;
> end;
gap> Iterated(List(f(7), x->Iterated(List(x, y-> y=x[x[y]]),g)),g);
true
The same holds for smaller values of n, which would lead one to ask whether every n-tuple that produces the identity permutation also is an involution. By involution I mean that if you were to have, e.g., the sequence of random indices 1, 5, 4, 3, 2 in shuffle, then you would have the permutation defined as:
1 -> 1
2 -> 5
3 -> 4
4 -> 3
5 -> 2
This is an involution, and as expected, (25)(34)(43)(52) (which is what shuffle produces) is the identity permutation. Conveniently, there is a well-known formula for the number of involutions on an n-element set, so the assertion would be that the number of times that the trivial permutation occurs is defined by the formula:
w(1) = 1
w(2) = 2
w(n) = w(n-1) + (n-1) w(n-2)
I don't have any jobs or backpacks to give away, but I'll invite any budding combinatorialists out there to prove the assertion about involutions. (It's not that bad.) If you think you have a proof (or counterexample), drop a comment here, and I'll let you know if it's right or wrong.
