3
$\begingroup$

A fair coin is tossed repeatedly and independently until two consecutive heads or two consecutive tails appear . What is the probability of the number of tosses ?


I tried it as :

For success, either we end up getting

  • HH,THH,HTHH,............
  • TT,HTT,THTT,.............

Then, Add up both the successes. Am I right with my understanding ?

$\endgroup$
  • $\begingroup$ What do you mean "probability of the number of tosses". Do you mean the expected value of the number of tosses? $\endgroup$ – gowrath Dec 25 '16 at 4:11
  • $\begingroup$ @gowrath I guess so. $\endgroup$ – Jon Garrick Dec 25 '16 at 4:24
  • $\begingroup$ @Garrick can you please tell me the answer. $\endgroup$ – Kanwaljit Singh Dec 25 '16 at 5:38
  • $\begingroup$ @bof That's a fair interpretation that I hadn't thought of. This sounds like a classic expected value question though. $\endgroup$ – gowrath Dec 25 '16 at 5:45
3
$\begingroup$

While other answers are correct, they don't explain the solution.

I am assuming your question is about the expected number of coin tosses. Let $X$ be the discreet random variable that is the number of throws until two of the same coin are observed. Your question is asking about the expected value of $X$ i.e. $E(X)$.

It is evident $P(X=1)= 0$.

So what is $P(X=2)$? In other words, what is the probability the game terminates after two tosses? Well whatever the first coin was, the probability of the second toss being the same is $1 \over 2$ So $P(X=2) = \frac{1}{2}$.

Similarly consider $P(X=3)$ which is the probability the game terminates after $3$ tosses. Whatever is tossed first, there is a $1 \over 2$ chance that the second throw is different and then a $1 \over 2$ chance the third throw is the same as the second. So the total probability is $P(X=3) = \frac{1}{ 2^2}$.

Continuing the pattern, we get that the probability of the game terminating after $n$ throws, for $n \geq 2$, is $P(X=n) = \frac{1}{2^{n-1}}$. Alternatively, the probability of the game terminating after $n+1$ throws, for $n \geq 1$, is $P(X=n+1) = \frac{1}{2^{n}}$.

Thus the expected value $E(X)$ is given by:

$$ \begin{align} E(X) &= \sum_{n = 1}^{\infty}(n+1) \cdot P(X = n+1) \\ &= \sum_{n = 1}^{\infty}(n+1) \cdot \frac{1}{2^{n}} \\ &= \sum_{n = 1}^{\infty}\frac{n}{2^n} + \sum_{n = 1}^{\infty}\frac{1}{2^{n}} \end{align} $$

We know the right term: $\sum_{n = 1}^{\infty}\frac{1}{2^{n}}$ is a geometric progression and is given by: $$ \begin{align} \sum_{n = 1}^{\infty}\frac{1}{2^{n}} &= \frac{1}{2} \cdot \frac{1}{1+ \frac{1}{2}} \\ &= 1 \end{align} $$

The other sum, $\sum_{n = 1}^{\infty}\frac{n}{2^n}$ is slightly harder but we can do a bit of trickery. Let us call the sum $S$ and consider $\frac{S}{2}$:

$$ \begin{align} S &= \sum_{n = 1}^{\infty}\frac{n}{2^n} \\ \frac{S}{2} &= \sum_{n = 1}^{\infty}\frac{n}{2^{n+1}} = \sum_{n = 1}^{\infty}\frac{n-1}{2^n} \\ \end{align} $$

Note how we shifted the indices in the second line for easier manipulation. Subtracting the two lines gives:

$$ \begin{align} S - \frac{S}{2} = \frac{S}{2} &= \sum_{n = 1}^{\infty}\frac{n}{2^n} - \sum_{n = 1}^{\infty}\frac{n-1}{2^n} \\ &= \sum_{n = 1}^{\infty}\frac{n}{2^n} - \frac{n-1}{2^n} \\ &= \sum_{n = 1}^{\infty}\frac{1}{2^n} \\ &= 1 \end{align} $$

and so $\frac{S}{2} = 1$ giving $S = 2$.

So in total:

$$ \begin{align} E(X) &= \sum_{n = 1}^{\infty}\frac{n}{2^n} + \sum_{n = 1}^{\infty}\frac{1}{2^{n}} \\ &= 2 + 1 = 3\\ \end{align} $$


Addendum (thanks to @bof)

An alternative, and excellent explanation offered by @bof is that:

