2
$\begingroup$

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.

$\endgroup$
0
2
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Are you sure that OEIS sequence is the right one? It looks like you've got a $k^2$ in your identity and the linked sequence has a $k$. $\endgroup$
    – Marcus M
    Sep 13 at 15:14
  • $\begingroup$ @MarcusM Thanks for spotting that. The correct link should be oeis.org/A175716. These are closely related sequences since A175716(n) = n*A124427(n), so I must have put the wrong sequence in the clipboard. $\endgroup$ Sep 13 at 15:25
  • $\begingroup$ Are you sure about that? You should double check your answer; if you make that edit then you'd end up with $E [|A|^2 ] = \Theta (n^2 )$, which doesn't seem like the right order. $\endgroup$
    – Marcus M
    Sep 14 at 13:05
  • $\begingroup$ I just verified these identities with code that produces the exact same sequence in 3 different ways. Here is the code in GAP. par:=[]; par[1]:=[[[1]]]; for n in [2..10] do par[n]:=[]; for a in par[n-1] do Add(par[n],Concatenation(a,[[n]])); for i in [1..Length(a)] do aa:=StructuralCopy(a); Add(aa[i],n); Add(par[n],aa); od; od; od; mak:=function(xx) return Sum(List(xx,v->Length(v)^2)); end; List(par,v->Sum(List(v,mak))); moo:=function(n) return Sum(List([1..n],k->Binomial(n,k)*Bell(n-k)*k^2)); end; List([1..10],moo); List([1..n],v->v*((v-1)*Bell(v-1)+Bell(v))); $\endgroup$ Sep 14 at 14:23

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.