Probability
Jump to navigation
Jump to search
Internal
Overview
All concepts discussed in this page are discrete probability concepts.
Sample Space and Probability Space
A sample space is the collection of all things that could happen, the universe in which we are going to discuss the probability of events. The sample space contains all possible outcomes. It is represented with Ω (big omega).
In case of discrete probabilities, the sample space is a finite set.
Outcome
Each outcome i∈Ω has a probability p(i) ≥ 0.
The constraint on all outcome probabilities is that the sum of all probabilities is over the sample space is 1:
∑ p(i) = 1 i∈Ω
Event
Notations
TODO
- Mathematics for Computer Science Eric Lehman and Tom Leighton Chapters 18 - Chapter 25.
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/UXerT/probability-review-i
- https://www.coursera.org/learn/algorithms-divide-conquer/lecture/cPGDy/probability-review-ii
Map Concepts:
- Sample space
- Outcome
- Events and outcomes
- Random variables
- Indicator random variable
- Expectation
- Decomposition principle - relevant for the analysis of randomized algorithms.
- Linearity of expectations
- Conditional probability
- Independent events
- Independent random variables
- Probability distribution