How does this work?
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."
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)
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.
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.
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.
if HT or HH
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.
Alice is looking for HT, so she will succeed in HTH, HHT, THT, HTT, that is 4 out of 8 possible outcomes. Bob on the other hand is looking for HH, that is only in HHH, THH, HHT, 3 out of 8 possible outcomes. So while HH and HT are equal in probability when you consider 2 coin flips, the combination of HT happens more often than HH. This is the case with 3 coin flips - there is no guarantee it translate to the same with more coin flips, but that is my bet.
Also the question "which substring occurs earlier on average" is intimately connected with algorithms for substring search. For example, if you want to check that a string doesn't contain HHH, you need to look at every third character, but for THH that's not enough.
For Bob, as soon as he sees a tail, his sequence is completely reset and he now has to get two tosses right.
I'm not sure how to calculate averages, though.
That makes sense.
Possible outcomes are: TTT, TTH, THT, THH, HTT, HTH, HHT, HHH
Alice successes are: HT, THT, and HHT, but Bob has less options: HH and THH. That's why he needs more tosses on average.
If Alice has failed to win on her second toss, her flip sequence was "HH", so she can win on the next toss, by flipping a T!
If Bob has failed to win on his second toss, his flip sequence was "HT", so he needs two more flips to win!
Multiple heads in a row are more bunched than transition sequences because, for example, a sequence of three heads in a row will include two sequences with two heads in a row. You can't do that with a transition sequence--it takes at least four tosses to get two identical transition sequences.
We basically have four cases for Bob:
- HH: terminates for Bob.
- HT: Bob restarts the sequence.
- TT: Bob restarts the sequence.
- TH: This is a continuation. It degenerates into the answer to a single throw. Otherwise its just a recursion.
Then we have another four cases for Alice:
- HH: This is a continuation. It degenerates into the answer to a single throw or else a recursion.
- HT: terminates for Alice.
- TT: Alice restarts the sequence.
So with that understanding it is a bit more clear how we get this result:
Alice has one win and two opportunities for a win and one for a restart. Bob has one win and one opportunity for a win and two restarts.
That was a bit confusing. I wonder how the problem could be worded to ensure that people got the answer correctly every time?
If Bob starts on H and gets T, he needs to continue flipping until he gets back to H.
In the case of failure, Alice still has 50% chance of success in each subsequent toss. On average she will need two additional tosses to get a tail and the answer is 2+2=4.
In the case of failure, Bob has to start again. If we call the answer x, we can write x=2+0.5 1+0.5 (1+x) and solving the equation we get x=6.