5 ms·

You didn't read it wrong, but you probably did fail the test ;-) There is no gotcha in the question, it's just a math problem that you either do or do not know

by jules 13y ago

You didn't read it wrong, but you probably did fail the test ;-) There is no gotcha in the question, it's just a math problem that you either do or do not know how to solve. This isn't really about intelligence as much as it is about whether you have taken a course on probability. If you flipped 10 heads in a row the probability of the coin you have being the double heads coin increases dramatically, so you have to take that into account for the next flip. For intuitive understanding it often helps to go to extremes. Suppose you do 1 billion flips and all come up heads. What is the probability that the next flip comes up heads? Because we had 1 billion heads it is virtually certain that we are dealing with the double heads coin, so the probability that the next flip will come up heads is close to 1.

joezydeco 13y ago
"If you flipped 10 heads in a row the probability of the coin you have being the double heads coin increases dramatically..." I disagree. The coin is the coin. It didn't magically transport itself or change state after flipping it 10, 100, or a billion times. Lets change the puzzle to the simplest state: you pull a coin from the 1000-coin jar and flip it just once. What's the probability of heads? This is why roulette and baccarat tables in Vegas have those signs showing previous outcomes. It's meant to mess with your head. Previous history has no effect on future outcomes. A fair coin could come up heads a billion times in a row as well. The next flip will still be 0.5.
- jules 13y ago
  The probability of heads is 0.999*0.5 + 0.001*1 = 0.5005 The important thing is that as you observe heads from the coin, you learn something about the coin. As you observe more heads it is less likely to be a fair coin and more likely to be the coin with double heads. This doesn't change anything about the coin, but it changes something about what you know about the coin. See here for the correct answer: https://news.ycombinator.com/item?id=7000523 https://news.ycombinator.com/item?id=7000523
  - joezydeco 13y ago
    Since the question simply asked what p(heads) was on the next flip, it seems our answers match. Thanks!
    - jules 13y ago
      Our answers to your question may match, but I very much doubt that our answers on the original question match. The crux is that your question is not equivalent to the original question. If you are interested in learning why that is I can explain it further, but it doesn't look like you are?
      - joezydeco 13y ago
        Okay yeah, I'm stupid for pressing on while crntaylor already gave his answer. I'll shut up now.
    - baddox 13y ago
      Not at all. The answer is about 0.75, and stated in the answer jules linked to.
