Hostname: page-component-78c5997874-ndw9j Total loading time: 0 Render date: 2024-11-17T08:19:50.378Z Has data issue: false hasContentIssue false
  • English
  • Français

A Combinatorial Approach to Small Ball Inequalities for Sums and Differences

Part of: Extremal combinatorics Probability theory on algebraic and topological structures Combinatorial probability

Published online by Cambridge University Press:  06 November 2018

JIANGE LI  and
MOKSHAY MADIMAN
JIANGE LI
Affiliation:
Department of Mathematical Sciences, University of Delaware, Newark, DE 19716, USA (e-mail: [email protected], [email protected])
MOKSHAY MADIMAN
Affiliation:
Department of Mathematical Sciences, University of Delaware, Newark, DE 19716, USA (e-mail: [email protected], [email protected])
Get access Rights & Permissions [Opens in a new window]

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.

MSC classification

Primary: 60C05: Combinatorial probability
Secondary: 05D05: Extremal set theory 60B15: Probability measures on groups or semigroups, Fourier transforms, factorization
Type
Paper
Information
Combinatorics, Probability and Computing , Volume 28 , Issue 1 , January 2019 , pp. 100 - 129
Copyright
Copyright © Cambridge University Press 2018 

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)

Footnotes

†

This work was supported in part by the US National Science Foundation through grants CCF-1346564 and DMS-1409504 (CAREER)

References

