Probability

From NovaOrdis Knowledge Base
Revision as of 22:59, 22 September 2021 by Ovidiu (talk | contribs) (→‎Notations)
Jump to navigation Jump to search

Internal

Overview

All concepts discussed in this page are discrete probability concepts.

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

Probability Space

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

For two sets of dice, all possible outcomes of rolling the dice are 36 pairs: {(1,1),(2,1), ...(6,6)}, where each pair is an outcome. For tossing a coin, there are only two outcomes (heads or tail). For well crafted dice or fair coins, the probability of each outcome is equally likely 1/36 and 1/2 respectively.

Event

An events is a subset of all things that could happen, or a subset of the sample space S ⊆ Ω. An event consists of distinct outcomes. An example of an event is the subset of outcomes when the sum of the dice equals 7.

Probability of an Event

The probability of an event is the sum of all the probabilities of all outcomes contained in that event.

 ∑ p(i)
i∈S

The probability of the event when the sum of the dice is 7 is P((1,6))+P((2,5))+P((3,4))+P((4,3))+P((5,3))+P((6,1))=6*1/36=1/6.

Probability of an event A is written P[A].

TODO

Map Concepts:


  • 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