Document Open Access Logo

Upper Tail Estimates with Combinatorial Proofs

Authors Jan Hazla, Thomas Holenstein

PDF
Thumbnail PDF

File

LIPIcs.STACS.2015.392.pdf
  • Filesize: 0.59 MB
  • 14 pages

Document Identifiers

Author Details

Jan Hazla
Thomas Holenstein

Cite As Get BibTex

Jan Hazla and Thomas Holenstein. Upper Tail Estimates with Combinatorial Proofs. In 32nd International Symposium on Theoretical Aspects of Computer Science (STACS 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 30, pp. 392-405, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015) https://doi.org/10.4230/LIPIcs.STACS.2015.392

Abstract

We study generalisations of a simple, combinatorial proof of a Chernoff bound similar to the one by Impagliazzo and Kabanets (RANDOM, 2010).

In particular, we prove a randomized version of the hitting property of expander random walks and use it to obtain an optimal expander random
walk concentration bound settling a question asked by Impagliazzo and Kabanets.  

Next, we obtain an upper tail bound for polynomials with input variables in [0, 1] which are not necessarily independent, but obey a certain condition inspired by Impagliazzo and Kabanets. The resulting bound 
is applied by Holenstein and Sinha (FOCS, 2012) in the proof of a lower bound for the number of calls in a black-box construction of a pseudorandom generator from a one-way function.

We also show that the same technique yields the upper tail bound for the number of copies of a fixed graph in an Erdös–Rényi random graph,
matching the one given by Janson, Oleszkiewicz, and Rucinski (Israel J. Math, 2002).

Subject Classification

Keywords
  • concentration bounds
  • expander random walks
  • polynomial concentration

Metrics

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

