Fog Creek Software
Discussion Board




painfully easy

I think the solution given in the tech interview site is wrong.
You have two coins, you flip both, you say one of them came up heads.
The chance that the other came up heads is 50% (not 33%).

Let's see the scenarios:

BEFORE knowing that one of the coins came up heads you have the following possibilities:

TT
TH
HT
HH

but, AFTER  knowing that, the scenarios are only 2:

HT
HH

Each one has a 50% of probability.

It is the same as having two different flips of the same coin and calculating the chances of a given result on the second launch after the first launch (you know the result of the first launch).

michele
Tuesday, June 29, 2004

Knowing "one" of the coins came up heads narrows it down to THREE choices:

H T
T H
H H

The only choice eliminated is T T.

You don't know whether it is coin 1 or coin 2 that came up heads.

So in the above 3 choices, the "other" coin is only heads in 1 case, so 1/3.

Brad Corbin
Tuesday, June 29, 2004

I'm not convinced.

The question is:

- you have two coins.
- one of them came up heads (and you can forget about it)
- what about the probability of having a heads also on the second coin?

Scenarios (you have to examine just 1 coin, not 2, the one came up heads is given, it doesn't matter which was, if the 1 or the 2):

H
T

So 50%.

michele
Tuesday, June 29, 2004

You're making the mistake of thinking of HT and TH as the same outcome when it isn't.

Flip two coins, here's the potential outcomes

H H
H T
T H
T T

One of the coins is heads.  That removes T T and leaves

H H
H T
T H

You say that H T and T H are the same, but that's two different scenarios. You can see the difference if you put some probabilities on the outcomes.

H H  25%
H T  25%
T H  25%
T T  25%

Now we know it isn't T T, leaving

H H 33%
H T 33%
T H 33%

But you're saying it's

H H 50%
H T 50%

And there's the difference.  If that doesn't shed enough light on the answer start flipping two coins and write down the outcomes.  20 - 40 flips should be sufficient to get the odds to even out enough.

Lou
Tuesday, June 29, 2004

Guys, I know that TH and HT are different (and, by the way, this is why flipping two coins is more probable to obtain one T and one F than TT or HH, 50% vs 25%). My point is that you have to guess the result of ONLY ONE COIN (the original question was "what is the chance that the other coin also came up heads?"), not of a combination of the two: so, since it can't be influenced from other launches, you have 50%.

What I'm saying is that the scenarios are only: T or H (1 coin).

This is how I see the things:

1) toss the coins: the scenarios are HH(25%), HT(25%), TH(25%), TT(25%).
2) call "A" the coin which came up heads and "B" the other;
3) which is the pobability B came up heads?: 50%

michele
Wednesday, June 30, 2004

I think you are going to have to break out two quarters and a pad of paper to convince yourself. I'm serious, try it.

1) toss the coins: the scenarios are HH(25%), HT(25%), TH(25%), TT(25%).

Correct. We can eliminate TT, so the first 3 options are really 33% each.

2) call "A" the coin which came up heads and "B" the other;

Let's make this even more obvious. Flip a nickel and a dime.

OK:
Nickel, Dime (Chance%)
HH (33%) - Either the nickel or the dime is A - B IS HEADS
HT (33%) - Nickel is A, Dime is B - B is NOT HEADS
TH (33%) - Nickel is B, Dime is A - B is NOT HEADS
TT (0%) - Eliminated

3) which is the pobability B came up heads?: 50%

Nope, see above. Only 33%
If you still don't see it, just start flipping. It really is true.

Brad Corbin
Wednesday, June 30, 2004

One final comment:

If the original question was:
"You flip two coins. The first one came up heads. What are the chances that the second one is also heads?"

Then you would be correct to say 50%. But since the question was:
"You flip two coins. ONE OF THEM came up heads. What are the chances the second one is also heads?"

then the answer is 33%

