## Odd coin problem

Posted by Chris on February 22, 2011 – 7:50 pm

On average, how many times do you need to flip a fair coin before you have seen a run of an odd number of heads, followed by a tail?

i.e. you only stop flipping when you have seen any of 1H1T or 3H1T or 5H1T or … all the way to infinity. e.g. HT, THT, HHHT, HHTTTHHHT are possible runs (you stop on the last T).

February 23rd, 2011 at 11:14 am

3/2

February 23rd, 2011 at 11:35 am

overlook many cases, new guess is e

February 23rd, 2011 at 3:56 pm

Odd = number of Heads in a row (1,3,5,…)

Even = number of Heads in a row (0,2,4,…)

If there are an Even number of Heads and we get a Tail, then the number of Heads is essentially 0 (we start over).

Odd = 1 + 1/2 Even

Even = 1 + 1/2 Even + 1/2 Odd

Is this the right track?

February 23rd, 2011 at 4:39 pm

I’ll tell you that the official answer is 6 flips. I regard this problem as being very difficult.

February 23rd, 2011 at 4:42 pm

Are you sure Chris? I think it is 7…

February 23rd, 2011 at 5:06 pm

OK, I agree – as usual when it is up to computations I make mistakes. 6 it is! Then the sum \sum(n=1 to infinity) n*f(n)/2^n =10, where f(n) are the Fibonacci numbers.

February 23rd, 2011 at 5:18 pm

Hi slavy. I can’t tell you how relieved I am that you agree I was going to allow the use of computers to confirm the result.

I had no idea that the Fibonacci numbers would crop up with this problem. The argument I’ve seen must be very different from the one you’ve used. I might well be asking if you could post your full reasoning.

The argument that I’d seen was fairly simple sounding, but it took every gram of my grey matter and intuition to be able to accept it.

I’ll try to post what I know tomorrow. It’ll include some stuff that I had tried (I think Markov Chains) that might be irrelevant. But when I did that, I had misinterpreted the question.

February 24th, 2011 at 2:28 am

Hi Chris. I use the same idea as you for computing the expectation – the recursive one, proposed by luv2fap. However, there is a nice combinatorial representation of the probability to succeed in exactly k flips. It leads to this infinite sum, which of course I can’t immediately find. But, since we already know the answer in advance, we can conclude what the sum should be

February 24th, 2011 at 7:33 am

This is a very slightly edited of what I’d done on the old ToM site. It’s also partly why I didn’t find the time to try the “Coin Toss” problem i.e. I didn’t know what to do with the result that follows and by the time I’d worked the following out, my brain was hurting too much. I’m pretty sure that this sort of thing is called a “Markov Chain”.

Let H[n] be the average number of flips needed to get n heads in a row. Now consider ourselves to have just got n-1 heads in a row. That has on average taken H[n-1] flips. Let p be the probability of throwing a head. I’ll substitute p = 1/2 at the end. On the next flip, there is a 1-p probability of throwing a tails; then the run is broken and we’ve used H[n-1]+1 throws and we’ve got H[n] throws to go to finish, on average. There is a probability p that we throw a heads; then we’ll have got our n heads in a row and it will have taken H[n-1]+1 throws to achieve that. So that gives us

H[n] = (1-p)*(H[n-1]+1+H[n]) + p*(H[n-1]+1)

So H[n](1-(1-p)) = H[n-1]((1-p) + p)) + (1-p) + p =>

H[n] = (H[n-1]+1))/p. To get this into closed form, start at n=1.

H[0] = 0 and hence H[1] = 1/p, then H[2] = (1/p + 1)/p = (1+p)/p^2,

H[3] = ((1+p)/p^2 + 1)/p = (1 + p + p^2)/p^3.

Continuing => H[n] = (1 + p + p^2 +…+ p^(n-1))/p^n.

Luckily, I spot a well known series.

Let Sn = 1 + p + p^2 + p^3 + … + p^(n-1) {n terms altogether}

Then p*Sn = p + p^2 + p^3 +…+ p^(n-1) + p^n

= 1 + p + p^2 + p^3 +…+ p^(n-1) + p^n – 1

= Sn + p^n – 1

Solving for Sn => Sn = (1 – p^n)/(1-p)

So H[n] = ((1-p^n)/(1-p))/p^n = (p^(-n)-1)/(1-p)

Substitute p = 1/2 => H[n] = 2^(n+1) – 2 = 2(2^n – 1)

