Hi, please help me with this since I've struggle for long and couldn't get it:
There are 5 men and 5 women are seated at random in a row of 10 seats. Compute the expected number of men that sit next to at least 1 woman.

Can you summarize your struggles to date?

By expected, I presume u mean most likely arrangement. Once u get this arrangement just see how many men are sitting next to women! is it getting the most probable arrangement thats causing u problems?

By expected, I presume u mean most likely arrangement. Once u get this arrangement just see how many men are sitting next to women! is it getting the most probable arrangement thats causing u problems?

I don't think that's what he means by expected number. I think he means the usual probability definition of the expected value of a random variable.

I think the direct approach should be easy enough. Find the # of arrangements where 1 man is next to a woman, 2 men, 3 men, and 4 men. All the remaining arrangements will have 5 men next to a woman. The 1, and 2 cases are pretty simple, 3 and 4 a bit more work. For 3 men next to a woman, try to think of arrangements that keep 2 of the men away from women (make sense?). Same idea for the 4 case.

Expected value is number/chance.
The expected value of the outcome of a six-sided die is
1*1/6 +
2*1/6 +
3*1/6 +
4*1/6 +
5*1/6 +
6*1/6
=21/6 = 7/2.

So, what we're looking for is (number of men sitting next to women in a particular arrangement) / (chance of that particular arrangement).

However, I don't know how to calculate sets like this with limited numbers of elements, so that's as much as I think I can help you...

Hi, please help me with this since I've struggle for long and couldn't get it:
There are 5 men and 5 women are seated at random in a row of 10 seats. Compute the expected number of men that sit next to at least 1 woman.

First check how many possible combinations there are. If you have 10 seats and you randomly divide 5 men over them, then also the women's seats are fixed. So you have to choose 5 positions for men from 10 in total, giving you

10 choose 5 = 10! / (5! * 5!) = 252

possible ways of arranging them.

Instead of now counting how many possible ways you can put man next to at least one woman, count how many ways there are to put no woman next to a man:

Expected number of men sitting next to at least one woman + Expected number of men sitting next to strictly less than one woman = 5 (you have total five).

or

Expected number of men sitting next to at least one woman = 5 - expected number of men sitting next to no woman.

To do this, we need to calculate probabilities:

Expected number of men sitting next to no woman = 0*Prob(no men sitting next to no woman) + 1*Prob(one man sitting next to no woman) + 2*Prob(two men sitting next to no woman) + ... + 5*Prob(5 men sitting next to no woman).

These probabilities are a matter of counting:

The first term vanishes because of the zero in front of it. Also, it is impossible to have 0 men sitting next to no woman. You must at least put one man next to a woman.<BR/>

It is impossible that 5 man are sitting next to no woman, because at least one man must be sitting next to one woman. If you denote "1" a man and "0" a woman, this is the configuration 1111100000 or 0000011111<BR/>

If FOUR men are sitting next to NO woman then they must all five be grouped and at the end of a row, e.g. the only allowed combinations are 1111100000 and 0000011111. The probability to have this configuration is 2 / 252.<BR/>

If THREE men are sitting next to NO woman then there must be a group of four, at a border, or a group of five somewhere in the middle of the row. The two border configurations are

11110xxxxx and xxxxx01111

where the x's can be randomly filled with one man and 4 remaining woman. The total number of "border" configurations is:

2 * (5 choose 4) = 2 * 5 = 10

because if you fixed the four women's seats then also the man knows where he has to sit. The configurations with the group of five in the middle are simply:

0111110000 , 0011111000, 0001111100, 0000111110

so the total probability to have THREE men sitting next to NO woman is 14 / 252<BR/>

If there are TWO men sitting next to NO woman, then you either have a group of THREE at the border, or a group of FOUR somewhere in the middle. If you put three at the border, you have 7 seats left to divide amongst 2 men and 3 woman, with the condition that the two man cannot sit next to eachother at the other border. First we count how many "border" configurations there are, and then we'll substract the number of configurations with the two remaining man at the other border:

