Series summation of polynomial on x multiplied by x power summation

Question

An unbiased coin is tossed repeatedly and outcomes are recorded. What is the expected no of toss to get HT ( one head and one tail consecutively) ?

I tried to solve above question using the following probability tree diagram.

Probability in each branch is = $0.5$. I double circled the satisfying toss events. While observing the diagram I noticed that, from 2nd toss onward our required event starts showing up. Additionally,

1. in the $\text{2nd}$ toss (or the 3rd level) we have one satisfying case.
2. in the $\text{3rd}$ toss (or the 4th level) we have two satisfying case.
3. in the $\text{4th}$ toss (or the 5th level) we have three satisfying case.
4. in the $\text{5th}$ toss (or the 6th level) we have four satisfying case.
5. etc.

i.e. in the $\text{kth}$ toss we would have $(k-1)$ satisfying case. So,

$\\ E = \sum_{k=2}^{\infty } k.P(k)\ \\ E = \sum_{k=2}^{\infty } k.\left \{ (k-1)*(0.5)^k \right \}\\ \\ E = \sum_{k=2}^{\infty } \left \{ (k^2-k)*(0.5)^k \right \}\\$

I understand the series summation would converge because we have the $0.5^{k}$ term which eventually becomes zero.

But could not solve this polynomial and power series summation.

Please suggest how to solve this and or any other method.

Answer 1

We can describe all valid tosses as follows:

The valid tosses are

• zero or more tosses of T followed by
• zero or more tossed of H followed by
• HT

This corresponds to the tree diagram where we can see following valid paths starting from the root

\begin{array}{lllllllllll} &HT\qquad&H^2T\qquad&H^3T\qquad&\color{blue}{H^4T}\qquad&H^5T\qquad&\cdots\\ &THT&TH^2T&\color{blue}{TH^3T}&TH^4T&TH^5T&\cdots\\ &T^2HT&\color{blue}{T^2H^2T}&T^2H^3T&T^2H^4T&T^2H^5T&\cdots\\ &\color{blue}{T^3HT}&T^3H^2T&T^3H^3T&T^3H^4T&T^3H^5T&\cdots\\ &T^4HT&T^4H^2T&T^4H^3T&T^4H^4T&T^4H^5T&\cdots\\ &\quad\vdots&\quad\vdots&\quad\vdots&\quad\vdots&\quad\vdots&\\ \end{array}

Note the entries in a diagonal have the same length, starting with the first node $HT$ of length $2$. The entries in the diagonal with length $5$ are marked in blue.

From this scheme we can derive the expectation value. We obtain following the same arrangement

\begin{align*} E[X]=\sum_{n=2}^\infty x_n p_n&=2p(HT)+3p(H^2T)+4p(H^3T)+\color{blue}{5p(H^4T)}+\cdots\\ &\qquad+3p(THT)+4p(TH^2T)+\color{blue}{5p(TH^3T)}+6p(TH^4T)+\cdots\\ &\qquad+4p(T^2HT)+\color{blue}{5p(T^2H^2T)}+6p(T^2H^3T)+7p(T^2H^4T)+\cdots\\ &\qquad+\color{blue}{5p(T^3HT)}+6p(T^3H^2T)+7p(T^3H^3T)+8p(T^3H^4T)+\cdots\\ &\qquad+\cdots\\ \end{align*}

We can add up these values along the diagonals. Note, the diagonal marked in blue has $4$ entries

$$\{HHHHT,THHHT,TTHHT,TTTHT\}$$ of length $5$.

We obtain \begin{align*} E[X]&=\sum_{n=1}^\infty n(n+1)\left(\frac{1}{2}\right)^{n+1}\\ &=\left.\sum_{n=1}^\infty n(n+1)x^{n+1}\right|_{x=\frac{1}{2}}\\ &=x^2\left.\sum_{n=1}^\infty n(n+1)x^{n-1}\right|_{x=\frac{1}{2}}\\ &=x^2\left.\sum_{n=2}^\infty (n-1)nx^{n-2}\right|_{x=\frac{1}{2}}\\ &=\left.\left(x^2D_x^2\sum_{n=0}^\infty x^n\right)\right|_{x=\frac{1}{2}}\\ &=\left.\left(x^2D_x^2\frac{1}{1-x}\right)\right|_{x=\frac{1}{2}}\\ &=\left.\frac{2x^2}{(1-x)^3}\right|_{x=\frac{1}{2}}\\ &=4 \end{align*}

Here we use the differential operator $D_x:=\frac{d}{dx}$ and apply it to the geometric series.

Answer 2

You can treat this as a Markov Chain with the following states:

End, Head, Tail (not end) (or equivalently worded, HT has occured, heads is most recent result, and no heads have occured respectively)

This has the transition matrix $\begin{bmatrix}1&0.5&0\\0&0.5&0.5\\0&0&0.5\end{bmatrix}$, which is in the standard form for an absorbing chain: $\left[\begin{array}{c|c}I&S\\\hline0&R\end{array}\right]$

We look to the fundamental matrix: $(I-R)^{-1}$ which in this case is $\begin{bmatrix}0.5&-0.5\\0&0.5\end{bmatrix}^{-1} = \frac{1}{1/4}\begin{bmatrix}0.5&0.5\\0&0.5\end{bmatrix}=\begin{bmatrix}2&2\\0&2\end{bmatrix}$

The fundamental matrix holds the information about how many steps are expected until we reach an absorbing state. Since our initial state can be thought of as being a tail (or more correctly worded, as being that no head has yet occurred), we look to the corresponding column and add the entries to find the expected time.

In this case, we see it will take an expected number of $2+2=4$ flips to have flipped a tails after a heads.