Probability

From NovaOrdis Knowledge Base
Jump to navigation Jump to search

External

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

Random Variable

A random variable is a statistic measure of what happens in a random outcome. It is a real value function defined on the sample space Ω to the real numbers. Once you know what happened, you have a real number.

X:Ω → ℝ

If we're rolling dice, an example of a random variable is the sum of the dice values.

Expectation of a Random Variable

The expectation of a random variable is the average of the random variable value weighted with the probability of each outcome.

Let X:Ω → ℝ be a random variable. The expectation (or the expected value) of the random variable is

E[X] = ∑ X(i) p(i)
      i∈S 

Linearity of Expectation

Linearity of expectation is a property (theorem) of random variables that consists in the following claim.

Let X1, X2 ... Xn be random variables defined on Ω. Then:

 ┌ n   ┐   n
E│ ∑ Xj│ = ∑ E[Xj]
 └ j=1 ┘   j=1

Expected value of the sum of random variables is equal to the sum of expectation of individual variables. This holds even if the random variables are NOT independent.

In case of two dice, the expected sum of two dice is the sum of expected value of each dice, which is the same of reach dice, and it is 1/6(1+2+3+4+5+6]=3.5, so the expected sum of two dice is 7.

Indicator Random Variable

A random variable that indicates whether an event happened or not - can be only 0 and 1.

Conditional Probability

One discusses the probability of one event given a second event. Let X, Y ⊆ Ω be two events. Then probability of the event X given the event Y is:

          Pr[X∩Y]
Pr[X|Y] = ───────
           P[Y]

Independent Events

Two events are independent if and only if the following equation holds:

 Pr[X∩Y] = Pr[X]*Pr[Y]

If we express the conditional probability of X given that Y happens and we substitute the above equation:

           Pr[X∩Y]    Pr[X]*Pr[Y]   
 Pr[X|Y] = ───────  = ─────────── = P[X]
            Pr[Y]        Pr[Y]

Intuitively, knowing that Y happened gives no information on probability of whether X happened.

Independence of Random Variables

TODO

  • Decomposition principle - relevant for the analysis of randomized algorithms.
  • Probability distribution