The Azuma-Hoeffding inequality is a concentration result for martingales with bounded differences, which states that the probability of the value of the martingale deviating from its expected value by more than a certain amount is bounded. It provides two-sided bounds on the deviation of the martingale from its expected value, and can be applied to sub-martingales and super-martingales.
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