Its an easy trap to fall into. Just because you've narrowed it down to two choices (both heads, or one heads and one tails), doesn't mean that those two choices are equally likely. In this case, they are not.

This is similar in some ways to the Monty Hall problem. You ultimately are faced with two choices, but those two choices actually have different odds.

(The Monty Hall problem, if you havent heard it:)
You are a contestant on Let's Make a Deal. You are faced with a choice of three closed doors: two contain goats, and one contains a new car. You choose door A. Monty Hall then shows you that door C contained a goat, and gives you the chance to switch to door B if you wish. Should you?

The answer: Yes. 66% chance that door B has the car. Only 33% chance you chose correctly the first time. This is because Monty has knowledge of which door has the car, and is deliberately showing you the OTHER door.

It's easy to think that Monty's elimination of a door simply changed the odds from 33/33/33 to 50/50/0, but that's not the case. It changed it to 33/66/0.

Brad Corbin
Wednesday, June 30, 2004

First I thought Michele is right because the two incidents (flip of coin 1 and flip of coin 2) are independent.

After I read Brad's last comment I changed my mind.  The wording(either the first or one of the coint) in the original question does make a difference.

Imagine you have 10 coins and toss them, if I tell you 9 of them are Head, what's the chance that last one is also head? The chance should be very slim( definitely not 50%).

Thanks for both of you. 

Steve Li
Thursday, July 01, 2004

When you say the last/other one "is also a heads" there are two ways to interpret that:

1. chance that both coins come up heads given that the first one is already heads

2. chance that the other/last coin comes up heads

I would interpret it as #2 but I see where it can be interpreted otherwise.  The question should be reworded to be more clear.

saberworks
Saturday, July 03, 2004

First, here's the riddle: "i flip a penny and a dime and hide the result from you. "one of the coins came up heads", i announce. what is the chance that the other coin also came up heads?"

Here's some proof of concept code I wrote to save my thumb the pain of flipping the coins enough times to be statistically significant.  Keep in mind, there's no mention in the riddle of whether it's the first or second coin that's heads.  This is definately the cue that HT != TH.  Thoughts?

#!/usr/bin/env python
import random
HEADS = 0
TAILS = 1
SAMPLESIZE = 100000L

def flipCoin():
    return random.randint(0,1)

def flipOne(size):
    """ Flips one coin 'size' number of times, written to test
    statistical distribution of the sim and although randint() isn't
    truely random it's obviously close """

    outcome = {'H':0, 'T':0}
    for i in range(0,size):
        flip = flipCoin()
        if flip == HEADS:
            outcome['H'] = outcome['H'] + 1
        else:
            outcome['T'] = outcome['T'] + 1
    return outcome

def flipTwo(size):
    """ Flips two coins 'size' number of times, written to test
    statistical distribution of the sim and although randint() isn't
    truely random it's obviously close """

    outcome = {'HH':0, 'HT':0, 'TH':0, 'TT':0}
    for i in range(0,size):
        flip1 = flipCoin()
        flip2 = flipCoin()
        if flip1 == HEADS:
            if flip2 == HEADS:
                outcome['HH'] = outcome['HH'] + 1
            else:
                outcome['HT'] = outcome['HT'] + 1
        elif flip2 == HEADS:
            outcome['TH'] = outcome['TH'] + 1
        else:
            outcome['TT'] = outcome['TT'] + 1
    return outcome

def flipTwoSpecial(size):
    """ Flips two coins 'size' number of times.  This is the proof of
    concept to prove the 33/66 distribution occurs when the TT state
    can never occur (given the scenario outlined).  I believe an easier
    to comprehend solution comes from using only flipTwo() and then
    dropping the TT value in your own head.  The version was written
    for the other half of the folks who think like I think.  """

    outcome = {'HH':0, 'HT':0, 'TH':0}
    i = 0
    while i < SAMPLESIZE:
        flip1 = flipCoin()
        flip2 = flipCoin()
        if flip1 == HEADS:
            i = i + 1
            if flip2 == HEADS:
                outcome['HH'] = outcome['HH'] + 1
            else:
                outcome['HT'] = outcome['HT'] + 1
        elif flip2 == HEADS:
            i = i + 1
            outcome['TH'] = outcome['TH'] + 1
    return outcome

