# Uniform convergence of 2-norm of a multinomial vector

Let $(X_1,X_2,\ldots,X_k)$ be distributed according to a multinomial distribution with parameters $(n;p_1,p_2,\ldots, p_k),$ i.e.

$$P(X_1=n_1,\ldots,X_k=n_k) = {n\choose n_1,n_2,\ldots,n_k} p_1^{n_1}\ldots p_k^{n_k}~,$$

for $n_i\geq 0, \sum_{i=1}^k n_i = n.$

The multivariate central limit theorem tells us that

$$\frac{1}{\sqrt{n}}(X_1-np_1,\ldots,X_k-np_k)\stackrel{d}{\to} (Z_1,\ldots Z_k)\sim \mathcal{N}(0,\Sigma),$$

where $\Sigma_{ij} = \begin{cases} p_i(1-p_i) & i=j \\ -p_ip_j & i\neq j\end{cases}.$

Uniform integrability tells us that

$$\frac{1}{\sqrt{n}}\mathbb{E}\left[\left(\sum_{i=1}^k (X_i-np_i)^2\right)^{\frac 12}\right]\to \mathbb{E}\left[\left(\sum_{i=1}^k Z_i^2\right)^{\frac 12}\right]~.$$

I am interested in showing uniform convergence above, i.e. I want an upper bound $f(n,k)$ on the difference

$$\left|\frac{1}{\sqrt{n}}\mathbb{E}\left[\left(\sum_{i=1}^k (X_i-np_i)^2\right)^{\frac 12}\right]-\mathbb{E}\left[\left(\sum_{i=1}^k Z_i^2\right)^{\frac 12}\right]\right|$$

that depends only on $n$ and $k$ but not on $(p_1,\ldots,p_k)$ such that $f(n,k)\to 0$ as $n\to\infty$ for every fixed $k.$

Let $(e_1,\dots,e_k)$ denote the standard basis in $\mathbb{R}^k$. Then $$\frac1{\sqrt n}\,(X_1-np_1,\dots,X_k-np_k)\overset{D}=\frac1{\sqrt n}\,\sum_{j=1}^nV_j=:V,$$ where $\overset{D}=$ stands for the equality in distribution, $V_j:=U_j-\mathbb{E}U_j$, and the $U_j$'s are iid random vectors in $\mathbb{R}^k$ such that $\mathbb{P}(U_j=e_\ell)=p_\ell$ for $\ell=1,\dots,k$. Let $W\sim N(0,\Sigma)$, where $\Sigma$ is the covariance matrix of $V_1$.

We shall show more than requested: $$(0)\qquad\big|\,\mathbb{E}\|V\|-\mathbb{E}\|W\|\,\big|<0.99 n^{-1/6};$$ the latter bound is uniform, not only in the $p_\ell$'s, but also in $k$.

By Corollary 2.1 and formula (1.10) in [1], $$(1)\qquad\big|\,\mathbb{E}\|V\|-\mathbb{E}\|W\|\,\big| \le\sqrt{\frac2\pi}\,\int_{\mathbb{R}^k}\gamma_k(du) \int_0^\infty\frac{dt}{t^2}|\mathbb{E}e^{itu\cdot V}-\mathbb{E}e^{itu\cdot W}|,$$ where $\gamma_k$ is the standard Gaussian measure on $\mathbb{R}^k$.

Using inequality (13) in [2] and writing $\int_0^{|b|}\frac{a^2}2\,\exp\big(\frac{a^2}2\big)\,da \le e^{b^2/2}\frac{|b|^3}6$ for real $b$, for all $u\in\mathbb{R}^k$ and $t\in\mathbb{R}$ we have $$(2)\qquad|\mathbb{E}e^{itu\cdot V}-\mathbb{E}e^{itu\cdot W}| \le c|t|^3\delta_n(u),\quad\text{where}\quad\delta_n(u):=\frac{\mathbb{E}|u\cdot V_1|^3}{\sqrt n}$$ and $c:=1/(6\sqrt{2\pi})$. Let $A:=\big(2/(c\delta_n(u))\big)^{1/3}$. Using (2) for $t\in(0,A)$ and the trivial inequality $|\mathbb{E}e^{itu\cdot V}-\mathbb{E}e^{itu\cdot W}|\le2$ for $t\ge A$, for the integral $\int_0^\infty$ in (1) one has $$\int_0^\infty\le\int_0^A t\,dt\,c\delta_n(u) +2\int_A^\infty\frac{dt}{t^2} =3\times2^{-1/3}(c\delta_n(u))^{1/3}.$$ So, by (1), with $c_1:=\sqrt{\frac2\pi}\,\times3\times2^{-1/3}c^{1/3}$, $$(3)\qquad\big|\,\mathbb{E}\|V\|-\mathbb{E}\|W\|\,\big| \le c_1 \int_{\mathbb{R}^k}\gamma_k(du)\delta_n(u)^{1/3} \le c_1 \Big(\int_{\mathbb{R}^k}\gamma_k(du)\delta_n(u)\Big)^{1/3}.$$ Next, by part (vi) of Theorem 2.3 of [3], $\mathbb{E}|u\cdot V_1|^3\le1.32\mathbb{E}|u\cdot U_1|^3 =1.32\sum_{\ell=1}^k p_\ell|u_\ell|^3$, where $u=(u_1,\dots,u_k)\in\mathbb{R}^k$. So, $$\sqrt n\,\int_{\mathbb{R}^k}\gamma_k(du)\delta_n(u) =\int_{\mathbb{R}^k}\gamma_k(du)\mathbb{E}|u\cdot V_1|^3 \le1.32\int_{\mathbb{R}^k}\gamma_k(du)\mathbb{E}|u\cdot U_1|^3$$ $$=1.32\sum_{\ell=1}^k p_\ell\int_{\mathbb{R}^k}\gamma_k(du)|u_\ell|^3 =1.32\sum_{\ell=1}^k p_\ell\int_{\mathbb{R}}\gamma_1(du_1)|u_1|^3 =1.32\times2\sqrt{\frac2\pi}.$$ Now (0) follows from (3).

Similarly one can obtain bounds on the rate of convergence for $\mathbb{E}\|V\|^p$ for $p$ other than $1$.

[1] http://arxiv.org/abs/1506.00537 ; a version of this is to appear In The American Mathematical Monthly.

• Thanks Iosif for taking the effort to write such a beautiful answer. – Hedonist Nov 9 '15 at 3:30