Expected number of coin flip to get HTT by conditioning

Question

What is the expected number of (fair) coin flips to get a sequence HTT? I know similar questions have been asked before and that the answer should be $8$, but I can't seem to get my head around this one. I'd like to solve it using conditional expectation technique (rather than Markov chains).

So let $X$ be the random variable "number of flips needed to get the sequence HTT". I condition on first 3 flips. Then the set of 4 events $\{HTT, T, HTH, HH\}$ partitions the sample space. We have

$E(X) = E(X|HTT)P(HTT) + E(X|T)P(T) + E(X|HTH)P(HTH) + E(X|HH)P(HH),$

Now $E(X|HTT) = 3$, $\quad E(X|T) = 1+E(X).$

Corresponding probabilities are $P(HTT) = \frac{1}{8}$, $\quad P(T) = \frac{1}{2}$, $\quad P(HTH) = \frac{1}{8}$, $\quad P(HH) = \frac{1}{4}$.

What I don't know is how to compute $E(X|HTH)$ and $E(X|HH)$. Please help.

Answer 1

Let $X$ be the number of flips to get $HTT$.

The goal is to compute $E(X)$.

For each sequence $Y\in\{H,HT\}$, let $X|Y$ be the number of flips to get $HTT$ assuming an initial sequence $Y$ where the sequence $Y$ is allowed to potentially be used to form $HTT$ but where the flip count starts at $0$ after the initial sequence $Y$ (i.e., the length of $Y$ doesn't count toward the flip count).

Then we get the equations $$ \left\lbrace \begin{align*} E(X)&={\small{\frac{1}{2}}}\bigl(1+E(X|H)\bigr)+{\small{\frac{1}{2}}}\bigl(1+E(X)\bigr)\\[4pt] E(X|H)&={\small{\frac{1}{2}}}\bigl(1+E(X|H)\bigr)+{\small{\frac{1}{2}}}\bigl(1+E(X|HT)\bigr)\\[4pt] E(X|HT)&={\small{\frac{1}{2}}}\bigl(1+E(X|H)\bigr)+{\small{\frac{1}{2}}}\\[4pt] \end{align*} \right. $$ which is a system of $3$ linear equations in the $3$ unknowns $E(X),E(X|H),E(X|HT)$.

Solving the system yields $E(X)=8$.

Answer 2

Conditional Approach

$T$ represents a $T$ before the first $H$; all other $T$s are covered below.
The other cases are $H$, $TH$, $TT$

Equations

Tossing an initial $T$ just adds one to the expected duration $$ E[X|T]=1+E[X]\tag1 $$ Tossing an $H$ adds $1$ and then $H$, $TH$, or $TT$ $$ E[X|H]=1+\frac12E[X|H]+\frac14E[X|TH]+\frac14E[X|TT]\tag2 $$ Tossing a $TH$ adds $2$ and then $H$, $TH$, or $TT$ $$ E[X|TH]=2+\frac12E[X|H]+\frac14E[X|TH]+\frac14E[X|TT]\tag3 $$ Tossing $TT$ after the first $H$ adds $2$ and ends $$ E[X|TT]=2\tag4 $$ The expected duration is $$ E[X]=\frac12E[X|T]+\frac12E[X|H]\tag5 $$ Solution

Equations $(1)$ and $(5)$ give $$ E[X]=1+E[X|H]\tag6 $$ Equations $(2)$ and $(3)$ give $$ E[X|TH]=1+E[X|H]\tag7 $$ Plugging $(4)$ and $(7)$ into $(2)$ gives $$ E[X|H]=7\tag8 $$ Finally, $(6)$ and $(8)$ yield $$ E[X]=8\tag9 $$

---

Generating Function Approach

The possible string of $H$s and $T$s can start with any number of $T$s, whose generating function is $$ 1+\frac x2+\frac{x^2}4+\frac{x^3}8+\cdots=\frac1{1-\frac x2}\tag{10} $$ Note that the exponent of $x$ represents the number of tosses, while the coefficient represents the probability.

After the initial string of $T$s, atoms of $H$ and $HT$ can follow, whose generating function is $$ 1+\overbrace{\left(\frac x2+\frac{x^2}4\right)^{\vphantom{2}}}^\text{$1$ atom}+\overbrace{\left(\frac x2+\frac{x^2}4\right)^2}^\text{$2$ atoms}+\cdots=\frac1{1-\frac x2-\frac{x^2}4}\tag{11} $$ Finally, the string must end with $HTT$ whose generating function is $$ \frac{x^3}8\tag{12} $$ Thus, the full generating function is $$ \begin{align} f(x) &=\overbrace{\ \frac{1\vphantom{x^3}}{1-\frac x2}\ }^{\substack{\text{any number}\\\text{of $T$s}}}\overbrace{\frac{1\vphantom{x^3}}{1-\frac x2-\frac{x^2}4}}^{\substack{\text{any number}\\\text{of $H$ and $HT$s}}}\overbrace{\quad\frac{x^3}8\quad}^{\substack{\text{terminal}\vphantom{\text{y}}\\\text{$HTT$}}}\tag{13}\\ &=\frac{x^3}{x^3-8x+8}\tag{14}\\[6pt] %&=\frac{x^3}8+\frac{x^4}8+\frac{x^5}8+\frac{7x^6}{64}+\frac{3x^7}{32}+\frac{5x^8}{64}+\cdots \end{align} $$ The coefficient of $x^n$ is the probability that we get $HTT$ after exactly $n$ tosses. Thus, since $$ \begin{align} f(x) &=\sum\limits_{k=0}^\infty p_kx^k\tag{15}\\ &=\frac{x^3}{x^3-8x+8}\tag{16} \end{align} $$ the total probability of all possibilities is $f(1)=1$.

Furthermore, since $$ \begin{align} f'(x) &=\sum\limits_{k=0}^\infty kp_kx^{k-1}\tag{17}\\ &=\frac{8x^2(3-2x)}{\left(x^3-8x+8\right)^2}\tag{18} \end{align} $$ the expected duration is $f'(1)=8$.