Skip to main content
corrected typos and link
Source Link

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 A124427A175716, 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[\|A\|_{2}^{2}]=n\big{[}(n-1)B_{n-1}+B_{n}\big{]}.$$$$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.

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 A124427, and we obtain a simpler formula. From the OEIS, we obtain another formula for the expected value squared $$B_{n}\cdot E[\|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.

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.

added 585 characters in body
Source Link

Computing $E[\|\mathcal{A}\|_{2}]$ is rather difficult. It is easier to computeSince $E[\|\mathcal{A}\|_{2}^{2}]$ where there arehas no square roots, so 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 A124427, and we obtain a simpler formula. From the OEIS, we obtain another formula for the expected value squared $$B_{n}\cdot E[\|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}}.$$$$E[\|\mathcal{A}\|_{2}]\leq\sqrt{n[1+(n-1)B_{n-1}B_{n}^{-1}]}.$$

We observe that the expression $B_{n}/B_{n-1}$ is simply the average number of blocks inFor a partitionlower bound of $[n-1]$ selected uniformly at random$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.

Computing $E[\|\mathcal{A}\|_{2}]$ is rather difficult. It is easier to compute $E[\|\mathcal{A}\|_{2}^{2}]$ where there are no square roots, so a good strategy for this problem will be to compute $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 A124427, and we obtain a simpler formula. From the OEIS, we obtain another formula for the expected value squared $$B_{n}\cdot E[\|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}}.$$

We observe that the expression $B_{n}/B_{n-1}$ is simply the average number of blocks in a partition of $[n-1]$ selected uniformly at random.

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 A124427, and we obtain a simpler formula. From the OEIS, we obtain another formula for the expected value squared $$B_{n}\cdot E[\|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.

Source Link

Computing $E[\|\mathcal{A}\|_{2}]$ is rather difficult. It is easier to compute $E[\|\mathcal{A}\|_{2}^{2}]$ where there are no square roots, so a good strategy for this problem will be to compute $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 A124427, and we obtain a simpler formula. From the OEIS, we obtain another formula for the expected value squared $$B_{n}\cdot E[\|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}}.$$

We observe that the expression $B_{n}/B_{n-1}$ is simply the average number of blocks in a partition of $[n-1]$ selected uniformly at random.