Condition probability distributions: Two people flipping fair coins

Question

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?

Answer 1

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.

Answer 2

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$.

Answer 3

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}$.

Then:

$$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.

Answer 4

$\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$