Hacker News Reader

Comment by filleokus | Hacker News Reader

> 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_numbe...

View on HN

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.

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)

  flip coins
    if HT or HH
      stop

  flip coins
    if HT
      stop

  flip coins
    if HH
      stop

two different scenarios

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.

"and stop whenever you hit HH or HT" is equivalent to say "whenever you hit H, flip one more then stop". Average to hit H is obviously 2, plus one is 3, so you are right, but IMO it's not that counter-intuitive.

Do I understand your first scenario correctly, that if for example you flip TTHH, you stop there, count that as "took four flips to get to HH," count nothing for HT, and then start over?

Seems like you're just taking a biased sample, which cancels out the differences. To take an extreme example, imagine one candidate is HHHHHHHHHH and the other candidate is any other sequence of ten flips. In the "try until you get either one" scenario, the average number of flips for either one will be 10. Testing them independently, the average number of flips for the second one will be slightly over 10, and for HHHHHHHHHH it'll be huge.

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).

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.

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.

That's a De Bruijn sequence. See 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/ . A search for "De Bruijn garage door" finds a couple of examples of what you mentioned.

Thanks for the name, with it I was able to find the article I was thinking of: http://samy.pl/opensesame/

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.

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

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.

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.

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.

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.

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).

Reply on news.ycombinator.com