Seyed Masoud Hosseini · Overview · Study log · Weekly summaries · Ideas · Search · Transcript · RSS feed

Probability · Lecture 67 of 76 · 10:45

Probability Bounds

Probabilty Bounds on YouTube

Study guide

What this lecture covers

This problem bounds the probability that the sum of ten independent uniform(0,1) random variables exceeds 7, using three progressively more informative techniques: the Markov inequality, the Chebyshev inequality, and the central limit theorem. It shows concretely how each method uses more information about the distribution to produce a tighter bound on the same probability.

It draws directly on the Markov and Chebyshev inequalities and the central limit theorem developed earlier in the course. After watching, you should be able to apply all three techniques to the same tail-probability problem and explain why they give progressively tighter results.

Key ideas

  • Setup: X = X1 + ... + X10, each Xi uniform on [0,1], independent; the goal is bounding P(X >= 7), where E[X] = 5.
  • Markov inequality bound: using only E[X] = 5, P(X >= 7) <= E[X]/7 = 5/7, a loose bound.
  • Chebyshev inequality bound: rewriting the event as a two-sided deviation from the mean and using the symmetry of the sum around 5, plus the variance Var(X) = 10/12, tightens the bound to 5/48, roughly 0.10.
  • Central limit theorem bound: standardizing X and treating it as approximately standard normal gives P(X >= 7) ~ 1 - Phi(2.19) ~ 0.014, far tighter than either inequality-based bound.
  • More information yields tighter bounds: each method uses progressively more distributional information (mean only, then mean and variance, then an approximation to the full shape), and the bounds improve accordingly, from 0.71 to 0.10 to 0.014.
  • Concentration around the mean: the shrinking bounds illustrate that the sum of even a modest number of independent random variables concentrates fairly tightly around its expected value.

Before you watch

  • Review the Markov and Chebyshev inequalities and the central limit theorem from the earlier lectures in this unit.
  • Be comfortable computing the mean and variance of a uniform random variable and of a sum of independent random variables.

Check your understanding

  1. Why does the Chebyshev bound require rewriting P(X >= 7) as a two-sided deviation from the mean before it can be applied?
  2. Why does using the central limit theorem produce a tighter bound than Chebyshev's inequality in this example?
  3. What does the progression from 5/7 to 5/48 to about 0.014 tell you about how much information each bounding method uses?
  4. Why is the symmetry of the uniform distribution around its mean important for the Chebyshev calculation here?

Vocabulary

tail probability (phrase)
The chance that a variable takes an extreme, far-from-average value.
We bound the tail probability that the sum exceeds 7.
progressively (adverb)
Step by step, becoming more so over time.
The bounds get progressively tighter with each method.
loose bound (phrase)
An estimate that allows for a wide range, not very precise.
The Markov inequality gives a fairly loose bound.
tighten (verb)
To make a range or estimate narrower and more precise.
The Chebyshev inequality tightens the bound further.
two-sided deviation (phrase)
A distance from the mean measured in both directions, above and below.
We rewrite the event as a two-sided deviation from the mean.
concentration (noun)
The tendency of a random variable to stay close to a particular value.
The tightening bounds show strong concentration around the mean.
symmetry (noun)
A balanced shape that looks the same on both sides of a center point.
The symmetry of the uniform distribution simplifies the calculation.
Markov inequality (phrase)
A rule that bounds the probability of a large value using only the mean, for non-negative variables.
The Markov inequality uses only E[X] = 5 to get a loose bound.
Chebyshev inequality (phrase)
A rule that bounds the probability of being far from the mean using the variance.
The Chebyshev inequality tightens the bound to 5/48.
central limit theorem (phrase)
The result that the sum of many independent random variables looks approximately normal.
The central limit theorem gives the tightest bound in this comparison.
bound (noun)
A limit placed on how large or small a probability or value can be.
Each method gives a different bound on the same probability.
standardize (verb)
To rescale a variable to have mean 0 and standard deviation 1.
We standardize X before applying the central limit theorem.
informative (adjective)
Giving useful details that help understand something better.
The Chebyshev inequality is more informative than the Markov inequality.
exceed (verb)
To be greater than a certain value.
We bound the probability that X exceeds 7.
approximate (verb)
To estimate a value that is close to, but not exactly, the true one.
The central limit theorem lets us approximate X as normal.
concrete (adjective)
Specific and clear, not vague or general.
This is a concrete numerical comparison of three bounding methods.
roughly (adverb)
Approximately, not exactly.
The Chebyshev bound is roughly 0.10.
distributional information (phrase)
Details about the shape or spread of a probability distribution.
Each method uses more distributional information than the last.
draw on (phrasal verb)
To use knowledge or results from earlier material.
This problem draws directly on inequalities developed earlier in the course.
modest (adjective)
Fairly small or moderate in size.
Even a modest number of independent variables concentrates around its mean.
technique (noun)
A specific method used to solve a type of problem.
The lecture applies three separate bounding techniques.
comparison (noun)
An examination of how two or more things differ or are alike.
The lecture makes a direct comparison of the three bounds.
sum (noun)
The total obtained by adding numbers together.
X is the sum of ten independent uniform random variables.
rewrite (verb)
To express something again in a different but equivalent form.
We rewrite the event as a two-sided deviation before applying Chebyshev.
shrinking (adjective)
Becoming smaller over successive steps.
The shrinking bounds go from 0.71 down to 0.014.

Chapters

From the YouTube description

MIT 6.041SC Probabilistic Systems Analysis and Applied Probability, Fall 2013
View the complete course: http://ocw.mit.edu/6-041SCF13
Instructor: Kuang Xu

License: Creative Commons BY-NC-SA
More information at http://ocw.mit.edu/terms
More courses at http://ocw.mit.edu

← Lecture 20: Central Limit Theorem · Using the Central Limit Theorem →