"Shape"/"norm" of a uniformly random set partition

Question

Let $\mathcal{A}=\{A_1, A_2, \ldots, A_m\}$ be a uniformly random set partition of $[n]$.

What can we say about $||\mathcal{A}||_2 = \sqrt{\sum_{i=1}^m |A_i|^2}$? It is clearly upper bounded by $n$, but since the ``typical'' size of these $A_i$ is more like $\log(n) - \log\log(n)$, it seems reasonable to expect that $||\mathcal{A}||_2$ is actually more like $O\left(\sqrt{n\log(n)}\right)$, or something like that. What I really need is two things: a) whether $||\mathcal{A}||_2$ concentrates around its expectation, and b) upper bounds on $\mathbb{E}\left[||\mathcal{A}||_2\right]$ better than the trivial $n$ bound.

In my search for papers on this topic, I've found the following result: If $Z_i = |\{j: |A_j| = i\}|$ is the number of parts of size $i$, then the vector $(Z_1, Z_2, \ldots, Z_n)$ is distributed as $Z_i \sim \mathrm{Po}\left(\frac{r^i}{i}\right)$ (where $r=r(n)$ is defined by $re^r = n$), independent other than for conditioning on $\sum_i iZ_i = n$. So my question could equivalently be phrased as asking about $$\mathbb{E}\left[\sqrt{\sum_i i^2 Z_i}\, \middle|\, \sum_i i Z_i = n \right]$$ but it's not clear to me if that is any easier than the original question.

Answer 1

Since $E[\|\mathcal{A}\|_{2}^{2}]$ has no square roots, a good strategy for this problem will be to first compute $E[\|\mathcal{A}\|_{2}^{2}]$ and then deal with $E[\|\mathcal{A}\|_{2}]$ only after we are comfortable with $E[\|\mathcal{A}\|_{2}^{2}]$.

We compute $$E[\|\mathcal{A}\|_{2}^{2}]=B_{n}^{-1}\sum_{P\in\mathbb{P}([n])}\sum_{R\in P}|R|^{2}=B_{n}^{-1}\sum_{R\subseteq[n]}\sum_{P\in\mathbb{P}([n]),R\in P}|R|^{2}$$ $$=B_{n}^{-1}\sum_{R\subseteq[n],R\neq\emptyset}|R|^{2}\cdot B_{n-|R|}=B_{n}^{-1}\cdot\sum_{k=1}^{n}\binom{n}{k}B_{n-k}k^{2}.$$

Here $\mathbb{P}([n])$ denotes the lattice of partitions of $[n]$ while $B_{r}$ denotes the $r$-th Bell number.

We now look up $B_{n}\cdot E[\|\mathcal{A}\|_{2}^{2}]$ from the OEIS, and this is sequence A175716, and we obtain a simpler formula. From the OEIS, we obtain another formula for the expected value of the norm squared $$B_{n}\cdot E[\|\mathcal{A}\|_{2}^{2}]=n\big{[}(n-1)B_{n-1}+B_{n}\big{]}.$$

By Jensen's inequality (or the formula of the variance), we have $E[\|\mathcal{A}\|_{2}]^{2}\leq E[\|\mathcal{A}\|_{2}^{2}],$ so $$E[\|\mathcal{A}\|_{2}]\leq\sqrt{n[1+(n-1)B_{n-1}B_{n}^{-1}]}.$$

For a lower bound of $E[\|\mathcal{A}\|_{2}]$, we have $\|\mathcal{A}\|_{2}\geq\frac{n}{\sqrt{m}}$ where $|\mathcal{A}|=m$. Therefore, by Jensen's inequality, we have $$E(\|\mathcal{A}\|_{2})\geq E(\frac{n}{\sqrt{m}})\geq\frac{n}{\sqrt{E(m)}}.$$

However, we know that $E(m)=(B_{n+1}/B_{n})-1$.

Therefore, $$\frac{n}{\sqrt{(B_{n+1}/B_{n})-1}}\leq E(\|\mathcal{A}\|_{2})\leq\sqrt{n[1+(n-1)B_{n-1}B_{n}^{-1}]}.$$

We therefore conclude that $$\text{Var}(\|\mathcal{A}\|_{2})=E(\|\mathcal{A}\|_{2}^{2})-E(\|\mathcal{A}\|)^{2}\leq n[1+(n-1)B_{n-1}B_{n}^{-1}]-\frac{n^{2}}{(B_{n+1}/B_{n})-1}.$$

We can therefore conclude that $\|\mathcal{A}\|_{2}$ does concentrate around its expected value.