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.

[2] http://arxiv.org/abs/0912.0726

[3] http://arxiv.org/abs/1111.2622 ; published at http://link.springer.com/chapter/10.1007%2F978-3-0348-0490-5_6

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

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.