Chernoff bound is an exponentially decreasing upper bound on the tail of a random variable based on its moment generating function. It is sharper than other bounds such as Markov's and Chebyshev's inequalities, but requires the variates to be independent. It is related to Bernstein inequalities and used to prove Hoeffding's, Bennett's and McDiarmid's inequalities.
Stanford University
Fall 2022
This course dives into the use of randomness in algorithms and data structures, emphasizing the theoretical foundations of probabilistic analysis. Topics range from tail bounds, Markov chains, to randomized algorithms. The concepts are applied to machine learning, networking, and systems. Prerequisites indicate intermediate-level understanding required.
No concepts data
+ 37 more concepts