- Bakkot 13y ago
  The coin is the coin, but your information about the coin has changed. Probability is a fact about you, not a fact about the coin. Here is perhaps a more visceral example: On any given day, your car has a 10% chance of having blown a wheel the previous night. If it has blown a wheel, every bump will feel jarring. If it hasn't blown a wheel, any given bump will feel jarring with 10% probability. You drive over a hundred bumps, and all feel jarring. Do you think the next bump will also feel jarring? Yes, right? Because the fact that the last hundred bumps have been jarring means you probably blew a wheel last night. Even though 'previous history has no effect on future outcomes', previous history does give you information about the state of the world. Edit: Or a better example, for this community. You're on a slightly flakey wifi connection, which sometimes drops a packet at random. Any given packet is dropped with probability 1/100. Also, any given time you connect to the router, the modem is down with probability 1/10, and all of your packets will get dropped. You connect, and the first hundred packets you send are dropped. What is the probability the next packet will get dropped? Very high, because now you know that the modem is probably down. The history of the connection gives you information about the state of the connection. Similarly, the history of coin toss results gives you information about the state of the coin. (Why is this different from roulette? Because there the previous history doesn't give you information.)
  - joezydeco 13y ago
    Probability is a fact about you, not a fact about the coin. Huh? It's a coin. You flip it. It has no knowledge of the past and no idea about the future. It lands and it's either heads 50% of the time and tails 50% of the time. It's all about the coin and nothing about what you've observed in the last N trials. That's the simple logic that the OP is trying to see if you understand.
    - harpastum 13y ago
      It's really interesting to watch this thread. I'm not saying that you should simply trust what the other commenters are saying, but the user crntaylor is the one that originally posted the question, and his solution is that the likelihood of the next flip being heads is 75%
- bluepen44 13y ago
  I think you're missing the point of the question which seems to get at whether the interviewee is familiar with/understands bayesian probability. For an excellent explanation you should see: http://yudkowsky.net/rational/bayes http://yudkowsky.net/rational/bayes.
  - baddox 13y ago
    I don't see why knowledge of Bayesian probability is necessary for this question. I don't have anything more than a passing knowledge of Bayesian probability, but I was able to produce the correct answer and a reasonable explanation using what I believe to be classical probability: https://news.ycombinator.com/item?id=7001288 https://news.ycombinator.com/item?id=7001288
- baddox 13y ago
  I think you're incorrect because your conceptual model of what constitutes "probability" is incorrect for this type of problem. Try thinking about it in a more brute force way: imagine literally all possible outcomes of performing this experiment. In other words, create a list like this (each coin in the jar is numbered from 000 to 999 with 999 being the only biased coin, and coin flips are represented by 0 being heads and 1 being tails): Picked fair coin #000, flipped 00000000000 (eleven flips) Picked fair coin #000, flipped 00000000001 Picked fair coin #000, flipped 00000000010 ... Picked fair coin #000, flipped 11111111111 .... Picked biased coin #999, flipped 11111111111 Now select all of the lines above where the first ten flips are heads. Of these outcomes, how many have an eleventh flip of heads and how many have an eleventh flip of tails? Unless my idea of probability is flawed, this should be the same answer that the mathematicians in this thread are providing, so something right around 75% heads.
  - jules 13y ago
    Where is the unfair coin in your list? Without that you just get 50% heads. This method can definitely work to get the correct answer, but you have to account for all possibilities and weigh them by their probability.
    - baddox 13y ago
      Sorry, I edited coin #999 to be the biased coin.
  - jonsen 13y ago
    Well if I can count: 00000 00000 0 00000 00000 1 for 999 fair coins = 1998 + 1 for fake coin = 1999 1000 of which has 11. flip 0 So 1000/1999 ~ 50%
    - baddox 13y ago
      True. I glossed over the crucial part, which is that you have to enumerate the same number of potential outcomes for the biased coin's ten flips as you do for each fair coin, because each coin is equally as likely to be selected from the jar. Of course, all 2^10 potential outcomes for the biased coin's ten flips are the same: all heads. So we have: 00000 00000 0 00000 00000 1 For 999 fair coins = 1998 And 2^11 instances of 00000 00000 0 for the biased coin = 2048. That's 1998 + 2048 = 4046 equally likely outcomes that begin with ten heads. Of those, only 1998 / 2 = 999 outcomes feature an eleventh tails. So the odds of getting an eleventh heads after seeing ten heads is (4046 - 999) / 4046 =~ 0.753.
- patmcc 13y ago
  >>>Previous history has no effect on future outcomes. A fair coin could come up heads a billion times in a row as well. The next flip will still be 0.5. You hit the nail on the head here - a fair coin would. But if there are unfair coins, things start to change. If we know there's an unfair coin, and we see an unusual run, we should consider that it may be that coin. Think of this: increase the flips to 1000, and you're still getting heads each time. Would you bet on the next being heads or tails?

by jules 13y ago

joezydeco 13y ago

"If you flipped 10 heads in a row the probability of the coin you have being the double heads coin increases dramatically..." I disagree. The coin is the coin. It didn't magically transport itself or change state after flipping it 10, 100, or a billion times. Lets change the puzzle to the simplest state: you pull a coin from the 1000-coin jar and flip it just once. What's the probability of heads? This is why roulette and baccarat tables in Vegas have those signs showing previous outcomes. It's meant to mess with your head. Previous history has no effect on future outcomes. A fair coin could come up heads a billion times in a row as well. The next flip will still be 0.5.

jules 13y ago
The probability of heads is 0.999*0.5 + 0.001*1 = 0.5005 The important thing is that as you observe heads from the coin, you learn something about the coin. As you observe more heads it is less likely to be a fair coin and more likely to be the coin with double heads. This doesn't change anything about the coin, but it changes something about what you know about the coin. See here for the correct answer: https://news.ycombinator.com/item?id=7000523 https://news.ycombinator.com/item?id=7000523
- joezydeco 13y ago
  Since the question simply asked what p(heads) was on the next flip, it seems our answers match. Thanks!
  - jules 13y ago
    Our answers to your question may match, but I very much doubt that our answers on the original question match. The crux is that your question is not equivalent to the original question. If you are interested in learning why that is I can explain it further, but it doesn't look like you are?
    - joezydeco 13y ago
      Okay yeah, I'm stupid for pressing on while crntaylor already gave his answer. I'll shut up now.
  - baddox 13y ago
    Not at all. The answer is about 0.75, and stated in the answer jules linked to.
Bakkot 13y ago
The coin is the coin, but your information about the coin has changed. Probability is a fact about you, not a fact about the coin. Here is perhaps a more visceral example: On any given day, your car has a 10% chance of having blown a wheel the previous night. If it has blown a wheel, every bump will feel jarring. If it hasn't blown a wheel, any given bump will feel jarring with 10% probability. You drive over a hundred bumps, and all feel jarring. Do you think the next bump will also feel jarring? Yes, right? Because the fact that the last hundred bumps have been jarring means you probably blew a wheel last night. Even though 'previous history has no effect on future outcomes', previous history does give you information about the state of the world. Edit: Or a better example, for this community. You're on a slightly flakey wifi connection, which sometimes drops a packet at random. Any given packet is dropped with probability 1/100. Also, any given time you connect to the router, the modem is down with probability 1/10, and all of your packets will get dropped. You connect, and the first hundred packets you send are dropped. What is the probability the next packet will get dropped? Very high, because now you know that the modem is probably down. The history of the connection gives you information about the state of the connection. Similarly, the history of coin toss results gives you information about the state of the coin. (Why is this different from roulette? Because there the previous history doesn't give you information.)
- joezydeco 13y ago
  Probability is a fact about you, not a fact about the coin. Huh? It's a coin. You flip it. It has no knowledge of the past and no idea about the future. It lands and it's either heads 50% of the time and tails 50% of the time. It's all about the coin and nothing about what you've observed in the last N trials. That's the simple logic that the OP is trying to see if you understand.
  - harpastum 13y ago
    It's really interesting to watch this thread. I'm not saying that you should simply trust what the other commenters are saying, but the user crntaylor is the one that originally posted the question, and his solution is that the likelihood of the next flip being heads is 75%
bluepen44 13y ago
I think you're missing the point of the question which seems to get at whether the interviewee is familiar with/understands bayesian probability. For an excellent explanation you should see: http://yudkowsky.net/rational/bayes http://yudkowsky.net/rational/bayes.
- baddox 13y ago
  I don't see why knowledge of Bayesian probability is necessary for this question. I don't have anything more than a passing knowledge of Bayesian probability, but I was able to produce the correct answer and a reasonable explanation using what I believe to be classical probability: https://news.ycombinator.com/item?id=7001288 https://news.ycombinator.com/item?id=7001288
baddox 13y ago
I think you're incorrect because your conceptual model of what constitutes "probability" is incorrect for this type of problem. Try thinking about it in a more brute force way: imagine literally all possible outcomes of performing this experiment. In other words, create a list like this (each coin in the jar is numbered from 000 to 999 with 999 being the only biased coin, and coin flips are represented by 0 being heads and 1 being tails): Picked fair coin #000, flipped 00000000000 (eleven flips) Picked fair coin #000, flipped 00000000001 Picked fair coin #000, flipped 00000000010 ... Picked fair coin #000, flipped 11111111111 .... Picked biased coin #999, flipped 11111111111 Now select all of the lines above where the first ten flips are heads. Of these outcomes, how many have an eleventh flip of heads and how many have an eleventh flip of tails? Unless my idea of probability is flawed, this should be the same answer that the mathematicians in this thread are providing, so something right around 75% heads.
- jules 13y ago
  Where is the unfair coin in your list? Without that you just get 50% heads. This method can definitely work to get the correct answer, but you have to account for all possibilities and weigh them by their probability.
  - baddox 13y ago
    Sorry, I edited coin #999 to be the biased coin.
- jonsen 13y ago
  Well if I can count: 00000 00000 0 00000 00000 1 for 999 fair coins = 1998 + 1 for fake coin = 1999 1000 of which has 11. flip 0 So 1000/1999 ~ 50%
  - baddox 13y ago
    True. I glossed over the crucial part, which is that you have to enumerate the same number of potential outcomes for the biased coin's ten flips as you do for each fair coin, because each coin is equally as likely to be selected from the jar. Of course, all 2^10 potential outcomes for the biased coin's ten flips are the same: all heads. So we have: 00000 00000 0 00000 00000 1 For 999 fair coins = 1998 And 2^11 instances of 00000 00000 0 for the biased coin = 2048. That's 1998 + 2048 = 4046 equally likely outcomes that begin with ten heads. Of those, only 1998 / 2 = 999 outcomes feature an eleventh tails. So the odds of getting an eleventh heads after seeing ten heads is (4046 - 999) / 4046 =~ 0.753.
patmcc 13y ago
>>>Previous history has no effect on future outcomes. A fair coin could come up heads a billion times in a row as well. The next flip will still be 0.5. You hit the nail on the head here - a fair coin would. But if there are unfair coins, things start to change. If we know there's an unfair coin, and we see an unusual run, we should consider that it may be that coin. Think of this: increase the flips to 1000, and you're still getting heads each time. Would you bet on the next being heads or tails?