Random weighting, asymptotic counting, and inverse isoperimetry

DOI10.1007/S11856-007-0008-8MaRDI QIDQ995359zbMATH OpenOpenAlexFDO

Authors Alex Samorodnitsky, Alexander Barvinok

Publication date 3 September 2007

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

Full work available at URL https://arxiv.org/abs/math/0302177, http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.239.8504

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)

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.

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

Cites work

• scientific article; zbMATH DE number 18980 (Why is no real title available?)
• scientific article; zbMATH DE number 1219584 (Why is no real title available?)
• scientific article; zbMATH DE number 1250549 (Why is no real title available?)
• scientific article; zbMATH DE number 1067837 (Why is no real title available?)
• scientific article; zbMATH DE number 2149438 (Why is no real title available?)
• A polynomial-time approximation algorithm for the permanent of a matrix with nonnegative entries.
• An asymptotic isoperimetric inequality
• Concentration of measure and isoperimetric inequalities in product spaces
• Probability and random processes.
• Sudakov minoration principle and supremum of some processes
• The Supremum of Some Canonical Processes
• The asymptotic distribution of the trimmed mean
• The concentration of measure phenomenon
• The distance approach to approximate combinatorial counting

Cited in

(11)

• Weighted probability density estimator with updated bandwidths
• 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
• Asymptotic properties of random weighted empirical distribution function
• 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
• Random weighting estimation of kernel density

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)