Distribution of a random variable in a coin toss

Consider a biased labeled dice $Z$ where $P(Z=T)=1/2$, $P(Z=H)=1/4$, $P(Z=END)=1/4$. We sample from $Z$ until we get $Z=END$ to form a sequence $( Z_i )$. For example $( Z_i ) = (T, H, H, T, T, H, T,END)$. The length of the sequence clearly follows $Geom(1/4)$.

We can biject $( Z_i )$ to $(Y_1, Y_2, ... , Y_X)$ in the obvious way:

$$( Z_i ) = (T, H, H, T, T, H, T, END) \leftrightarrow (2,1,3,2)=(Y_1,Y_2,Y_3,Y_4)$$

i.e. $X=4$ and the tosses were $(T,H)$,$(H)$,$(T,T,H)$,$(T,H)$. Notice $length(Z_i)=S$ and $num((Z_i)=H)+1=X$

The probability of the two are equal: $P((Z_i))=\frac{1}{2^{length+num((Z_i)=H)+1}}$ and $P((Y_i))=\frac{1}{2^{S+X}}$. Thus, $S$ follows the same distribution as length of $(Z_i)$.

Not very elegant, but ....

$$\begin{align} P(S=s) &= \sum_x P(S=s \mid X = x) P(X=x)\\ &=\sum_{x=1}^s\binom{s-1}{x-1} \left(\frac12\right)^{s} \left(\frac12\right)^{x}\\ &= \left(\frac12\right)^{s+1} \sum_{u=0}^{s-1}\binom{s-1}{u} \left(\frac12\right)^{u}\\ &= \left(\frac12\right)^{s+1} \left(1+\frac12\right)^{s-1}\\ &= \frac14 \left(\frac34\right)^{s-1} \end{align}$$

---

Update: For a more elegant solution, see the answer (+1) by John Ma.

Essentially, he notices that the process is equivalent to the following one: toss a fair coin until you get H. Then, throw a new fair coin to decide if you end the process, elsewhere start again. Here S is the total number of coins. And this is equivalent to a geometric distribution with $p=\frac14$.

You have $P(S=s \mid X=k)= \dfrac{s-1 \choose k-1}{2^s}$ and $P( X=k) = \dfrac{1}{2^s}$ and $1 \le k \le s$

and so $P(S=s )= \sum\limits_{k=1}^s \dfrac{s-1 \choose k-1}{2^{s+k}} = \dfrac{1}{2^{s+1}} \sum\limits_{j=0}^{s-1} \dfrac{s-1 \choose j}{2^{j}} = \dfrac{1}{2^{s+1}} \left(1+\dfrac12\right)^{s-1} = \dfrac14\left(\dfrac34\right)^{s-1} $ as required to show $S \sim \text{Geom}\left(\frac14\right)$