The magical Ewens sampling formula
Simon Tavaré
Abstract
Starting with n cooked spaghetti strands, tie randomly chosen ends together to produce a collection of spaghetti hoops. What is the expected number of hoops? What can be said about the distribution of the number of hoops of length 1, 2, ...? What is the behaviour of the longest hoops when n is large? What is the probability that all the hoops have different lengths? Questions like these appear in many guises in many areas of mathematics, one connection being their relation to the Ewens sampling formula (ESF). I will describe a number of related examples, including prime factorisation, random mappings and random permutations, illustrating the central role played by the ESF. I will also discuss methods for simulating decomposable combinatorial structures by exploiting another wonder of the ESF world, namely the Feller coupling (FC). Analysis of the spaghetti game in which ends of different strands must be tied shows that apparently small departures from the FC can open up a number of unsolved problems. Several past presidents of the London Mathematical Society (LMS) have contributed to the theory around the ESF, as I will illustrate.