In this post we will give a heuristic derivation of a result of Vershik, describing the shape of a random partition of a large integer . (Vershik’s Russian original is available here; English translation is pay-walled.)

By a partition of , we mean positive integers with . We draw a partition as a collection of boxes: For example, this is :

Suppose we let , select partitions of uniformly at random and rescale the size of the boxes by , so that the diagram of the partition always has area . What is the shape of the most likely diagram?

We want to describe, given a particular shape, how many partitions have roughly that shape. To that end, let , , …, be a sequence of points with and . Let's count partitions which fit inside the box and whose boundary passes through the points .

To describe such a partition, we simply must describe the portion between and , and then describe the portion between and , and so forth; each of these portions is independent. Set and (so ). Set .

So the number of such partitions is

.

From our computations in an earlier post, this is roughly

where . Moreover, if we rescale all of the and by , this approximation becomes better.

So, if we want there to be a lot of partitions, we should make large.

We have now described what happens if we require the boundary of the partition to pass through finitely many fixed points. Suppose instead we insist that the partition lie near a fixed curve? Parametrize that curve as , with the normalization that . I’m not even going to say what I mean precisely, but we can extrapolate from the preceding formula that the number of partitions whose boundary is near is roughly

We thus obtain a problem in the calculus of variations: Consider curves , with the normalizations that and the area enclosed by and the coordinate axes is . Subject to these conditions, maximize . The next several paragraphs are solving this variational problem.

Rotating the coordinates , we see that the condition on the enclosed area is simply that .

As always in problems involving the calculus of variations, the first step is to perturb our proposed solution and see how it changes. Replace by . If was optimal, than should be a maximum, so the first order variation in should vanish.

This is only valid if our perturbation preserves the conditions on . We want the perturbed functions to obey , so we take , and we want to preserve the area, so we take .

For such a perturbation, the first order variation in is supposed to vanish. We compute:

.

Integrating by parts:

.

We want this to hold for any obeying . This will happen if and only if is a constant. So we want for some constants and . So .

The formula , in some sense, solves the variational problem. Our next task is to simplify that formula.

From the previous post, we know that . So , where is another constant of integration.

As , we want . This shows that .

As , we want . This shows that . So we have and .

To evaluate the final constant , we need to use that the area under the curve is . It is convenient to eliminate and relate and directly as , or, . Now, the area under the curve is . We deduce that .

In other words, our final answer is that the curve is .

How good is this approximation? See for yourself! Here is a random partition of , and the approximating curve.

The thing which I think is really cool is that we never needed the explicit formula ; we only needed that it was Legendre dual to . Suppose that we looked at some other sort of local probability distribution on partitions: For example, maybe we would weight the likehood of a partition by or something like that. We could still build a generating function for partitions fitting in a box with this weighting. We could then try to compute . If we succeeded, the exact same logic as before would show that was the shape of a random partition of area chosen from this distribution. Which brings me to the thing I really want to talk about … next time.

Neato.

Curious now; how does one generate a uniform random partition?

Like this :).

Without that: Let be the number of partitions of whose largest part is at most . We can quickly compute a table of values of by the recursion .

We then write a recursive function which builds a random partition of with largest part at most : If , return . Otherwise, choose an integer between and with probability and return , where is the output of .

I had this implemented and it ran pretty much instantly up to or so, when I discovered that Mathematica already had a function to do this.

Can you say anything analogous for choosing a random partition according to Plancherel measure?

Yes! There is also a limit shape, but it is a different one! This is due to Logan and Shepp, and also to Vershik and Kerov, see page 4 of http://www.math.uni-augsburg.de/andrejewski-2013/data/encycl.pdf . I don’t know a similar entropy argument for that case.