PMF of the number of trials required for two successive heads

Question

A coin with probability $p$ of landing a head is tossed repeatedly till the occurrence of two consecutive heads. Let $X$ be the random variable denoting the the number of trials needed. What is the distribution of $X$?

We consider a partition of the sample space where the sequence of events begins with a $T$, an $HT$ and an $HH$. So we have,

\begin{align} \mathbb{E}(X)&=\mathbb{E}(X\mid T)\mathbb{P}(T)+\mathbb{E}(X\mid HT)\mathbb{P}(HT)+\mathbb{E}(X\mid HH)\mathbb{P}(HH) \\&=\mathbb{E}(X+1)q+\mathbb{E}(X+2)pq+2p^2\qquad,\,q=1-p \end{align}

Thus in general for a function $g$ we have,

$$\mathbb{E}(g(X))=\mathbb{E}(g(X+1))q+\mathbb{E}(g(X+2))pq+g(2)p^2$$

Let $g(X)=t^X$, so that we get the PGF of $X$ as

\begin{align} P(t)=\mathbb{E}(t^X)&=tqP(t)+t^2pqP(t)+t^2p^2 \\&=p^2t^2(1-qt-pqt^2)^{-1} \end{align}

Now to get the p.m.f. of $X$ I need to find the coefficient of $t^j$ in the expansion of $P(t)$.

$$P(t)=p^2t^2(1-qt(1+pt))^{-1}=p^2t^2\sum_{j=0}^\infty(qt(1+pt))^j\,,$$

assuming $|qt(1+pt)|<1$.

But I could not separate the $t^j$ and its coefficient in the above expression.

Answer 1

Factor $$1 - qt(1+pt) = (1-at)(1-bt)$$ by finding its roots and notice $a\ne b$. From the resulting partial fraction decomposition

$$(1 - qt(1+pt))^{-1} = \frac{a}{a-b}(1 - a t)^{-1} - \frac{b}{a-b}(1 - b t)^{-1}$$

apply the Binomial Theorem to each of $(1-at)^{-1}$ and $(1-bt)^{-1}$ and combine the series to obtain

$$p^2t^2(1 - qt(1+pt))^{-1} = \frac{p^2}{a-b}\left(\sum_{i=0}^\infty \left(a^{i+1} - b^{i+1}\right)t^{i+2}\right).$$

The coefficient of $t^j = t^{i+2}$ for $j\ge 2$ therefore is $$\frac{p^2(a^{j-1}-b^{j-1})}{a-b}.$$

---

These manipulations are fully justified as formal power series in $t$. But since everything converges absolutely for $|t|\lt \min(1/|a|, 1/|b|)$, there's no problem considering them as analytic functions in a neighborhood of $0$, either.

Answer 2

You have found the pgf (probability generating function) for the waiting time $X$, the least possible value of $X$ is two. I cannot find a really simple closed form for the pmf (probability mass function), but I will show one possibility.

You found that $$ P(t) = p^2 t^2 \sum_{k=0}^\infty (qt(1+pt))^k $$ we can start with expanding $(1+pt)^k$ using the binomial theorem, that gives $$ P(t) = p^2 t^2 \sum_{k=0}^\infty \sum_{j=0}^k \binom{k}{j} p^j q^k t^{j+k} $$ To be able to read off probabilities, we want to write this such that the power of $t$ is directly the (outer) summation variable. So define $n=j+k$ and rewrite the sum with $n$ as summation variable, but at first $n$ will appear in the inner sum. This gives $$ P(t)=p^2 t^2 \sum_{k=0}^\infty (\frac{q}{p})^k \sum_{n=k}^{2k} \binom{k}{n-k} p^n t^n $$ Finally, we want to change the order of summation. Note that the index $n$ satisfies (from the limits on the inner sum) $n \ge k, n \le 2k$. Solve this inequalities for $k$ to get $k \le n, k \ge n/2$. Remembering that $k$ must be an integer we write this as $k \le n, k \ge \lceil n/2\rceil$ where the last strange brackets indicate the ceiling function, the smallest integer gretare that or equal to its argument (that is, rounding up to closest integer). Using this we finaly get $$ P(t) = p^2 t^2 \sum_{n=0}^\infty \sum_{k=\lceil n/2 \rceil}^n \binom{k}{n-k} (\frac{q}{p})^k p^n t^n $$ and from that formula we can read off $$ \DeclareMathOperator{\P}{\mathbb{P}} \P(X=n+2) = p^{n+2} \sum_{k=\lceil n/2 \rceil}^n \binom{k}{n-k} (\frac{q}{p})^k $$ but I dont know about simplifying that last expression. But, it could be used for small $n$, and then for large $n$ some approximation, maybe a saddlepoint approximation which can use the pgf directly.