Calculate expected number of heads in 10+$\xi$ coin tosses (GRE problem)

Question

This is a problem from a preparatory GRE preparatory GRE test made by guys form University of Chicago.

Problem: A man flips $10$ coins. With $H$ the number of heads, and $T$ the number of tails, the man then flips $\max \left\{2 H-T^2, 0\right\}$ coins. What is the expected number of heads of both groups?

---

My solution (giving wrong answer): Let $X$ be the random variable corresponding to the number of heads in both groups. Note that $2H-T^2<0$ for $H<7$ and $2H-T^2>0$ for $H\geq 7.$ To my understanding, the answer must be $$\mathbb{E}(X)=\mathbb{E}(H | 2H-T^2\leq 0) \mathbb{P}(2H-T^2\leq 0) +\mathbb{E}(\xi_1+\xi_2+\xi_3+\xi_4)\mathbb{P}(2H-T^2 > 0),$$ where $\xi_1=7+\text{"number of heads in 5 additional tosses"},\\ \xi_2=8+\text{"number of heads in 12 additional tosses"},\\ \xi_3=9+\text{"number of heads in 17 additional tosses"},\\ \xi_4=10+\text{"number of heads in 100 additional tosses"}.$

Now let's try to carefully calculate that.

1. $\mathbb{E}(\xi_1+\xi_2+\xi_3+\xi_4)=\sum\limits_{i=1}^4\mathbb{E}(\xi_i)=(7+2.5)+(8+6)+(9+8.5)+(10+50)=101.$

2. $\mathbb{P}(2H-T^2\leq 0)=\mathbb{P}(H<7)=\frac{1}{2^{10}}+\frac{10}{2^{10}}+\frac{C_{10}^2}{2^{10}}+\frac{C_{10}^3}{2^{10}}+\frac{C_{10}^4}{2^{10}}+\frac{C_{10}^5}{2^{10}}+\frac{C_{10}^6}{2^{10}}=\frac{848}{2^{10}}.$ Consequently, $\mathbb{P}(2H-T^2> 0)=1-\frac{848}{2^{10}}=\frac{176}{2^{10}}.$

3. Finally, \begin{align*} &\mathbb{E}(H | 2H-T^2\leq 0)=\sum\limits_{n=0}^6 n \mathbb{P}(H=n | H<7)=\sum\limits_{n=0}^6 n \frac{\mathbb{P}(H=n \text{ and } H<7)}{\mathbb{P}(H<7)}=\\ &=\frac{1}{\mathbb{P}(H<7)}\sum\limits_{n=0}^6 n \mathbb{P}(H=n)=\frac{2^{10}}{848} \sum\limits_{n=0}^6 n \frac{C_{10}^n}{2^{10}}=\frac{1}{848} \sum\limits_{n=0}^6 n C_{10}^n=\frac{3820}{848}. \end{align*}

So, $$\mathbb{E}(X)=\frac{3820}{848} \frac{848}{2^{10}} +101 \frac{176}{2^{10}}=\frac{3828+101 \cdot 176}{2^{10}} > 21.$$

---

My questions:

1. Where did I make a mistake? According to the authors, correct answer lies between $0$ and $8$. I did the computations on a calculator, so there must be a conceptual error here.

2. Are there ways to simplify the solution? May be with some geometric interpretation or clever observations. In a real exam there are 2.5 minutes per problem, and I am not sure how one is supposed to finish this so quickly.

Thank you.

Answer 1

