5 ms·

> Intuitively, first, both have to get a head. After that, if Alice "fails" by getting a head, then she still needs only one tail. Her first head doesn't get "r

> Intuitively, first, both have to get a head. After that, if Alice "fails" by getting a head, then she still needs only one tail. Her first head doesn't get "reset" by failing her second try. But after getting a head, if Bob fails by getting a tail then he does get reset -- he has to start all over. https://www.reddit.com/r/math/comments/4abm4k/expected_number_of_coin_flips_different_for/ https://www.reddit.com/r/math/comments/4abm4k/expected_numbe...

tremon 11y ago
Ah, thanks for that. So it's not a property of the coin toss itself, but the fact that a failure at the second step in the series only resets to before step 2, instead of before step 1.
hellofunk 11y ago
I thought the article was saying Alice must get a head followed immediately by a tail. If that's not the case, then it makes total sense, but it would seem the article is a bit vague about that. Actually, the details in the article say: >even though head-tail and head-head have an equal chance of appearing after two coin tosses. That implies that the tail is expected immediately after the head for Alice's goal.
- thefreeman 11y ago
  Correct, but the point is if Alice doesn't get a tail, that means she got a head, so she is still in the same position as she was before the flip, only needing a single tail to complete the sequence. If Bob gets a head, then a tail, he now needs two consecutive heads to complete his sequence.
- frobozz 11y ago
  The only way she can get a tail which isn't immediately after a head is to never get a head in the first place.
ghshephard 11y ago
What's interesting, is that if you reword this slightly, and ask, "If you flip coins until you get either a head followed by a tail, or a head followed by a head, how many flips on average are required before you get a Head, followed by a Tail, versus a Head, followed by a Head" - the answers are 3 and 3 respectively. But worded, "If you flip coins until you get a Head followed by a Tail, or flip coins until you get a Head followed by a Head, the answer reverts back to 4 and 6." Very counterintuitive.
- knughit 11y ago
  Explain the difference? Are you saying that HH causes an early failure for HT , instead of a potentially longer success HHHT? If so , it is poorly worded, to be ambiguous about how to count failures. (In the 4-6 variation, there are no failures)
  - ghshephard 11y ago
    I'm saying that if you just keep flipping coins (So, no Bob/Alice situation), and stop whenever you hit HH or HT, that the average number of flips to get to HH is 3, and the average number of flips to get to HT is 3. But, if you are focussing on a particular scenario that you will flip coins until you get to HT, the average number of flips will be 4, and if you flip coins until you get to HH, the average number of flips will be 6. I just find that really hard to grasp intuitively.
    - zipppy 11y ago
      I don't think that's true. I think that the average number of flips before _stopping_ might be 3, but it doesn't become more likely to get HT simply because you're also looking for HH (or vice versa).
      - ghshephard 11y ago
        It turns out that the average number of flips to get HH and HT is 3 - someone else on the thread described it well - on average, the number of flips to get to a "H" will be 2, and then you will always stop on the next flip - 50% at flip 3 with a HT, and 50% at flip 3 with a HH. Explained that way, it makes sense that the average number of flips is 3. But, I still find it strange that if you are flipping with one particular scenario in mind, HT or HH, that the average number of flips goes from 3 to 4 or 6, even if I can reason it out with a bit of thinking.
mabbo 11y ago
That was going to bother me all day. Thank you.
Qwertious 11y ago
Yeah, thought so - it's specifically heads->tails, rather than either heads->tails or tails->heads being okay. So the probabilities don't seem remotely counterintuitive, just crappily communicated IMO.
- tempestn 11y ago
  I'm not sure your explanation fits with the probabilities. Pointing out that you're only looking for heads->tails and not tails->heads seems to suggest that the HT pattern should be less likely than the HH, but it's actually more likely (for reasons explained well by others).
aidenn0 11y ago
A similar property was recently taken advantage of to reduce the time needed to brute-force older garage door openers; roughly speaking openers look for a particular base-3 string, but don't require a start/stop sequence, so you can try N length M permutations with much less than N*M symbols transmitted.
- dalke 11y ago
  That's a De Bruijn sequence. See https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence . A example applied to door codes is at http://stefangeens.com/2001-2013/2004/10/the-de-bruijn-code/ http://stefangeens.com/2001-2013/2004/10/the-de-bruijn-code/ . A search for "De Bruijn garage door" finds a couple of examples of what you mentioned.
  - aidenn0 11y ago
    Thanks for the name, with it I was able to find the article I was thinking of: http://samy.pl/opensesame/ http://samy.pl/opensesame/

