1 of 41

Probability Refresher

Probability and events

​

Random variables

2 of 41

PROBABILITY AND EVENTS

2

3 of 41

Key Take Aways (Events)

  • Independence: P{E∩F} = P{E}×P{F}
  • Conditional probability: P{E|F} = P{E∩F}/P{F}, F ≠ ∅
  • Conditional independence: P{E∩F|G} = P{E|G}×P{F|G}
  • Union Law: P{E∪F} = P{E}+P{F}–P{E∩F}
  • Law of total probability: For any partition ∪iFi = Ω

​

​

​

  • Bayes Law:

​

  • Bayes Law + Law of total probability:

3

 

 

 

4 of 41

Events

  • Sample space Ω consists of all possible outcomes (discrete or continuous) of an experiment
    • Single throw of a dice: {1, 2, 3, 4, 5, 6}
  • Events are any sub-space of the sample space
  • Combinations (union & intersection) of events are also events
    • E = E1 OR E2 = E1 ∪ E2 – (OR ⇔ ∪)
    • E = E1 AND E2 = E1 ∩ E2 – (AND ⇔ ∩)
    • Mutually exclusive events: E1 ∩ E2 = ∅
    • Complementary events: E & F are complements of each other if

E ∩ F = ∅ and E ∪ F = Ω

    • Partition (of sample space Ω): Set of mutually exclusive events that cover the entire sample space

4

5 of 41

Events & Probabilities – (1)

  • P{E}: Odds that event E occurs (P{Ω} = 1)
  • Union Law: P{E∪F} = P{E}+P{F}–P{E∩F}
    • P{E∪F} ≤ P{E}+P{F} with equality only if E and F are mutually exclusive (complementary events are mutually exclusive)
  • Conditional probability
    • P{E|F} = P{E∩F}/P{F} ⇒ P{E∩F} = P{E|F}×P{F}

​

  • Fair dice example: 6 possible outcomes with the same probability of 1/6
    • Probability of a 2 given that outcome is an even number?
      • P{2 AND Even}/ P{Even} = (1/6)/(3/6) = 1/3
      • 2 is one of three possible outcomes that yield an even number

​

5

6 of 41

Events & Probabilities – (2)

  • Independence
    • E & F are independent if P{E∩F} = P{E}×P{F}
    • Note: If E & F are independent P{E|F}=P{E∩F}/P{F}=(P{E}×P{F})/P{F}=P{E}
    • Examples: Dice throwing
      • P{ODD & Multiple of 3}= P{3}=1/6; and P{ODD}=1/2, P{Multiple of 3}=1/3, so that P{ODD}*P{Multiple of 3}=1/6 as well
      • P{ODD & ≤5}=P{1}+P{3}+P{5}=1/2; and P{ODD}=1/2, P{≤5}=P{1}+P{2}+P{3}+P{4}+P{5}=5/6, so that P{ODD}*P{≤5}=5/12≠1/2
  • Conditional independence
    • E & F are conditionally independent given G if

P{E∩F|G} = P{E|G}×P{F|G}

    • Examples: Dice throwing
      • P{≥2 & ≤4|EVEN}=P{{2,3,4,5,6}∩{1,2,3,4}∩{2,4,6}}/P{{2,4,6}}=2/3; and P{≥2 |EVEN}=1, P{≤4|EVEN}=2/3, so that P{≥2 |EVEN}*P{≤4|EVEN}=2/3 as well
      • Note that P{≥2 & ≤4}=1/2≠P{≤4}*P{≥2)=4/6*5/6=5/9, so conditionally independent but not independent

6

7 of 41

Events & Probabilities – (3)

  • Law of total probability: For any partition F1,…,FN, of the sample space (∪iFi = Ω)

​

​

  • Bayes Law

​

    • Prove using definition of conditional probability
  • Combining Bayes Law and Law of total probability

​

​

​

7

 

 

 

8 of 41

Bayes Law

    • Conditional probability

(1) P{E|F} = P{E∩F}/P{F} ⇒ P{E∩F} = P{E|F}×P{F}

(2) P{F|E} = P{E∩F}/P{E} ⇒ P{E∩F} = P{F|E}×P{E}

    • Combining (1) in (2) gives

P{F|E} = P{E|F}×P{F}/P{E}

​

​

8

 

9 of 41

Example – Anti-virus s/w Test

  • We know that our s/w is 95% accurate, i.e., gives the correct answer:
    • P{positive | infected} = 0.95 (true positive) and P{negative | infected} = 0.05 (false negative)
    • P{negative | not infected} = 0.95 (true negative) and P{positive | not infected} = 0.05 (false positive)

