{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,4]],"date-time":"2026-04-04T01:04:33Z","timestamp":1775264673838,"version":"3.50.1"},"reference-count":74,"publisher":"Cambridge University Press (CUP)","issue":"1","license":[{"start":{"date-parts":[[2018,11,6]],"date-time":"2018-11-06T00:00:00Z","timestamp":1541462400000},"content-version":"unspecified","delay-in-days":0,"URL":"https:\/\/www.cambridge.org\/core\/terms"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Combinator. Probab. Comp."],"published-print":{"date-parts":[[2019,1]]},"abstract":"<jats:p>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 \u2013 abelian or non-abelian groups, or vector spaces, or Banach spaces \u2013 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.<\/jats:p>","DOI":"10.1017\/s0963548318000494","type":"journal-article","created":{"date-parts":[[2018,11,6]],"date-time":"2018-11-06T06:19:33Z","timestamp":1541485173000},"page":"100-129","source":"Crossref","is-referenced-by-count":4,"title":["A Combinatorial Approach to Small Ball Inequalities for Sums and Differences"],"prefix":"10.1017","volume":"28","author":[{"given":"JIANGE","family":"LI","sequence":"first","affiliation":[]},{"given":"MOKSHAY","family":"MADIMAN","sequence":"additional","affiliation":[]}],"member":"56","published-online":{"date-parts":[[2018,11,6]]},"reference":[{"key":"S0963548318000494_ref68","first-page":"106","article-title":"On the increase of dispersion of sums of independent random variables.","volume":"6","author":"Rogozin","year":"1961","journal-title":"Teor. Verojatnost. i Primenen"},{"key":"S0963548318000494_ref65","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-39286-3_16"},{"key":"S0963548318000494_ref74","doi-asserted-by":"publisher","DOI":"10.1007\/BF00533722"},{"key":"S0963548318000494_ref72","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.3.7"},{"key":"S0963548318000494_ref66","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(79)90074-8"},{"key":"S0963548318000494_ref71","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2006.03.008"},{"key":"S0963548318000494_ref60","unstructured":"Madiman M. , Wang L. and Woo J. O. (2017) Discrete entropy power inequalities via Sperner theory. arXiv:1712.00913"},{"key":"S0963548318000494_ref36","doi-asserted-by":"publisher","DOI":"10.1016\/0047-259X(76)90032-4"},{"key":"S0963548318000494_ref28","doi-asserted-by":"crossref","unstructured":"Gao F. (2018) A probabilistic characterization of negative definite functions. Preprint.","DOI":"10.1007\/978-3-030-26391-1_5"},{"key":"S0963548318000494_ref69","doi-asserted-by":"publisher","DOI":"10.1016\/j.aim.2008.01.010"},{"key":"S0963548318000494_ref45","first-page":"159","article-title":"Probabilistic inequalities from extremal graph results (a survey).","volume":"28","author":"Katona","year":"1985","journal-title":"Ann. Discrete Math."},{"key":"S0963548318000494_ref27","doi-asserted-by":"publisher","DOI":"10.1016\/j.crma.2007.10.006"},{"key":"S0963548318000494_ref21","doi-asserted-by":"publisher","DOI":"10.1007\/s10959-014-0538-z"},{"key":"S0963548318000494_ref14","unstructured":"Burchard A. (2009) A short course on rearrangement inequalities. http:\/\/www.math.utoronto.ca\/almut\/rearrange.pdf"},{"key":"S0963548318000494_ref15","doi-asserted-by":"publisher","DOI":"10.1007\/PL00001681"},{"key":"S0963548318000494_ref43","doi-asserted-by":"publisher","DOI":"10.1007\/BF00535724"},{"key":"S0963548318000494_ref54","doi-asserted-by":"crossref","first-page":"73","DOI":"10.1007\/978-3-0348-0490-5_5","article-title":"A probabilistic inequality related to negative definite functions.","volume":"66","author":"Lifshits","year":"2013","journal-title":"Progr. Probab."},{"key":"S0963548318000494_ref73","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2014.2338852"},{"key":"S0963548318000494_ref48","first-page":"27","article-title":"Sur les propri\u00e9t\u00e9s des fonctions de concentrations de M. P. L\u00e9vy.","volume":"16","author":"Kolmogorov","year":"1958","journal-title":"Ann. Inst. H. Poincar\u00e9"},{"key":"S0963548318000494_ref35","doi-asserted-by":"publisher","DOI":"10.1016\/0022-1236(75)90056-7"},{"key":"S0963548318000494_ref22","doi-asserted-by":"publisher","DOI":"10.1137\/S0040585X97986254"},{"key":"S0963548318000494_ref49","first-page":"123","volume-title":"Convex Geometric Analysis","author":"Lata\u0142a","year":"1996"},{"key":"S0963548318000494_ref7","unstructured":"Bobkov S. , Fradelizi M. , Li J. and Madiman M. (2018) When can one invert H\u00f6lder's inequality? (and why one may want to). Preprint."},{"key":"S0963548318000494_ref40","unstructured":"Katona G. O. H. (1978) Continuous versions of some extremal hypergraph problems. In Proceedings of the Colloquium Mathematical Society, Vol. 18 of J\u00e1nos Bolyai Mathematical Studies, pp. 653\u2013678."},{"key":"S0963548318000494_ref51","first-page":"1299","article-title":"Boundaries for packings in n-dimensional Euclidean space.","volume":"245","author":"Leven\u0161te\u012dn","year":"1979","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"S0963548318000494_ref29","first-page":"514","article-title":"Arak's inequalities for concentration functions and the Littlewood\u2013Offord problem.","volume":"467","author":"G\u00f6tze","year":"2016","journal-title":"Dokl. Akad. Nauk"},{"key":"S0963548318000494_ref33","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2005.162.1065"},{"key":"S0963548318000494_ref11","doi-asserted-by":"publisher","DOI":"10.1007\/BF02384761"},{"key":"S0963548318000494_ref64","first-page":"153","article-title":"The problem of the twenty-five spheres.","volume":"58","author":"Musin","year":"2003","journal-title":"Uspekhi Mat. Nauk"},{"key":"S0963548318000494_ref26","volume-title":"High Dimensional Probability VII: The Carg\u00e8se Volume","author":"Fradelizi","year":"2016"},{"key":"S0963548318000494_ref41","doi-asserted-by":"publisher","DOI":"10.1007\/BF01896826"},{"key":"S0963548318000494_ref61","doi-asserted-by":"publisher","DOI":"10.4064\/fm-32-1-115-121"},{"key":"S0963548318000494_ref34","volume-title":"Concentration Functions","author":"Hengartner","year":"1973"},{"key":"S0963548318000494_ref30","doi-asserted-by":"publisher","DOI":"10.1214\/aop\/1176993138"},{"key":"S0963548318000494_ref67","doi-asserted-by":"publisher","DOI":"10.1214\/ss\/1177012394"},{"key":"S0963548318000494_ref57","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4939-7005-6_14"},{"key":"S0963548318000494_ref46","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0075060"},{"key":"S0963548318000494_ref56","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2016.2620470"},{"key":"S0963548318000494_ref38","first-page":"123","article-title":"Graphs, vectors and inequalities in probability theory.","volume":"20","author":"Katona","year":"1969","journal-title":"Mat. Lapok."},{"key":"S0963548318000494_ref20","first-page":"35","article-title":"Sur les sommes d'un grand nombre des variables al\u00e9atoires ind\u00e9pendantes","volume":"63","author":"Doeblin","year":"1939","journal-title":"Bull. Sci. Math."},{"key":"S0963548318000494_ref50","doi-asserted-by":"publisher","DOI":"10.2307\/3610264"},{"key":"S0963548318000494_ref62","doi-asserted-by":"publisher","DOI":"10.1090\/S0002-9947-97-01966-1"},{"key":"S0963548318000494_ref9","doi-asserted-by":"publisher","DOI":"10.1109\/TIT.2011.2158475"},{"key":"S0963548318000494_ref18","doi-asserted-by":"publisher","DOI":"10.1023\/A:1017501308452"},{"key":"S0963548318000494_ref4","doi-asserted-by":"publisher","DOI":"10.1080\/00029890.1951.11999682"},{"key":"S0963548318000494_ref1","doi-asserted-by":"publisher","DOI":"10.3390\/e19090235"},{"key":"S0963548318000494_ref6","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4612-1128-0"},{"key":"S0963548318000494_ref31","doi-asserted-by":"publisher","DOI":"10.1112\/S002557930000766X"},{"key":"S0963548318000494_ref16","doi-asserted-by":"publisher","DOI":"10.4007\/annals.2017.185.3.8"},{"key":"S0963548318000494_ref2","doi-asserted-by":"publisher","DOI":"10.1016\/0097-3165(95)90071-3"},{"key":"S0963548318000494_ref63","first-page":"178","article-title":"Inequalities for concentration functions.","volume":"25","author":"Miro\u0161nikov","year":"1980","journal-title":"Teor. Veroyatnost. i Primenen"},{"key":"S0963548318000494_ref37","first-page":"1293","article-title":"Combinatorial numbers, geometric constants and probabilistic inequalities.","volume":"251","author":"Katona","year":"1980","journal-title":"Dokl. Akad. Nauk SSSR"},{"key":"S0963548318000494_ref32","doi-asserted-by":"publisher","DOI":"10.1007\/s00039-011-0136-5"},{"key":"S0963548318000494_ref10","doi-asserted-by":"publisher","DOI":"10.1016\/j.jfa.2012.01.011"},{"key":"S0963548318000494_ref70","doi-asserted-by":"publisher","DOI":"10.1070\/IM1983v020n03ABEH001617"},{"key":"S0963548318000494_ref58","unstructured":"Madiman M. , Melbourne J. and Xu P. (2017) Rogozin's convolution inequality for locally compact groups. arXiv:1705.00642"},{"key":"S0963548318000494_ref39","first-page":"466","article-title":"Inequalities for the distribution of the length of a sum of random vectors.","volume":"22","author":"Katona","year":"1977","journal-title":"Teor. Verojatnost. i Primenen"},{"key":"S0963548318000494_ref12","doi-asserted-by":"publisher","DOI":"10.1214\/aos\/1176325376"},{"key":"S0963548318000494_ref52","volume-title":"Th\u00e9orie de l'Addition des Variables Al\u00e9atoires","author":"L\u00e9vy","year":"1937"},{"key":"S0963548318000494_ref42","doi-asserted-by":"publisher","DOI":"10.1016\/S0195-6698(81)80006-6"},{"key":"S0963548318000494_ref59","unstructured":"Madiman M. , Wang L. and Woo J. O. (2017) Entropy inequalities for sums in prime cyclic groups. arXiv:1710.00812"},{"key":"S0963548318000494_ref3","doi-asserted-by":"crossref","DOI":"10.1093\/oso\/9780198502456.001.0001","volume-title":"Functions of Bounded Variation and Free Discontinuity Problems","author":"Ambrosio","year":"2000"},{"key":"S0963548318000494_ref55","doi-asserted-by":"crossref","unstructured":"Madiman M. and Kontoyiannis I. (2010) The entropies of the sum and the difference of two IID random variables are not too different. In 2010 IEEE International Symposium on Information Theory, IEEE.","DOI":"10.1109\/ISIT.2010.5513562"},{"key":"S0963548318000494_ref5","first-page":"15","volume-title":"Positive Definite Functions: From Schoenberg to Space-Time Challenges","author":"Berg","year":"2008"},{"key":"S0963548318000494_ref8","doi-asserted-by":"publisher","DOI":"10.1214\/10-AOP592"},{"key":"S0963548318000494_ref47","doi-asserted-by":"publisher","DOI":"10.7146\/math.scand.a-10950"},{"key":"S0963548318000494_ref23","doi-asserted-by":"publisher","DOI":"10.1007\/BF00533057"},{"key":"S0963548318000494_ref25","unstructured":"Fradelizi M. , Li J. and Madiman M. (2015) Concentration of information content for convex measures. arXiv:1512.01490"},{"key":"S0963548318000494_ref24","doi-asserted-by":"publisher","DOI":"10.1007\/BF00531753"},{"key":"S0963548318000494_ref19","doi-asserted-by":"publisher","DOI":"10.1007\/s11139-005-0835-3"},{"key":"S0963548318000494_ref13","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-07441-1"},{"key":"S0963548318000494_ref53","doi-asserted-by":"crossref","DOI":"10.1090\/gsm\/014","volume-title":"Analysis","author":"Lieb","year":"2001"},{"key":"S0963548318000494_ref44","first-page":"377","volume-title":"Combinatorial Mathematics","author":"Katona","year":"1983"},{"key":"S0963548318000494_ref17","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4757-6568-7"}],"container-title":["Combinatorics, Probability and Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.cambridge.org\/core\/services\/aop-cambridge-core\/content\/view\/S0963548318000494","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,4,3]],"date-time":"2026-04-03T23:58:51Z","timestamp":1775260731000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.cambridge.org\/core\/product\/identifier\/S0963548318000494\/type\/journal_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2018,11,6]]},"references-count":74,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2019,1]]}},"alternative-id":["S0963548318000494"],"URL":"https:\/\/doi.org\/10.1017\/s0963548318000494","relation":{},"ISSN":["0963-5483","1469-2163"],"issn-type":[{"value":"0963-5483","type":"print"},{"value":"1469-2163","type":"electronic"}],"subject":[],"published":{"date-parts":[[2018,11,6]]}}}