8
$\begingroup$

Let $n$ be a positive integer. If we take the set of all partitions of $n$ and choose a random partition from it (uniformly), then the expected value of the number of parts of this partition is a known result. The highest order term of the expected value is $\sqrt{n}\operatorname{Log}(n)$ (Kessler & Livingston, 1976).

Instead of the set of all partitions of $n$, I only want to consider $k \%$ of the total spectrum of partitions. Let $P^k(n)$ denote the set which contains $k \%$ of the total partitions of $n$. The partitions in $P^k(n)$ are chosen as follows. We begin with the empty set and add partitions one by one. At every step we choose to add a partition that has the smallest number of parts. We stop adding partitions once the set $P^k(n)$ contains the required $k \%$ of the total number of partitions.

I am interested in the partition in $P^k(n)$ that has the highest number of parts, call this $max\left(P^k(n)\right)$. Numerical experiment has shown that for large $n$, $\operatorname{max}\left(P^k(n)\right) \approx k \sqrt{n}\operatorname{Log}(nk)$. So for fixed $k$ and increasing $n$ we get $\operatorname{max}\left(P^k(n)\right) = \mathcal{O}(\sqrt{n}\operatorname{Log}(n))$.

Is there a way to apply Kessler and Livingston's result to the set $P^k(n)$, so that we get the expected value for the number of parts of partitions in that set? This would be incredibly helpful as it would be a lower bound for $\operatorname{max}\left(P^k(n)\right)$.

$\endgroup$
  • 1
    $\begingroup$ You can get the proper font and spacing for $\max$ and $\log$ using \max and \log. For operators that don't have a command of their own, you can use \operatorname{name}. $\endgroup$ – joriki Apr 24 at 2:12
  • $\begingroup$ Apparently you mean the 1976 paper "The Expected Number of Parts of a Partition of $n$"? This is available online here. $\endgroup$ – joriki Apr 24 at 2:19
  • 1
    $\begingroup$ Excuse me if this is a silly question -- I am new to this. :) Let $X =$ the number of parts in a random partition. Then 1976 result is about the mean $E[X]$, while you're asking about the $k$-th percentile for a fixed $k$, am I right? The 1976 paper (which I only vaguely understand) seems to use a standard technique of differentiating a generating function to find the mean. Is there a similar technique for percentile statistics? Nothing comes to my mind but I'm a newbie at generating functions. $\endgroup$ – antkam Apr 28 at 17:45
  • 1
    $\begingroup$ [cont'd] Alternatively, are there known theories about families of distributions (indexed by $n$ here) s.t. the growth (w.r.t. $n$) of the mean is similar to the growth of the $k$th percentile? E.g. consider the family $Binomial(n,p)$ - because of CLT, the leading terms are both linear. $\endgroup$ – antkam Apr 28 at 17:51
  • 1
    $\begingroup$ If the bounty expires without a good answer, let me suggest posting the question to mathoverflow.net $\endgroup$ – Gerry Myerson May 5 at 3:46
4
+50
$\begingroup$

It is known that the number of partitions of $n$ with largest part $k$ is the same as the number of partitions into $k$ parts (see e.g. here). Thus we can translate your question into asking about the size of the largest part of a (uniform) random partition. The asymptotic distribution of the largest part is given by the Erdős Lehner theorem ([1]) which states that ([2], equation 2.2)

$\begin{equation} \lim_{n\rightarrow\infty}P_n(\lambda \in \mathcal{P}_n : \frac{c}{\sqrt{n}}\lambda_1 − \log \frac{\sqrt{n}}{c}\leq x) = e^{−e^{−x}} \end{equation}$, where $c=\frac{\pi}{\sqrt{6}}$.

Here $\mathcal{P}_n$ is the set of partitions of $n$, $P_n$ the uniform measure on $\mathcal{P}_n$, elements (partitions) of $\mathcal{P}_n$ are denoted by $\lambda$ ,and $\lambda_1$ denotes the largest part of $\lambda$. As an aside, this limiting distribution is known as the Gumbel distribution.

In particular, if we let $\lambda_1^{(k)}$ denote the largest part of the $k$th percentile partition (ordered in increasing order of largest part), set $e^{-e^{-x}} = k$, solve for $x$ and then for $\lambda_1$ using $\frac{c}{\sqrt{n}}\lambda_1 − \log \frac{\sqrt{n}}{c} = x$, we get $x = \log (\frac{1}{\log (1/k)})$ and $\lambda_1^{(k)} = \frac{\sqrt{n}}{c}\log (\frac{\sqrt{n}}{c\log (1/k)})$.

References:

  1. P. Erdős, J. Lehner: The distribution of the number of summands in the partition of a positive integer. Duke Math. J. Vol. 8 (1941)

  2. Zhonggen Su: Asymptotic analysis of random partitions

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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