General Question

PhiNotPi's avatar

What is the average number of coin tosses required to flip both sides at least once?

Asked by PhiNotPi (12291 points ) August 2nd, 2011

On average, how many coin tosses in a row are required to flip both a heads and a tails at least once? For example the sequence HHTH required 3 flips, while the sequence THHT required 2 flips to get at least one tail and one head.

It is important to note that I said “on average.” If I left that out, the answer would be infinity. Since I did say “average”, you have to take into account the percentage of times that you expect each thing to happen.

Observing members: 0 Composing members: 0

32 Answers

msbcd's avatar

I agree with @RealEyesRealizeRealLies , it should be twice because each toss has a 50/50 chance.

PhiNotPi's avatar

@msbcd and @RealEyesRealizeRealLies Here is a short disproof of your answers
Say I throw the tosses HT, which is 2.
I then throw the tosses TH, which is 2
I then throw the tosses HHT, which is 3
(2 + 2 + 3) / (3 tosses) = an average of 2.33
There is nothing to bring the average down to two because you cannot flip both in less than two flips.

filmfann's avatar

3.
You flip the coin once, and it lands on either heads or tails.
Now, you have to flip and get the other side. The odds are 50/50.
Two more flips should take care of it, on average.

PhiNotPi's avatar

@filmfann How did you come to the conclusion that two more flips should take care of it on average? I’m not calling it right or wrong, I just want to understand your reasoning.

YoBob's avatar

Given a very large number of flips (approaching infinity) the average will be 2.

However, I’m guessing that for a smaller sampling the answer is slightly greater than 2.

Mariah's avatar

Hmmm…
In two flips you can either get HT, TH, TT, or HH. Since all these options are equally likely, you have a 50% chance of getting both sides in two flips.
In three flips you can get HHH, TTT, HHT, HTH, HTT, TTH, THT, THH. So you have a 75% chance of getting both sides.
So half of the time you’ll get to stop at two flips. In the other half of the time, you’ll have to flip again, and when that happens, you’ll get to stop there 3 times out of 4. So the only chance you’ll have to flip a fourth time is one fourth of one half, or one eighth.
What can you conclude from this? The chances of having to move on to each successive flip are 1/(2^n) where n is the number of flips. The series 1/(2^n) converges to 2 as n approaches infinity, so that is the answer. I think.

I think the reason the disproof you provided above is false is that you can lower the average of 2.33 because you can get a value of 2. Over time you’ll get 2 so often that, although some numbers will be higher than two, the sum will approach two.

woodcutter's avatar

the correct answer is four. I just played around with a piece of round money and that’s that.

PhiNotPi's avatar

@Mariah You can lower it, but you can never lower it back to exactly 2. In response to your criticism, I have formulated a new disproof, which I believe is far simpler.

50% of the time, you will need only two flips. You proved this yourself. That means that the other 50% of the time, you will need at least three flips.

For simplicity, I will assume that all flips that do not require 2 will only require 3. Even though some will require four in actuallity, that actually bumps the average up further and only strengthens my argument.

Since 50% require 2 and 50% require at least three, the average will be at least 2.5.

RealEyesRealizeRealLies's avatar

“That means that the other 50% of the time…”

There is no “other” 50% of the time. That would be considered a different set altogether.

The first 50% of the time is a whole unit of 100%.

RealEyesRealizeRealLies's avatar

All things equal, this question is like asking which side of a scale would weigh heavier on average if each side held 50lbs.

Mariah's avatar

No you can’t lower it to exactly two, but I was thinking it would approach 2. Most limits never reach “exactly” their value.

However, reading your further explanation, I am convinced. I think I see my error. I misconstrued the implications of the series’ convergence.
Okay, so ½ of the time the answer will be 2. ¾ of the other ½, or 3/8 of the time, it’ll be 3. 7/8 of the remaining 1/8 of the time, or 7/64 it’ll be 4. Etc.

So your answer is actually going to be the sum of the series (½)(2) + (3/8)(3) + (7/64)(4)...
We can get the answer by figuring out what that series converges to (if it does indeed converge…I would think it would). To do that, first we need to represent it in terms of n. I’ll work on that next, gimme a minute…

Mariah's avatar

Okay, I think the formula for that series is:

