Derive this probability generating function

generating-functionsprobabilityprobability distributionssequences-and-series

The question is as follows:

"A fair coin is tossed repeatedly until two heads occur consecutively. The random variable $X$ represents the number of tosses up to and including the two consecutive heads. Show that the probability generating function for $X$ is given by
$$\mathrm{G}(z)=\frac{z^2}{4-2z-z^2}"$$

I've made the attempts to find $\mathrm{P}(X=r)$ for $r=2, 3, 4, 5, 6$ in hopes to recognise a pattern in order to sum the series, and I happened to get
$$\mathrm{P}(X=2)=\left(\frac{1}{2}\right)^2, \mathrm{P}(X=3)=\left(\frac{1}{2}\right)^3, \mathrm{P}(X=4)=2\times\left(\frac{1}{2}\right)^4, \mathrm{P}(X=5)=3\times\left(\frac{1}{2}\right)^5 \quad \mathrm{and} \quad\mathrm{P}(X=6)=5\times\left(\frac{1}{2}\right)^6$$
but I'm struggling to spot any pattern to sum
$$\sum_{r=2}^{\infty}z^r\mathrm{P}(X=r)$$
in order to reach the given expression.

Best Answer

Let $P_n$ be the probability that the string ends on the $n^{th}$ toss. Then $P_1=0,P_2=\frac 14$.

We work recursively from there.

Good strings of length longer than $2$ must begin with either $T$ or $HT$, with probabilities $\frac 12$ and $\frac 14$ respectively. Thus, for $n>2$ $$P_n=\frac 12P_{n-1}+\frac 14P_{n-2}$$.

Now let $F(x)=\sum_{n=1}^{\infty}P_nx^n$ denote the generating function. We have $$F(x)=\frac {x^2}4+\sum_{n=3}^{\infty}P_nx^n=\frac {x^2}4+\frac 12\sum_{n=3}^{\infty}P_{n-1}x^n+\frac 14\sum_{n=3}^{\infty}P_{n-2}x^n$$

Thus $$F(n)=\frac {x^2}4+\left(\frac x2+\frac {x^2}4\right)\sum_{n=1}^{\infty}P_nx^n=\frac {x^2}4+\left(\frac x2+\frac {x^2}4\right)F(n)$$

And the rest is straight forward.

Note: as discussed in the comments, the connection to the Fibonacci numbers is strong. Indeed, the number of good strings of a fixed length is given by those numbers (since the string prior to the final $HH$ consists of steps $T$ and $HT$, one of which has length $1$ and the other has length $2$).

Related Question