Suppose that two people are playing a game where they each flip a fair coin 100 times. The winner of this game is the person who has flipped the most heads.

What is the expected number of heads flipped by the winner?

I understand that in general the probability of a given number of heads flipped will be given by the binomial distribution and we can approximate it using a normal distribution. On average, we expect them to both flip around the same number of heads, but conditional on the fact that there will be a winner, we should expect the number of heads of the winner to be slightly above 50. How does one get the distribution of the winning player from the initial distribution?

  • $\begingroup$ How do you want to treat ties? $\endgroup$ – Doug M May 27 '16 at 16:55
  • $\begingroup$ @DougM Correct me if I am wrong, but as $n$ increases, I imagine the effect that ties have would be negligible, so ignoring them would be my first intuition. $\endgroup$ – Andrew Mascioli May 27 '16 at 17:09
  • $\begingroup$ There is a 5.6% chance of getting a tie. Small, but not non-existent. $\endgroup$ – Doug M May 27 '16 at 17:26
  • $\begingroup$ Certainly non-negligible. I believe heropup sidesteps the issue by just computing the expected value of the maximum, and lulu uses the normal distribution, for which the probability of a tie is in fact negligible (it very nearly, but not quite, cuts ties in half). $\endgroup$ – Brian Tung May 27 '16 at 17:35

To approach the problem via normal approximations, let's first think about normal distributions in general

to understand the distribution of the maximum we assume that $X_1,X_2$ are independently distributed as normal variables with mean $\mu$ and standard deviation $\sigma$. We see that $$P(\max (X_1,X_2)<\mu+t\sigma)=P(X_1<\mu+t\sigma)\times P(X_2<\mu+t\sigma)=\Phi(t)^2$$

Where $\Phi$ denotes the standardized normal cdf. Differentiating yields $$E[max]=\mu +\sigma\int_{-\infty}^{\infty}t\frac d{dt}\Phi(t)^2dt=\mu+\frac {\sigma}{\sqrt {\pi}} $$

In your case, you want $\mu=50$ and $\sigma =5$. This approximation gives $\fbox {52.8209479}$.

A few remarks:

As expected, this answer is quite similar to the answer obtained using the more exact method employed by @heropup.

Using the normal lets us ignore the question of ties, which are pretty low probability for large numbers of tosses anyway.

There is a simple closed formula for the expectation of the max of three such variables as well, but above three I am not aware of a pleasant computation for the relevant integral.

  • $\begingroup$ That's a lot of significant digits for an approximate answer. :-P $\endgroup$ – Brian Tung May 27 '16 at 17:32
  • $\begingroup$ @BrianTung Full disclosure: I had included many more digits (just cut and pasted from a program) and actually chose to truncate it where I did. Couldn't defend that choice if I tried. $\endgroup$ – lulu May 27 '16 at 17:34
  • $\begingroup$ Funny! Incidentally, as I mentioned in my comment to the OP, ties are really not that negligible, but the normal approximation treats them as such by fitting a continuous distribution (thereby cutting the ties approximately in half). $\endgroup$ – Brian Tung May 27 '16 at 17:37
  • 1
    $\begingroup$ It's a very skewed distribution...I wouldn't expect this to be a great approximation. You can read more on the distribution here $\endgroup$ – lulu May 27 '16 at 22:01
  • 1
    $\begingroup$ The maximum is not a normal distribution! For skewed distributions there is no particular connection between the point you found and the expected value. Of course, in this case the distribution is fairly tight so it's not shocking that the two numbers are close. More to the point...why would you layer another approximation on top of the normal? The formula I gave is exact for the normal, and it is simpler than your approximation. $\endgroup$ – lulu May 27 '16 at 23:16

Let $X$ be the random number of heads flipped by Player $1$ and $Y$ be the random number of heads flipped by Player $2$. Suppose $X$ and $Y$ are IID binomial random variables with common parameters $n$ and $p$. Then the desired expectation is $$\operatorname{E}[\max(X,Y)] = \sum_{x=0}^n \sum_{y=0}^n \max(x,y) \binom{n}{x} p^x (1-p)^{n-x} \binom{n}{y} p^y (1-p)^{n-y}.$$ For $n = 100$ and $p = 1/2$, computer calculation of this double sum gives $$\operatorname{E}[\max(X,Y)] = \textstyle\frac{5304645496609667364710519591933271144989711198306894287945925}{100433627766186892221372630771322662657637687111424552206336}$$ which is approximately $52.817423950462821112$.

