Document Open Access Logo

Tight Chernoff-Like Bounds Under Limited Independence

Author Maciej Skorski

PDF
Thumbnail PDF

File

LIPIcs.APPROX-RANDOM.2022.15.pdf
  • Filesize: 0.76 MB
  • 14 pages

Document Identifiers

Author Details

Maciej Skorski
  • University of Luxembourg, Luxembourg

Funding

The research supported by the FNR grant C17/IS/11613923.

Acknowledgements

The author thanks the reviewers of RANDOM'22 for insightful comments.

Cite AsGet BibTex

Maciej Skorski. Tight Chernoff-Like Bounds Under Limited Independence. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2022). Leibniz International Proceedings in Informatics (LIPIcs), Volume 245, pp. 15:1-15:14, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2022)
https://doi.org/10.4230/LIPIcs.APPROX/RANDOM.2022.15

Abstract

This paper develops sharp bounds on moments of sums of k-wise independent bounded random variables, under constrained average variance. The result closes the problem addressed in part in the previous works of Schmidt et al. and Bellare, Rompel. The work also discusses other applications of independent interests, such as asymptotically sharp bounds on binomial moments.

Subject Classification

ACM Subject Classification
  • Mathematics of computing → Statistical paradigms
  • Mathematics of computing → Probabilistic inference problems
  • Theory of computation → Randomness, geometry and discrete structures
Keywords
  • concentration inequalities
  • tail bounds
  • limited independence
  • k-wise independence

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Related Versions

