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.