1110xxxxxx and xxxxxx01111

were you have to divide the 5 remaining seats amongst 4 woman and 1 man. Divide the four woman and you know where the man have to sit, so you in total have

2 * (5 choose 4) = 10

borderconfigurations here. We have to subtract the number of "the two men sit at the border configurations", but these are only two:

1110000011 and 1100000111

So there are 8 total border configurations. The "4 men in middle" configurations are easy to obtain; the group of four is quite limited to move around:

011110xxxx , x011110xxx , xx011110xx , xxx011110x , xxxx011110

where the remaining four seats are to be divided amongst one man and three woman. Fix the women's seats and then the man also has his seat, so we have:

5*(4 choose 3) = 20

possible configurations here. The probability to find TWO man sitting next to NO woman is 28 / 252.<BR/>

The remaining configurations are those with one man sitting next to no woman. There are 252-(28+14+2) configurations left = 180 possibilities left.


In total, this gives you:

1*180/252 + 2*28/252 + 3*14/252 + 4*2/252 = 1,135 men are expected NOT to sit next to a woman. Subtract this number from 5 and you would expect 3,86 men to sit next to at least one woman, or in integer units: 4 men.

That this number is rather high is not that surprising (to be honest, I would have expected it to be much closer to 5). The most "fractured" configurations are the most probable in a sense (highest entropy), so a "typical" configuration would be 1010101010, which gives you 5 men sitting next to at least one woman. Since there is a slight "clustering" effect, this number decreases a bit (appearantly with one man).

Perhaps there is a counting error somewhere, but I think this is one way to solve the problem.

Bye!

Crisp

Hi, you do have a few counting errors.

For THREE men next to NO women, you missed the

1110000011 and 1100000111 configurations, so you get 16 ways here.


For TWO men next to NO women, you miss quite a few configurations.
Four men in the middle is 20 like you said.
With 3 on one border on one on the other, you get 8 like you said.
You can also have 3 on one border, and none on the other:
1110x0x0x0x0 or 0x0x0x0x0111 where each extra man gets put on his own "x" for 2*(4 choose 2)=12 ways
also,
1110x0x0x0x0 or 0x0x0x0x0111 where the remaining 2 men share an "x" for 2*4=8 more ways

You can also have 2 on each border, one in the middle:
110x0x0x0x011 (the 5th man goes on an x) for 4 more ways

You can also have 2 on one border and a group of 3 in the middle:
110x0x0x0x0 or 0x0x0x0x011 (the group of 3 goes on an x) for 2*4=8 more ways.

So a total of 20+8+12+8+4+8=60 ways for TWO men next to NO women.


Finally, to get the ways for ONE man to be sitting next to NO women, you need to find 252-(60-16-2-#of ways for NO men to be sitting next to NO women).

To find #of ways for NO men to be sitting next to NO women, first place women
y0x0x0x0x0y
then group the men in 3 ways:
1)no men next to another man, each man gets his own "x" or "y". (6 choose 5)=6 ways
2)2 men next to each other, then other 3 alone. First put the group of 2 on an "x", then place remaining 3 on their own "x" or "y", so 4*(5 choose 3)=40 ways
3) 2 groups of 2 men and one loner. First put the 2 groups each on their own "x" then put the loner on an "x" or "y" for (4 choose 2)*4=24 ways.

So 70 ways total and thus there are 104 ways to put ONE man next to NO women. Find expected value as before.


I'm curious to see what happens if you have n women and n men, what kind of asymptotic for expected value as n->infinity? Of course this way of solving the n=5 problem gives no info for this.

Hi, you do have a few counting errors.

Oh, doesn't surprise me; even when typing the post I regularly had to go back and make corrections because I realised I had forgotten sets of configurations :).

