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.

enter image description here

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.


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.

  • $\begingroup$ The wiki link directly points me the exact required formula. Thanks. $\endgroup$ – Debashish Sep 26 '16 at 5:39
  • 1
    $\begingroup$ @Debashish: You're welcome! Good to see the answer is helpful! $\endgroup$ – Markus Scheuer Sep 26 '16 at 6:32

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.

  • $\begingroup$ Thanks ! please suggest or give some good reference regarding this Markov Chain Method. $\endgroup$ – Debashish Sep 24 '16 at 6:38
  • 1
    $\begingroup$ The wikipedia links I already included have a good bit of information in them. Otherwise, PatrickJMT covers the basics rather well, though his notation differs from mine and textbooks from which I've taught and studied from in the past in that he uses row-stochastic matrices instead of column-stochastic matrices, so his state vectors will appear on the left and have rows summing to one, whereas I would write it with column vectors on the right of matrix with columns summing to one. He begins discussing absorbing chains in part 7 of his videos. $\endgroup$ – JMoravitz Sep 24 '16 at 6:46

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.