# What is the expected number of coin tosses it would take to get N many heads OR N many tails?

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\}$$?

• You might be asking a question related to negative binomial distribution. check this link en.wikipedia.org/wiki/Negative_binomial_distribution – Vamshi Kumar Kurva Aug 9 at 9:41
• Well this is Banach matchbox problem... :-) en.wikipedia.org/wiki/Banach%27s_matchbox_problem – Olivier Aug 9 at 10:45
• 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... – Olivier Aug 9 at 10:48
• 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. – TeenPhilosopher Aug 9 at 13:02
• @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. – 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:

$$\sum_{i=N}^{2N-1}i\binom{i-1}{N-1}2^{1-i}=2N\sum_{i=N}^{2N-1}\binom{i}{N}2^{-i}$$

• 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! – TeenPhilosopher Aug 9 at 13:01
• You are welcome. Just keep on developing these abilities. Your mathematical maturity will grow then. – 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 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}
• To match the variables in the question, $m\mapsto i$ and $n\mapsto N$. – robjohn Aug 10 at 17:01