(2^n-1)/(2^n) * 1/(((n-1)^2+(n-1))/2) * (n+1)
Starting with n=1

(I’m sure that can be simplified)
It is going to be tricky to determine whether this series converges, and even more difficult to determine what value it converges to. But I’ll work on it. :P

Mariah's avatar

Oh, I made a mistake typing that out. The second denominator is supposed to be 2 raised to what I wrote.

It simplifies (fortunately)!
(2^n-1)/(2^n) * 1/(2^(n(n-1)/2) * (n+1)
Still messy, but lots better.

It’s still gonna be a bitch to completely answer your question though. Maybe I’ll write a program to approximate the sum of the series by doing it out to n=800 or something. Yeah, that sounds good….gimme another minute. XD

Mariah's avatar

Screw the program actually, this sequences vanishes so quickly that we’ll be able to get a very good approximation using only a small value of n. The fifth term of the sequence is approx .00567627. Calculating to n= 5, I got, get this… approx 2.64142. I seriously think this is going to converge on e…. how fucking awesome is that?!?

Mariah's avatar

Okay. Damn. It doesn’t appear to converge on e. I was so excited. XD

What it does appear to converge on is 2.641632561, and unfortunately that’s all the decimal places my calculator will display. I realized that TI83 can do the exact thing I was just talking about writing a program to do (d’oh) so I did it on my calculator, and no matter how high a value of n I input, it stays 2.641632561. That number seems extremely arbitrary….but, I think it is right. It’s not very satisfying though is it? XD

Zaku's avatar

The answer to the mean average is: two flips.

The second flip always has a 50% chance of being the opposite as the first flip, so 50% of the time, it takes two flips.

The other 50% of the time, it will take 3 or more flips, so the chances of getting the “one you still need to get” is half of the remaining chance each time, i.e. it is:

25% – 3 flips
12.5% – 4 flips
6.25% – 5 flips

That is, getting it on the second flip will happen half the time you try, while getting it on the third try will happen ¼ of the time, fourth try 1/8th of the time, etc.

However if you are looking for a fractional average, then I’ll defer to Mariah’s calculations.

RealEyesRealizeRealLies's avatar

This question is not answered by the number of potential flips.
It is answered by the number of potential sides of a coin.

Hexr's avatar

It would end up being 2. If you were to have millions of people flipping coins and counting all of their results, and found the average, it would be near 2. But the average itself is kind of meaningless, since to statistically analyse something like that with enough data would require a bell curve. This is a relatively basic statistical concept, but if you think of it in terms of another set of data which has more than 2 results, the answer is not so clear cut, and requires some formulation.

PhiNotPi's avatar

@Zaku You are thinking of the median, were there is 50–50 chance. With the set of numbers {2, 2, 2, 2, 3, 5,}, the mean would be 8/3, but the median would simply be 2.

Mariah's avatar

WAIT A MINUTE…..go look at my first reply again. I made a mistake, so my calculations…...are useless. D:

Look at the list of permutations for three flips that I provided. Some of them get both sides within the first two flips, so you wouldn’t have gone on to the third flip. therefore those permutations shouldn’t be included because they can’t happen, so you don’t actually get it in 75% of the third flips, it’s something else.

I’ll come back to this and solve it again after I’ve had breakfast. XD

Mariah's avatar

Okay. So.
In two flips you can get HT, TH, HH, TT. 50% chance.
You’ll only move onto the third flip if you get HH or TT. So the only permutations of three flips that make sense in the context of this problem are HHH, HHT, TTH, TTT. Again, a 50% chance. Not 75% as I said before (So the chances that you’ll need to move onto the fourth flip are 50% of 50% or 25%).
It’ll continue, forever, to be a 50% chance. This changes things significantly (actually makes them easier).

The actual series that answers your question is this:
(½)(2) + (¼)(3) + (1/8)(4)...
Because 50% of the time you’ll get both sides within 2 flips, 50% of the remaining 50% (25%) you’ll get it in 3, 50% of the remaining 25% you’ll get it in 4 flips (12.5%) etc.

So the formula that represents that series is:
(n+1)/(2^n) starting with n=1
SO much easier than the crap I was doing last night. XD

So what does that converge on?
Three. It converges on three.

The answer is three. I’m certain this time. :)

Mariah's avatar

