Central moment analysis for cost accumulators in probabilistic programs
Di Wang, Jan Hoffmann, Thomas Reps
Abstract
For probabilistic programs, it is usually not possible to automatically derive exact information about their properties, such as the distribution of states at a given program point. Instead, one can attempt to derive approximations, such as upper bounds on tail probabilities. Such bounds can be obtained via concentration inequalities, which rely on the moments of a distribution, such as the expectation (the first raw moment) or the variance (the second central moment). Tail bounds obtained using central moments are often tighter than the ones obtained using raw moments, but automatically analyzing central moments is more challenging.
Topics & Concepts
Central momentMoment (physics)Probabilistic logicVariance (accounting)Point (geometry)L-momentDistribution (mathematics)Computer scienceMethod of moments (probability theory)Applied mathematicsProbability distributionMathematical optimizationMathematicsStatisticsMathematical analysisMoment-generating functionPhysicsOrder statisticGeometryClassical mechanicsBusinessEstimatorAccountingFormal Methods in VerificationMachine Learning and AlgorithmsAdvanced Bandit Algorithms Research