Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Expected Tosses for Consecutive Heads with a Fair Coin

Date: 06/29/2004 at 23:35:35
From: Adrian
Subject: Coin Toss

What is the expected number of times a person must toss a fair coin 
to get 2 consecutive heads?  I'm having difficulty in finding the
probabilty when the number of tosses gets bigger. 

Here's my thinking:

1) You will only stop when the last two tosses are heads.
2) The random variable should be # of tosses


 # of tosses    1      2      3         4               5
 Prob           0   P(HH)  P(THH)  P(TTHH)+P(HTHH)   and so on....

However I get 2(1/4)+ 3(1/8) + 4(2/16) + 5(4/32) + ....

Am I doing something wrong here?



Date: 07/01/2004 at 19:23:53
From: Doctor Mitteldorf
Subject: Re: Coin Toss

Hi Adrian -


Your thinking is very good and clear.  But the calculation you have
set up is potentially infinite.  Sometimes that's ok, and you can get
very close with just the first few terms; in this case, you'll have to
go out past 20, taking 2^20 possibilities into account in order to get
a reasonably accurate number.  So we might look for a trick or 
shortcut.

In this case, the standard trick is "recursion".  Try to write the
probability after a certain number of flips in terms of itself.  Let's
let X = the expected count (the thing we're looking for).  Start the
way you started:

  X = [2(1/4) for HH] + [something for HT] + [something for TT]
    + [something for TH]

Here's how we can evaluate the "something" for HT.  There's a 1/4 
probability of getting there.  And once you've gotten there, you're 
exactly where you were when you started, except you've wasted 2 
flips.  So for that "something" I'm going to write (1/4)(X + 2).  The 
1/4 says that you have a 1/4 chance of flipping HT.  The (X + 2) says 
that we have the same expectation now as we did when we started (X) 
except that we've wasted two flips.

Similarly, the [something for TT] becomes another (1/4)(X + 2), just 
the same as HT.

The last term, TH, is a little trickier, because we're NOT in the same
position we started in, because we've got one H "in the bank".  We
have a 1/2 chance of getting another head on the 3rd flip, so that 
gives a contribution of (1/4)(1/2)(3).  We also have a 1/2 chance of 
getting a tail on the 3d flip, leaving us in the same position we 
started, except that we've wasted 3 flips now.  So that is 
represented by (1/4)(1/2)(X + 3).

Put all this together now to make an equation for X:

  X = 2(1/4) + (1/4)(X+2) + (1/4)(X+2) + (1/4)(1/2)3 + (1/4)(1/2)(X+3)

What I would do at this point is first to solve for X, and see if I
got a reasonable answer.  A reasonable answer is something bigger than
4 and smaller than 10.  Next, I wouldn't trust my abstract reasoning -
I'd go write a computer program to check the value that I got from the
algebra.

Will you let me know if this works out?

- Doctor Mitteldorf, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 07/01/2004 at 20:22:46
From: Doctor Anthony
Subject: Re: Coin Toss

Hi Adrian -

A difference equation is often useful here.

Let a = expected number of throws to first head.

We must make 1 throw at least and we have probability 1/2 of a head 
and probability 1/2 of returning to a, so

   a = (1/2)1 + (1/2)(1 + a)

   (1/2)a = 1

        a = 2.

Let E = expected number of throws to 2 consecutive heads.

Consider that we have just thrown a head and what happens on the next
throw.  We are dealing with the (a + 1)th throw, with probability 1/2
this is not a head and we return to E.

So  E = (1/2)(a + 1) + (1/2)(a + 1 + E)     

  (1/2)E = a + 1

       E = 2(a + 1)

and now putting in the value a = 2 we get  E = 2(3)  =  6

Expected throws to 2 consecutive heads is 6.

- Doctor Anthony, The Math Forum
  http://mathforum.org/dr.math/ 



Date: 07/03/2004 at 01:20:24
From: Adrian
Subject: Thank you (Coin Toss)

Thanks.  The answer is indeed 6.  I've got a simple C++ program to
show this... 

//------------------------------------
#include <iostream>
#include <cmath>
#include <ctime>
using namespace std;

int flips();

void main()
{	int result = 0;
	int i;
	srand(time(NULL));
	
	for (i = 1; i < 999999; i++)
		result += flips();

	cout << "Expected value = "<< result / i << endl;
}
	

int flips()
{	int i, j, counter;
	i = 0;
  j = rand() % 2;
	counter = 1;

	while ((i+j) != 2)
	{	i = j;
		j = rand() % 2;
		counter++;
	}
	return counter;
}
//---------------------------



Date: 07/03/2004 at 06:29:56
From: Doctor Mitteldorf
Subject: Re: Thank you (Coin Toss)

Dear Adrian,

Yes, 6 is the answer.  I'm glad to see that your instincts are like
mine--you'll believe it when it comes out of a computer program!

But the abstraction is worth something, too.  Infinite calculations
are inconvenient, so we often look for tricks that use recursion to 
cut the calculation short, and make it finite.  You're probably
familiar with the simplest, most standard trick for evaluating the sum

  S = 1 + 1/2 + 1/4 + 1/8 + 1/16 + ...  

The trick is to multiply the whole sum by 2.  You find that
 
  2S = 2 + 1 + 1/2  + 1/4 + 1/8 + 1/16 + ...

But this sum is identical to the original one, except for the 2 in 
front.  So you can write 2S = S + 2, and solve for S = 2, exactly.  
We're using a different trick, but the same idea, to evaluate the 
infinite sum for the expectation value that you asked about.

- Doctor Mitteldorf, The Math Forum
  http://mathforum.org/dr.math/ 
Associated Topics:
High School Probability
High School Sequences, Series

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/