if __name__ == "__main__":
    for i in range(0,10):
        #print flipOne(SAMPLESIZE) # Commentted after testing, feel free to try it
        #print flipTwo(SAMPLESIZE) # Commentted after testing, feel free to try it
        print flipTwoSpecial(SAMPLESIZE)

Steve
Saturday, July 03, 2004

The answer seems so obvious that I dont understand why people are discussing it in so much details. The two tosses are independent. Nowhere the problem says that the coins are biased or their results are independent. So the answer is 0.5 or 50% no matter how many coins you flip or how many times you flip a same coin. Meaning if I toss a coin 1000 times and each time I get a  head, the probability that I get a head on 1001th toss is still 1/2 !!!

Does anyone agree with me on this?

Mitesh Vasa
Friday, July 09, 2004

Nope.  :)

Here's the problem as originally stated:
I flip a penny and a dime and hide the result from you. "One of the coins came up heads", I announce. What is the chance that the other coin also came up heads?"

If I had instead announced: "The dime came up heads" and asked the chances of the penny coming up heads, you would be right by saying 50%. But that's not the case here.

Let me simplify the question:
"I flip two coins. What are the chances that both of them are heads?"

Obviously, the answer is 25%
HH
HT
TH
TT

So if you read the original question like this:
"I flip two coins. If I said "both are tails", I would be lying. What is the chance both are heads?"

Then its easier to see that you really do have
HH
HT
TH
TT <--eliminated

And the chance is 33%, not 50%.

Brad Corbin
Saturday, July 10, 2004

Yup, the 50% theory is wrong.  The chance of any one flip is 50% but that's not the scenario presented.  Now I'm not silly enough to think the whole world speaks english which is why I posted code.  Code is understandable by all.

There are 4 possible outcomes of two flips.  If you explicitly state that 1 of the 4 outcomes is no longer possible than there are 3 possible outcomes left.  33% chance of a HEADS/HEADS situation.  33% chance of HEADS/TAILS and 33% chance of TAILS/HEADS.  Since the only outcome we care about is the chance that HEADS/HEADS will occur, the HEADS/TAILS and TAILS/HEAD are for our purposes the same.  If you want to understand the question, you really must try and see why HT and TH are not the same values.

Steve
Monday, July 12, 2004

Why do you people persist with this 50% nonsense?  Let me rephrase it so that you better understand it.  Here is the experiment.  Try it yourself:

1) Flip two coins
2) Look at both of them.  Ask yourself: "is (at least) one of them heads?"  If no, go to 1.  Else, continue.
3) Ask yourself "is the other one heads?"

Keep track of how many times you answer "yes" to 3 versus how many times you run the experiment.  You will only answer "no" to question 2 if you see TT.  3/4 of the time, you will go to question 3 (HT, TH, HH).  Only one of those times will you answer "yes" to 3.

As for the previous suggestion of flipping 10 coins, noting that (at least) 9 are heads, and asking what the chances of the 10th one being heads are... it's clearly 1/11.  In general, after flipping N coins and having at least N-1 heads, there is a 1/(N+1) chance the "last' one (in quotes because which one is indeterminate) will be heads.

Aditya K. Prasad
Wednesday, July 14, 2004

It'e funny how the inevitable "try it yourself" argument always comes with much more detailed instructions than are implied by the problem in question. Where do you get step 2 from?

Ham Fisted
Thursday, July 22, 2004

The second step comes from a process to actually set up the conditions of the test described. We are told that 'at least one of the coins is heds', which is logically equivalent to saying that 'not both of them are tails'. Cases where both coins are tails are therefore rejected from the sample set. We run the tests on the sample cases remaining.

David Clayworth
Monday, July 26, 2004

I like this problem.  People get fooled because the wording is deceiving (not quite a "trick question", but close).  Here's a clearer version of the problem:

"i flip a penny and a dime and hide the result from you. "AT LEAST one of the coins came up heads", i announce. what is the chance that BOTH OF THE COINS came up heads?

Obviously 1/3, as shown above.

Dave Howard
Tuesday, July 27, 2004

The question is *slightly* ambiguous. For instance, the interviewer may never say "one of" unless he means "only one of". But it's traditional in this sort of problem to ignore that sort of thing. IF SO, the answer is unambiguous. Possible rephrasings to make it COMPLETELY clear:

I will toss a nickel and a dime. After that, I will tell you if it is the case that there is one of them that shows heads (while making no statement about the other). *tosses* Oh look, that did happen. What's the chance both are heads?

A nickel and a dime are tossed. One of them shows a head. What's the chance the other shows a head?

I have just tossed 100 pairs, each one nickel and one dime. 71 pairs have at least one head. (Slightly lower than I expected, whatever.) Of those, how many would you expect to have two heads?

Jack
Friday, July 30, 2004

The question tests your understanding of conditional probabilities and reduced sample spaces. 

The original sample space was

{(T,T),  (T,H), (H,T), (H,H)}. 

The information we are given excludes (T,T) so the reduced sample space, given (D,P)!=(T,T), is

{(T,H), (H,T), (H,H)}

The question asks for

P[(H,H) | (D,T)!=(T,T)]

(T,T), (T,H), (H,T) and (H,H) were equally likely to begin with, and learning that (T,T) is excluded doesn't affect the balance among the remaining three outcomes.  They are *still* equally likely and the conditional probabilities over that (reduced) sample space must still add up to 1, so  the answer is

P[(H,H) | (D,T)!=(T,T)] = 1/3

Chuck Boyer
Sunday, August 15, 2004


The puzzle is ambiguously stated.  The problem is that I have no way
of knowing what you are going announce for the various possibilities.
For example,

D  P  You say
=    =    =======
H  H    At least one came up heads
H  T    At least one came up tails
T  H    At least one came up tails
T  T    At least one came up tails

OR

D  P  You say
=    =    =======
H  H    At least one came up heads
H  T    At least one came up tails
T  H    At least one came up heads
T  T    At least one came up tails

OR

D  P  You say
=    =    =======
H  H    Both coins came up heads
H  T    At least one came up heads
T  H    At least one came up heads
T  T    At least one came up tails

Each of these three cases is consistent with the information given in the problem and their answers are respectively 1, 1/2, and 0, none of which is the intended answer.  Without knowing what you are going to say in each case, it is impossible
to give a definitive answer.  Heck you may not even know what you are going
to say ahead time; you may decide what to say on the spur of the moment.

I've seen this problem before in both ambiguous and unambiguous forms.
A clean way to state this puzzle is the following.

I flip a penny and a dime, and hide the result from you. You ask me
"Did at least one coin come up heads?".  I truthfully answer yes.
What is the probability that the other coin also came up heads?

By having me ask the question, any uncertaintities about your announcements
vanish; you are "forced" to answer yes in exactly the three cases HH, HT, and TH.
Hence, the unambiguous answer is 1/3 as intended.

Also, this puzzle is a good example of how subtle differences in the wording
can make a big difference in probability problems.

Glenn C. Rhoads
Friday, August 27, 2004

To make it clear, the way I read the problem is,
A penny and a dime are flipped.  At least one of the coins came up heads.  What is the chance the other coin came up heads as well?

I believe the answer is 50%.

If the dime came up heads, the penny could be either heads or tails.  If the penny came up heads, the dime could either be heads or tails.

In other words, the "HH" possibility is actually two possibilities, because you don't know which one the person who flipped the coins looked at.

Jason Owen
Friday, September 10, 2004

*  Recent Topics

*  Fog Creek Home