A Combinatorial Approach to Small Ball Inequalities for Sums and Differences. (6th November 2018)

• Record Type: Journal Article
• Authors: LI, JIANGE; MADIMAN, MOKSHAY
• Is Part Of: Combinatorics, probability and computing. Volume 28:Number 1(2019)
• Page Start: 100
• Page End: 129
• Publication Date: 2018-11-06
• Subjects: Primary 60C05, -- Secondary 05D05, -- 60B15; Combinatorial analysis -- Periodicals; Probabilities -- Periodicals; Computer science -- Mathematics -- Periodicals; 511.6
• DOI: 10.1017/S0963548318000494
• Languages: English
• ISSNs: 0963-5483

Abstract

Abstract : Small ball inequalities have been extensively studied in the setting of Gaussian processes and associated Banach or Hilbert spaces. In this paper, we focus on studying small ball probabilities for sums or differences of independent, identically distributed random elements taking values in very general sets. Depending on the setting – abelian or non-abelian groups, or vector spaces, or Banach spaces – we provide a collection of inequalities relating different small ball probabilities that are sharp in many cases of interest. We prove these distribution-free probabilistic inequalities by showing that underlying them are inequalities of extremal combinatorial nature, related among other things to classical packing problems such as the kissing number problem. Applications are given to moment inequalities.