References

  1. Jayadev Acharya, Alon Orlitsky, Ananda Theertha Suresh, and Himanshu Tyagi. Estimating rényi entropy of discrete distributions. IEEE Transactions on Information Theory, 63(1):38-56, 2016. Google Scholar
  2. Zeyuan Allen-Zhu, Rati Gelashvili, Silvio Micali, and Nir Shavit. Sparse sign-consistent johnson-lindenstrauss matrices: Compression with neuroscience-based constraints. Proceedings of the National Academy of Sciences, 111(47):16872-16876, 2014. Google Scholar
  3. Noga Alon and Asaf Nussboim. K-wise independent random graphs. In 2008 49th Annual IEEE Symposium on Foundations of Computer Science, pages 813-822. IEEE, 2008. Google Scholar
  4. Marshall Ball, Dana Dachman-Soled, Siyao Guo, Tal Malkin, and Li-Yang Tan. Non-malleable codes for small-depth circuits. In 2018 IEEE 59th Annual Symposium on Foundations of Computer Science (FOCS), pages 826-837. IEEE, 2018. Google Scholar
  5. Boaz Barak, Ronen Shaltiel, and Eran Tromer. True random number generators secure in a changing environment. In International Workshop on Cryptographic Hardware and Embedded Systems, pages 166-180. Springer, 2003. Google Scholar
  6. Louay MJ Bazzi. Polylogarithmic independence can fool dnf formulas. SIAM Journal on Computing, 38(6):2220-2272, 2009. Google Scholar
  7. Mihir Bellare and John Rompel. Randomness-efficient oblivious sampling. In Proceedings 35th Annual Symposium on Foundations of Computer Science, pages 276-287. IEEE, 1994. Google Scholar
  8. George Bennett. Probability inequalities for the sum of independent random variables. Journal of the American Statistical Association, 57(297):33-45, 1962. Google Scholar
  9. Jöran Bergh and Jörgen Löfström. Interpolation spaces: an introduction, volume 223. Springer Science & Business Media, 2012. Google Scholar
  10. SN Bernstein. Probability theory, ogiz, moscow-leningrad (1946). Google Scholar
  11. Henry W Block, Thomas H Savits, Moshe Shaked, et al. Some concepts of negative dependence. The Annals of Probability, 10(3):765-772, 1982. Google Scholar
  12. Stéphane Boucheron, Olivier Bousquet, Gábor Lugosi, Pascal Massart, et al. Moment inequalities for functions of independent random variables. The Annals of Probability, 33(2):514-560, 2005. Google Scholar
  13. Stéphane Boucheron, Gábor Lugosi, and Pascal Massart. Concentration inequalities: A nonasymptotic theory of independence. Oxford university press, 2013. Google Scholar
  14. Keren Censor-Hillel, Merav Parter, and Gregory Schwartzman. Derandomizing local distributed algorithms under bandwidth restrictions. Distributed Computing, 33(3):349-366, 2020. Google Scholar
  15. Herman Chernoff et al. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):493-507, 1952. Google Scholar
  16. Hamza ES Daoub. The fundamental theorem on symmetric polynomials. The Teaching of Mathematics, 28:55-59, 2012. Google Scholar
  17. Yevgeniy Dodis, Krzysztof Pietrzak, and Daniel Wichs. Key derivation without entropy waste. In Annual International Conference on the Theory and Applications of Cryptographic Techniques, pages 93-110. Springer, 2014. Google Scholar
  18. Devdatt P Dubhashi and Alessandro Panconesi. Concentration of measure for the analysis of randomized algorithms. Cambridge University Press, 2009. Google Scholar
  19. Devdatt P Dubhashi and Desh Ranjan. Balls and bins: A study in negative dependence. BRICS Report Series, 3(25), 1996. Google Scholar
  20. Morris L Eaton. A note on symmetric bernoulli random variables. The annals of mathematical statistics, 41(4):1223-1226, 1970. Google Scholar
  21. Morris L Eaton. A review of selected topics in multivariate probability inequalities. The Annals of Statistics, pages 11-43, 1982. Google Scholar
  22. T Figiel, P Hitczenko, W Johnson, G Schechtman, and J Zinn. Extremal properties of rademacher functions with applications to the khintchine and rosenthal inequalities. Transactions of the American Mathematical Society, 349(3):997-1027, 1997. Google Scholar
  23. Mohsen Ghaffari and Fabian Kuhn. Derandomizing distributed algorithms with small messages: Spanners and dominating set. In 32nd International Symposium on Distributed Computing (DISC 2018). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2018. Google Scholar
  24. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):13-30, 1963. Google Scholar
  25. Russell Impagliazzo, Raghu Meka, and David Zuckerman. Pseudorandomness from shrinkage. In 2012 IEEE 53rd Annual Symposium on Foundations of Computer Science, pages 111-119. IEEE, 2012. Google Scholar
  26. Meena Jagadeesan. Simple analysis of sparse, sign-consistent jl. arXiv preprint, 2017. URL: http://arxiv.org/abs/1708.02966.
  27. Svante Janson. New versions of suen’s correlation inequality. Random Structures and Algorithms, 13(3-4):467-483, 1998. Google Scholar
  28. Daniel M Kane and Jelani Nelson. A derandomized sparse johnson-lindenstrauss transform. arXiv preprint, 2010. URL: http://arxiv.org/abs/1006.3585.
  29. David R Karger and Matthias Ruhl. Simple efficient load balancing algorithms for peer-to-peer systems. In Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, pages 36-43, 2004. Google Scholar
  30. Andreas Knoblauch. Closed-form expressions for the moments of the binomial probability distribution. SIAM Journal on Applied Mathematics, 69(1):197-204, 2008. Google Scholar
  31. MJ Kronenburg. The binomial coefficient for negative arguments. arXiv preprint, 2011. URL: http://arxiv.org/abs/1105.3689.
  32. Rafał Latała et al. Estimation of moments of sums of independent real random variables. The Annals of Probability, 25(3):1502-1513, 1997. URL: https://projecteuclid.org/download/pdf_1/euclid.aop/1024404522.
  33. John E Littlewood. On the probability in the tail of a binomial distribution. Advances in Applied Probability, 1(1):43-72, 1969. Google Scholar
  34. Michael Luby, Michael George Luby, and Avi Wigderson. Pairwise independence and derandomization, volume 4. Now Publishers Inc, 2006. Google Scholar
  35. Colin Maclaurin. A second letter to martin folkes, esq.; concerning the roots of equations, with demonstration of other rules of algebra. Philos. Trans. Roy. Soc. London Ser. A, 36:59-96, 1729. Google Scholar
  36. Andrew McGregor and Hoa T Vu. Better streaming algorithms for the maximum coverage problem. Theory of Computing Systems, 63(7):1595-1619, 2019. Google Scholar
  37. Brendan D McKay. On littlewood’s estimate for the binomial distribution. Advances in Applied Probability, 21(2):475-478, 1989. Google Scholar
  38. Abbas Mehrabian. Summary of concentration inequalities for the sum of k-wise independent random variables, 2011. URL: https://www.cs.mcgill.ca/~amehra13/Articles/kwise_independent_concentration_summary.pdf.
  39. Dragoslav S. Mitrinović. Certain inequalities for elementary symmetric functions. Publikacije Elektrotehničkog fakulteta. Serija Matematika i fizika, (181/196):17-20, 1967. URL: http://www.jstor.org/stable/43667273.
  40. Gergő Nemes. On the coefficients of the asymptotic expansion of n! arXiv preprint, 2010. URL: http://arxiv.org/abs/1003.2907.
  41. Isaac Newton. Arithmetica universalis sive de compositione et resolutione arithmetica liber, volume 1. apud Marcum Michaelem Rey, 1761. Google Scholar
  42. Constantin Niculescu and Lars-Erik Persson. Convex functions and their applications. Springer, 2006. Google Scholar
  43. Maciej Obremski and Maciej Skorski. Renyi entropy estimation revisited. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik, 2017. Google Scholar
  44. Thomas K Philips and Randolph Nelson. The moment bound is tighter than chernoff’s bound for positive tail probabilities. The American Statistician, 49(2):175-178, 1995. Google Scholar
  45. Arjun Ramachandra and Karthik Natarajan. Tight probability bounds with pairwise independence. arXiv preprint, 2020. URL: http://arxiv.org/abs/2006.00516.
  46. Herbert Robbins. A remark on stirling’s formula. The American mathematical monthly, 62(1):26-29, 1955. Google Scholar
  47. Haskell P Rosenthal. On the subspaces ofl p (p> 2) spanned by sequences of independent random variables. Israel Journal of Mathematics, 8(3):273-303, 1970. Google Scholar
  48. Shmuel Rosset. Normalized symmetric functions, newton’s inequalities, and a new set of stronger inequalities. The American Mathematical Monthly, 96(9):815-819, 1989. Google Scholar
  49. Jörg-Rüdiger Sack and Jorge Urrutia. Handbook of computational geometry. Elsevier, 1999. Google Scholar
  50. Jeanette P Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-hoeffding bounds for applications with limited independence. SIAM Journal on Discrete Mathematics, 8(2):223-250, 1995. Google Scholar
  51. Roman Vershynin. High-dimensional probability: An introduction with applications in data science, volume 47. Cambridge university press, 2018. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact