On the error bound in a combinatorial central limit theorem

摘要

Let X = {X-ij: 1 <= i, j <= n} be an n x n array of independent random variables where n >= 2. Let it be a uniform random permutation of {1, 2,... n}, independent of X, and let W = Sigma(n)(i=1) X-i pi(i). Suppose X is standardized so that EW = 0, Var(W) = 1. We prove that the Kolmogorov distance between the distribution of W and the standard normal distribution is bounded by 451 Sigma(n)(i,j=1) E vertical bar X-ij vertical bar(3). Our approach is by Stein's method of exchangeable pairs and the use of a concentration inequality.