Chapter 10: Brainteasers 363
probability of the next coin being tails and add this to
the product of the probability of an even number and
the probability of getting a head next:
pn=pn− 1(
1 −1
2 n+ 1)
+( 1 −pn− 1 )1
2 n+ 1.This becomes
pn=pn− 12 n− 1
2 n+ 1+1
2 n+ 1.Now we just have to solve this difference equation, with
the starting value that before any tossing we have zero
probability of an odd number, sop 0 =0. If we write
pn=an/(2n+1) then the difference equation foran
becomes the very simple
an=an− 1 + 1.The solution of this witha 0 =0isjustnandsothe
required probability is
pn=n
2 n+ 1.Two heads
When flipping an unbiased coin, how long do you have
to wait on average before you get two heads in a row?
And more generally, how long beforenheads in a row.
(Thanks to MikeM.)
Solution
It turns out that you may as well solve the general prob-
lem fornin a row. LetNnbe the number of tosses
needed to getnheads in the row. It satisfies the recur-
sion relationship
Nn=^12 (Nn− 1 +1)+^12 (Nn− 1 + 1 +Nn).