$$ E(X)=\sum_{k=1}^\infty P(X\ge k)=1+1+\frac12+\frac14+\frac18+\cdots=3. $$

To see why this is, consider the following (quoted from bof's comment):

Since $X$ takes only positive integer values, $$ \begin{array} \ P(X\ge1)= &P(X=1)&+ & P(X=2) & + & P(X=3)+\cdots \\ P(X\ge2)= & & & P(X=2) & + & P(X=3)+\cdots \\ P(X\ge3)= & & & & & P(X=3)+\cdots \\ \end{array} $$ Adding by columns: $$\sum_{k=1}^\infty P(X\ge k)=P(X=1)+2P(X=2)+3P(X=3)+\cdots=E(X).$$

In other words: Let the "indicator variable" $X_k=1$ if the kth toss is needed (no HH or TT in first $k-1$ tosses), $X_k=0$ otherwise; then $X=\sum_{k=1}^\infty X_k$ so

$$ E(X)=\sum_{k=1}^\infty E(X_k)=\sum_{k=1}^\infty P(X\ge k). $$

$\endgroup$
  • $\begingroup$ @bof I see why this is true but it is not immediately obvious for those less versed in probability. Could you explain in a comment here or write up an answer as to why $E(X) = \sum_{k=1}^{\infty}P(X \geq k)$ for the people looking at this question? Or if you would prefer, I can append it to my answer. $\endgroup$ – gowrath Dec 25 '16 at 5:52
  • $\begingroup$ @bof Done (y). Great explanation! $\endgroup$ – gowrath Dec 25 '16 at 6:37
3
$\begingroup$

Your enumerations of the possibilities are correct. We must compute the probability of each:

$\overbrace{\ \ \ \ HH\ \ \ \ }^{\normalsize\frac14},\overbrace{\ \ \ THH\ \ \ }^{\normalsize\frac18},\overbrace{\ HTHH\ }^{\normalsize\frac1{16}},\overbrace{THTHH}^{\normalsize\frac1{32}}\quad$ length $k$ has probability $2^{-k}$
$\overbrace{\ \ \ \ TT\ \ \ \ }^{\normalsize\frac14},\overbrace{\ \ \ HTT\ \ \ }^{\normalsize\frac18},\overbrace{\ \ THTT\ \ }^{\normalsize\frac1{16}},\overbrace{HTHTT}^{\normalsize\frac1{32}}\quad$ length $k$ has probability $2^{-k}$

Thus, the probability of lasting $k$ tosses is $2^{-k+1}$ for $k\ge2$.

Therefore, the expected number of tosses would be $$ \sum_{k=2}^\infty k2^{-k+1}=3 $$


Derivation of the Last Sum $$ \begin{align} \sum_{k=2}^\infty k2^{-k+1} &=\sum_{k=2}^\infty\binom{k}{k-1}2^{-k+1}\tag1\\ &=\sum_{k=2}^\infty\binom{-2}{k-1}\left(-\frac12\right)^{k-1}\tag2\\ &=\sum_{k=0}^\infty\binom{-2}{k}\left(-\frac12\right)^k-1\tag3\\ &=\left(1-\frac12\right)^{-2}-1\tag4\\[12pt] &=3\tag5 \end{align} $$ Explanation:
$(1)$: $k=\binom{k}{k-1}$
$(2)$: $\binom{k}{k-1}=(-1)^{k-1}\binom{-2}{k-1}$ (Negative Binomial Coefficients)
$(3)$: substitute $k\mapsto k+1$ and add the $k=0$ term ($=1$) to the sum and subtract $1$
$(4)$: Binomial Theorem
$(5)$: evaluate

$\endgroup$
  • $\begingroup$ The probability of lasting $k$ tosses should be $\frac{1}{2^{k-1}}$ no? $\endgroup$ – gowrath Dec 25 '16 at 4:31
  • $\begingroup$ I believe that's what I have there. $\endgroup$ – robjohn Dec 25 '16 at 4:32
  • $\begingroup$ Ah there are parentheses missing. Thanks (y) $\endgroup$ – gowrath Dec 25 '16 at 4:32
  • $\begingroup$ You should show how you compute the sum. $\endgroup$ – Royi Oct 8 '17 at 23:05
  • $\begingroup$ @Royi: Although I think that the derivation of the sum is a bit off topic for this answer, I have added it. $\endgroup$ – robjohn Oct 9 '17 at 3:29

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.