I'm curious to see what happens if you have n women and n men, what kind of asymptotic for expected value as n->infinity? Of course this way of solving the n=5 problem gives no info for this.

Ugggh... you probably end up with one of those ugly combinatorial problems that you can spend a long time on.

I actually spent 5 or 6 months fulltime (at work) solving such a combinatorial problem and what would happen in the limit n -> oo. It comes down to finding the mechanism behind the "counting" argument; in my single-case experience that was not really the problem, and I suspect that generally it is not the problem. The problem starts when you find this expression which consists of a few dozen sums, a few dozen combinatorial factors, some divisions and functions of summation variables ... and then trying to interpret the darn formula, or even proving that it converges ;). Darn messy...

After a little more thought, I think as n->infinity the expected number of men sitting next to at least one woman will go to 3/4*n. As n gets really big, selecting a random permutation of n men and n women should be "about the same" as taking a random sequence of length 2*n where each entry is independantly chosen to be a man or woman with probability 1/2 each. In this easier to handle model, each man has a 3/4 chance of being next to a woman (not counting a man on the edge of the sequence, but in the limit, they won't matter), so 3/4*n looks right.

I expect this is a standard problem, the next stats/probability person I run into, I'll interrogate. :)

Thanks for all of you. Though the counting procedure is no good, since it's limited to a countable number of men and women, like 10, it took forever. So, it's no problem if there're 3 men and 3 women but large number. The teacher somehow wants us to deal it with double sum (sigma notation) of various random varible to solve this. I do'nt know how, but it's ok, as others don't neither.
For n men and n women I can give answer to it because it's in my book, but it slightly change to 'n man, n woman, find expected number of men who have a woman next to them' instead of 'sit next to at least 1 woman'. Then it look like this:

http://www.geocities.com/sagacious8850/ans_1woman.pdf

For 'sit next to at least 1 woman' we'll have to do tricks from the i in the solution!! Hope this would help:
The probability to have a man at the fixed place is 1/2. We choose one
person from 2n. The number of all events is 2n. The number of man is n.
We get n/(2n)=1/2.

Next step. We have 2n-1 persons and n women. The probability to have a
women at the (i+1)th seats is n/(2n-1). The probability is

P(X_i=1)=.5n/(2n-1)

Now the expected value is

0xP(X_i=0) + 1xP(X_i=1)=.5n/(2n-1).

Another way. The number of all possible choices two persons from 2n is
2n(2n-1). The number of pairs Man-Women is n square: we may choose any
men and then any women.

Evidently, X_2n is always 0. There is no next women since no next
place.

We have 2n-1 independent random variables with the same mean. Its sum
has then the expected value

(2n-1)E[X_i]=n/2.



However, thanks for your help!!!!

Oh I forget to mention, it's claimed to be best to solve with some partial differential equation methods.

For n men and n women I can give answer to it because it's in my book, but it slightly change to 'n man, n woman, find expected number of men who have a woman next to them' instead of 'sit next to at least 1 woman'.

I hope you see that this greatly simplifies the problem ;)

For n men and n women I can give answer to it because it's in my book, but it slightly change to 'n man, n woman, find expected number of men who have a woman next to them' instead of 'sit next to at least 1 woman'. Then it look like this:

http://www.geocities.com/sagacious8850/ans_1woman.pdf


I may be a little confused, but I see those problems as identical :confused:. I read "a man has a woman sitting next to him" as being true if he has one or two women next to him, which is what your original problem was looking for.

In the link you give, when they are finding E(Xi), for i not 1 or 2n, they find 1-(probability men on both sides), that's what you want, no? They treat the Xi's as independant, which I don't believe is true. If you know X3 and X5 are 1 , then you know there's a man in positions 3 and 5, thus X4 must be 0.

I think they're independant enough to give an asymptotic answer easily (my "about the same" comment above), but if you're looking for a precise formula for each n, this could be a problem.