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.$


1 Answer 1


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
    Commented Nov 9, 2015 at 3:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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