Probability

Internal

• Statistics
• Randomized Algorithms

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 Ω.

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