4 ms·
> If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require f
by krick 7y ago
> If Alice tosses a coin until she sees a head followed by a tail, and Bob tosses a coin until he sees two heads in a row, then on average, Alice will require four tosses while Bob will require six tosses (try this at home!), even though head-tail and head-head have an equal chance of appearing after two coin tosses.
Ok, I verified on 10 000 tosses, it works, but I cannot see why. Can somebody explain?
Edit: nevermind, it can be found in the previous discussion.
- vegizombie 7y agoFor anyone else interested, the way this was explained to me a while ago was to look at the failure mode after an H. For Alice, her failure for HT is HH, therefore her next flip can land on T, completing the sequence. For Bob, his failure mode is HT, so he now needs to flip a H before he can try for the 2nd H.
- boi4 7y agoRelated: https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm https://en.wikipedia.org/wiki/Knuth–Morris–Pratt_algorithm
- natmaka 7y agoRelated and well-known by software developers: https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-search_algorithm https://en.wikipedia.org/wiki/Boyer%E2%80%93Moore_string-sea...