CONCENTRATION OF MEASURE AND ISOPERIMETRIC INEQUALITIES IN PRODUCT SPACES

CONCENTRATION OF MEASURE AND ISOPERIMETRIC INEQUALITIES IN PRODUCT SPACES

February '94 | MICHEL TALAGRAND
The paper explores the concentration of measure phenomenon in product spaces, where if a set A in a product space has measure at least 1/2, most points are close to A. This is formalized through isoperimetric-type inequalities bounding the measure of exceptional sets. The concept of "close" is defined in three ways, each leading to related inequalities. These inequalities are proven via a common scheme, yielding optimal results and near-optimal constants. Applications include percolation, geometric probability, and probability in Banach spaces. The paper introduces a systematic approach to concentration of measure, using isoperimetric inequalities and a general scheme of proof. It discusses various notions of fattening, including Hamming distance, weighted distances, and other metrics. The results are applied to problems like bin packing, longest increasing subsequences, and percolation. The paper also compares methods, highlighting the power of isoperimetric inequalities over martingale methods in many cases. Key results include bounds on the concentration function and applications to various probabilistic and geometric problems. The paper emphasizes the wide applicability of these abstract tools in concrete situations.The paper explores the concentration of measure phenomenon in product spaces, where if a set A in a product space has measure at least 1/2, most points are close to A. This is formalized through isoperimetric-type inequalities bounding the measure of exceptional sets. The concept of "close" is defined in three ways, each leading to related inequalities. These inequalities are proven via a common scheme, yielding optimal results and near-optimal constants. Applications include percolation, geometric probability, and probability in Banach spaces. The paper introduces a systematic approach to concentration of measure, using isoperimetric inequalities and a general scheme of proof. It discusses various notions of fattening, including Hamming distance, weighted distances, and other metrics. The results are applied to problems like bin packing, longest increasing subsequences, and percolation. The paper also compares methods, highlighting the power of isoperimetric inequalities over martingale methods in many cases. Key results include bounds on the concentration function and applications to various probabilistic and geometric problems. The paper emphasizes the wide applicability of these abstract tools in concrete situations.
Reach us at info@study.space