Mathematics for Computer Science

Chapter 18 Random Variables786

Homework Problems

Problem 18.26.
Applying linearity of expectation to the binomial distributionfn;pimmediately
yielded the identity 18.13:

ExŒfn;pçWWD

Xn

kD 0

k

n

k

!

pk.1p/nkDpn: (*)

Though it might seem daunting to prove this equation without appeal to linearity, it
is, after all, pretty similar to the binomial identity, and this connection leads to an
immediate alternative algebraic derivation.

(a)Starting with the binomial identity for.xCy/n, prove that

xn.xCy/n^1 D

Xn

kD 0

k

n

k

!

xkynk: (**)

(b)Now conclude equation (*).

Problem 18.27.
A coin will be flipped repeatedly until the sequenceTTH(tail/tail/head) comes
up. Successive flips are independent, and the coin has probabilitypof coming up
heads. LetNTTHbe the number of coin flips untilTTHfirst appears. What value of
pminimizes ExŒNTTHç?

Problem 18.28.
(A true story from World War Two.)
The army needs to testnsoldiers for a disease. There is a blood test that accu-
rately determines when a blood sample contains blood from a diseased soldier. The
army presumes, based on experience, that the fraction of soldiers with the disease
is approximately equal to some small numberp.
Approach (1) is to test blood from each soldier individually; this requiresntests.
Approach (2) is to randomly group the soldiers intoggroups ofksoldiers, where
nDgk. For each group, blend thekblood samples of the people in the group,
and test the blended sample. If the group-blend is free of the disease, we are done
with that group after one test. If the group-blend tests positive for the disease, then
someone in the group has the disease, and we to test all the people in the group for
a total ofkC 1 tests on that group.