The question is

Suppose 100 fair coins were flipped. Given that there are at least as many heads as tails, what's the expected number of heads?

Brute forcing, the answer is easy: if $n \geq 50$, one can compute $P(n | H \geq T)$ and use this to compute $$E = \sum_{n=50}^{100} n*P(n | H \geq T) = 53.6861.$$ Are there any general techniques or heuristics to approximate this answer without a calculator, perhaps with the central limit theorem followed by the empirical rule?

  • $\begingroup$ The half-normal distribution could be helpful to you here. $\endgroup$ – JMoravitz Aug 27 '16 at 1:49
  • $\begingroup$ PS: "More heads than tails" means $H>T$ rather than $H\geq T$. $\endgroup$ – Graham Kemp Aug 27 '16 at 2:57
  • $\begingroup$ Ah typo on my part, its supposed to be at least as many heads as tails $\endgroup$ – user369210 Aug 27 '16 at 4:48

Sure - the binomial distribution is (for 100 flips) approximately normal with expectation 50 and standard deviation of 5. For the unit normal distribution, the expectation conditioned on $x \ge 0$ is $\sqrt{2/\pi}$ (as the OP pointed out in a comment, I had 1 when I posted initially) - by direct computation with change of variables, so after translation and scaling the answer to your question should be 53.9894. However, that answer assumes only 1/2 of the many cases when you have equal number of heads and tails. In the actual computation, you are including all of them, so this will drag down the expectation for your problem. By how much? Well, by a non-trivial amount it seems; 53.6861 is close to 53.9894, but not very close. For 1000000 flips the answer will be much closer (in relative terms).

  • $\begingroup$ Why 55? $\qquad\qquad$ $\endgroup$ – user369210 Aug 27 '16 at 1:51
  • $\begingroup$ Shift right by 50 and scale horizontally by 5 (shift for the expected value of 5, scale for the standard deviation of 5). $\endgroup$ – mathguy Aug 27 '16 at 1:55
  • $\begingroup$ Isn't the expectation conditioned on $X> 0$ equal to $\sqrt{2/\pi}$? $\endgroup$ – user369210 Aug 27 '16 at 2:03
  • $\begingroup$ err... sorry, you are right; I forgot the constants in the density for the normal! So perhaps the result is actually very close... $\endgroup$ – mathguy Aug 27 '16 at 2:09

Indicator functions are a very useful tool for finding expectations, thanks to the linearity of expectation.

There are $100$ Bernoulli trials with success rate $1/2$.   Let $X$ count the number of heads, $Y$ the number of tails.   So $X,Y\sim\mathcal {Bin}(100,1/2)$ and $Y=100-X$.

Then $X>Y$ means $X>50$.

We ask, what is the probability that any particular toss is a head when give such condition?   Which is the expectation of the indicator function $X_k$, given the condition.

$$\begin{align}\mathsf E(X_k\mid X>Y)~=~&\mathsf P(X_{k}=1\mid X>50) \\[1ex]~=~&\mathsf P(X_{100}=1\mid X>50) \\[1ex]=~& \dfrac{\mathsf P(X_{100}=1)~\mathsf P(\sum_{j=1}^{99} X_j>49)}{\mathsf P(X_{100}=1)~\mathsf P(\sum_{j=1}^{99} X_j>49)+\mathsf P(X_{100}=0)~\mathsf P(\sum_{j=1}^{99} X_j>50)} \\[1ex]=~& \dfrac{\mathsf P(\sum_{j=1}^{99} X_j>49)}{\mathsf P(\sum_{j=1}^{99} X_j>49)+\mathsf P(\sum_{j=1}^{99} X_j>50)} \\[1ex]=~& \dfrac{\tfrac 12}{\tfrac 12+(\tfrac 12-\mathsf P(\sum_{j=1}^{99} X_j=50))} \\[1ex]=~& \dfrac{\tfrac 12}{1-\tfrac 1{2^{99}}\binom{99}{50}} \\[3ex] \therefore\quad \mathsf E(X\mid X>Y)~=~& \dfrac{2^{99}50}{2^{99}-\binom{99}{50}} \\[1ex]~\approx~& 54.3{\tiny 2357163888677080506821478650525162917956114844...} \end{align}$$

  • $\begingroup$ It seems you still need a calculator for the binomial coefficient... $\endgroup$ – mathguy Aug 27 '16 at 3:50
  • $\begingroup$ Note that the result is for $X>Y$. The OP said "more" but then in the rest of the problem description he used $\ge$. The exact answer is approx. $54.3$ for $>$ and approx. $53.7$ for $\ge$. The normal approximation gives the average, $54.0$ (obviously). $\endgroup$ – mathguy Aug 27 '16 at 3:52
  • $\begingroup$ The question was edited after this answer was posted. $\endgroup$ – Graham Kemp Aug 28 '16 at 2:09
  • $\begingroup$ OK, I see that. Your answer was correct in any case, since you stated explicitly what you calculated. $\endgroup$ – mathguy Aug 28 '16 at 2:11

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.