Two gamblers have an argument. The first one claims that if a fair coin is tossed
repeatedly, getting two consecutive heads is very unlikely. The second, naturally, is
denying this.
They decide to settle this by an actual trial; if, within n coin tosses, no two consecutive
heads turn up, the first gambler wins.
(a) What value of n should the second gambler insist on to have more than a 50%
chance of winning?
(b) In general, let P (n) denote the probability that two consecutive heads show up
within n trials. Write a recurrence relation for P (n).
(c) Implicit in the second gambler’s stand is the claim that for all sufficiently large n,
there is a good chance of getting two consecutive heads in n trials; i.e. P (n) > 1/2.
In the first part of this question, one such n has been demonstrated. What
happens for larger values of n? Is it true that P (n) only increases with n? Justify
your answer.