Note: In general, the two may not be equal, and defining accuracy is more challenging

  • We also know that on average 1 out every 1,000 computers is infected with a virus, i.e., P{infected} = 0.001 (P{not infected} = 0.999)
  • What are the odds p that a computer that tests positive is infected with a virus?
    • p = P{infected| positive}
    • Bayes Law: p = [P{positive | infected}×P{infected}]/P{positive} – we don’t know P{positive}
    • Bayes Law + Total Probability Law: Replace P{positive} with

P{positive} = P{positive | infected}×P{infected}+P{positive | not infected} ×P{not infected}

P{positive} = 0.95×0.001+0.05×0.999 = 0.0509

​

    • This gives p = 0.95×0.001/0.509 = 0.0187, i.e., less than 2%

If we test 1,000 computers ~50 will return a positive test. Of those 50, one is likely to be really infected (based on P{infected}=0.001), but the other 49 are not ⇒ True positives = 1/50 or ~2%

9

10 of 41

Example – Anti-virus s/w Test

  • We know that our s/w is 95% accurate, i.e., gives the correct answer:
    • P{positive | infected} = 0.95 (true positive) and P{negative | infected} = 0.05 (false negative)
    • P{negative | not infected} = 0.95 (true negative) and P{positive | not infected} = 0.05 (false positive)

Note: In general, the two may not be equal, and defining accuracy is more challenging

  • We also know that on average 1 out every 1,000 computers is infected with a virus, i.e., P{infected} = 0.001 (P{not infected} = 0.999)
  • What are the odds p that a computer that tests positive is infected with a virus?
    • p = P{infected| positive}
    • Bayes Law: p = [P{positive | infected}×P{infected}]/P{positive} – we don’t know P{positive}
    • Bayes Law + Total Probability Law: Replace P{positive} with

P{positive} = P{positive | infected}×P{infected}+P{positive | not infected} ×P{not infected}

P{positive} = 0.95×0.001+0.05×0.999 = 0.0509

​

    • This gives p = 0.95×0.001/0.509 = 0.0187, i.e., less than 2%

If we test 1,000 computers ~50 will return a positive test. Of those 50, one is likely to be really infected (based on P{infected}=0.001), but the other 49 are not ⇒ True positives = 1/50 or ~2%

10

11 of 41

Example – Anti-virus s/w Test

  • We know that our s/w is 95% accurate, i.e., gives the correct answer:
    • P{positive | infected} = 0.95 (true positive) and P{negative | infected} = 0.05 (false negative)
    • P{negative | not infected} = 0.95 (true negative) and P{positive | not infected} = 0.05 (false positive)

Note: In general, the two may not be equal, and defining accuracy is more challenging

  • We also know that on average 1 out every 1,000 computers is infected with a virus, i.e., P{infected} = 0.001 (P{not infected} = 0.999)
  • What are the odds p that a computer that tests positive is infected with a virus?
    • p = P{infected| positive}
    • Bayes Law: p = [P{positive | infected}×P{infected}]/P{positive} – we don’t know P{positive}
    • Bayes Law + Total Probability Law: Replace P{positive} with

P{positive} = P{positive | infected}×P{infected}+P{positive | not infected} ×P{not infected}

P{positive} = 0.95×0.001+0.05×0.999 = 0.0509

​

    • This gives p = 0.95×0.001/0.509 = 0.0187, i.e., less than 2%

If we test 1,000 computers ~50 will return a positive test. Of those 50, one is likely to be really infected (based on P{infected}=0.001), but the other 49 are not ⇒ True positives = 1/50 or ~2%

11

12 of 41

Example – Anti-virus s/w Test

  • We know that our s/w is 95% accurate, i.e., gives the correct answer:
    • P{positive | infected} = 0.95 (true positive) and P{negative | infected} = 0.05 (false negative)
    • P{negative | not infected} = 0.95 (true negative) and P{positive | not infected} = 0.05 (false positive)

Note: In general, the two may not be equal, and defining accuracy is more challenging

  • We also know that on average 1 out every 1,000 computers is infected with a virus, i.e., P{infected} = 0.001 (P{not infected} = 0.999)
  • What are the odds p that a computer that tests positive is infected with a virus?
    • p = P{infected| positive}
    • Bayes Law: p = [P{positive | infected}×P{infected}]/P{positive} – we don’t know P{positive}
    • Bayes Law + Total Probability Law: Replace P{positive} with

P{positive} = P{positive | infected}×P{infected}+P{positive | not infected}×P{not infected}

P{positive} = 0.95×0.001+0.05×0.999 = 0.0509

​

    • This gives p = 0.95×0.001/0.509 = 0.0187, i.e., less than 2%

If we test 1,000 computers ~50 will return a positive test. Of those 50, one is likely to be really infected (based on P{infected}=0.001), but the other 49 are not ⇒ True positives = 1/50 or ~2%

12

