This week the project is pivoting directions. We plan on reframing the NIST statistical tests in the view of concentration bounds instead of hypothesis testing. As a result, I spent most of the week learning about Chernoff and Hoeffding bounds. Working through the proofs is unironically going to give me brain damage, but seeing these probabilistic tools being applied is very cool!
I’m also pretty sure there is an error with the formulation and proof of Chernoff-Hoeffding in one of the textbooks I was going through. In any case, progress this week can be summarized with working through the proofs of the theorems, and doing the exercises Periklis sent me.
Textbooks:
- Concentration of Measure for the Analysis of Randomized Algorithms (https://dl.acm.org/doi/book/10.5555/1568639)
- Randomized Algorithms (https://www.google.com/books/edition/Randomized_Algorithms/QKVY4mDivBEC?hl=en)