Distribution of a random variable in a coin toss

Question

Amanda tosses a fair coin until she gets $H$. Let $X$ be the number of these tosses.

After that she tosses $X$ fair coins, each one until she gets $H$. Let $Y_i$ be the number of tosses for the coin $i\in\{1,\dots,X\}$.

Finally, Let $S=Y_1+Y_2+\dots+Y_X$ the total number of tosses (excluding the first $X$ tosses).

Prove: $S\sim \mathrm{Geo}\left(\frac14 \right)$

My try:

I know that $(S|X=k)\sim \mathrm{NegBin}(k, 1/2)$ as sum of geometric random variables. How can I conclude that $S\sim \mathrm{Geo}(1/4 )$?

Answer 1

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$.

Answer 2

One way to do it is calculation of characteristic function.

$$\phi_{S}\left(t\right):=\mathbb{E}e^{itS}=\sum_{k=1}^{\infty}\mathbb{E}\left(e^{itS}\mid X=k\right)P\left(X=k\right)=\sum_{k=1}^{\infty}\left(\mathbb{E}e^{itY_{1}}\right)^{k}2^{-k}=\sum_{k=1}^{\infty}\left(\frac{e^{it}}{2-e^{it}}\right)^{k}2^{-k}=\sum_{k=1}^{\infty}\left(\frac{e^{it}}{4-2e^{it}}\right)^{k}=\frac{\frac{e^{it}}{4-2e^{it}}}{1-\frac{e^{it}}{4-2e^{it}}}=\frac{e^{it}}{4-3e^{it}}$$

Not very elegant, though.

I would not be surprised if a better solution turns up.

Answer 3

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)$

Answer 4

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)$.