A fully polynomial-time approximation scheme for approximating a sum of random variables

Given nn independent integer-valued random variables X1,X2,…,XnX1,X2,…,Xn and an integer CC, we study the fundamental problem of computing the probability that the sum X=X1+X2+⋯+Xn is at most CC. We assume that each random variable XiXi is implicitly given by an oracle OiOi, which given two input integers n1,n2n1,n2 returns the probability of n1≤Xi≤n2n1≤Xi≤n2. We give the first deterministic fully polynomial-time approximation scheme (FPTAS) to estimate the probability up to a relative error of 1±ϵ1±ϵ. Our algorithm is based on the technique for approximately counting knapsack solutions, developed in Gopalan et al. (2011).