The point needing an adjustment is: $$ \begin{aligned} \mathbb{E}[X] &=\mathbb{E}[\ H\ |\ 2H-T^2\ \leq 0]\cdot \mathbb{P}(H\le 6\ ,\ T\ge 4\ ,\ 2H-T^2\leq 0) \\ &\qquad\qquad+\mathbb{E}[\ \xi_1\ ]\cdot \mathbb{P}(H=7\ ,\ T= 3\ ,\ 2H-T^2 =5)\\ &\qquad\qquad+\mathbb{E}[\ \xi_2\ ]\cdot \mathbb{P}(H=8\ ,\ T= 2\ ,\ 2H-T^2 =12)\\ &\qquad\qquad+\mathbb{E}[\ \xi_3\ ]\cdot \mathbb{P}(H=9\ ,\ T= 1\ ,\ 2H-T^2 =17)\\ &\qquad\qquad+\mathbb{E}[\ \xi_4\ ]\cdot \mathbb{P}(H=10\ ,\ T= 0\ ,\ 2H-T^2 =20)\\ &= \sum_{0\le n\le 6}n\cdot\frac 1{2^{10}}\binom {10}n \\&\qquad\qquad +\left(7+5\cdot \frac 12\right)\cdot\frac 1{2^{10}}\binom {10}7 \\&\qquad\qquad +\left(8+12\cdot \frac 12\right)\cdot\frac 1{2^{10}}\binom {10}8 \\&\qquad\qquad +\left(9+17\cdot \frac 12\right)\cdot\frac 1{2^{10}}\binom {10}9 \\&\qquad\qquad +\left(10+20\cdot \frac 12\right)\cdot\frac 1{2^{10}}\binom {10}{10}\\ &= 10\cdot \frac 12 \color{gray}{-7\cdot\frac 1{2^{10}}\binom {10}7 -8\cdot\frac 1{2^{10}}\binom {10}8 -9\cdot\frac 1{2^{10}}\binom {10}9 -10\cdot\frac 1{2^{10}}\binom {10}{10}} \\&\qquad\qquad +\left(\color{gray}{7}+5\cdot \frac 12\right)\cdot\frac 1{2^{10}}\binom {10}7 \\&\qquad\qquad +\left(\color{gray}{8}+12\cdot \frac 12\right)\cdot\frac 1{2^{10}}\binom {10}8 \\&\qquad\qquad +\left(\color{gray}{9}+17\cdot \frac 12\right)\cdot\frac 1{2^{10}}\binom {10}9 \\&\qquad\qquad +\left(\color{gray}{10}+20\cdot \frac 12\right)\cdot\frac 1{2^{10}}\binom {10}{10} \\ &=\frac 12\left( 10 +5\cdot\frac{120}{1024} +12\cdot\frac{45}{1024} +17\cdot\frac{10}{1024} +20\cdot\frac{1}{1024} \right) \\ &=5+\frac 1{2048}(600+540+170+20) =5+\frac {1330}{2048} =5+\frac {665}{1024} \\ &=5.6494140625\ . \end{aligned} $$ Here, the mean of the number of heads in an $N$ times repeated Bernoulli experiment with probabilities $p$ for the positive result is $Np$. The above should be doable as it is in five minutes, rough approximations lead also quickly to an upper bound.

---

Computer check:

sage: p = 1/2

sage: sum([n                         * binomial(10, n)*p^10 for n in [0.. 6]]) + \
....: sum([(n + (2*n -(10 - n)^2)*p) * binomial(10, n)*p^10 for n in [7..10]])
5785/1024

sage: _.n()
5.64941406250000

Answer 2

I'm not sure why you include $\mathbb E(\xi_1 + \xi_2 + \xi_3 + \xi_4)$ in your expression for the total expectation; you need to weigh the scenarios by probability. I'm also not sure where the $100$ in your definition of $\xi_4$ comes from. Assuming your other calculations are correct, I get an answer of $$\frac{5785}{1024} \approx 5.65.$$

As for how you can approximate this quickly: you can quickly estimate $\mathbb{P}(H > 7) < 0.2$ by calculating four binomials, and you know that $\mathbb{E}(H | H < 7)$ is less than $5$. Then by assuming the tail probabilities are uniform (which will give an overestimate) and noting that the additional expectation is bounded by $H$, we have

$$ \mathbb{E}(\text{total}) < 5 \cdot 0.8 + \frac{14+16+18+20}{4} \cdot 0.2 < 8. $$ [As the function $5p + 17(1-p)$ is decreasing in $p$, taking $p = 0.8$ suffices.]

Answer 3

A very quick and dirty approximation: Let $X$ be the number of heads in the initial $10$ tosses. Let $Y$ be the number of heads in the bonus tosses. Clearly $E[X]=5$.

One only gets into the bonus with $7$ or more heads. This happens with probability $\frac{1+10+45+120}{1024}=\frac{176}{1024}$. Let's overestimate that probability as $0.2$. In these cases you get at most $20$ bonus tosses. Let's be very generous and take $20$ bonus tosses every time we get $7$ or more heads (again an overestimate). Each time you take $20$ bonus tosses you get an average of $10$ (additional) heads.

So $E[Y]<0.2\cdot 10=2$.

So we have that the expected total number of heads (by linearity of expectation) satisfies: $$E[X+Y]=E[X]+E[Y]<5+2=7$$

Safely within given answer of "between $0$ and $8$".

P.S. I think that the actual expected value is $5+\frac{665}{1024}$, but that requires a more careful calculation.

Answer 4

$\def\ed{\stackrel{\text{def}}{=}}$ You can simplify the calculation by using the rules $$ \mathbb{E}(H_2|N)=\frac{N}{2} $$ and \begin{align} \mathbb{E}(H_2)&=\mathbb{E}(\mathbb{E}(H_2|N))\\ &=\frac{1}{2}\mathbb{E}(N)\ , \end{align} where $\ H_2\ed X-H\ $ is the number of heads occurring in the second group of tosses, and \begin{align} N&\ed\max\big(0,2H-T^2\big)\\ &=\max\big(0,20-2T-T^2\big) \end{align} is the total number of tosses in the second group. The random variable $\ N\ $ is positive if and only if $ 0\le T\le3\ $. Therefore \begin{align} \mathbb{E}(N)&=\frac{1}{2^{10}}\sum_{t=0}^3\big(20-2t-t^2\big){10\choose t}\\ &=\frac{665}{512} \end{align} and $$ \mathbb{E}\big(H_2\big)=\frac{665}{1024}\ . $$