References

  1. Carlos A. León and François Perron. Optimal Hoeffding bounds for discrete reversible Markov chains. The Annals of Applied Probability, 14(2):958-970, 05 2004. Google Scholar
  2. Miklós Ajtai, János Komlós, and Endre Szemerédi. Deterministic simulation in LOGSPACE. In Proceedings of the Nineteenth Annual ACM Symposium on Theory of Computing, STOC '87, pages 132-140, New York, NY, USA, 1987. ACM. Google Scholar
  3. Noga Alon, Uriel Feige, Avi Wigderson, and David Zuckerman. Derandomized graph products. Computational Complexity, 5(1):60-75, 1995. Google Scholar
  4. Sanjeev Arora and Boaz Barak. Computational Complexity - A Modern Approach. Cambridge University Press, 2009. Google Scholar
  5. Kazuoki Azuma. Weighted sums of certain dependent random variables. Tôhoku Math. J. (2), 19:357-367, 1967. Google Scholar
  6. Sergei N. Bernstein. On a modification of Chebyshev’s inequality and of the error formula of Laplace. Ann. Sci. Inst. Sav. Ukraine, Sect. Math., 1, 1924. Google Scholar
  7. Herman Chernoff. A measure of asymptotic efficiency for tests of a hypothesis based on the sum of observations. The Annals of Mathematical Statistics, 23(4):pp. 493-507, 1952. Google Scholar
  8. Kai-Min Chung, Henry Lam, Zhenming Liu, and Michael Mitzenmacher. Chernoff-Hoeffding bounds for Markov chains: Generalized and simplified. In Christoph Dürr and Thomas Wilke, editors, STACS, volume 14 of LIPIcs, pages 124-135. Schloss Dagstuhl - Leibniz-Zentrum fuer Informatik, 2012. Google Scholar
  9. Victor H. de la Peña and S. J. Montgomery-Smith. Bounds on the tail probability of U-statistics and quadratic forms. Bulletin of the American Mathematical Society, 31(2):223-227, 1994. Google Scholar
  10. Devdatt Dubhashi and Alessandro Panconesi. Concentration of Measure for the Analysis of Randomized Algorithms. Cambridge University Press, New York, NY, USA, 1st edition, 2009. Google Scholar
  11. David Gillman. A Chernoff bound for random walks on expander graphs. SIAM J. Comput., 27(4):1203-1220, 1998. Google Scholar
  12. Alexander Healy. Randomness-efficient sampling within NC^1. Computational Complexity, 17(1):3-37, 2008. Google Scholar
  13. Wassily Hoeffding. Probability inequalities for sums of bounded random variables. Journal of the American Statistical Association, 58(301):pp. 13-30, 1963. Google Scholar
  14. Thomas Holenstein and Makrand Sinha. Constructing a pseudorandom generator requires an almost linear number of calls. In FOCS, pages 698-707. IEEE Computer Society, 2012. Google Scholar
  15. Shlomo Hoory, Nathan Linial, and Avi Wigderson. Expander graphs and their applications. Bulletin of the AMS, 43(4):439-561, 2006. Google Scholar
  16. Russell Impagliazzo and Valentine Kabanets. Constructive proofs of concentration bounds. In Maria J. Serna, Ronen Shaltiel, Klaus Jansen, and José D. P. Rolim, editors, APPROX-RANDOM, volume 6302 of Lecture Notes in Computer Science, pages 617-631. Springer, 2010. Google Scholar
  17. Svante Janson, Krzysztof Oleszkiewicz, and Andrzej Ruciński. Upper tails for subgraph counts in random graphs. Israel Journal of Mathematics, 142(1):61-92, 2004. Google Scholar
  18. Svante Janson and Andrzej Ruciński. The infamous upper tail. Random Struct. Algorithms, 20(3):317-342, 2002. Google Scholar
  19. Svante Janson and Andrzej Ruciński. Upper tails for counting objects in randomly induced subhypergraphs and rooted random graphs. Arkiv för matematik, 49(1):79-96, 2011. Google Scholar
  20. Nabil Kahalé. Eigenvalues and expansion of regular graphs. J. ACM, 42(5):1091-1106, September 1995. Google Scholar
  21. Nabil Kahalé. Large deviation bounds for Markov chains. Combinatorics, Probability & Computing, 6(4):465-474, 1997. Google Scholar
  22. Jeong Han Kim and Van H. Vu. Concentration of multivariate polynomials and its applications. Combinatorica, 20(3):417-434, 2000. Google Scholar
  23. Rafał Latała and Rafał Łochowski. Moment and tail estimates for multidimensional chaoses generated by positive random variables with logarithmically concave tails. Progr. Probab., 56:77-92, 2003. Google Scholar
  24. Pascal Lezaud. Chernoff-type bound for finite Markov chains. Ann. Appl. Probab., 8(3):849-867, 1998. Google Scholar
  25. Michael Mitzenmacher and Eli Upfal. Probability and Computing: Randomized Algorithms and Probabilistic Analysis. Cambridge University Press, New York, NY, USA, 2005. Google Scholar
  26. Rajeev Motwani and Prabhakar Raghavan. Randomized algorithms. Cambridge University Press, Cambridge, New York, Melbourne, 1995. Réimpressions : 1997, 2000. Google Scholar
  27. Anup Rao. Parallel repetition in projection games and a concentration bound. In In Proc. 40th STOC, pages 1-10. ACM, 2008. Google Scholar
  28. Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. Chernoff-Hoeffding bounds for applications with limited independence. SIAM J. Discret. Math., 8(2):223-250, May 1995. Google Scholar
  29. Warren Schudy and Maxim Sviridenko. Concentration and moment inequalities for polynomials of independent random variables. In Yuval Rabani, editor, SODA, pages 437-446. SIAM, 2012. Google Scholar
  30. Salil P. Vadhan. Pseudorandomness. Foundations and Trends in Theoretical Computer Science, 7(1-3):1-336, 2012. Google Scholar
  31. V. H. Vu. Concentration of non-Lipschitz functions and applications. Random Struct. Algorithms, 20(3):262-316, May 2002. Google Scholar
  32. Roy Wagner. Tail estimates for sums of variables sampled by a random walk. Combinatorics, Probability and Computing, 17:307-316, 3 2008. 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 About DROPS Imprint Privacy Contact