1 of 57

Lecture 7B: �Probability Review

UC Berkeley CS70

Summer 2023

Nikki Suzani

2 of 57

Discrete Probability

Define Probability Spaces:

Sample Space (Ω)
Probability of each sample point, P(ω)

Combine omega, ω, into events

For uniform probability, P(A) = |A| / |Ω|

Lecture 4A - Slide 2

UC Berkeley CS70 - Nikki Suzani

3 of 57

Conditional Probability

Bayes’ Rule

Lecture 4A - Slide 3

Pr[A\|B] =	P(A∩B)
	P(B)

Pr[A\|B] =	Pr[B\|A] x Pr[A]
	Pr[B]

UC Berkeley CS70 - Nikki Suzani

4 of 57

Bayes’ Rule Exam Question

Lecture 4A - Slide 4

UC Berkeley CS70 - Nikki Suzani

5 of 57

Lecture 4A - Slide 5

UC Berkeley CS70 - Nikki Suzani

6 of 57

Intersections and Unions

Independent: P(A | B) = P(A), P(A ∩ B) = P(A)P(B)

Product Rule:

Principle of Inclusion-Exclusion:

Union Bound: P(A U B) ≤ P(A) + P(B)

Lecture 4A - Slide 6

UC Berkeley CS70 - Nikki Suzani

7 of 57

Independence Exam Question

Lecture 4A - Slide 7

UC Berkeley CS70 - Nikki Suzani

8 of 57

Lecture 4A - Slide 8

UC Berkeley CS70 - Nikki Suzani

9 of 57

Union Bound Exam Question

Lecture 4A - Slide 9

UC Berkeley CS70 - Nikki Suzani

10 of 57

Lecture 4A - Slide 10

UC Berkeley CS70 - Nikki Suzani

11 of 57

Expectation

Lecture 4A - Slide 11

Tail Sum:

UC Berkeley CS70 - Nikki Suzani

12 of 57

Linearity of Expectation

E[aX + b] = aE[X] + b

E[X + Y] = E[X] + E[Y]

Lecture 4A - Slide 12

UC Berkeley CS70 - Nikki Suzani

13 of 57

More Expectation

Lecture 4A - Slide 13

E[X] = E[E[X | Y]]

UC Berkeley CS70 - Nikki Suzani

14 of 57

Wald’s Identity

Lecture 4A - Slide 14

UC Berkeley CS70 - Nikki Suzani

15 of 57

Expectation Exam Question

Lecture 4A - Slide 15

UC Berkeley CS70 - Nikki Suzani

16 of 57

Lecture 4A - Slide 16

UC Berkeley CS70 - Nikki Suzani

17 of 57

Indicator Expectation Exam Question

Lecture 4A - Slide 17

UC Berkeley CS70 - Nikki Suzani

18 of 57

Lecture 4A - Slide 18

UC Berkeley CS70 - Nikki Suzani

19 of 57

Conditional Expectation Exam Question

Lecture 4A - Slide 19

UC Berkeley CS70 - Nikki Suzani

20 of 57

Lecture 4A - Slide 20

UC Berkeley CS70 - Nikki Suzani

21 of 57

Discrete Random Variables, Expectation, Variance

Lecture 4A - Slide 21

UC Berkeley CS70 - Nikki Suzani

22 of 57

Continuous Random Variables, Expectation, Variance

Lecture 4A - Slide 22

UC Berkeley CS70 - Nikki Suzani

23 of 57

Random Variable Exam Question

Lecture 4A - Slide 23

UC Berkeley CS70 - Nikki Suzani

24 of 57

Lecture 4A - Slide 24

UC Berkeley CS70 - Nikki Suzani

25 of 57

Random Variable Exam Question

Lecture 4A - Slide 25

UC Berkeley CS70 - Nikki Suzani

26 of 57

Lecture 4A - Slide 26

UC Berkeley CS70 - Nikki Suzani

27 of 57

Independent RVs Question

Lecture 4A - Slide 27

*Given independent X, Y

UC Berkeley CS70 - Nikki Suzani

28 of 57

Lecture 4A - Slide 28

