darthsid

If Alice fails, and gets a second head, she only has to get one toss right, and hasn't completely reset her sequence.

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.

It is hard for a lot of people to reduce ambiguity in their instructions, to make no assumptions, so that the instruction will achieve the same result no matter who carries it out. That's why programming is difficult. You have to constantly think how someone else (a computer) will interpret you.