In light of the “Three Dice” and “Coin Toss” problems I can’t help but notice:

H[n] = (1-p)*(H[n-1]+1+H[n]) + p*(H[n-1]+1) =>

H[n]= 1 + H[n-1] + (1-p)*H[n], and that sure looks like I should have been able to write it down immediately.

February 24th, 2011 at 7:52 am

The official solution. I have nicked this straight from the old ToM site. I don’t realy understand it (yet). I believe (thanks to slavy’s confirmation of the result) that it must be correct.

First consider the probability of throwing an odd number of heads followed by a tail. The probability of doing that is:

P(HT)+P(HHHT)+ P(HHHHHT)+ … = (1/2)^2 + (1/2)^4 + (1/2)^6 + …

= 1/(1-(1/2)^2) – 1 (using 1/(1-a) = 1 + a^2 + a^3 + … for |a| < 1)

= 1/3

So, on average, it will require three such attempts; however, we want to count flips, not attempts. Now for the bit that I really don't understand (later: but it’s growing on me )- for each H or T, we need on average 2 flips to get it. So we need 2*3 = 6 flips.

February 24th, 2011 at 7:56 am

How about the easier formula H=(1/2)*(H+1)+(1/4)*2+(1/4)*(H+2), where H is the expected number of flips? I should not be the one to explain it, since I am borrowing the method from luv2fap, but I will, anyway. Let the expected number of tosses be H. Then, if on the first flip we got T, then we “wasted” one flip, and due to the independence of the tosses, we again expect to stop flipping after H turns (the probability of flipping a T is 1/2). Now, if we managed to flip an H, we need to examine the second toss more carefully. In case of a T – we are done and we used exactly 2 flips (the probability, however, to have HT is 1/4 and this is why we multiply 2 by it). In case of an H – we are back to square 1 having wasted 2 flips and expecting to be done after H flips. The probability for HH is 1/4, again.

February 24th, 2011 at 8:21 am

Now, what I had in mind for computing the infinite sum: The standard formula for the mathematical expectation of a (discrete) random variable X is: E(X)=\sum(n from 1 to infinity) n*P(X=n), where P is the probability measure. Now we can try to compute P(X=n). Since we have 2^n different “words” of length n (for example, when n=2 we have TT, HT, TH, HH) P(X=n)=a(n)/2^n, where a(n) is the exact number of n-lettered words that finnish at odd heads and then a tail and for which this does not appear before (in simple words this is the case, when we are done exactly on the n-th flip). Obviously a(1)=0 (we need at least one H and at least one T and there is no chance to achieve it in a one-letter word). a(2)=1 (HT). For the others, analogously to the recursive argument in the formula from the previous post, we have a(n)=a(n-1)+a(n-2). Indeed, if we take each element from a(n-1) and put an extra letter T at its beginning, we obtain a legitimate member of a(n). Moreover, every member of a(n) that start with T can be obtained by this procedure exactly once! Now, take a member of a(n) that starts with H. The second letter should be H again, otherwise HT is a “finishing” combination and we should stop and n=2 – contradiction. But a word HH….. belongs to a(n) if and only if the remaining part ….. belongs to a(n-2). This establishes our recursive argument, and since a(1)=0 and a(2)=1, we derive by induction a(n)=f(n-1), where f(n-1) is the corresponding Fibonacci number.

Now we have several observations. First, since our random variable X=”#flips” possesses only natural values, we need \sum(n=1 to infinity) P(X=n) =1, so in other words \sum (n=1 to infinity) f(n)/2^(n+1)=1 (This is already some nice, probably nontrivial result). THen 6=E(X)=\sum(from 1 to infinity) (n+1)f(n)/2^{n+1}, and due to the first remark, when we split the samo into two sums and replace the second one with its answer 1, we obtain \sum(from 1 to infinity) n*f(n)/2^{n+1}=5. Finally, by multiplying by 2 we derive the formula I mentioned in post #6

February 24th, 2011 at 8:48 am

Hi slavy. Thanks for posting, especially post 11 (as it continues a theme). I was going to have a bash at doing it that way using my newly acquired skills. But I suspect that it was still going to hurt my brain at least a little bit.

I see that after a trivial spot of manipulation, we get H = 6 as required.

February 24th, 2011 at 8:55 am

No problem By the way, at least at a first glance without writing anything down, the case of even (but positive) number of Heads, followed by a Tail looks more chalenging. Maybe someone will give it a try? I believe I can get the answer but in a more complicated manner.