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

Question

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?

Answer 1

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*}

Answer 2

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?