On the error bound in a combinatorial central limit theorem

Abstract

Let $\mathbb{X}=\{X_{ij}:1\le i,j\le n\}$ be an $n\times n$ array of independent random variables where $n\ge 2$. Let $\pi$ be a uniform random permutation of $\{1,2,\dots ,n\}$, independent of $\mathbb{X}$, and let $W={\sum }_{i=1}^n{X}_{i\pi (i)}$. Suppose $\mathbb{X}$ is standardized so that $\mathbb{E}W=0,\mathrm{Var}(W)=1$. We prove that the Kolmogorov distance between the distribution of $W$ and the standard normal distribution is bounded by $451{\sum }_{i,j=1}^n\mathbb{E}|X_{ij}{|}^3/n$. Our approach is by Stein's method of exchangeable pairs and the use of a concentration inequality.

Published at http://dx.doi.org/10.3150/13-BEJ569 in the Bernoulli (http://isi.cbs.nl/bernoulli/) by the International Statistical Institute/Bernoulli Society (http://isi.cbs.nl/BS/bshome.htm)

References in corpus (4)

• Normal approximation under local dependence
• Berry Esseen bounds for combinatorial central limit theorems and pattern occurrences, using zero and size biasing
• $L^1$ bounds in normal approximation
• On randomness reduction in the Johnson-Lindenstrauss lemma

Cited by in corpus (1)

• Functional approximations with Stein's method of exchangeable pairs