I learned an interesting fact in my Stochastic Processes class the other day, and I managed to come up with an easier way to present it than using Markov chains (which are really cool, but not conducive to making a good blog post).
The question was about the expected number of flips with a fair coin before seeing two tails in a row (TT), compared to a head then a tail (HT). Intuitively, most people (including myself and the professor) thought the expected number of flips should be the same. There’s an equal chance of getting a head as a tail, so why would it make a difference? Let’s walk through the calculation though. I don’t have good intuition as to why it makes since we get the answer we do, but it is fun either way! Let’s call the expected (see: average) number of flips before seeing two consecutive tails $latex E_{TT}$, and let’s start flipping some coins! If our first flip is a head, which occurs half of the time, our new expected number of flips is $latex \frac{1}{2}(1+E_{TT})$, as we got a flip that occurs half of the time, and we only flipped once. What if we flipped a tail (so close!) but then a head? This happens with probability $latex 1/4$, so the adjusted expected value would be $latex \frac{1}{4}(2 +E_{TT})$. Finally, what if we were able to flip 2 tails in a row, which occurs with probability $latex 1/4$? Well that is just 2 flips, so the expected number of flips would be 2. Thus in total we get the equation $latex E_{TT} = \frac{1}{2}(1+E_{TT}) + \frac{1}{4}(2+E_{TT}) + \frac{1}{2}(2)$ Solving this (I won’t show my work), you end up with $latex E_{TT} = 6$. Thus we expect to need 6 flips before getting consecutive tails. So what about $latex E_{HT}$? Our equations will look a little different, since if we flip $latex HH$ we “miss” our target, but still end up closer to our target than starting at zero flips. So suppose we flip a tail. Then the expected number is $latex \frac{1}{2}(1+E_{HT})$ similar to before. But if we flip two heads in a row, we are 1 flip away now, so our expected number of flips will be $latex \frac{1}{4}(2+E_{HT}/2)$. Finally, if we flip a head then tail the expected number is $latex \frac{1}{4}(2)$. So in total we have $latex E_{HT} = \frac{1}{2}(1+E_{HT}) + \frac{1}{4}(2+E_{HT}/2) + \frac{1}{2}(2)$ Solving this we get that $latex E_{HT} = 4$. Well that seems odd. It takes fewer flips on average to obtain a head then a tail, than to get two tails in a row. As I said before, I still don’t have great intuition on this result, but it is interesting (and true!) Probability is always a fun little game.