4
$\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$
4
  • $\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$
2
  • $\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$
6
  • $\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

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