13 of 41

Some “Intuition”

  •  

13

14 of 41

RANDOM VARIABLES

14

15 of 41

Key Take Aways (Random Variables - 1)

  • Events are mapped to numbers (discrete or continuous)
  • Distributions, first, second & higher moments

​

​

    • Linearity of expectation: E[X+Y] = E[X] + E[Y]
  • Joint & conditional distributions
    • PX,Y(x,y) = P{X=x AND Y=y) – but on different sample spaces

​

  • Independent random variables
    • PX,Y(x,y) = PX(x)×PY(y) and E[XY] = E[X]E[Y]
    • Var(X+Y) = Var(X) + Var(Y)

​

15

 

 

 

16 of 41

Key Take Aways (Random Variables - 2)

  •  

16

17 of 41

Random Variables

  •  

17

18 of 41

Joint Probability

  • Discrete r.v.: Joint probability mass function PX,Y(x,y)
    • PX,Y(x,y) = P{X=x AND Y=y)
    • PX(x) = ΣyPX,Y(x,y) and PY(y) = ΣxPX,Y(x,y)
  • Continuous r.v.: Joint density function fX,Y(x,y)

​

​

​

​

  • If X and Y are independent r.v.’s (X ⊥ Y)
    • Discrete: PX,Y(x,y) = PX(x)×PY(y)
    • Continuous: fX,Y(x,y) = fX(x)×fY(y)
    • E[XY] = E[X]E[Y]

18

 

19 of 41

Conditional Probabilities & Expectations

  •  

19

 

 

 

20 of 41

Conditional Probabilities & Expectations

  •  

20

 

21 of 41

Conditional Probabilities & Expectations

  •  

21

 

 

 

22 of 41

Conditional Probabilities & Expectations

  •  

22

23 of 41

Conditional Probabilities & Expectations

  •  

23

 

 

 

24 of 41

Conditional Probabilities & Expectations

  •  

24

 

25 of 41

Conditional Probabilities & Expectations

  •  

25

 

 

 

26 of 41

Conditional Probabilities & Expectations

  •  

26

27 of 41

More on Expectation

  • Expected value from conditional expectation
    • Discrete r.v.: E[X] = ΣyE[X|Y=y]P{Y=y}
      • More generally: E[g(X)] = ΣyE[g(X)|Y=y]P{Y=y}
    • Continuous r.v.: E[X] = ∫yE[X|Y=y]fY(y)dy
      • More generally: E[g(X)] = ∫yE[g(X)|Y=y]P{Y=y}
  • Linearity of expectation: E[X+Y] = E[X] + E[Y]
  • Linearity of variance for independent r.v.’s
    • If X ⊥ Y then Var(X+Y) = Var(X) + Var(Y)

27

28 of 41

Random Sum of Random Variables

  • Let X1, X2, X3,… be i.i.d. random variables and N be a non-negative, integer-valued random variable, independent of the Xi’s (e.g., waiting time in a queue)

​

  • Define

​

  • Find expressions for E[S] and Var(S)
    • Condition on N and use linearity of expectation
    • For variance, use the fact that Var(S|N = n) = nVar(X)
      • Variance of sum of independent r.v.’s is sum of the variances

28

 

29 of 41

Mean of Random Sum of Random Variables

29

 

30 of 41

Variance of Random Sum of Random Variables

  • Start with Var(S|N=n)

​

​

​

  • So that

​

​

​

  • Hence

​

30

 

 

 

31 of 41

Sample Paths, Convergence, and Averages

32 of 41

Key Take Aways (Convergence & Averages)

  • Convergence
    • Almost surely (with probability 1)
    • In probability

Probability of the limit vs. limit of the probability

​

  • Its role in averages (for systems of interest)
    • Time and ensemble averages
      • Time: Pick one system and look at it for a long time
      • Ensemble: Run many systems and look at all of them after some time
    • Ergodicity: time average = ensemble average

​

​

​

32

33 of 41

Convergence

  • Definition: {an : n = 1, 2, …} converges to b as n → ∞ means that

∀ε > 0, ∃n0(ε), such that ∀n > n0(ε), |an – b| < ε

​

  • Example: an = 1/n converges to 0 as n → ∞ since ∀ε > 0, choosing n0(ε) = ⎡1/ε⎤ ensures that ∀n > n0(ε), an = 1/n < 1/n0(ε) < ε

​

​

33

34 of 41

Why Do We Care About Convergence?

  • A key factor in defining what we mean by “averages”
    • Time vs. ensemble averages (observing one system for a very long time vs. looking at many systems in parallel) – different ways of estimating the sample space by collecting individual samples
  • Of importance is whether the two types of averages converge to the same answer
    • They do for ergodic systems

34

35 of 41

