Random weighting, asymptotic counting, and inverse isoperimetry

DOI10.1007/S11856-007-0008-8zbMATH Open1204.60014arXivmath/0302177OpenAlexW2127007261MaRDI QIDQ995359FDOQ995359

Authors: Alex Samorodnitsky, Alexander Barvinok 

Publication date: 3 September 2007

Published in: Israel Journal of Mathematics (Search for Journal in Brave)

Abstract: For a family X of k-subsets of the set 1,...,n, let |X| be the cardinality of X and let Gamma(X,mu) be the expected maximum weight of a subset from X when the weights of 1,...,n are chosen independently at random from a symmetric probability distribution mu on R. We consider the inverse isoperimetric problem of finding mu for which Gamma(X,mu) gives the best estimate of ln|X|. We prove that the optimal choice of mu is the logistic distribution, in which case Gamma(X,mu) provides an asymptotically tight estimate of ln|X| as k^{-1}ln|X| grows. Since in many important cases Gamma(X,mu) can be easily computed, we obtain computationally efficient approximation algorithms for a variety of counting problems. Given mu, we describe families X of a given cardinality with the minimum value of Gamma(X,mu), thus extending and sharpening various isoperimetric inequalities in the Boolean cube.

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

Recommendations

• scientific article; zbMATH DE number 1067837
• The distance approach to approximate combinatorial counting
• Entropy, optimization and counting
• scientific article; zbMATH DE number 2119675
• A result in order statistics related to probabilistic counting

zbMATH Keywords

weightssymmetric probability distributioncomputationally efficient approximation algorithmsinverse isoperimetric problemisoperimetric inequalities in the Boolean cube

Mathematics Subject Classification ID

Combinatorial probability (60C05) Extremal set theory (05D05)

Cites Work

• Probability and random processes.
• The concentration of measure phenomenon
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• Title not available (Why is that?)
• Concentration of measure and isoperimetric inequalities in product spaces
• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• The asymptotic distribution of the trimmed mean
• The Supremum of Some Canonical Processes
• An asymptotic isoperimetric inequality
• Sudakov minoration principle and supremum of some processes
• Title not available (Why is that?)
• The distance approach to approximate combinatorial counting

Cited In (11)

• Random weighting estimation of confidence intervals for quantiles
• Large deviations for randomly weighted least squares estimator in a nonlinear regression model
• Weak convergence for random weighting estimation of smoothed quantile processes
• A bound for the number of vertices of a polytope with applications
• The distance approach to approximate combinatorial counting
• Log-concave polynomials. I: Entropy and a deterministic approximation algorithm for counting bases of matroids
• Hafnians, perfect matchings and Gaussian matrices
• Log-concave polynomials. II: High-dimensional walks and an FPRAS for counting bases of a matroid
• Asymptotic Properties of Random Weighted Empirical Distribution Function
• Random weighting estimation of kernel density
• Weighted probability density estimator with updated bandwidths

This page was built for publication: Random weighting, asymptotic counting, and inverse isoperimetry

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