Alice and Bob toss coins

[ReformedCharacter]

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?

RC

[psychodom]

Intuitively you might think the expected number of tosses for HH (2 Heads in a row) is the same as HT (Head then Tails), since the probability of HH and HT with 2 tosses is both 1/4.
However, observe that whilst Alice and Bob both require an initial Head, if Alice flips a second Head she is no nearer or further from achieving HT, but if Bob flips a Tail on his second coin then he has reset back to requiring 2 further Heads to achieve his goal.
With that in mind we can assume that the answer is not going to be 4.

spoiler
.
.
.
.
.
.
.
.
.
.



Let X be the number of coin flips that you need to get 2 heads in a row
We want to calculate E(X), the expected number of flips required.

Let E(X|H) denote the number of remaining flips required given you've just flipped a Head,
and similarly
E(X|H) denote the number of remaining flips required given you've just flipped a Tail

Then
E(X) = 1/2(1 + E(X|H)) + 1/2(1 + E(X|T))

if we flipped a tail on the first try then we are no closer to achieving 2 Heads in a row, therefore

E(X|T) = E(X)

Similarly we can split E(X|H) as:

E(X|H) = 1/2(1 + E(X|HH)) + 1/2(X|HT))

and again observe that

E(X|HT)) = E(X) (a Head then Tail means we have to start over on progressing towards 2 Heads in a row)

also observe that

E(X|HH) = 0 (no more flips are required!)

these give us 2 simultaneous equations:
E(X) = 1/2(1 + E(X|H)) + 1/2(1 + E(X))
E(X|H) = 1/2(1 + 0) + 1/2(1+ E(X))

E(X) = 1/2(1 + (1/2 + 1/2(1 + E(X))) + 1/2 + 1/2(E(X))
= 3/2 + 3/4(E(X))
= 12/2
= 6

Expected number of tosses to achieve 2 heads in a row is 6.

-Dom

[Gengulphus]

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

[jfgw]

I disagree with the answer above and believe it to be 4. I hope to give an explanation when I get home late tonight.

Julian F. G. W.

[Gengulphus]

I disagree with the answer above and believe it to be 4. I hope to give an explanation when I get home late tonight.

Well, to try to save you some wasted effort...

Obviously Bob has to take at least two tosses. The only sequence that gives him precisely 2 tosses is HH, which happens 1 time in 4.

The only sequence that gives him precisely 3 tosses is THH, which happens 1 time in 8.

The only sequences that give him precisely 4 tosses are TTHH and HTHH, which happen 2 times in 16.

The only sequences that give him precisely 5 tosses are TTTHH, THTHH and HTTHH, which happen 3 times in 32.

Together, those happen 19 times in 32, so 13 times in 32 he takes 6 tosses or more.

So his average number of tosses is at least 1/4 * 2 + 1/8 * 3 + 2/16 * 4 + 3/32 * 5 + 13/32 * 6 = (16+12+16+15+78)/32 = 137/32 > 4.

Incidentally, it's easy to see that the sequences that give him precisely N+1 tosses are T followed by any sequence that gives him precisely N tosses, or H followed by any sequence that starts with T and gives him precisely N tosses. From that, it's not difficult to see that there are F(N-1) sequences that give him precisely N tosses, where F(i) is the well-known Fibonacci sequence, defined by F(0) = 0, F(1) = 1, F(i) = F(i-2) + F(i-1) for i >= 2.

So the term N in the infinite sum that adds up to the answer is (F(N-1)/2^N) * N. (If one strictly follows the above argument, the sum starts with N=2, which produces a bit of confusion about term 2 being the first term - but since term 1 calculated by that formula is zero one can equally well start the sum with term 1 and have the less confusing situation of term 1 being the first term!)

And so the previous arguments say that the value of the infinite sum of (F(N-1)/2^N) * N from N=2 (or 1, or indeed 0) upwards is 6 - assuming it exists at all!

Gengulphus

[jfgw]

That makes sense, thanks.

I have resolved the source of my confusion. For a given number of coin tosses, the sequence is more likely to contain at least one HT sequence than at least one HH sequence. However, multiple HH sequences are disproportionately more likely than multiple HT sequences. For a large number of coin tosses, HH and HT are likely to occur approximately equally.

Julian F. G. W.

[UncleEbenezer]

Meanwhile, if Guildenstern tosses a coin until he sees a single tails, what is his average number of tosses?