You toss a coin until you see $3$ (not necessarily consecutive heads). What's the expected number of coin tosses you make?
I tried a lot of things, and I've seen the solution for three consecutive heads, but I'm not so sure how to do it if they are non-consecutive.
With probability $1/8$, we stop after the first three coin tosses (if we get HHH).
With probability $3/16$, we will terminate after the first four coin tosses (we can get THHH, HTHH, HHTH).
It gets really messy for the rest of them, and so I don't think this approach is quite correct. Can anyone please help me solve this problem?