Discrete random variables: expectation, variance and the binomial, geometric and Poisson
Ten problems on discrete random variables: expectation and variance from a probability table, a fair die and Var(aX + b), the binomial probabilities and its mean and variance from indicators, linearity of expectation without independence in the matching problem, the geometric distribution and memorylessness, Poisson counts and the Poisson limit of the binomial, the laws of total expectation and variance, and the expected number of distinct examples in a bootstrap sample, with worked solutions and the mistakes of squaring the mean, dropping the binomial coefficient and adding probabilities that overlap.
Before you start
A discrete random variable is a number that comes out of a random experiment: the count of correct predictions in a batch, the number of retries before a request succeeds, the number of events in a minute. Its distribution is a list of values and their probabilities, and almost everything asked about it is a weighted sum over that list. Two facts do most of the work. Expectation is linear, ,E[X+Y]=E[X]+E[Y], whether or not X and Y are independent, which turns hard counts into sums of easy indicators. Variance is not linear, and the place it goes wrong is the place the squares are. These ten problems build the binomial, geometric and Poisson distributions from first principles, and end with the expected number of distinct examples in a bootstrap sample, the 63.2% behind bagging's out-of-bag estimate.
A discrete random variable X has a probability mass function p(x)=P(X=x) with p(x)≥0 and .∑xp(x)=1.
Expectation.,E[X]=∑xxp(x), and for any function ,g,.E[g(X)]=∑xg(x)p(x). In general ;E[g(X)]=g(E[X]); in particular .E[X2]=(E[X])2.
Linearity.,E[aX+b]=aE[X]+b, and E[X+Y]=E[X]+E[Y] for anyX and ,Y, independent or not.
Variance.,Var(X)=E[(X−E[X])2]=E[X2]−(E[X])2, and the standard deviation is its square root. .Var(aX+b)=a2Var(X). For independent X and ,Y,;Var(X+Y)=VarX+VarY; otherwise add .2Cov(X,Y).
Indicators. For an event ,A,IA=1 if A happens and 0 otherwise. E[IA]=P(A) and .IA2=IA.
Binomial:(n,p): the number of successes in n independent trials with success probability .p.P(X=k)=(kn)pk(1−p)n−k for ,k=0,…,n, where (kn)=k!(n−k)!n! counts the orders in which the k successes can occur.
Geometric:(p): the number of the trial on which the first success happens, P(X=k)=(1−p)k−1p for k=1,2,… Some books count the failures before it instead, which shifts everything by .1.
Poisson:(λ):P(X=k)=e−λλk/k! for ,k=0,1,2,…, a count of events that occur independently at an average rate λ per interval. The series ∑k≥0λk/k!=eλ makes the probabilities sum to .1.
Conditioning.E[X]=E[E[X∣Y]] and .Var(X)=E[Var(X∣Y)]+Var(E[X∣Y]).
Problems
·
X takes the values 0,1,2,3 with probabilities ,0.1,,0.3,0.4 and .0.2. Find ,E[X],,E[X2],Var(X) and the standard deviation.
·
X is the roll of a fair six-sided die. Find ,E[X],E[X2] and ,Var(X), and then E[2X+3] and .Var(2X+3).
··
A classifier labels 10 independent examples, each correctly with probability .0.8. Find the probability that exactly 8 are correct, the probability that at least 9 are, and the mean and variance of the number correct.
··
Show that a Binomial(n,p) variable has mean np and variance np(1−p) by writing it as a sum of indicators.
··
n≥2 letters are put into n addressed envelopes in a uniformly random order. Let X be the number that land in the right envelope. Find E[X] and .Var(X).
··
A request succeeds on each attempt with probability ,0.2, independently, and is retried until it succeeds. Let X be the number of attempts. Find ,E[X],,P(X>3), the probability of success within 3 attempts, and .P(X>5∣X>2).
··
Errors arrive in a log at an average of 3 per minute, as a Poisson count. Find the probability of no errors in a minute, of at most ,2, and of at least ,3, and show from the series that .E[X]=λ.
···
A rare label occurs with probability 0.002 per example, independently, in a batch of .1000. Compare the exact binomial probabilities of 0 and of 3 occurrences with the Poisson approximation, and say why the approximation works.
···
A fair die is rolled, and if it shows ,K, then K fair coins are flipped. Let X be the number of heads. Find E[X] and .Var(X).
···
A bootstrap sample draws n examples uniformly at random, with replacement, from a training set of .n. Find the expected number of distinct examples in it, evaluate it for ,n=10, and find the fraction it approaches as n grows.
Answers
,E[X]=1.7,,E[X2]=3.7,,Var(X)=0.81, standard deviation 0.9
,E[X]=1.7,,E[X2]=3.7,,Var(X)=0.81, standard deviation 0.9Check from the definition: .0.1(1.7)2+0.3(0.7)2+0.4(0.3)2+0.2(1.3)2=0.289+0.147+0.036+0.338=0.81.
Problem 2
X is the roll of a fair six-sided die. Find ,E[X],E[X2] and ,Var(X), and then E[2X+3] and .Var(2X+3).
E[X]=61+2+⋯+6=621=3.5Each face has probability .61.
E[X2]=61+4+9+16+25+36=691The same weights on the squares.
Var(X)=691−449=12182−147=1235About .2.917.
E[2X+3]=2(3.5)+3=10 and Var(2X+3)=4⋅1235=335Shifting by 3 moves every value and the mean together, so the spread is unchanged; scaling by 2 doubles every deviation and so multiplies their squares by .4.
,E[X]=3.5,,E[X2]=691,;Var(X)=1235;,E[2X+3]=10,Var(2X+3)=335≈11.67Check: 2X+3 takes the values ,5,7,…,15, and the mean of their squares minus 102 is .625+49+81+121+169+225−100=6670−100=335.
Problem 3
A classifier labels 10 independent examples, each correctly with probability .0.8. Find the probability that exactly 8 are correct, the probability that at least 9 are, and the mean and variance of the number correct.
X∼Binomial(10,0.8)A fixed number of independent trials with the same success probability.
P(X=8)=(810)(0.8)8(0.2)2=45⋅0.16777⋅0.04≈0.3020:(810)=(210)=45: the two errors can be any two of the ten examples.
P(X≥9)=(910)(0.8)9(0.2)+(0.8)10≈0.2684+0.1074=0.3758The events X=9 and X=10 are disjoint, so their probabilities add.
E[X]=np=8 and Var(X)=np(1−p)=10⋅0.8⋅0.2=1.6Problem 4 derives both.
,P(X=8)≈0.302,,P(X≥9)≈0.376,,E[X]=8,Var(X)=1.6Even at the mean, 8 correct happens less than a third of the time; the standard deviation is 1.6≈1.26 examples.
Problem 4
Show that a Binomial(n,p) variable has mean np and variance np(1−p) by writing it as a sum of indicators.
,X=I1+I2+⋯+In, where Ij=1 if trial j succeedsCounting successes is adding a 1 for each one.
,E[Ij]=1⋅p+0⋅(1−p)=p, so E[X]=npLinearity of expectation; no independence needed for this step.
,E[Ij2]=E[Ij]=p, so Var(Ij)=p−p2=p(1−p)An indicator is 0 or ,1, so it equals its square.
Var(X)=∑jVar(Ij)=np(1−p)The trials are independent, so the covariances are 0 and the variances add. This step does use independence.
,E[X]=np,Var(X)=np(1−p)The variance is largest at p=21 and is 0 at p=0 or ,1, when the outcome is certain.
Problem 5
n≥2 letters are put into n addressed envelopes in a uniformly random order. Let X be the number that land in the right envelope. Find E[X] and .Var(X).
X=I1+⋯+In with Ij=1 if letter j is in its own envelope, and P(Ij=1)=n1Each letter is equally likely to be in any of the n envelopes.
E[X]=n⋅n1=1Linearity holds even though the Ij are dependent: if n−1 letters are right, the last one must be.
E[IiIj]=P(both right)=n1⋅n−11 for i=jGiven letter i is right, letter j has n−1 envelopes left.
E[X2]=∑jE[Ij2]+∑i=jE[IiIj]=n⋅n1+n(n−1)⋅n(n−1)1=2Expand the square of the sum: n diagonal terms and n(n−1) ordered pairs.
E[X]=1 and ,Var(X)=2−12=1, for every n≥2Each pair has ,Cov(Ii,Ij)=n(n−1)1−n21>0, and the n(n−1) of them add exactly the n1 that the independent formula n⋅n1(1−n1) misses (Mistake 5).
Problem 6
A request succeeds on each attempt with probability ,0.2, independently, and is retried until it succeeds. Let X be the number of attempts. Find ,E[X],,P(X>3), the probability of success within 3 attempts, and .P(X>5∣X>2).
,P(X=k)=0.8k−1(0.2), so E[X]=∑k≥1k(0.8)k−1(0.2)=(1−0.8)20.2=5∑k≥1kqk−1=(1−q)21 is the derivative of the geometric series .∑qk=1−q1. In general .E[X]=p1.
P(X>3)=0.83=0.512X>3 means the first three attempts all failed.
P(X≤3)=1−0.512=0.488The complement: at least one success in three attempts.
P(X>5∣X>2)=P(X>2)P(X>5)=0.820.85=0.83=0.512X>5 is contained in ,X>2, so the intersection is .X>5.
,E[X]=5,,P(X>3)=0.512,,P(X≤3)=0.488,P(X>5∣X>2)=0.512Memorylessness: after two failures, the wait for success starts afresh, so the past attempts are no evidence that success is due.
Problem 7
Errors arrive in a log at an average of 3 per minute, as a Poisson count. Find the probability of no errors in a minute, of at most ,2, and of at least ,3, and show from the series that .E[X]=λ.
P(X=0)=e−3≈0.0498.λ0/0!=1.
P(X≤2)=e−3(1+3+29)=8.5e−3≈0.4232The three terms .k=0,1,2.
P(X≥3)=1−8.5e−3≈0.5768The complement, instead of an infinite sum.
E[X]=∑k≥1kk!e−λλk=λe−λ∑k≥1(k−1)!λk−1=λe−λeλ=λThe k=0 term is ;0; cancel k against k! and re-index with .j=k−1.
,P(0)≈0.0498,,P(X≤2)≈0.4232,,P(X≥3)≈0.5768,E[X]=3The same trick on E[X(X−1)]=λ2 gives :Var(X)=λ2+λ−λ2=λ: for a Poisson count, mean and variance are equal.
Problem 8
A rare label occurs with probability 0.002 per example, independently, in a batch of .1000. Compare the exact binomial probabilities of 0 and of 3 occurrences with the Poisson approximation, and say why the approximation works.
P(X=0)=0.9981000≈0.13506Binomial with ,n=1000,.p=0.002.
Poisson: 3!e−223=34e−2≈0.18045Agreement to about .0.1%.
Exact 0.13506 and ;0.18063; Poisson 0.13534 and 0.18045With ,p=λ/n,(1−nλ)n→e−λ and (kn)pk→k!λk as n→∞ with λ fixed: many trials, each rarely a success, give a Poisson count.
Problem 9
A fair die is rolled, and if it shows ,K, then K fair coins are flipped. Let X be the number of heads. Find E[X] and .Var(X).
Given ,K=k,,X∼Binomial(k,21), so E[X∣K]=2K and Var(X∣K)=4KProblem 4 with .p=21.
E[X]=E[2K]=23.5=1.75The law of total expectation, with E[K]=3.5 from Problem 2.
E[Var(X∣K)]=43.5=87The average spread within each value of .K.
Var(E[X∣K])=Var(2K)=41⋅1235=4835The spread of the conditional means, using .Var(K)=1235.
E[X]=1.75 and Var(X)=87+4835=4877≈1.604Using only the first term, ,87, would ignore the uncertainty in how many coins are flipped.
Problem 10
A bootstrap sample draws n examples uniformly at random, with replacement, from a training set of .n. Find the expected number of distinct examples in it, evaluate it for ,n=10, and find the fraction it approaches as n grows.
D=∑j=1nIj with Ij=1 if example j is drawn at least onceCount distinct examples one example at a time.
P(Ij=0)=(1−n1)nEach of the n independent draws misses example j with probability .1−n1.
E[D]=n(1−(1−n1)n)Linearity; the Ij are dependent, which does not matter for the mean.
:n=10:E[D]=10(1−0.910)≈10(1−0.3487)=6.513About 6.5 distinct examples out of 10 draws.
;E[D]=n(1−(1−n1)n);6.513 for ;n=10; the fraction tends to 1−e−1≈0.632.(1−n1)n→e−1. So each bootstrap sample leaves out about 36.8% of the training set, which bagging uses as a free validation set: the out-of-bag examples.
Where this goes wrong
1. E[X²] taken as (E[X])²
The expectation of a function is computed by putting the mean into the function.
E[X]=1.7 for the table of Problem 1Right so far.
“E[X2] is the square of the mean.”The step that causes the mistake: expectation does not pass through a square.
,E[X2]=1.72=2.89, so Var(X)=2.89−2.89=0A variance of 0 would mean X is always ,1.7, which it never is. ,E[X2]=∑x2p(x)=3.7, and .Var(X)=0.81. The gap between E[X2] and (E[X])2 is exactly the variance, so it is never negative.
2. Var(2X + 3) taken as 2 Var(X)
E[2X+3]=2E[X]+3 is linear, and the variance is expected to behave the same way.
Var(X)=1235 for a fair dieRight so far: Problem 2.
“Scaling by 2 doubles the variance, and the +3 drops out.”The +3 does drop out; the factor is what goes wrong.
Var(2X+3)=2⋅1235=635≈5.83Variance is in squared units: doubling every deviation from the mean multiplies every squared deviation by .4.,Var(2X+3)=335≈11.67, and the standard deviation, not the variance, doubles.
3. Binomial probability without the coefficient
The probability of one particular sequence of results is written down, and it looks like the answer.
10 independent examples, each correct with probability 0.8Right so far: Problem 3.
“Eight correct and two wrong has probability .0.88⋅0.22.”True for one specified pattern, such as the first eight right and the last two wrong.
P(X=8)=0.88(0.2)2≈0.00671There are (810)=45 patterns with exactly eight correct, each with that probability, so .P(X=8)=45×0.00671≈0.302. Without the coefficient, the eleven probabilities P(X=0),…,P(X=10) would not sum to .1.
4. Adding probabilities that overlap
Three tries at a 20% chance sounds like a 60% chance.
Each attempt succeeds with probability ,0.2, independentlyRight so far: Problem 6.
“Success within three attempts is success on the first, the second or the third.”Also right; the events are not disjoint, though.
P(X≤3)=0.2+0.2+0.2=0.6Adding counts the outcomes where two or three attempts would succeed more than once; with six attempts the same rule would give .1.2. Go through the complement: .P(X≤3)=1−0.83=0.488.
5. Variances of dependent indicators added as if independent
Problem 4 adds the variances of indicators, and the same move looks fine for the matching problem.
X=I1+⋯+In with Var(Ij)=n1(1−n1)Right so far: Problem 5.
“So Var(X) is n times that.”The step that causes the mistake: it needs the Ij to be uncorrelated, and they are not.
,Var(X)=1−n1, which is 0.75 for n=4Every pair has a positive covariance ,n(n−1)1−n21, and the n(n−1) ordered pairs add ,n1, so Var(X)=1 for every .n≥2. Linearity of expectation needs no independence; adding variances does.