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

Probability · Lecture 46 of 76 · 10:06

Widgets and Crates

Study guide

What this lecture covers

This is a worked recitation problem applying the law of iterated expectations and the law of total variance to a random sum: a crate holds a random number N of boxes, each box holds a random number of widgets, and the problem finds the expectation and variance of the total number of widgets T. It is similar in structure to the stick-breaking problem covered earlier, but here the randomness is in how many terms are summed rather than in a nested interval.

After watching, you should be able to recognize when a quantity is a sum of a random number of independent, identically distributed random variables, and compute its mean and variance by conditioning on the number of terms.

Key ideas

Setup: T = X1 + X2 + ... + XN, where N (number of boxes) and each Xi (widgets per box) are independent, with E[Xi] = 10, Var(Xi) = 16, E[N] = 10, Var(N) = 16.
Condition on N to simplify: if N were a fixed number n, E[sum] = n * E[Xi] and Var(sum) = n * Var(Xi) follow directly from linearity of expectation and independence.
Law of iterated expectations gives the mean: E[T] = E[N] * E[Xi] = 10 * 10 = 100.
Law of total variance gives the variance: Var(T) = E[Var(T|N)] + Var(E[T|N]), where E[Var(T|N)] = E[N] * Var(Xi) = 160 and Var(E[T|N]) = (E[Xi])^2 * Var(N) = 1600, giving Var(T) = 1760.
Independence is essential: the simplification relies on the widget counts per box not depending on how many boxes there are.
Hierarchical conditioning: problems with a natural hierarchy (widgets inside boxes inside crates) are naturally solved by conditioning at each level and building up.

Before you watch

Watch the main lecture on iterated expectations and, ideally, the stick-breaking recitation problem, since this problem reuses the same two laws in a similar divide-and-conquer style.
Be comfortable with linearity of expectation and the variance formula for a sum of independent random variables.

Check your understanding

Why does conditioning on the number of boxes N make the problem tractable?
Derive E[T] = 100 using the law of iterated expectations.
Walk through both terms of the law of total variance calculation and explain what each one represents.
Why is independence between N and the Xi's necessary for these formulas to hold?

Vocabulary

crate (noun): A large box used to hold and transport many smaller items.
A crate holds a random number of boxes of widgets.
widget (noun): A general word for a small manufactured item or part, used in examples.
Each box holds a random number of widgets.
random sum (phrase): A total made by adding together a random, not fixed, number of terms.
T is a random sum of the widget counts across boxes.
law of iterated expectations (phrase): The rule that averaging a conditional expectation over all cases gives the overall expectation.
The law of iterated expectations gives the mean number of widgets.
law of total variance (phrase): A rule for splitting overall variance into two parts based on conditioning.
The law of total variance is needed for the variance of the total widget count.
hierarchical (adjective): Organized in levels, one inside another.
This is a hierarchical problem: widgets inside boxes inside a crate.
essential (adjective): Absolutely necessary for something to work.
Independence between N and the Xi's is essential for the formula.
linearity of expectation (phrase): The rule that the expectation of a sum equals the sum of the expectations.
Linearity of expectation gives E[sum] = n * E[Xi] for a fixed n.
independent (adjective): Not affected by, or related to, another variable.
N and each Xi are independent of each other.
identically distributed (phrase): Following the exact same probability pattern as other variables in a group.
The widget counts per box are identically distributed.
tractable (adjective): Possible to solve or manage without too much difficulty.
Conditioning on N makes the problem tractable.
build up (phrasal verb): To construct something gradually, step by step.
We build up the answer by conditioning at each level of the hierarchy.
divide-and-conquer (phrase): A strategy that solves a hard problem by breaking it into easier smaller pieces.
This problem is solved in a divide-and-conquer style.
structure (noun): The way parts of something are organized and related.
The problem has a natural hierarchical structure.
natural (adjective): Occurring in a normal, expected way, without being forced.
Widgets inside boxes inside crates form a natural hierarchy.
quantity (noun): An amount or number being measured or calculated.
T is the quantity we want the mean and variance of.
recognize (verb): To correctly identify something as a known type or pattern.
You should learn to recognize a sum of a random number of variables.
derive (verb): To work out a result step by step from known rules or facts.
We derive E[T] = 100 using the law of iterated expectations.
formula (noun): A fixed rule written with symbols that gives a result from given values.
The variance formula for a sum of independent variables is used here.
term (noun): One separate part of a sum or expression.
Each Xi is one term in the random sum.
apply (verb): To use a rule or method in a specific situation.
We apply the law of total variance to find Var(T).
depend on (phrasal verb): To be affected by, or to rely on, something else.
The widget counts don't depend on how many boxes there are.
setup (noun): The starting conditions and definitions of a problem.
The setup defines N, Xi, and their means and variances.
similar in structure (phrase): Having a matching shape or pattern to another problem.
This problem is similar in structure to the stick-breaking problem.
recitation problem (phrase): An example problem worked in a practice class to apply lecture ideas.
This is a worked recitation problem on random sums.

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: Jimmy Li

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

← The Variance in the Stick Breaking Problem · Using the Conditional Expectation and Variance →