Probability: Difference between revisions

From NovaOrdis Knowledge Base
Jump to navigation Jump to search
 
(18 intermediate revisions by the same user not shown)
Line 39: Line 39:


=Random Variable=
=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 Ω.  
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:Ω → ℝ
  X:Ω → ℝ
If we're rolling dice, an example of a random variable is the sum of the dice values.
==Indicator Random Variable==
A random variable that indicates whether an event happened or not - can be only 0 and 1.


If we're rolling dice, an example of a random variable is the sum of the dice values.
==<span id='Expectation'></span>Expectation of a Random Variable==
==Expectation of a Random Variable==
The expectation of a [[#Random_Variable|random variable]] is the average of the random variable value weighted with the probability of each outcome.
The expectation of a [[#Random_Variable|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
Let X:Ω → ℝ be a random variable. The expectation (or the expected value) of the random variable is:
<font size=-1>
<font size=-1>
  E[X] = ∑ X(i) p(i)
  E[X] = ∑ X(i) p(i)
       i∈S  
       i∈S  
</font>
</font>
==Linearity of Expectation==
==Linearity of Expectation==
Linearity of expectation is a property (theorem) of random variables that consists in the following claim.
Linearity of expectation is a property (theorem) of random variables that consists in the following claim.
Line 63: Line 66:


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.
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=
=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:
<font size=-1>
          Pr[X∩Y]
Pr[X|Y] = ───────
            P[Y]
</font>
==Independent Events==
Two events are independent if and only if the following equation holds:
<font size=-1>
  Pr[X∩Y] = Pr[X]*Pr[Y]
</font>
If we express the conditional probability of X given that Y happens and we substitute the above equation:
<font size=-1>
            Pr[X∩Y]    Pr[X]*Pr[Y] 
  Pr[X|Y] = ───────  = ─────────── = P[X]
            Pr[Y]        Pr[Y]
</font>
Intuitively, knowing that Y happened gives no information on probability of whether X happened.
==Independence of Random Variables==
Informally, knowing the value taken on by one of the random variables tells you nothing about what value is taken by the other random variable.
If A, B random variable are independent, then [[#Expectation|expectation]]:
<font size=-1>
E[A⋅B] = E[A]⋅E[B]
</font>
This only holds for independent variable, it does not work for dependent variables.


=TODO=
=Decomposition Principle=
<font color=darkkhaki>Relevant for the analysis of randomized algorithms. Return to lecture.</font>


* Decomposition principle - relevant for the analysis of randomized algorithms.
=Probability Distribution=
* Independent events
* Independent random variables
* Probability distribution

Latest revision as of 01:47, 30 November 2021

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.

Indicator Random Variable

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

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.

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

Informally, knowing the value taken on by one of the random variables tells you nothing about what value is taken by the other random variable.

If A, B random variable are independent, then expectation:

E[A⋅B] = E[A]⋅E[B]

This only holds for independent variable, it does not work for dependent variables.

Decomposition Principle

Relevant for the analysis of randomized algorithms. Return to lecture.

Probability Distribution