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

DOI10.1016/J.ORL.2014.02.004MaRDI QIDQ1785211zbMATH OpenOpenAlexFDO

Authors Jian Li, Tianlin Shi

Publication date 28 September 2018

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1303.6071

zbMATH Keywords

tail probabilityFPTASapproximate countingthreshold probabilitycounting knapsack

Mathematics Subject Classification ID

Probability distributions: general theory (60E05) Approximations to statistical distributions (nonasymptotic) (62E17) Combinatorial optimization (90C27) Dynamic programming (90C39) Approximation algorithms (68W25)

Abstract: Given $n$ independent random variables $X_1,X_2,\mathrm{...},X_n$ and an integer $C$, we study the fundamental problem of computing the probability that the sum $X=X_1+X_2+\mathrm{...}+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}leqk$. We give the first deterministic fully polynomial-time approximation scheme (FPTAS) to estimate the probability up to a relative error of $1pmepsilon$. Our algorithm is based on the idea developed for approximately counting knapsack solutions in [Gopalan et al. FOCS11].

Recommendations

• Sublinear time approximate sum via uniform random sampling
• Direct calculation of probabilities of sums of independet lattice random variables
• Algorithms for computing the distributions of sums of discrete random variables
• A numerical method for computing the probability distribution of a finite sum of independent nonnegative random variables
• Computing best-possible bounds for the distribution of a sum of several variables is NP-hard

Cites work

• scientific article; zbMATH DE number 1559582 (Why is no real title available?)
• A PTAS for the chance-constrained knapsack problem with random item sizes
• A deterministic polynomial-time approximation scheme for counting knapsack solutions
• An FPTAS for #Knapsack and Related Counting Problems
• Approximate counting by dynamic programming
• Approximation algorithms for reliable stochastic combinatorial optimization
• Improved approximation results for stochastic knapsack problems
• Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems
• On stochastic spanning tree problem
• On the Probabilities of Large Deviations for Sums of Independent Random Variables
• Probability Inequalities for the Sum of Independent Random Variables
• Probability and Computing
• Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions
• Saddle point approximation for the distribution of the sum of independent random variables
• Stochastic Shortest Paths Via Quasi-convex Maximization
• Stochastic combinatorial optimization via Poisson approximation
• Tail Probability Approximations

Cited in

(10)

• Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
• Efficient optimal Kolmogorov approximation of random variables
• An FPTAS for the volume of some \(\mathcal{V} \)-polytopes -- it is hard to compute the volume of the intersection of two cross-polytopes
• Maximizing expected utility for stochastic combinatorial optimization problems
• Approximation complexity of sums of random processes
• An FPTAS for the volume computation of 0-1 knapsack polytopes based on approximate convolution
• An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
• Sublinear time approximate sum via uniform random sampling
• Toward breaking the curse of dimensionality: an FPTAS for stochastic dynamic programs with multidimensional actions and scalar states
• Approximation algorithms for stochastic combinatorial optimization problems

This page was built for publication: A fully polynomial-time approximation scheme for approximating a sum of random variables

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1785211)