ReformedCharacter wrote:If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses. How many coin tosses will Bob require on average, and why?
Spoiler...
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
As a preliminary exercise, let's work out why Alice averages 4 tosses. Her task can be broken down into two steps:
1) Toss a coin until she tosses a head. How many tosses does that take on average? Let's suppose the answer is T. We know that if the first toss is a head, she takes 1 toss, and if the first toss is a tail, she's basically still where she started, except that she's already taken one toss, and so her average number of tosses if the first toss is a tail is 1+T. So her overall average is 0.5 * 1 + 0.5 * (1+T) = 1 + 0.5T. But T is her overall average, so T = 1 + 0.5T, from which it follows that T = 2. So this first step takes 2 tosses on average.
2) Then toss a coin until she tosses a tail. By the same argument, except with heads and tails swapped, this also takes 2 tosses on average.
So the two steps take an average of 2+2 = 4 steps.
Bob has the same first step, but a different second step:
2') Toss a coin. If it is a head, he succeeds, in an average of T+1 = 3 tosses. If it is a tail, he goes back to the start of step 1, except that he has already used an average of T+1 = 3 tosses. Those two possibilities have a chance of 1/2 each, so if his average total number of tosses is B, his overall average number of tosses breaks down as 0.5 * 3 + 0.5 * (3+B) = 3 + 0.5B. So B = 3 + 0.5B, from which it follows that B = 6
So the answer is that Bob's average number of tosses is 6.
By the way, this is meant as a puzzle-level answer,
not a proper mathematical proof. The problem with it as a proper mathematical proof is that it assumes that T and B actually exist and are finite sums, or in mathematical parlance, that the infinite sums involved in the mathematical definitions concerned converge. One can get some very wrong conclusions from such arguments that ignore that issue - as a silly example:
Suppose S is the sum of the powers of 2 from 1 upwards, i.e. S = 1 + 2 + 4 + 8 + 16 + 32 + 64 + 128 + ...
Then 2S is the sum of the powers of 2 from 2 upwards, i.e. 2S = 2 + 4 + 8 + 16 + 32 + 64 + 128 + ...
By inspection, that says that 1 + 2S = S, from which it follows that S = -1!
Anyway, I haven't yet thought out whether there's a mathematically rigorous proof of Bob's average number of tosses is 6 that I can present reasonably succinctly on this board, without just asking people to take a lot of mathematical theorems on trust. So I'm making do with a puzzle-level answer. And incidentally, I am certain that the relevant infinite sums do have the appropriate convergence properties to make that puzzle-level answer correct - I'm just not certain I can demonstrate it in a way suitable for this board!
Gengulphus