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

DOI10.1016/J.ORL.2014.02.004zbMATH Open1408.90259arXiv1303.6071OpenAlexW1965740534MaRDI QIDQ1785211FDOQ1785211

Authors: Jian Li, Tianlin Shi 

Publication date: 28 September 2018

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

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].

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

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

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)

Cites Work

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

Cited In (10)

• An FPTAS for Computing the Distribution Function of the Longest Path Length in DAGs with Uniformly Distributed Edge Lengths
• Approximation algorithms 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
• Toward Breaking the Curse of Dimensionality: An FPTAS for Stochastic Dynamic Programs with Multidimensional Actions and Scalar States
• Sublinear time approximate sum via uniform random sampling
• 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
• Computation of Exact Bootstrap Confidence Intervals: Complexity and Deterministic Algorithms
• Maximizing expected utility 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)