In the large-trial (large $n$) case, a normal approximation to the binomial using $\mu = np$, $\sigma^2 = np(1-p)$ gives (without continuity correction) $$\operatorname{E}[\max(X,Y)] = \mu + \frac{\sigma}{\sqrt{\pi}} = np + \sqrt{\frac{np(1-p)}{\pi}}.$$ I leave this calculation as an exercise. With $n = 100$ and $p = 1/2$, this gives about $52.820947917738781435$. This approximation, as one would expect, becomes progressively worse if $np$ or $n(1-p)$ is very small; e.g., if $n = 100$ and $p = 1/1000$, the exact calculation gives about $0.190914$ but the approximation gives $0.278323$.

  • $\begingroup$ While this gives a correct answer, is there a method that isn't a brute force computation? $\endgroup$ – Andrew Mascioli May 27 '16 at 16:44
  • $\begingroup$ @AndrewMascioli The expectation of the maximum order statistic for two IID binomial variables does not appear to have a simple closed form. We can write the PMF in terms of regularized incomplete beta functions, but I doubt there's a nice expression for a general number of trials $n$ even in the special case $p = 1/2$. $\endgroup$ – heropup May 27 '16 at 16:54
  • $\begingroup$ If you use the normal approximation the calculation is a lot easier (though it's still a calculation). doing it that way I got $52.821$. $\endgroup$ – lulu May 27 '16 at 16:56
  • $\begingroup$ @lulu Indeed, the normal approximation is more tractable and is the more reasonable approach in the large $n$ case. I was going to write a section on this method but didn't have the time. Perhaps you should write a separate answer to that end? $\endgroup$ – heropup May 27 '16 at 16:59
  • $\begingroup$ @heropup It's not surprising to me that using the binomial variables doesn't provide closed form solution. However, given that we have a fairly large N, I think a closed form solution in the normal approximation would be what I'm looking for. $\endgroup$ – Andrew Mascioli May 27 '16 at 17:04

$\sum_\limits{x=0}^{99} P(x)\sum_\limits{y=x+1}^{100} P(y) = P(Y>X)$

$(\sum_\limits{x=0}^{99} P(x)\sum_\limits{y=x+1}^{100} P(y))y = E[y|y>x]P(y>x) = \frac 12 E[Y]$

I am having a hard time remembering exactly why this is....more later...

$\frac {E[Y]}{2P(Y>X)} = \frac {E[Y]}{1-P(X=Y)} = \frac{50}{1-0.0563} = 52.98$

If we relax the condition to $y\ge x$

$E[Y|y=x] = E[Y]\\ E[Y|y\ge x] = E[Y] (1 + P(Y=X)) = 50 (1.0563) = 52.82$


EDIT: I made the mistake of including the case where $|X_1-X_2|=0$ in $E(|X_1-X_2|)$, when that has no impact on it. I've changed that now.

I have a closed form expression that is somewhat inelegant, if anyone is interested. The distribution is clear but I'll proceed as if we didn't know what it was.$$$$

The space of events is $\{0,1\}^{200}$. If $X_1$ is the number of heads flipped by the first player and $X_2$ defined similarly, then $\max\{X_1,X_2\}=\frac{X_1+X_2+|X_1-X_2|}{2}$. Hence, since you want to find $E(X_1\lor X_2)$ (i.e., the pointwise maximum) you want $$E(X_1\lor X_2)=E(\frac{X_1+X_2+|X_1-X_2|}{2})=\frac{1}{2} (E(X_1)+E(X_2)+E(|X_1-X_2|))$$ Now, $E(X_1)=E(\sum_i X_{1,i})$ where $X_{1,i}$ is the indicator of the event that the first player throws $i$ heads. It is clear that there are ${100 \choose i}!$ ways to do that, and $2^{100}$ ways for his opponent to roll his die. Thus, $P(X_1=k)=\frac{{100 \choose k}2^{100}}{2^{200}}$. Thus you have $E(X_1)=\sum_{k=0}^{100}k\frac{{100 \choose k}2^{100}}{2^{200}}=\frac{1}{2^{100}}\sum_{k=0}^{100}k{100 \choose k}=\frac{100\cdot 2^{99}}{2^{100}}=50$. Similarly, $E(X_2)=50$.


Now, if $k>0$, $P(|X_2-X_1|=k)=P(X_1-X_2=k)+P(X_2-X_1=k)$ since $X_1-X_2>0$ xor $X_2-X_1>0$, not both. $P(X_1-X_2=k)=P(X_2-X_1=k)$ by the obvious symmetry, so we want $\sum_{k=1}^{100} 2k P(X_1-X_2=k)$. If $X_1=n$, then $X_2=n-k$. Thus, $P(X_1-X_2=k)=\sum_{n=k}^{100}P(X_1=n\text{ and } X_2=n-k)=\sum_{n=k}^{100}P(X_1=n)P(X_2=n-k)$. We know these, hence, $P(X_1-X_2=k)=\left(\sum_{n=k}^{100}\frac{{100 \choose n}{100 \choose n-k}}{2^{200}}\right)$. Now $E(|X_1-X_2|)=\sum_{k=1}^{100}2k\left(\sum_{n=k}^{100}\frac{{100 \choose n}{100 \choose n-k}}{2^{200}}\right)$.

Mathematica tells me the inner sum (reversing the order of the sums didn't seem to help) is $\frac{(200)! (k! \binom{100}{k})}{\left(2^{200} 100!\right) (100+k)!}$ and summing $\sum_{k=1}^{100}2k\frac{(200)! (k! \binom{100}{k})}{\left(2^{200} 100!\right) (100+k)!}=\frac{(200!)}{2^{199}(100!)}\sum_{k=1}^{100}k\frac{k! \binom{100}{k}}{(100+k)!}$ which Mathematica also tells me is $\frac{1}{2\cdot 99!}$. Thus $E(|X_1-X_2|)=\frac{(200!)}{2^{200}(100!)(99!)}=\frac{100}{2^{200}}{200 \choose 100}$.


$$E(X_1\lor X_2)=\frac{1}{2}\left(100+\frac{100}{2^{200}}{200 \choose 100}\right)$$

I think it is possible to divine that $E(|X_1-X_2|)=\frac{100}{2^{200}}{200 \choose 100}$ but I'm not seeing it immediately.


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.