# Expected value of number of tosses until we get $k$ tails and $k$ heads

Let $k$ be a fixed positive number. We toss a normal coin until we get at least $k$ heads and at least $k$ tails (not necessarily consecutively). Let $X$ be number of needed tosses. Find distribution of $X$ and its expected value.

So this is my attempt: first of all, we see that $P(X=j)$ is $0$ for $j<2k$. For $j \ge 2k$ we have the following:

Let A be the event that in the last toss we get a head.

Let B be the event that in the last toss we get a tail. So:

$P(X=j) = P(X=j | A) P(A) + P(X=j|B) P(B) =$ ${j-1}\choose{k-1}$$(\frac{1}{2})^{j-1} \frac{1}{2} + {j-1}\choose{k}$$ (\frac{1}{2})^{j-1} \frac{1}{2} = (\frac{1}{2})^j [$${j-1}\choose{k-1} {j-1}\choose{k}$$] = (\frac{1}{2})^j $${j}\choose{k} So I found the distribution of X. But the problem comes with the expected value: E(X) = \sum_{j=2k}^\infty j (\frac{1}{2})^j$${j}\choose{k}$=...

How to compute it? May you help me and show me how?

First of all, your formula for the probability is not quite correct. You should have $p_j={j-1\choose k-1}(1/2)^{j-1}$ for $j\geq 2k$ and zero otherwise. In particular, this gives
$$1=\sum_{j\geq 2k}{j-1\choose k-1}(1/2)^{j-1}=\sum_{j-1>2(k-1)}{j-1\choose k-1}(1/2)^{j-1}.\tag1$$

To find the expected value, we calculate (using (1) and the absorption identity) \begin{eqnarray*} \sum_{j\geq 2k}j{j-1\choose k-1}\left({1\over2}\right)^{j-1} &=&\sum_{j\geq 2k} k{j\choose k}\left({1\over2}\right)^{j-1}\\[8pt] &=&2k\sum_{j\geq 2k} {j\choose k}\left({1\over2}\right)^{j}\\[8pt] &=&2k\left(1+{2k\choose k}\left({1\over2}\right)^{2k}\right). \end{eqnarray*}

• Thank You for your answer. Can you just explain me how did you get the last equality?
– Anne
May 19, 2014 at 19:47
• When you apply formula (1), you see that $\sum_{j>2k}{j\choose k}\left({1\over 2}\right)^j=1.$
– user940
May 19, 2014 at 20:05
• That's right, thank you!
– Anne
May 19, 2014 at 21:36

Let $D$ denote the absolute difference between the number of heads and the number of tails at time $2k$, then $[D=0]$ means that one produced $k$ heads and $k$ tails in $2k$ throws hence $$P(D=0)={2k\choose k}\cdot\frac1{2^{2k}},$$ and, for every $1\leqslant i\leqslant k$, $[D=2i]$ means that one produced $k+i$ heads and $k-i$ tails in $2k$ throws, or the other way round, hence $$P(D=2i)=2\cdot{2k\choose k+i}\cdot\frac1{2^{2k}}.$$ If $D=0$, then $X=2k$. If $D=2i$, then $X=2k+T_{i}$ where $T_{i}$ is the time necessary to produce $i$ new heads in a new game of heads-and-tails. Let $T_0=0$. Thus, for every $n\geqslant0$, $$P(X=2k+n)=\sum_{i=0}^kP(D=2i)P(T_{i}=n).$$ Furthermore, each $T_{i}$ is the sum of $i$ times necessary to produce one head, that is, of $i$ i.i.d. random variables $G_k$ with geometric distribution of parameter $\frac12$. Thus, $$P(X=2k)=P(D=0)={2k\choose k}\cdot\frac1{2^{2k}},$$ and, for every $n\geqslant1$, $$P(X=2k+n)=\sum_{i=1}^kP(D=2i)P(G_1+\cdots+G_{i}=n).$$ A consequence is that the expectation is $$E(X)=2k+\sum_{n\geqslant1}P(X\geqslant 2k+n),$$ that is, $$E(X)=2k+\sum_{i=1}^kP(D=2i)\sum_{n\geqslant1}P(G_1+\cdots+G_{i}\geqslant n).$$ Each inner sum is $E(G_1+\cdots+G_{i})=iE(G_1)=2i$ hence $$E(X)=2k+2i\sum_{i=1}^kP(D=2i)=2k+E(D).$$ Maybe you can carry on from here?

• I think you want $X=2k+T_i$ the time to add $i$ new heads, not $2i$ new heads.
– user940
May 19, 2014 at 17:29
• @ByronSchmuland I definitely do (and you know what, with this modification, I think one falls back on your formula). Thanks a bunch.
– Did
May 19, 2014 at 17:31
• Yep, now our answers are the same.
– user940
May 19, 2014 at 17:51