UC Berkeley CS70 - Nikki Suzani

29 of 57

Independent RVs Question

Lecture 4A - Slide 29

Given *independent X, Y, Z

UC Berkeley CS70 - Nikki Suzani

30 of 57

Lecture 4A - Slide 30

UC Berkeley CS70 - Nikki Suzani

31 of 57

Variance, Covariance, Correlation

Var(X) = E((X - μ)²) = E[X²] - E[X]²

Var(cX + b) = c²Var(X + b) = c²Var(X)

Cov(aX + bY, aX + bY) =

If independent:

Var(X + Y) = Var(X) + Var(Y) + 2Cov(X, Y) = Var(X) + Var(Y)

E[XY] = E[X]E[Y]

Lecture 4A - Slide 31

UC Berkeley CS70 - Nikki Suzani

32 of 57

Covariance with Indicators

Var(X₁ + … + X_n)

Lecture 4A - Slide 32

UC Berkeley CS70 - Nikki Suzani

33 of 57

Variance with Indicators Exam Question

Lecture 4A - Slide 33

UC Berkeley CS70 - Nikki Suzani

34 of 57

Lecture 4A - Slide 34

UC Berkeley CS70 - Nikki Suzani

35 of 57

Concentration Inequalities

Lecture 4A - Slide 35

UC Berkeley CS70 - Nikki Suzani

36 of 57

Law of Large Numbers

Lecture 4A - Slide 36

UC Berkeley CS70 - Nikki Suzani

37 of 57

Concentration Inequalities Exam Question

Lecture 4A - Slide 37

UC Berkeley CS70 - Nikki Suzani

38 of 57

Lecture 4A - Slide 38

UC Berkeley CS70 - Nikki Suzani

39 of 57

Concentration Inequalities Exam Question

Lecture 4A - Slide 39

UC Berkeley CS70 - Nikki Suzani

40 of 57

Lecture 4A - Slide 40

UC Berkeley CS70 - Nikki Suzani

41 of 57

LLN Exam Question

Lecture 4A - Slide 41

UC Berkeley CS70 - Nikki Suzani

42 of 57

Lecture 4A - Slide 42

UC Berkeley CS70 - Nikki Suzani

43 of 57

Markov Chains

Define aperiodic, irreducible

Lecture 4A - Slide 43

0.2

0.6

0.2

0.4

0.6

0.3

0.7

UC Berkeley CS70 - Nikki Suzani

44 of 57

Markov Chains Exam Question

Lecture 4A - Slide 44

Coin has probability p = ⅗ of landing heads.

UC Berkeley CS70 - Nikki Suzani

45 of 57

Lecture 4A - Slide 45

UC Berkeley CS70 - Nikki Suzani

46 of 57

Continuous Probability

Lecture 4A - Slide 46

UC Berkeley CS70 - Nikki Suzani

47 of 57

Continuous Probability

Lecture 4A - Slide 47

UC Berkeley CS70 - Nikki Suzani

48 of 57

Lecture 4A - Slide 48

UC Berkeley CS70 - Nikki Suzani

49 of 57

Exponential

Lecture 4A - Slide 49

UC Berkeley CS70 - Nikki Suzani

50 of 57

Exponential Exam Question

Lecture 4A - Slide 50

UC Berkeley CS70 - Nikki Suzani

51 of 57

Lecture 4A - Slide 51

UC Berkeley CS70 - Nikki Suzani

52 of 57

Uniform Exam Question

Lecture 4A - Slide 52

UC Berkeley CS70 - Nikki Suzani

53 of 57

Lecture 4A - Slide 53

UC Berkeley CS70 - Nikki Suzani

54 of 57

Central Limit Theorem

Lecture 4A - Slide 54

UC Berkeley CS70 - Nikki Suzani

55 of 57

CLT Exam Question

Lecture 4A - Slide 55

UC Berkeley CS70 - Nikki Suzani

56 of 57

Lecture 4A - Slide 56

UC Berkeley CS70 - Nikki Suzani

57 of 57

Good Luck!

I believe in you :))

Lecture 4A - Slide 57

UC Berkeley CS70 - Nikki Suzani