Did a quick empirical test. Flipped a coin until I got both sides and wrote down how many tries it took. Repeated this 30 times. Here’s how the data stacks:

Took 2 tries 14 times (46.666…%, theoretically 50%)
3 tries 8 times (26.666…%, theoretically 25%)
4 tries 6 times (20%, theoretically 12.5%)
5 tries 2 times (6.666…%, theoretically 6.25%)
6 tries 0 times (0%, theoretically 3.125%)
All others 0 times
I got heads a total of 44 times and tails a total of 42 times, so the data seems pretty normal.
And the average number of flips required? 2.8666… flips (theoretically 3).
I think the data is pretty spot on considering the small sample size!

Maybe @woodcutter had the right idea all along! XD

gorillapaws's avatar

I just wrote a Monte Carlo Simulation app and simulated it 100 million times. The answer is 3. I am very certain of this.

gorillapaws's avatar

The code in C:

#import <stdio.h>

#define TRIAL_SIZE 100000000
#define HEADS 1
#define TAILS 0

int main( int argc, const char *argv[] )
{
long flipCount = 0;
bool isHeads;
bool isTails;

for( long i = 0; i < TRIAL_SIZE; i++ )
{
isHeads = false;
isTails = false;
while( (isHeads == false) || (isTails == false) )
{
flipCount++;
int theFlip = arc4random() % 2;

if( theFlip == HEADS )
{
isHeads = true;
}
else if( theFlip == TAILS )
{
isTails = true;
}
else
{
printf( “Error” );
}
}
}
double average = (double)flipCount / TRIAL_SIZE;
printf( “Average is %g”, average );

return 0;
}

gorillapaws's avatar

An interesting corollary, the most number of flips before getting both heads and tails in 100 million trials has been coming in the 26 – 29 range.

RealEyesRealizeRealLies's avatar

Actually, the answer to this question = 0. Since it can all be figured with math, then no actual coin tosses are necessary whatsoever.

flutherother's avatar

@Mariah I like your answer but my maths is a bit rusty. Where did that number 3 come from exactly? I understand your thinking up to the formula that represents the series but then I get stuck.

Mariah's avatar

@flutherother To do a more formal proof, I could have used other methods to determine the convergence of the series. However, I was lazy, so what I did was I used my TI83 calculator to calculate an approximation of the series. The TI83 can calculate a given series (if you tell it the formula, which is why I had to determine the formula in terms of n) on a range you specified. I think I told my calculator to calculate it on the range from n=1 to n=100 or something like that and my calculator spit out something like 2.99996 so I concluded that the limit was approaching 3.

flutherother's avatar

@Mariah OK, thanks, I am sure you are right, I will go with that. These probability questions can be so confusing.

PhiNotPi's avatar

I am also sure that the limit is three, I just summed up the first 100 terms and it is 2.9999… for a while. This is my attempt at how someone could prove that in math, since you can’t simply add up an infinite number of terms.
Each term has the form (x+1) / (2^x). I am going to separate this into x/(2^x) + 1/(2^x). If x is greater than one, I can continue to expand this into a series of 1/(2^x)‘s added together.

The series-
2/2 + ¾ + 4/8…
Can be expanded into-
½ + ½ + ¼ +¼ + ¼ + 1/8 +1/8 +1/8 +1/8…
I am now going to convert this to multiples of the series ½ + ¼ + 1/8… = 1

Take many copies of the the inverse-powers-of-two series-
½ + ¼ + 1/8…
½ + ¼ + 1/8…
½ + ¼ + 1/8…
½ + ¼ + 1/8…
½ + ¼ + 1/8
...
You will notice that all but 2 copies of the first term are crossed out, all but three of the second term, etc. If you sum up the columns, you will end up with the first sequence I started with. A very neat thing happens when I go back to that block and sum up the rows.
½ +¼ +1/8… = 1
½ +¼ +1/8… = 1
½ +¼ +1/8… = ½
½ +¼ +1/8… = ¼
½ +¼ +1/8… = 1/8
...
It is very clear that sums of rows is 2 + (½ + ¼ +1/8…) = 2 + 1 = 3

Answer this question

Login

or

Join

to answer.

This question is in the General Section. Responses must be helpful and on-topic.

Your answer will be saved while you login or join.

Have a question? Ask Fluther!

What do you know more about?
or
Knowledge Networking @ Fluther