9
$\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$
9
  • 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$ Commented Apr 24, 2020 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$ Commented Apr 24, 2020 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$ Commented Apr 28, 2020 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$ Commented Apr 28, 2020 at 17:51
  • 1
    $\begingroup$ If the bounty expires without a good answer, let me suggest posting the question to mathoverflow.net $\endgroup$ Commented May 5, 2020 at 3:46

1 Answer 1

Reset to default
6
+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

$\endgroup$
1
  • $\begingroup$ One could view the partition of n as a probability mass function in the plane by making each box have mass 1/n, and then maybe the question is asking, for that x-value where k% of the mass is $\leq x$ what is the expectation of $x$? $\endgroup$ Commented Sep 9 at 21:43

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.