Convergence Almost Surely�(with Probability 1)

  • {Yn : n = 1, 2, …} converges almost surely to μ as n → ∞, if

∀ε > 0, P{limn→∞ |Yn – μ| > ε} = 0

  • In other words, the probability mass (odds) of the set of sample paths that misbehave (Yn deviates from μ by more than ε) is 0 if we take n to be large enough
    • Note: This does not mean that no sample path misbehaves, and only that the total probability mass of these “bad” paths is (of measure) zero
    • A sample path misbehaves if no matter what value of n we choose, it is still possible to have |Yn – μ| > ε

Consider the average of n coin flips. Most sample paths will converge to a value of ½. However, some sample paths wont, e.g., the sample path 1,1,1,1,1,1,… We have convergence almost surely, because even though there are an uncountable number of “bad” paths, that number becomes vanishingly small (of measure 0) as n goes to infinity

35

36 of 41

Convergence in Probability

  • {Yn : n = 1, 2, …} converges in probability to μ as n → ∞, if

∀ ε > 0, limn→∞P{|Yn – μ| > ε} = 0

(the limit applies to the probability, and not the random variables)

  • In other words, the odds that an individual sample path behaves badly for Yn go to 0 as n → ∞
    • Pick a given n and a random path, what are the odds that it is “bad” (deviates from μ by more than ε at n)?
    • As n grows, those odds should go to 0
  • However, this does not preclude the possibility that all (or a non-negligible number) sample paths occasionally behave badly as n → ∞
    • For n∈[M2k, M2k+1–1], Yn = 0 except once randomly selected in [M2k, M2k+1–1], for which Yn = 1
    • No sample path converges but limn→∞P{|Yn | > ε} = limk→∞ 1/M2k = 0
  • Convergence almost surely implies convergence in probability, but the converse is not true (see also review problem S2.4)

36

37 of 41

Strong & Weak Laws of Large Numbers�Convergence and Averages

  • Weak Law: Let X1, X2, X3,… be i.i.d. random variables with mean E[X], Sn = Σ{i=1,…,n}Xi, and Yn = Sn/n

Then Yn converges in probability to E[X]

    • The probability that the sample mean Yn deviates from E[X] goes to 0 as n grows large
  • Strong Law: Let X1, X2, X3,… be i.i.d. random variables with mean E[X], Sn = Σ{i=1,…,n}Xi, and Yn = Sn/n

Then Yn converges almost surely to E[X]

    • The sequence of random variables Yn (the sample means) converges to E[X] with probability 1 as n grows large

​

Strong Law is harder to prove than Weak Law but implies it

​

  • Almost every sample paths of successive trials of Xn converges to a mean value of E[X]
    • There can still be bad sample paths, but the odds of picking one tend to zero as n → ∞

37

38 of 41

Time & Ensemble Averages

  • Basic concept: Run a single experiment for 10 hours versus run 100 experiments of 6 minutes each
    • Record average value of experiment variable over the 10 hours of the first experiment and compare it to the average of the experiment variable at the end of each of the hundred 6 minutes experiments
  • Time average

​

  • Ensemble average

where pi = limt→∞P{N(t) = i}

38

 

 

39 of 41

Computing Averages in Practice

  • Average number of jobs in system: N
    • Time average: Record duration ti, of successive time intervals during which the number of jobs is constant, and number of jobs, ni
      • Time average of number of jobs is Ntime = (Σiniti)/(Σiti)
    • Ensemble average: Run M experiments, each of duration t, where Mt = Σiti, and record nk(t), k = 1, 2, …, M
      • Ensemble average of number of jobs is Nensemble = Σknk(t)/M
  • Also of interest: Average job time in system (Little’s Law – more on this later)

39

40 of 41

Ergodicity

  • System state: Defines the sample space of the system’s main metric of interest, e.g., number of jobs in the system
  • An ergodic system is positive recurrent, aperiodic, and irreducible (we’ll make this more concrete later)
    • Irreducible: We can get from any “state” to any other “state”
    • Positive recurrent: Every system state is visited infinitely often, and the mean time between successive visits is finite (and the visit of each state is a renewal point – the system probabilistically restart itself)
    • Aperiodic: The system state is not deterministically coupled to a particular time period
  • For an ergodic system, the ensemble average exists and with probability 1 is equal to the time average

40

41 of 41

Non-Ergodic Systems

  • Systems where the state evolution depends on some initial conditions
    • Flip a coin and with probability p the system will receive 1 job/sec, and with probability 1 – p it will receive 2 jobs/sec
    • System state at time t will be very different depending on the starting condition
  • Periodic systems
    • At the start of every 5mins interval, the system receives 2 jobs each taking 1min to process
    • The ensemble average does not exist in this case (different results depending on when the systems are sampled), though time averages are still well-defined

41