18.5. Linearity of Expectation 787
Since the groups are chosen randomly, each soldier in the group has the disease
with probabilityp, and it is safe to assume that whether one soldier has the disease
is independent of whether the others do.
(a)What is the expected number of tests in Approach (2) as a function of the
number of soldiersn, the disease fractionp, and the group sizek?
(b)Show how to choosekso that the expected number of tests using Approach (2)
is approximatelyn
p
p.Hint:Sincepis small, you may assume that.1 p/k 1
and ln.1 p/ p.
(c)What fraction of the work does Approach (2) expect to save over Approach
(1) in a million-strong army of whom approximately 1 % are diseased?
(d)Can you come up with a better scheme by using multiple levels of grouping,
that is, groups of groups?
Problem 18.29.
A wheel-of-fortune has the numbers from 1 to2narranged in a circle. The wheel
has a spinner, and a spin randomly determines the two numbers at the opposite ends
of the spinner. How would you arrange the numbers on the wheel to maximize the
expected value of:
(a)the sum of the numbers chosen? What is this maximum?(b)the product of the numbers chosen? What is this maximum?Hint:For part (b), verify that the sum of the products of numbers oppposite each
other is maximized when successive integers are on the opposite ends of the spin-
ner, that is, 1 is opposite 2 , 3 is opposite 4, 5 is opposite 6,....
Problem 18.30.
LetRandSbe independent random variables, andfandgbe any functions such
that domain.f /Dcodomain.R/and domain.g/Dcodomain.S/. Prove thatf.R/
andg.S/are also independent random variables.
Hint:The eventŒf.R/Daçis the disjoint union of all the eventsŒRDrçforr
such thatf.r/Da.
Problem 18.31.
Peeta bakes between 1 and2nloaves of bread to sell every day. Each day he rolls