1. ## Difficult probability question

The question:

Tom and Bob play a game by each tossing a fair coin. The game consists of tossing the two coins together, until for the first time either two heads appear when Tom wins, or two tails appear when Bob wins.

a) Show that the probability that Tom wins at or before the $\displaystyle n^{th}$ toss is $\displaystyle \frac{1}{2} - \frac{1}{2^{n + 1}}$

b) Show that the probability that the game is decided at or before the $\displaystyle n^{th}$ toss is $\displaystyle 1 - \frac{1}{2^{n}}$

My attempt:
I'm quite confused as to how to attempt this. I tried drawing a tree to get my head around it, but I'm sure I'm missing something obvious here. Any assistance would be most appreciated.

2. a) Try finding a pattern.

P(Tom wins at 1st toss) = P(2 heads) = $\displaystyle \left(\dfrac12 \times \dfrac12\right)$

P(Tom wins at 2nd toss) = P(first toss give a head and a tail, second toss gives two heads) = $\displaystyle \left[\left(\dfrac12 \times \dfrac12\right) + \left(\dfrac12 \times \dfrac12\right)\right] \times \left(\dfrac12 \times \dfrac12\right)$

P(Tom wins at 3rd toss) = P(1st Head/Tail, 2nd Head/Tail, 3rd 2 heads) = $\displaystyle \left[\left(\dfrac14\right) + \left(\dfrac14\right)\right] \times \left[\left(\dfrac14\right) + \left(\dfrac14\right)\right] \times \left(\dfrac14\right)$

You see the pattern? You're multiplying by [(1/2 x 1/2) + (1/2 x 1/2)] after each successive toss.

The probability that Tom wins at the 2nd toss, or the 1st toss is P(win 1st toss) + P(win 2nd toss)

Hence, P(win at or before nth toss) = Sum of all probabilities up to nth toss.

This is a geometric sum, with starting term 1/4, common ratio 1/2.

Spoiler:
Sum to n:

$\displaystyle S_n = \dfrac{a(1-r^n)}{1-r} = \dfrac{0.25(1-0.5^n)}{1-0.5} = \dfrac12\left(1-\dfrac{1}{2^n}\right) = \dfrac12 - \dfrac{1}{2.2^n} = \dfrac12 - \dfrac{1}{2^{n+1}}$

b) I'm afraid I don't quite understand what part b) is asking for... must be my english

EDIT: I think I understand, but not sure. If this means that the game ends at or before the nth term, that is either Tom or Bob wins, then you only multiply by two, since

P(either Tom or Bob wins at nth toss) = $\displaystyle \dfrac{1}{4(2^{n-1})} \times 2$

Spoiler:
The sum is multiplied by two, hence the answer above times two gives:

$\displaystyle 2S_n = 2\left(\dfrac12 - \dfrac{1}{2^{n+1}}\right) = 1 - \dfrac{1}{2^n}$

3. Thank you, I understand now.