A Fully Polynomial-Time Approximation Scheme for Approximating a Sum of Random Variables

Abstract

Given $n$ independent random variables $X_1,X_2,...,X_n$ and an integer $C$, we study the fundamental problem of computing the probability that the sum $X=X_1+X_2+...+X_n$ is at most $C$. We assume that each random variable $X_i$ is implicitly given by an oracle which, given an input value $k$, returns the probability $X_i\le k$. We give the first deterministic fully polynomial-time approximation scheme (FPTAS) to estimate the probability up to a relative error of $1\pm \epsilon$. Our algorithm is based on the idea developed for approximately counting knapsack solutions in [Gopalan et al. FOCS11].

11 pages, new title, proofs polished, several typos revised. Also added a section about the bit complexity

References in corpus (1)

• Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems

Cited by in corpus (5)

• Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
• Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar states
• An FPTAS for the Volume of a $\mathcal{V}$-polytope ---It is Hard to Compute The Volume of The Intersection of Two Cross-polytopes
• An FPTAS for Stochastic Unbounded Min-Knapsack Problem
• The Distribution Function of the Longest Path Length in Constant Treewidth DAGs with Random Edge Length