4
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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

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

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?

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

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.