Chapter 18 Random Variables780
H T
A
C
B C
H T
B
T H
Figure 18.10 Outcome Tree for Flipping Until HH or TTProblem 18.16.
A coin with probabilitypof flipping Heads and probabilityqWWD 1 pof flipping
tails is repeatedly flipped until two consecutive flips match—that is, until HH or
TT occurs. The outcome tree,A, for this setup is illustrated in Figure 18.10.
Lete.T/be the expected number of flips starting at the root of subtreeTofA.
So we’re interested in findinge.A/.
Write a small system of equations involvinge.A/;e.B/, ande.C/that could be
solved to finde.A/.You donotneed to solve the equations.
Homework Problems
Problem 18.17.
We are given a random vector ofndistinct numbers. We then determine the maxi-
mum of these numbers using the following procedure:
Pick the first number. Call it thecurrent maximum. Go through the rest of the
vector (in order) and each time we come across a number (call itx) that exceeds
our current maximum, we update the current maximum withx.
What is the expected number of times we update the current maximum?
Hint:LetXibe the indicator variable for the event that theith element in the
vector is larger than all the previous elements.