ConceptTheory & Algos
Union bound
A probability rule stating that the probability of the union of multiple events is at most the sum of their individual probabilities.
Know first
Named as a prerequisite by the lectures that define this. The number is how many say so. A grey one has no page yet.
Opens up
Concepts that name this one as a prerequisite.
Lecturers
6Each in their own terms, from the easiest level.
Ryan O'Donnell
Yaser Abu-Mostafa
A rule stating that the probability of a union of events is less than or equal to the sum of the probabilities of the individual events.Tom Leighton
The probability of a union of events is upper bounded by the sum of the probabilities of the individual events.Venkatesan Guruswami
The probability of the union of multiple events is at most the sum of the individual probabilities of those events.Srini Devadas
A rule stating that the probability that at least one of a countable set of events occurs is at most the sum of the probabilities of the individual events.Ankur Moitra
The probability of a union of events is at most the sum of the probabilities of the individual events.
Lectures that assume it
3Connections
23The lectures that define it or assume it, and the concepts next to it.
Concepts9
- Probability axioms
- Probability theory
- Event
- Probability
- Degree reduction via random bits
- Hoeffding's inequality with multiple hypotheses
Show 3 moreShow fewer
Lectures14
- Large Deviations
- Is Learning Feasible?
- The Linear Model I
- BPP (Bounded-Error Probabilistic Polynomial Time) Complexity Class
- Randomization: Skip Lists
- Period-Finding (Simon's Algorithm over Z_N)
Show 8 moreShow fewer
- Transmitting Information Reliably over a Noisy Channel & Shannon’s Noisy Coding Theorem
- Training Versus Testing
- Probabilistic Complexity Classes
- Spectral Concentration and Learning
- Introduction to Arthur-Merlin classes, MA and AM
- Theory of Generalization
- Razborov Smolensky Lower Bounds for AC0[p]
- DNF Formulas