Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

There is a known phenomenon in integer partition theory that almost all integer partitions, after a normalization ($\pi/\sqrt{6n}$ where $n$ is the norm of the partition), have young diagrams which are approximated by the curve $$e^{-x}+ e^{-y} = 1. $$ This curve is called the limit shape. I was wondering "how large must $n$ be for one to see a close curve fitting?" I ask because I tried observing this by drawing a random parittion of size $n=1000$ and have observed only topologically similarity but the curves did not match precisely.

share|improve this question
    
What are you calling topological similarity? Young diagrams all looks topologically the same to me. –  Benoît Kloeckner Jun 12 '13 at 8:16
    
The curves look similar but don't fit. It is an imprecise term –  Daniel Parry Jun 12 '13 at 15:07

1 Answer 1

up vote 3 down vote accepted

It sounds like you are asking about large deviations.

For partitions, there is a paper by Boris Pittel called "On a Likely Shape of the Random Ferrers Diagram." (1997). This paper contains a proof of the formula in your question, along with big-O estimates about the variability around that curve. I am not aware of any guaranteed error bounds that are not in the Big-O format for this curve.

Unless guaranteed error bounds exist somewhere for a finite $n$, any attempt to look "by eye" at an empirical limit shape and compare it to the theoretical one is in general inconclusive, since the constants implied by the Big-O might be so huge that it crowds out the limiting curve for the particular $n$ chosen.

Also, if you are simulating partitions of $n$ uniformly at random there are only a few methods I am aware of that don't introduce bias into the distribution, which I will list here in case the issue is the random generation method.

  1. The recursive method of Nijenhuis and Wilf (1970s): Generate parts of the partition one at a time from largest to smallest by calculating the conditional distributions in the form of a table. (This one is very fast for small $n$, and storing the table is usually the bottleneck)

  2. The independent counts model from Fristedt (1993) : Generate independent $Z_1, Z_2, \ldots, Z_n$, where $Z_i$ is a geometric random variable with parameter $1-x^i$, $i=1,2,\ldots,n$, for any $x$ between 0 and 1 (a good choice for $x$ is $x = \exp(-\pi/\sqrt{6n})$). Generate these random $n$-tuples until $\sum_{i=1}^n i Z_i = n$, then $Z_i$ is the number of parts of size $i$ in the partition. (This one is my favorite because it requires very little programming effort).

  3. Probabilistic Divide and Conquer from Arratia and DeSalvo (2012) : This one is a bit more involved to implement and probably not necessary unless you need to simulate very large $n$ (if Fristedt's method above is too slow for your purposes then this method is probably worth looking into). It modifies Fristedt's method to make simulations faster, at the expense of calculating some rejection probabilities (we use von Neumann rejection sampling in the algorithm). (This one appeared in my thesis and there is a paper on the ArXiv. This is a link to my papers page which has links to both https://sites.google.com/site/stephendesalvo/home/papers).

EDIT: After perusing another post I now recall the large deviations work of Dembo, Zeitouni, and Vershik, "Large Deviations for integer partitions" (1998). This work should provide a complete answer to the question.

share|improve this answer
    
Thanks. The paper is all I needed. –  Daniel Parry Jul 14 '13 at 16:06

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.