In looking at the results of the Beer Test 2009, I wondered how much better than chance we were able to guess which beer was which. In other words, if for all beers one just does a random guess (with no double guesses), how many correct answers would one expect to have?

Or, to phrase this a bit more mathematically: what is the distribution for the number of fixed points of a random permutation of n elements?

First of all, the expected value of the number of fixed points is one, by a very simple argument: let X(i) denote the random variable that is 1 if the ith point was a fixed point, and 0 otherwise. Obviously, this has expected value 1/n, so by linearity of the expected value operator, the total number of expected fixed points is the sum of the X(i), ie, 1. This argument is made, for example, in Example 6.8 of Introduction to probability by Grinstead and Snell.

Note that this is exactly the same as the expected number of fixed points when we did allow double guesses, which to me was not so obvious.

As for the probability distribution: the number of permutations of n with k fixed point is, I found out, called the Rencontres number Dn,k. More information can be found on Wikipedia and Mathworld. The first few values can, of course, be found in  The On-Line Encyclopedia of Integer Sequences (OEIS).

Which was, in fact, how I found the name of this distribution: I wrote a small Mathematica function to calculate these numbers, and searching for the results with n=5 quickly gave this reference.

Wikipedia and OEIS give some hints on how to calculate the Rencontres number; however, I will also give my ready-to-use (and, probably, horribly inefficient) Mathematica function to calculate it:

rencontre[n_, k_] := 1 /; n == 0 && k == 0
rencontre[n_, k_] := 0 /; n == 0 && k != 0
rencontre[n_, k_] := Binomial[n, k]*rencontre[n - k, 0] /; n > 0 && k > 0
rencontre[n_, k_] := n! - Sum[rencontre[n, i], {i, n}] /; n > 0 && k == 0

The idea is pretty simple: if we know Dn,0 (ie, the number of permutations with length n without fixed points), then calculating Dn,k is easy: it is the number of possibilities to pick the k correct places times the number of n-k-permutations without fixed points.

To calculate Dn,0 I simply substracted all Dn,k for k>0 from the total number of permutations, n!. This calculation could, according to Wikipedia, be done much faster, but I did not try this.

So how does this distribution look like? I myself was mostly was interested in the case n=12 and n=13. Here’s the distributions in this case:

Last Modified : July 10th, 2009 Filed under : projects Navigate : Previous post / Next post