1 of 34

Lecture 5D: �Concentration Inequalities

​

​

Lecture 5D - Slide 1

UC Berkeley CS70

Summer 2023

Nikki Suzani

2 of 34

How do we bound probabilities?

Lecture 5D - Slide 2

UC Berkeley CS70 - Nikki Suzani

3 of 34

Option 1: Markov’s Inequality

Dealing with the definition of expectation – looking at non-negative random variables.

Lecture 4A - Slide 3

UC Berkeley CS70 - Nikki Suzani

4 of 34

Option 1: Markov’s Inequality

​

\

​

Emphasis: Non-Negative Random Variable

Lecture 4A - Slide 4

UC Berkeley CS70 - Nikki Suzani

5 of 34

Markov’s Inequality Proof

Lecture 4A - Slide 5

UC Berkeley CS70 - Nikki Suzani

6 of 34

Markov’s Inequality Proof

​

Lecture 4A - Slide 6

UC Berkeley CS70 - Nikki Suzani

7 of 34

What happens if we know the (negative) lower bound?

Can we still use Markov’s?

Lecture 4A - Slide 7

UC Berkeley CS70 - Nikki Suzani

8 of 34

Coin Tosses Example

We toss a coin with probability ⅓ of being heads n times. What is the probability of getting more than 50% heads?

Lecture 4A - Slide 8

UC Berkeley CS70 - Nikki Suzani

9 of 34

Cheating Chess Players

Chess Professionals take an average of 5 trips away from the board during a standard chess game. What is an upper bound on the probability that Hans Niemann takes 25 trips away?

Lecture 4A - Slide 9

UC Berkeley CS70 - Nikki Suzani

10 of 34

More Chess Players

​

Chess Professionals take an average of 5 trips away from the board during a standard chess game. What is a bound on the probability that Magnus Carlsen takes less than 2 trips away?

​

Lecture 4A - Slide 10

UC Berkeley CS70 - Nikki Suzani

11 of 34

More Chess Players

​

Chess Professionals take an average of 5 trips away from the board during a standard chess game. What is a bound on the probability that Magnus Carlsen takes less than 2 trips away?

​

Lecture 4A - Slide 11

UC Berkeley CS70 - Nikki Suzani

12 of 34

When is Markov’s a tight bound?

Lecture 4A - Slide 12

UC Berkeley CS70 - Nikki Suzani

13 of 34

Generalized Markov’s Inequality

Lecture 4A - Slide 13

UC Berkeley CS70 - Nikki Suzani

14 of 34

Generalized Markov’s Inequality Proof

Lecture 4A - Slide 14

Let X be an indicator variable for |Y| meaning greater than or equal to c.

UC Berkeley CS70 - Nikki Suzani

15 of 34

Option 2: Chebyshev’s Inequality

Variance measures the deviation from the mean – can we use that information?

Lecture 4A - Slide 15

UC Berkeley CS70 - Nikki Suzani

16 of 34

Option 2: Chebyshev’s Inequality (Formally)

Lecture 4A - Slide 16

UC Berkeley CS70 - Nikki Suzani

17 of 34

Proof of Chebyshev’s Inequality

Lecture 4A - Slide 17

UC Berkeley CS70 - Nikki Suzani

18 of 34

Generalized Chebyshev’s Inequality

Lecture 4A - Slide 18

UC Berkeley CS70 - Nikki Suzani

19 of 34

Coin Tosses Again

Lecture 4A - Slide 19

We toss a coin with probability ⅓ of being heads n times. What is the probability of getting more than 50% heads?

​

UC Berkeley CS70 - Nikki Suzani

20 of 34

Let’s talk about estimation

Say we have a coin – but don’t know the probability it flips heads. How can we guess?

Lecture 4A - Slide 20

UC Berkeley CS70 - Nikki Suzani

21 of 34

Let’s talk about confidence

​

We can’t be sure that our estimate is good, though. So we want to bound the probability that we’re wrong.

Lecture 4A - Slide 21

UC Berkeley CS70 - Nikki Suzani

22 of 34

Estimating Probabilities

Let’s put it into practice. How many samples do we need to be confident?

Lecture 4A - Slide 22

UC Berkeley CS70 - Nikki Suzani

23 of 34

Estimating Probabilities

Let’s put it into practice. How many samples do we need to be confident?

​

Lecture 4A - Slide 23

UC Berkeley CS70 - Nikki Suzani

24 of 34

Estimating Probabilities

Lecture 4A - Slide 24

UC Berkeley CS70 - Nikki Suzani

25 of 34

Example: How many people play chess?

We want to estimate the percent of people in CS70 who play chess. Let’s say we want an error of 0.05, and confidence of 90%. How many people do I need to sample?

Lecture 4A - Slide 25

UC Berkeley CS70 - Nikki Suzani

26 of 34

What about estimating a value?

Lecture 4A - Slide 26

UC Berkeley CS70 - Nikki Suzani

27 of 34

What about estimating a value?

​

​

​

Upper or lower bound on μ?

​

Upper or lower bound on σ?

Lecture 4A - Slide 27

UC Berkeley CS70 - Nikki Suzani

28 of 34

Average Rating of Chess Players on Course Staff

Many people on CS70 Course Staff play chess. Some are… better than others. Let’s say our lower bound on the mean rating is 600, and our upper bound on variance is 100. We want to be 70% confident in our guess, with an error level of 0.05. How many people do we need to ask?

Lecture 4A - Slide 28

UC Berkeley CS70 - Nikki Suzani

29 of 34

When is Chebyshev’s a tight bound?

Lecture 4A - Slide 29

UC Berkeley CS70 - Nikki Suzani

30 of 34

The Law of Large Numbers

Intuition: We expect a random variable to converge to its average.

Lecture 4A - Slide 30

UC Berkeley CS70 - Nikki Suzani

31 of 34

The Law of Large Numbers (Formally)

Lecture 4A - Slide 31

UC Berkeley CS70 - Nikki Suzani

32 of 34

Proof of LLN

Lecture 4A - Slide 32

UC Berkeley CS70 - Nikki Suzani

33 of 34

(If time) Derivation of Variance of the Poisson

Let X ~ Poisson(λ). What is Var(X)?

​

Lecture 4A - Slide 33

UC Berkeley CS70 - Nikki Suzani

34 of 34

Recap

Learned about Concentration Inequalities:

  • Markov’s Inequality
    • Generalized Markov’s Inequality
  • Chebyshev’s Inequality
    • Confidence Levels!!

​

Learned about the Law of Large Numbers:

  • Proof using Chebyshev’s!

Lecture 4A - Slide 34

UC Berkeley CS70 - Nikki Suzani