Two tails in a row - what's the probability that the game started with a head?

If I may, there is an easier approach to that problem.

We know the game ended with tails, so we have one of the following states:

$(T, T), (H, T, T), (T, H, T, T), (H, T, H, T, T), (T, H, T, H, T, T), \cdots $

You get the pattern.

Now notice that if you have a sequence of $n $ flips, the probability you got that sequence was $\frac{1}{2^n} $ right? Because the outcome of one flip was not influenced by the other.

Now we can start by infering this: the first sequence does not start with heads and has probability $\frac14$. The sequence afterwards starts with heads and has probability $\frac12\frac14$ i.e. half the probability of occurring when compared to the previous one. Doing this for all pairs of sequences, we see that each tail-starting sequence has double the probability of happening when compared to a heads-starting sequence and this can only happen if the probability of the game starting with tails is $66\% $ and with heads is $33\% $.

Another way of doing this is by explicitly summing all the probabilities of all sequences that start with heads. That sum is

$$\sum_{i = 1}^{\infty} \frac{1}{2^{2i + 1}} = \frac16$$

This is $P(\text{starts with heads|ends with tails}) $. Now all we have to do is divide by the probability it ended with double tails, since that is already given, to get $P(\text{starts with heads})$. The probability it ended with double tails is given by summing the probabilities of all these sequences (show it equals $\frac12$).

Now $\frac16/\frac12 = \frac13$ which is the result we obtained intuitively.

Suppose the game ends on the $n$th toss with a tail. If $n$ is even, then the first toss must be tails; if $n$ is odd, then the first toss must be heads. For example, if $n=3$, then the sequence must be $HTT$. If $n=4$, it must be $THTT$. If $n=5$, it must be $HTHTT$. Etc.

\begin{align} P(H_1 | \text{ends with tails}) &= \frac{P(H_1,\text{ends with tails})}{P(\text{ends with tails})}\\ &= \frac{\sum_{n=2}^\infty P(H_1, \text{ends on $n$th toss with tails})}{1/2}\\ &= 2(0 + 2^{-3} + 0 + 2^{-5} + 0 + 2^{-7} + \cdots)\\ &= \frac{1}{4} \cdot \frac{1}{1-(1/4)}\\ &= \frac{1}{3}. \end{align}

You have already made a key observation about the structure of the game. In general, if $x,y \in \{T,H\}$and $x\neq y$ a game will take one of these forms (always ending with two tosses of the same outcome) $$ \begin{array}{rl} \color{red}{x\ x} &\quad 2 \text{-toss sequence} \\ y\ \color{red}{x\ x} &\quad 3 \text{-toss sequence} \\ x\ y\ \color{red}{x\ x} &\quad 4 \text{-toss sequence}\\ y\ x\ y\ \color{red}{x\ x} &\quad 5 \text{-toss sequence}\\ ... &\quad ... \end{array} $$

What is the probability for the first case (length = $2$)? It's $\frac{1}{2}$ (we start with any face and then we have to get the same face). For length =$3$? It's $1 \over 4$ (we start with any face and then we have to get the opposite face twice). For a length 4 sequence we start with any face and then have to get the opposite face and the same face twice (probability $1 \over 8$). In general, the probability of getting a sequence of $n$ tosses is $\frac{1}{2^{n-1}}$. As a quick sanity test, we see that if we sum up the probabilities of the infinite number of cases we get $1$ .

Now notice that we start with the same face as we end for cases of lengths $2,4,6,8,\dots$ and we start with the opposite face when the length is $3,5,7,9,\dots$

The crucial observation is to see that sequences with lengths $2,4,6,\dots$ have double the probability of sequences of length $3,5,7,\dots$

Hence we have double the probability of starting with the same face we end, compared to starting with the opposite face. So:

$$P(H_1|T_n) = \frac{1}{3} \quad \text{and}\quad P(T_1|T_n) = \frac{2}{3}$$