Determining probability generating function for event "$SS$"

Question

Given a sequence of Bernouilli trials, we have $P(S) = \frac{2}{3}$ with $0<p<1$. The event "SS" occurs on the $i$-th trial if we observe an $S$ on the $i$-th trial following a $S$ on the $(i-1)$-th trial. We let $Q$ be the waiting time random variable to see the first event "SS". Show that the probability generating function of $Q$ is given by $$ \frac{4}{27}s^{2}\bigg(\dfrac{2}{1-\frac{2}{3}s} + \dfrac{1}{1+\frac{1}{3}s}\bigg) $$

I cannot determine how to approach this question to get the probability generating function in that form. My first thought is to let $Q_{1}$ be the waiting time for the first "$S$", and let $Q_{2}$ be the waiting time for the second "$S$" after getting the first "$S$".

Then $Q_{1} \sim Geo(\frac{2}{3})$, and $Q_{2} \sim Geo(\frac{2}{3})$, and as they are independent I can multiply their respective probability generating functions to get the probability generating function for $Q$.

But this gives me $$ \dfrac{\frac{4}{9}s^{2}}{(1-\frac{1}{3}s)^{2}}$$ which I cannot simplify to be the requested form. This leads me to think that I made an error in my approach, and I should be approaching this question completely differently.

Answer 1

robjohn already has a solid answer for you, but here's another approach if you're more inclined to conditioning, which I see you considered in the comments.

---

Let $Q_{1}$ be the waiting time for the first "$S$". Then, as you noted, $Q_{1} \sim Geo(\frac{2}{3})$. Now we condition on the $(Q_{1}+1)$-th trial.

We have that \begin{equation*} Q= \begin{cases} 1+Q_{1},& \text{if } (Q_{1}+1)\text{-th trial is "S"}\\ 1 + Q_{1} + R, & \text{if } (Q_{1}+1)\text{-th trial is not "S"} \end{cases} \end{equation*} where $R$ is the remaining time to get "$SS$" after getting a failure. Note that $R$ and our event $Q$ have the same distribution, ^i.e. $E(S^{R}) = E(S^{Q})$

Now conditioning,

\begin{align*} G(s) = E(s^{Q}) &= E(s^{1+Q_{1}}) \cdot P[(Q_{1}+1) \text{-th trial is "S"}] + E(s^{1+Q_{1} + R}) \cdot P[(Q_{1}+1) \text{-th trial is "F"}] \\ &=s \cdot E(s^{Q_{1}}) \cdot \frac{2}{3} + s \cdot E(s^{Q_{1}}) \cdot E(s^{Q}) \cdot \frac{1}{3} \end{align*}

Now you know the probability generating function of $Q_{1}$ as it is geometrically distributed, and you solve for $E(s^{Q})$ accordingly. You should end up with $\dfrac{4s^{2}}{9-3s-2s^{2}}$, and partial fractions will get you to your desired result.

---

What's wrong with your approach:

You cannot simply take the summation of $Q_{1}$ and $Q_{2}$ to find your probability generating function for $Q$, as you require the second "$S$" to occur immediately after the first one. Were you looking for the event of the first occurrence of the pattern "$SF$" say, then you could use a summation like you did. This would work because your pattern would not be "resetting" with each subsequent "$S$" before your required "$F$".

Answer 2

The atomic monomials are

$ \begin{array}{} S=\color{#00A000}{2}\left(\frac x{\color{#00A000}{3}}\right)^{\color{#C00000}{1}}&\text{length $\color{#C00000}{1}$, probability $\color{#00A000}{\frac23}$}\\ NS=\color{#00A000}{2}\left(\frac x{\color{#00A000}{3}}\right)^\color{#C00000}{2}&\text{length $\color{#C00000}{2}$, probability $\color{#00A000}{\frac29}$}\\ NNS=\color{#00A000}{2}\left(\frac x{\color{#00A000}{3}}\right)^{\color{#C00000}{3}}&\text{length $\color{#C00000}{3}$, probability $\color{#00A000}{\frac2{27}}$}\\ NNNS=\color{#00A000}{2}\left(\frac x{\color{#00A000}{3}}\right)^{\color{#C00000}{4}}&\text{length $\color{#C00000}{4}$, probability $\color{#00A000}{\frac2{81}}$}\\ \qquad\vdots \end{array} $

The first element can be any of the atomic monomials.

The middle elements can be any non-negative number of the atomic monomials, except $S$.

The last element is an $S$.

$$ \overbrace{\frac{2\left(\frac x3\right)^1}{1-\frac x3}}^{\text{first element}}\ \overbrace{\frac{1\vphantom{\left(\frac x3\right)^1}}{1-\frac{2\left(\frac x3\right)^2}{1-\frac x3}}}^{\text{middle elements}}\ \overbrace{\frac{2x\vphantom{\left(\frac x3\right)^1}}3}^{\text{last element}}=\frac{2\left(\frac x3\right)^1}{1-\frac x3-2\left(\frac x3\right)^2}\frac{2x}3=\bbox[5px,border:2px solid #C0A000]{\frac{4x^2}{9-3x-2x^2}} $$

---

Explanation of the Generating Functions Above

The "first element" can be $S,NS,NNS,\dots$. Its generating function is $$ \overbrace{2\left(\frac x3\right)^1}^{S}+\overbrace{2\left(\frac x3\right)^2}^{NS}+\overbrace{2\left(\frac x3\right)^3}^{NNS}+\cdots=\frac{2\left(\frac x3\right)^1}{1-\frac x3} $$ Each "middle element" can be $NS,NNS,NNNS,\dots$. Their generating function is
$$ \overbrace{2\left(\frac x3\right)^2}^{NS}+\overbrace{2\left(\frac x3\right)^3}^{NNS}+\overbrace{2\left(\frac x3\right)^4}^{NNNS}+\cdots=\frac{2\left(\frac x3\right)^2}{1-\frac x3} $$ The "middle elements" can consist of $0$ or more of these. Their generating function is $$ 1+\left(\frac{2\left(\frac x3\right)^2}{1-\frac x3}\right)+\left(\frac{2\left(\frac x3\right)^2}{1-\frac x3}\right)^2+\left(\frac{2\left(\frac x3\right)^2}{1-\frac x3}\right)^3+\dots=\frac1{1-\frac{2\left(\frac x3\right)^2}{1-\frac x3}} $$ The "last element" is $S$. Its generating function is $$ \frac{2x}3 $$