Where we do NOT require that the heads or tails be consecutive (though they may be!)

Obviously, this expectation, $E[T]$, is bound as follows: $N < E[T] < 2N - 1$

And obviously $E[T] = \sum_{i=N}^{n=2N-1}i*P[Game \ Ends \ On \ i^{th} \ Round]$, where $\sum_{i=N}^{n=2N-1}P[Game \ Ends \ On \ i^{th} \ Round] = 1$

But how would one find such a probability for an arbitrary $i \in \{N, N+1, ..., 2N-1\}$?

  • $\begingroup$ You might be asking a question related to negative binomial distribution. check this link en.wikipedia.org/wiki/Negative_binomial_distribution $\endgroup$ – Vamshi Kumar Kurva Aug 9 at 9:41
  • 1
    $\begingroup$ Well this is Banach matchbox problem... :-) en.wikipedia.org/wiki/Banach%27s_matchbox_problem $\endgroup$ – Olivier Aug 9 at 10:45
  • $\begingroup$ And, according to the same reference, your expectation will satisfy $2n - \mathbb E[T_n] \sim (2/ \sqrt{\pi}) \sqrt{n}$ - I have not done the calculation again... $\endgroup$ – Olivier Aug 9 at 10:48
  • $\begingroup$ I don't think this problem is quite the same as the Banach Matchbox Problem, but it is certainly similar! I'll go and play around with it for a bit. $\endgroup$ – TeenPhilosopher Aug 9 at 13:02
  • 1
    $\begingroup$ @Olivier: according to my answer, $2n-\mathbb{E}[T_n]=2n\frac{\binom{2n}{n}}{4^n}\sim\frac{2n}{\sqrt{\pi n}}$, which agrees. $\endgroup$ – robjohn Aug 13 at 13:32

The probability that the game ends at round $i$ is:$$\binom{i-1}{N-1}2^{1-i}$$If e.g. the game ends with a tail at $i$-th round then among the $i-1$ results in the former rounds must be $N-1$ tails. There are $\binom{i-1}{N-1}$ configurations for that and each of them has probability $2^{1-i}$ to occur. Further we must multiply with the probability that a tail will appear at $i$-th trial which is $\frac12$. Same outcome if the game ends with a head at $i$-th round so a multiplication with $2$ is also needed.

So to be found is:


  • $\begingroup$ Absolutely brilliant! Thank you so much! I would like to think that I gave this problem an honest and fair try, but it seems that my combinatorics abilities still has quite a ways to go! $\endgroup$ – TeenPhilosopher Aug 9 at 13:01
  • $\begingroup$ You are welcome. Just keep on developing these abilities. Your mathematical maturity will grow then. $\endgroup$ – drhab Aug 9 at 14:01

Preliminary Formula $$ \begin{align} a_n &=\sum_{m=n}^{2n}\frac1{2^m}\binom{m}{n}\\ &=\sum_{m=n}^{2n}\frac1{2^m}\left[\binom{m-1}{n}+\binom{m-1}{n-1}\right]\\ &=\frac12\sum_{m=n-1}^{2n-1}\frac1{2^m}\left[\binom{m}{n}+\binom{m}{n-1}\right]\\ &=\frac12\left[a_n-\frac1{2^{2n}}\binom{2n}{n}+a_{n-1}+\frac1{2^{2n-1}}\binom{2n-1}{n-1}\right]\\[3pt] &=\frac12(a_n+a_{n-1})\\[9pt] &=a_{n-1}\tag1 \end{align} $$ and since $a_0=1$, we have $$ \bbox[5px,border:2px solid #C0A000]{\sum_{m=n}^{2n}\frac1{2^m}\binom{m}{n}=1}\tag2 $$

The Answers

The number of ways to get to $n$ heads on flip $m$ and not on flip $m-1$ is $$ \binom{m}{n}-\binom{m-1}{n}=\binom{m-1}{n-1}\tag3 $$ This is also the number of ways to get to $n$ tails on flip $m$ and not on flip $m-1$. Thus, the probability of getting to $n$ heads or $n$ tails on flip $m$ and not on flip $m-1$ is $$ \frac2{2^m}\binom{m-1}{n-1}=\bbox[5px,border:2px solid #C0A000]{\frac1{2^{m-1}}\binom{m-1}{n-1}}\tag4 $$ Note that $(2)$ shows that $$ \sum_{m=n}^{2n-1}\frac1{2^{m-1}}\binom{m-1}{n-1}=1\tag5 $$ That is, the probability of getting $n$ heads or $n$ tails by flip $2n-1$ is $1$. The expected duration is then $$ \begin{align} \sum_{m=n}^{2n-1}\frac{m}{2^{m-1}}\binom{m-1}{n-1} &=2n\sum_{m=n}^{2n-1}\frac1{2^m}\binom{m}{n}\\ &=\bbox[5px,border:2px solid #C0A000]{2n\left(1-\frac1{4^n}\binom{2n}{n}\right)}\tag6 \end{align} $$

  • $\begingroup$ To match the variables in the question, $m\mapsto i$ and $n\mapsto N$. $\endgroup$ – robjohn Aug 10 at 17:01

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.