tremon 11y ago

Ah, thanks for that. So it's not a property of the coin toss itself, but the fact that a failure at the second step in the series only resets to before step 2, instead of before step 1.

hellofunk 11y ago

I thought the article was saying Alice must get a head followed immediately by a tail. If that's not the case, then it makes total sense, but it would seem the article is a bit vague about that. Actually, the details in the article say: >even though head-tail and head-head have an equal chance of appearing after two coin tosses. That implies that the tail is expected immediately after the head for Alice's goal.

thefreeman 11y ago
Correct, but the point is if Alice doesn't get a tail, that means she got a head, so she is still in the same position as she was before the flip, only needing a single tail to complete the sequence. If Bob gets a head, then a tail, he now needs two consecutive heads to complete his sequence.
frobozz 11y ago
The only way she can get a tail which isn't immediately after a head is to never get a head in the first place.

ghshephard 11y ago

What's interesting, is that if you reword this slightly, and ask, "If you flip coins until you get either a head followed by a tail, or a head followed by a head, how many flips on average are required before you get a Head, followed by a Tail, versus a Head, followed by a Head" - the answers are 3 and 3 respectively. But worded, "If you flip coins until you get a Head followed by a Tail, or flip coins until you get a Head followed by a Head, the answer reverts back to 4 and 6." Very counterintuitive.

knughit 11y ago
Explain the difference? Are you saying that HH causes an early failure for HT , instead of a potentially longer success HHHT? If so , it is poorly worded, to be ambiguous about how to count failures. (In the 4-6 variation, there are no failures)
- ghshephard 11y ago
  I'm saying that if you just keep flipping coins (So, no Bob/Alice situation), and stop whenever you hit HH or HT, that the average number of flips to get to HH is 3, and the average number of flips to get to HT is 3. But, if you are focussing on a particular scenario that you will flip coins until you get to HT, the average number of flips will be 4, and if you flip coins until you get to HH, the average number of flips will be 6. I just find that really hard to grasp intuitively.
  - zipppy 11y ago
    I don't think that's true. I think that the average number of flips before _stopping_ might be 3, but it doesn't become more likely to get HT simply because you're also looking for HH (or vice versa).
    - ghshephard 11y ago
      It turns out that the average number of flips to get HH and HT is 3 - someone else on the thread described it well - on average, the number of flips to get to a "H" will be 2, and then you will always stop on the next flip - 50% at flip 3 with a HT, and 50% at flip 3 with a HH. Explained that way, it makes sense that the average number of flips is 3. But, I still find it strange that if you are flipping with one particular scenario in mind, HT or HH, that the average number of flips goes from 3 to 4 or 6, even if I can reason it out with a bit of thinking.

mabbo 11y ago

That was going to bother me all day. Thank you.

Qwertious 11y ago

Yeah, thought so - it's specifically heads->tails, rather than either heads->tails or tails->heads being okay. So the probabilities don't seem remotely counterintuitive, just crappily communicated IMO.

tempestn 11y ago
I'm not sure your explanation fits with the probabilities. Pointing out that you're only looking for heads->tails and not tails->heads seems to suggest that the HT pattern should be less likely than the HH, but it's actually more likely (for reasons explained well by others).

aidenn0 11y ago

A similar property was recently taken advantage of to reduce the time needed to brute-force older garage door openers; roughly speaking openers look for a particular base-3 string, but don't require a start/stop sequence, so you can try N length M permutations with much less than N*M symbols transmitted.

dalke 11y ago
That's a De Bruijn sequence. See https://en.wikipedia.org/wiki/De_Bruijn_sequence https://en.wikipedia.org/wiki/De_Bruijn_sequence . A example applied to door codes is at http://stefangeens.com/2001-2013/2004/10/the-de-bruijn-code/ http://stefangeens.com/2001-2013/2004/10/the-de-bruijn-code/ . A search for "De Bruijn garage door" finds a couple of examples of what you mentioned.
- aidenn0 11y ago
  Thanks for the name, with it I was able to find the article I was thinking of: http://samy.pl/opensesame/ http://samy.pl/opensesame/