[1] Abbe, E., Li, J. and Madiman, M. (2017) Entropies of weighted sums in cyclic groups and an application to polar codes. Entropy 19 235.Google Scholar
[2] Alon, N. and Yuster, R. (1995) The 123 theorem and its extensions. J. Combin. Theory Ser. A 72 322–331.Google Scholar
[3] Ambrosio, L., Fusco, N. and Pallara, D. (2000) Functions of Bounded Variation and Free Discontinuity Problems, Clarendon Press.Google Scholar
[4] Bateman, P. and Erdős, P. (1951) Geometrical extrema suggested by a lemma of Besicovitch. Amer. Math. Monthly 58 306–314.Google Scholar
[5] Berg, C. (2008) Stieltjes–Pick–Bernstein–Schoenberg and their connection to complete monotonicity. In Positive Definite Functions: From Schoenberg to Space-Time Challenges (Mateu, J. and Porcu, E., eds), University Jaume I, pp. 15–45.Google Scholar
[6] Berg, C., Christensen, J. P. R. and Ressel, P. (1984) Harmonic Analysis on Semigroups: Theory of Positive Definite and Related Functions, Springer.Google Scholar
[7] Bobkov, S., Fradelizi, M., Li, J. and Madiman, M. (2018) When can one invert Hölder's inequality? (and why one may want to). Preprint.Google Scholar
[8] Bobkov, S. and Madiman, M. (2011) Concentration of the information in data with log-concave distributions. Ann. Probab. 39 1528–1543.Google Scholar
[9] Bobkov, S. and Madiman, M. (2011) The entropy per coordinate of a random vector is highly constrained under convexity conditions. IEEE Trans. Inform. Theory 57 4940–4954.Google Scholar
[10] Bobkov, S. and Madiman, M. (2012) Reverse Brunn–Minkowski and reverse entropy power inequalities for convex measures. J. Funct. Anal. 262 3309–3339.Google Scholar
[11] Borell, C. (1974) Convex measures on locally convex spaces. Ark. Mat. 12 239–252.Google Scholar
[12] Buja, A., Logan, B. F., Reeds, J. A. and Shepp, L. A. (1994) Inequalities and positive-definite functions arising from a problem in multidimensional scaling. Ann. Statist. 22 406–438.Google Scholar
[13] Burago, Y. D. and Zalgaller, V. A. (1988) Geometric Inequalities, Vol. 285 of Grundlehren der Mathematischen Wissenschaften, Springer.Google Scholar
[14] Burchard, A. (2009) A short course on rearrangement inequalities. http://www.math.utoronto.ca/almut/rearrange.pdfGoogle Scholar
[15] Burchard, A. and Schmuckenschläger, M. (2001) Comparison theorems for exit times. Geom. Funct. Anal. 11 651–692.Google Scholar
[16] Cohn, H., Kumar, A., Miller, S., Radchenko, D. and Viazovska, M. S. (2017) The sphere packing problem in dimension 24. Ann. Math. 185 1017–1033.Google Scholar
[17] Conway, J. H. and Sloane, N. J. A. (1999) Sphere Packings, Lattices and Groups, Vol. 290 of Grundlehren der Mathematischen Wissenschaften, Springer.Google Scholar
[18] Deshouillers, J.-M., Freiman, G. A. and Yudin, A. A. (2001) On bounds for the concentration function II. J. Theoret. Probab. 14 813–820.Google Scholar
[19] Deshouillers, J.-M. and Sutanto, . (2005) On the rate of decay of the concentration function of the sum of independent random variables. Ramanujan J. 9 241–250.Google Scholar
[20] Doeblin, W. (1939) Sur les sommes d'un grand nombre des variables aléatoires indépendantes. Bull. Sci. Math. 63 23–32, 35–64.Google Scholar
[21] Dong, D., Li, J. and Li, W. V. (2015) A note on distribution-free symmetrization inequalities. J. Theoret. Probab. 28 958–967.Google Scholar
[22] Eliseeva, Y. S. and Zaitsev, A. Y. (2013) Estimates of the concentration functions of weighted sums of independent random variables. Theory Probab. Appl. 57 670–678.Google Scholar
[23] Esseen, C. G. (1966) On the Kolmogorov–Rogozin inequality for the concentration function. Z. Wahrsch. Verw. Gebiete. 5 210–216.Google Scholar
[24] Esseen, C. G. (1968) On the concentration function of a sum of independent random variables. Z. Wahrsch. Verw. Gebiete. 9 290–308.Google Scholar
[25] Fradelizi, M., Li, J. and Madiman, M. (2015) Concentration of information content for convex measures. arXiv:1512.01490Google Scholar
[26] Fradelizi, M., Madiman, M. and Wang, L. (2016) Optimal concentration of information content for log-concave densities. In High Dimensional Probability VII: The Cargèse Volume (Houdré, C., Mason, D., Reynaud-Bouret, P. and Rosinski, J., eds), Progress in Probability, Birkhäuser.Google Scholar
[27] Friedland, O. and Sodin, S. (2007) Bounds on the concentration function in terms of the Diophantine approximation. CR Math. Acad. Sci. Paris 345 513–518.Google Scholar
[28] Gao, F. (2018) A probabilistic characterization of negative definite functions. Preprint.Google Scholar
[29] Götze, F., Eliseeva, Y. S. and Zaitsev, A. Y. (2016) Arak's inequalities for concentration functions and the Littlewood–Offord problem. Dokl. Akad. Nauk 467 514–518.Google Scholar
[30] Giné, E. and Zinn, J. (1984) Some limit theorems for empirical processes. Ann. Probab. 12 929–998.Google Scholar
[31] Guédon, O. (1999) Kahane–Khinchine type inequalities for negative exponent. Mathematika 46 165–173.Google Scholar
[32] Guédon, O. and Milman, E. (2011) Interpolating thin-shell and sharp large-deviation estimates for isotropic log-concave measures. Geom. Funct. Anal. 21 1043–1068.Google Scholar
[33] Hales, T. C. (2005) A proof of the Kepler conjecture. Ann. Math. 162 1065–1185.Google Scholar
[34] Hengartner, W. and Theodorescu, R. (1973) Concentration Functions, Academic Press.Google Scholar
[35] Jain, N. C. and Marcus, M. B. (1975) Central limit theorems for C(S)-valued random variables. J. Funct. Anal. 19 216–231.Google Scholar
[36] Kanter, M. (1976) Probability inequalities for convex sets and multidimensional concentration functions. J. Multivariate Anal. 6 222–236.Google Scholar
[37] Katona, D. and Stečkin, B. S. (1980) Combinatorial numbers, geometric constants and probabilistic inequalities. Dokl. Akad. Nauk SSSR 251 1293–1296.Google Scholar
[38] Katona, G. O. H. (1969) Graphs, vectors and inequalities in probability theory. Mat. Lapok. 20 123–127.Google Scholar
[39] Katona, G. O. H. (1977) Inequalities for the distribution of the length of a sum of random vectors. Teor. Verojatnost. i Primenen 22 466–481.Google Scholar
[40] Katona, G. O. H. (1978) Continuous versions of some extremal hypergraph problems. In Proceedings of the Colloquium Mathematical Society, Vol. 18 of János Bolyai Mathematical Studies, pp. 653–678.Google Scholar
[41] Katona, G. O. H. (1980) Continuous versions of some extremal hypergraph problems II. Acta Math. Acad. Sci. Hungar. 35 67–77.Google Scholar
[42] Katona, G. O. H. (1981) Sums of vectors and Turán's problem for 3-graphs. European J. Combin. 2 145–154.Google Scholar
[43] Katona, G. O. H. (1982) ‘Best’ estimations on the distribution of the length of sums of two random vectors. Z. Wahrsch. Verw. Gebiete 60 411–423.Google Scholar
[44] Katona, G. O. H. (1983) Sums of vectors and Turán's graph problem. In Combinatorial Mathematics, Vol. 75 of North-Holland Mathematics Studies, North-Holland, pp. 377–382.Google Scholar
[45] Katona, G. O. H. (1985) Probabilistic inequalities from extremal graph results (a survey). Ann. Discrete Math. 28 159–170.Google Scholar
[46] Kawohl, B. (1985) Rearrangements and Convexity of Level Sets in PDE, Vol. 1150 of Lecture Notes in Mathematics, Springer.Google Scholar
[47] Kesten, H. (1969) A sharper form of the Doeblin–Lévy–Kolmogorov–Rogozin inequality for concentration functions. Math. Scand. 25 133–144.Google Scholar
[48] Kolmogorov, A. (1958) Sur les propriétés des fonctions de concentrations de M. P. Lévy. Ann. Inst. H. Poincaré 16 27–34.Google Scholar
[49] Latała, R. (1996) On the equivalence between geometric and arithmetic means for log-concave measures. In Convex Geometric Analysis, Vol. 34 of Mathematical Sciences Research Institute Publications, Cambridge University Press, pp. 123–127.Google Scholar
[50] Leech, J. (1956) The problem of the thirteen spheres. Math. Gaz. 40 22–23.Google Scholar
[51] Levenšteĭn, V. I. (1979) Boundaries for packings in n-dimensional Euclidean space. Dokl. Akad. Nauk SSSR 245 1299–1303.Google Scholar
[52] Lévy, P. (1937) Théorie de l'Addition des Variables Aléatoires, Gauthier-Villars.Google Scholar
[53] Lieb, E. H. and Loss, M. (2001) Analysis, second edition, American Mathematical Society.Google Scholar
[54] Lifshits, M., Schilling, R. L. and Tyurin, I. (2013) A probabilistic inequality related to negative definite functions. Progr. Probab. 66 73–80.Google Scholar
[55] 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.Google Scholar
[56] Madiman, M. and Kontoyiannis, I. (2018) Entropy bounds on abelian groups and the Ruzsa divergence. IEEE Trans. Inform. Theory 64 77–92.Google Scholar
[57] Madiman, M., Melbourne, J. and Xu, P. (2017) Forward and reverse entropy power inequalities in convex geometry. In Convexity and Concentration (Carlen, E., Madiman, M. and Werner, E. M., eds.), Vol. 161 of IMA Volumes in Mathematics and its Applications, Springer, pp. 427–485.Google Scholar
[58] Madiman, M., Melbourne, J. and Xu, P. (2017) Rogozin's convolution inequality for locally compact groups. arXiv:1705.00642Google Scholar
[59] Madiman, M., Wang, L. and Woo, J. O. (2017) Entropy inequalities for sums in prime cyclic groups. arXiv:1710.00812Google Scholar
[60] Madiman, M., Wang, L. and Woo, J. O. (2017) Discrete entropy power inequalities via Sperner theory. arXiv:1712.00913Google Scholar
[61] Marcinkiewicz, J. and Zygmund, A. (1939) Quelques inégalités pour les opérations linéaires. Fund. Math. 32 115–121.Google Scholar
[62] Mattner, L. (1997) Strict definiteness of integrals via complete monotonicity of derivatives. Trans. Amer. Math. Soc. 349 3321–3342.Google Scholar
[63] Mirošnikov, A. L. and Rogozin, B. A. (1980) Inequalities for concentration functions. Teor. Veroyatnost. i Primenen 25 178–183.Google Scholar
[64] Musin, O. R. (2003) The problem of the twenty-five spheres. Uspekhi Mat. Nauk 58 153–154.Google Scholar
[65] Nguyen, H. H. and Vu, V. H. (2013) Small ball probability, inverse theorems, and applications. In Erdős Centennial (Lovász, L., Ruzsa, I. Z. and Sós, V. T., eds), Vol. 25 of Bolyai Society Mathematical Studies, Springer, pp. 409–463.Google Scholar
[66] Odlyzko, A. M. and Sloane, N. J. A. (1979) New bounds on the number of unit spheres that can touch a unit sphere in n dimensions. J. Combin. Theory Ser. A, 26 210–214.Google Scholar
[67] Pollard, D. (1989) Asymptotics via empirical processes. Statist. Sci. 4 341–366.Google Scholar
[68] Rogozin, B. A. (1961) On the increase of dispersion of sums of independent random variables. Teor. Verojatnost. i Primenen 6 106–108.Google Scholar
[69] Rudelson, M. and Vershynin, R. (2008) The Littlewood–Offord problem and invertibility of random matrices. Adv. Math. 218 600–633.Google Scholar
[70] Sidorenko, A. F. (1983) Extremal estimates of probability measures and their combinatorial nature. Math. USSR-Izv. 20 503–533.Google Scholar
[71] Siegmund-Schultze, R. and von Weizsäcker, H. (2007) Level crossing probabilities I: One-dimensional random walks and symmetrization. Adv. Math. 208 672–679.Google Scholar
[72] Viazovska, M. S. (2017) The sphere packing problem in dimension 8. Ann. Math. 185 991–1015.Google Scholar
[73] Wang, L and Madiman, M. (2014) Beyond the entropy power inequality, via rearrangements. IEEE Trans. Inform. Theory 60 5116–5137.Google Scholar
[74] Watanabe, T. (1983) The isoperimetric inequality for isotropic unimodal Lévy processes. Z. Wahrsch. Verw. Gebiete 63 487–499.Google Scholar