2
$\begingroup$

This questions relates to this question Fifty men and thirty woman are lined up at random. How do I find the expected number of men who have a woman standing next to them. and the answer given by André Nicolas.

(I would normally just comment on that question but don't have enough reputation to do that and I am dying to find out what I am missing)

It seems to me like the linearity of expectation would apply to independent random events and it seems like the location of the men relative to the women are not independent in this problem. As you move from man $1$ to $50$, wouldn't the probability of a man standing next to a woman change depending on the number of men and women already seen?

If I understand André's answer correctly, the expected number of men standing next to a woman would be:

$$2(1-(i))+48(1-(ii)) \approx 32.1$$

I wrote a simulation and came up with approximately $30.62$ as the answer.

What am I missing?

$\endgroup$
2
$\begingroup$

Linearity of expectation is (sometimes surprisingly) always valid. If I roll two dice then the expected value of the first is $3.5$ and the exopected value of the second is $3.5$ and the expected value of the sum is $7$. Now you'll say "Sure, that's cause they are independent." But now do this: I roll the first die and then manually place the second die so that it shows the same number. Again each die has an expected value of $3.5$ and the sum has an expected value of $7$. Or I roll a first die and then I manually place the second die so that it shows one more than the first (in a cyclic sense, that is if the first shows "6" I set the second to "1"). Again each die has an expected value of $3.5$ and the sum has an expected value of $7$.

Just note that $$\begin{align}E[\alpha X+\beta Y]&=\sum_{i,j}P(X=x_i, Y=y_j)(\alpha x_i+\beta y_j)\\&=\sum_i\alpha x_i\sum_jP(X=x_i,Y=y_j)+\sum_j\beta y_j\sum_iP(X=x_i,Y=y_j) \\&= \alpha \sum_ix_iP(X=x_i)+ \beta \sum_jy_jP(Y=y_j)\\&=\alpha E[X]+\beta E[Y]\end{align}$$

Now why your simulation differs from your computation: For a single man $i$ ("Jack", say) the expected value of his $X_i$ is $$\begin{align}E[X_i]&=\operatorname{Pr}(X_i=1)\\&=1-\operatorname{Pr}(X_i=0)\\&=1-\left(\frac{2}{80}\cdot \frac{49}{79}+\frac{78}{80}\cdot \frac{49}{79}\cdot\frac{48}{78}\right)\\&=\frac{154041}{249640} \end{align}$$ and this is the same for all $i$; note that we cannot split end men and middle men in the final sum because we don't know beforehand how many end men there will be. Instead we subsumize the possibility of being at an end or not alreday in the expected value for each single man. Either Jack ends up at an end or he does not; since these are mutually exclusive, we added the probabilities in the parenthesis. Because there is no distinction among the men, we have $E[X_1]=\ldots=E[X_{50}]$ and hence $$E[Y]=50\cdot \frac{154041}{249640}=\frac{770205}{24964}\approx 30.85$$ which is much better in accordance with your simulation (though you didn't specify the observed variance, which could have hinted to the quality of the simulated result).

$\endgroup$
2
  • $\begingroup$ What a great answer!! Though I still have to figure out why my simulation is so far off. On 10M iterations, I never veer more than .01 off of 30.62. Great idea though to calculate the variance. When I do I am sure that I will find that my results are miles away from 30.85. What an amazing world we live in that we can tap into somebody like Hagen who can supply an answer like this in just a handful of minutes. Incredible. $\endgroup$ – jch Apr 22 '15 at 22:49
  • $\begingroup$ I did your calculations and came up with an answer that matches my simulation. 50(1-(98/6320+183456/492960)) approx equal to 30.61709. $\endgroup$ – jch Apr 22 '15 at 23:16

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.