1. 7

  2. 4

    I think there’s an easier proof that Knuth-Yao: from state S1 there are four possible 2-flip sequences: TT, TH, HT, HH. But HH just brings us back to S2, so only three of the sequences lead to unique states, and they’re all terminating. So each of them has probability 1/3 from S2, and we have a probability 1/2 of reaching S2 for a total prob of 1/6.

    1. 2

      Oh yeah actually, that makes sense. You just kind of throw away the HH flips; hadn’t considered it that way. Actually really similar to Von Neumann’s method for getting a fair coin from a biased coin: https://en.wikipedia.org/wiki/Fair_coin#Fair_results_from_a_biased_coin