Beyond the Central Limit theorem: Asymptotic Expansions and Pseudorandomness for Combinatorial Sums

摘要

We prove a new asymptotic expansion in the central limit theorem for sums of discrete independent random variables. The classical central limit theorem asserts that if {Xi}n i=1 is a sequence of n i.i.d. Random variables, then S = ≥ n i=1 Xi converges to a Gaussian whose first two moments match those of S. Further, the rate of convergence is O(n -- 1/2) Roughly speaking, asymptotic expansions of the central limit theorem show that by considering a family of limiting distributions specified by k ≥ 2 (k=2 corresponds to Gaussians) and matching the first k moments of S to such a limiting distribution, one can achieve a convergence of n -- (k -- 1)/2. While such asymptotic expansions have been known since Cramer, they did not apply to discrete and non-identical random variables. Further, the error bounds in nearly all cases was non-explicit (in their dependence on {Xi}), thus limiting their applicability. In this work, we prove a new asymptotic expansions of the central limit theorem which applies to discrete and non-identical random variables and the error bounds are fully explicit. Given the wide applicability of the central limit theorem in probability theory and theoretical computer science, we believe that this new asymptotic expansion theorem will be applicable in several settings. As a main application in this paper, we give an application in derandomization: Namely, we construct PRGs for the class of combinatorial sums, a class of functions first studied by [GMRZ13] and which generalize many previously studied classes such as combinatorial rectangles, small-biased spaces and modular sums among others. A function f : [m]n → {0, 1} is said to be a combinatorial sum if there exists functions f1,, fn : [m] → {0, 1} such that f(x1,, xn) = f1(x1) ++ fn(xn). For this class, we give a seed length of O(logm + log3/2 (n/ε)), thus improving upon [2] whenever ε ≤ 2 -- )l- gn)3/4.