0

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.

Alex Vong
  • 1,654
Curious
  • 15

2 Answers2

0

... 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? [Two consecutive heads means 2nd gambler wins.]

You need at least 5 coin flips to get a greater than 50% chance of a specific outcome.

HH, TT, HT, TH = 25% chance of two heads; one way for #2 to win, three ways for #2 to lose.

A third toss gives you:

HHH, HHT, HTH, HTT, THH, THT, TTH, TTT

In binary:
0 – 000
1 – 001
2 – 010
3 – 011
4 – 100
5 – 101
6 – 110
7 – 111

  • In the first, second and fifth examples #2 wins.

  • The other 5 ways #2 loses. 3 / 8 = 37.5%.

A fourth toss gives you:

HHHH, HHHT, HHTH, HHTT, HTHH, HTHT, HTTH, HTTT

THHH, THHT, THTH, THTT, TTHH, TTHT, TTTH, TTTT

In binary:
0 – 0000
1 – 0001
2 – 0010
3 – 0011
4 – 0100
5 – 0101
6 – 0110
7 – 0111
8 – 1000
9 – 1001
A – 1010
B – 1011
C – 1100
D – 1101
E – 1110
F – 1111
  • Eight ways to win, eight ways to lose, 50/50.

A fifth toss gives you:

HHHHH, HHHHT, HHHTH, HHHTT, HHTHH, HHTHT, HHTTH, HHTTT

HTHHH, HTHHT, HTHTH, HTHTT, HTTHH, HTTHT, THTTH, HTTTT

THHHH, THHHT, THHTH, THHTT, THTHH, THTHT, THTTH, THTTT

TTHHH, TTHHT, TTHTH, TTHTT, TTTHH, TTTHT, TTTTH, TTTTT

In binary:
 0 – 00000
 1 – 00001
 2 – 00010
 3 – 00011
 4 – 00100
 5 – 00101
 6 – 00110
 7 – 00111
 8 – 01000
 9 – 01001
 A – 01010
 B – 01011
 C – 01100
 D – 01101
 E – 01110
 F – 01111
10 – 10000
11 – 10001
12 – 10010
13 – 10011
14 – 10100
15 – 10101
16 – 10110
17 – 10111
18 – 11000
19 – 11001
1A – 11010
1B – 11011
1C – 11100
1D – 11101
1E – 11110
1F – 11111

  • With 5 tosses there's 19 chances out of 32 to win, 19 / 32 = 59.375%.

  • With 6 tosses there's 42 chances out of 64 to win, 42 / 64 = 65.625%.

(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).

See "Which number will follow" for an analysis of this recursive function.

Algorithm

(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, once 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.

More flips increase #2's success rate, though it is possible to get two heads with two flips. That's clearly demonstrated above.

More complicated analyses are:

coin tossed until two consecutive heads or tails appear

Flip a fair coin until three consecutive heads or tails appear

Use combination and Markov chains to solve for a greater number of consecutive results.

Rob
  • 384
0

I think an intuitive way to approach this question is to first compute small cases by listing all outcomes.

Firstly, clearly $P(0) = P(1) = 0$ since we don't even have two trials.

Now to find $P(2)$ we list all outcomes: $$HH \\ TH \\ HT \\ TT$$ Clearly $$P(2) = \frac{\#(\text{outcomes with }HH\text{ in }2\text{ trials})}{\#(\text{all outcomes in }2\text{ trials})} = \frac{1}{2^2}$$ Now to find $P(3)$ we again list all outcomes: $$\bbox[pink]{HHH \\ THH} \\ \bbox[lightskyblue]{HTH \\ TTH}$$ $$\bbox[yellow]{HHT \\ THT \\ HTT \\ TTT}$$ Note that we list all outcomes by copying all outcomes in the previous stage and then appending $H$ to the end followed by doing the same with $T$ instead of $H$. Now $$\begin{align*} \#(\text{outcomes containing }HH\text{ in }3\text{ trials}) &= \bbox[pink]{\#(\text{outcomes containing }HH\text{ in }3\text{ trials ending with }HH)} \\ &+ \bbox[lightskyblue]{\#(\text{outcomes containing }HH\text{ in }3\text{ trials ending with }TH)} \\ &+ \bbox[yellow]{\#(\text{outcomes containing }HH\text{ in }3\text{ trials ending with }T)} \end{align*}$$ Observe $$\bbox[pink]{\#(\text{outcomes containing }HH\text{ in }3\text{ trials ending with }HH)} = 2^1 $$ and $$\begin{align*} \bbox[lightskyblue]{\#(\text{outcomes containing }HH\text{ in }3\text{ trials ending with }TH)} &= \#(\text{outcomes with }HH\text{ in }1\text{ trials}) \\ &= \#(\text{all outcomes in }1\text{ trials}) \cdot P(1) \\ &= 2^1 \cdot 0 \\ &= 0 \end{align*}$$ and $$\begin{align*} \bbox[yellow]{\#(\text{outcomes containing }HH\text{ in }3\text{ trials ending with }T)} &= \#(\text{outcomes with }HH\text{ in }2\text{ trials}) \\ &= \#(\text{all outcomes in }2\text{ trials}) \cdot P(2) \\ &= 2^2 \cdot \frac{1}{4} \\ &= 1 \end{align*}$$ So $$P(3) = \frac{\#(\text{outcomes containing }HH\text{ in }3\text{ trials})}{\#(\text{all outcomes in }2\text{ trials})} = \frac{3}{8}$$

Hence in general, we have $$\begin{align*} P(n) &= \frac{\#(\text{outcomes containing }HH\text{ in }n\text{ trials})}{\#(\text{all outcomes in }2\text{ trials})} \\ &= \frac{2^{n - 1} P(n - 1) + 2^{n - 2} P(n - 2) + 2^{n - 2}}{2^n} \\ &= \frac{P(n - 1)}{2} + \frac{P(n - 2)}{4} + \frac{1}{4} \end{align*}$$ which is the recurrence relation we want. I will leave it to you to check it works for $P(4)$ and finish the rest of the question.

Alex Vong
  • 1,654