Double Heads
Citadel
You flip a coin until you get a H. What's the chance it took you an odd number of flips to get a H? Same question for two H - i.e. you stop when you get two H (not necessarily consecutive, just two in total).
Answer
Usually when you're asked about a process that ends when some condition is met, and it seems like there's infinite podssibilities to take into account (which is the case here, as you could get infinite tails before the first heads), think: markov chains. This is to say, draw a tree of possibilities until you find either a desired outcome or (function of) a state you've already encountered.
So let's start evaluating the different scenarios to see if we can recognise some repeatign state. When we first flip a coin, it can be heads - in which case we've reached H with an odd number of flips, or it can be tails - in which case we continue flipping. Okay, so now we need a further even number of flips until the first H, so that including the first T we have an odd number of flips in total. Now we haven't been in this state before, but perhaps we can express it in term of something we've seen before. Say we denote p the probability we get the first heads on an odd flip. Then the chance we get the first H on an even flip is 1-p, as if we're flipping until the first H we'll either take odd or even flips in total (no other option). Therefore, if our first flip is a tails, there's 1-p chance it takes an extra even number of flips before the first H (so that total is odd).
We can now compute p by the law fo total probability based on the possibilities we just set up. Recall there's $\frac{1}{2}$ chance of getting heads, in which case chance of odd flips before first H is 1. And there's $\frac{1}{2}$ chance of getting tails, in which case there's 1-p chance of odd flips before first H. Then: $$p=\frac{1}{2}\cdot 1+\frac{1}{2}\cdot(1-p)\Rightarrow p=\frac{2}{3}$$So we get the first H on an odd flip with chance $\frac{2}{3}$ and even flip with chance $1-\frac{2}{3}=\frac{1}{3}$.
Now for the second part of the question. We need the probability of getting two heads (in total, not necessarily consecutive) with an odd number of flips. Can we somehow use the solution we got for the single H case to solve this? Yes, first problem is a subproblem of the two H case. First problem considers a flippjng process that stops when you get the first H. Second problem is simply two such processes: you flip until you get the first H, and then flip again until you get the second. For the total number of flips to be odd, either first process has to take odd flips and second even flips, or vice-versa. This is because sum of two numbers is odd only if exactly one of them is odd, and the total number of flips to get two H is the sum of the flips of the two single-H processes.
So how do we find the probability? Well first process is odd and second even with probabilility $\frac{2}{3}\cdot \frac{1}{3}$. Similarly, first is even and second odd with probability $\frac{1}{3}\cdot \frac{2}{3}$. Since total path is odd if either of these two is true, we sum their probabilities:$$\frac{2}{3}\cdot \frac{1}{3}+\frac{1}{3}\cdot \frac{2}{3}=\frac{4}{9}$$Our answer is therefore $\frac{4}{9}$.