0
$\begingroup$

A group of $200$ persons consisting of $100$ men and $100$ women is randomly divided into $100$ pairs of $2$ each.Find the maximum chance that at most $30$ of these pairs will consist of a man and a woman.

Solution : Let m1,m2,m3.....m100 be the men and w1,w2,w3,....w100 be the women.

Let X1 be the random variable such that

X1= 1 if m1 is paired with some wj

=0 if m1 is paired with some mj

Similar is true for X2,X3,...,X100

In the way we construct the random variables, obviously they are dependent and if we define a random variable as ,

X=X1+X2+X3+....+X100, then the spectrum of X=$0$ ,$1$ ,$2$ ,$3$ ,$4$,...,$100$

For the m1, probability that he is paired with a woman is $100/199$

Probability that the man is paired with another man is $1-100/199 = 99/199$

THE SAME IS TRUE FOR ALL THE MEN FROM $2$ TO $100$

Now the problem turns out be $P(X<=30)$,

Here we can easily apply one-sided Tchebycheff's Inequality and get the result...

My question lies somewhere else,

The way the solution to the problem defined the variable $X$ , $X$ actually now defined the event that $X=k$, the people are divided such that there are $k$ pairs containing men and women.

Now i can't understand the way the m1 getting a woman is mutually exclusive to the situation when m2,m3,..m100 gets a woman.

The way Xi has been defined , it is quite logical for the ith man to have the possibility of having all the rest of woman, but but i feel that is so when a sort of CHOOSING WITH REPLACEMENT IS THERE, but when we are dividing into groups there is a sort of conditional probability that comes into play,that when m1 takes up a woman, m2,m3,.. can't possibly take up that woman. However if m2 takes up that woman, then m1,m3,..shall not be able to take up that woman...

Please can anyone explain me the situation in a clear cut solid way. Thanks in advanced.

$\endgroup$
  • 1
    $\begingroup$ I don't see how to do this with Chebyshev's inequality. It's easy enough to compute $E(X),$ but to use Chebyshev's inequality don't you also have to know $\mathrm{Var}(X)?$ Since the $X_i$ are dependent, this doesn't look easy to me. I can see how to do it with Markov's inequality. Am I overlooking something? $\endgroup$ – saulspatz Apr 16 at 14:06
  • $\begingroup$ The E(x) turns out to be 50.25 then you can calculate var(x) using the formula var(sigma Xi)= sigma(var(Xi))+(double sigma)(cov(Xi,Xj) $\endgroup$ – Abhishek Ghosh Apr 16 at 14:10
  • 1
    $\begingroup$ Thank you. I'd forgotten about that. $\endgroup$ – saulspatz Apr 16 at 14:18
  • 1
    $\begingroup$ I'm sorry but I don't understand your question. We can model the situation by arranging the $200$ people in a line randomly, then pairing number $1$ with number $2$, number $3$ with number $4,$ and so on. Obviously, if the first pair comprises a man and a woman, that has an effect on the probability that the second pair comprises a man and a woman. There is no sampling with replacement at all. Can you pinpoint where the difficulty lies, please? $\endgroup$ – saulspatz Apr 16 at 15:11
  • 1
    $\begingroup$ If you think of the model I mentioned in my comment, isn't it clear? There are ${200\choose100}$ ways to arrange $100$ M's and $100$ W's in a line. To compute the probability that a particular pair is an M and a W we say it can come in the order MW or WM and the remaining $198$ letters can be arranged in ${198\choose99}$ ways, etc. You seem to thinking of it as some kind of sequential choice, but the phrase "is randomly divided into $100$ pairs of $2$ each" doesn't suggest that to me. In particular if $m_1$ gets paired with $m_2$ then $m_2$ doesn't get a choice. $\endgroup$ – saulspatz Apr 16 at 15:30
1
$\begingroup$

As you say, the chance the first pair is a man and a woman is $\frac {100}{199}$. This means the expected number of man-woman pairs is $\frac {10^4}{199}\approx 50.25$ We expect that the chance of $30$ is quite small. If we draw with replacement the chance becomes $\frac 12$ and the correlations disappear. We can say the mean will be $50$ and the standard deviation $\sqrt{100 \cdot \frac 1{2^2}}=5$. We are four standard deviations away from the mean, so the chance will be very small. I suspect you are expected to use a z-score table at four standard deviations and find the chance of being outside that is about $3 \cdot 10^{-5}$

If we want to be more exact, we can compute the chance of exactly $k$ matches. $k$ must be even. There are $200!$ ways to put the people in order. When we make each pair there are $2^{100}$ ways to reverse the people in a pair and $100!$ ways to order the pairs, so the number of pairings is $\frac {200!}{2^{100}100!}$. To get $k$ man-woman matches we can select $k$ men and $k$ women in $100 \choose k$ ways each. We can pair them up in $k!$ ways, then pair the remaining men in $\frac {(100-k)!}{2^{k/2}(50-\frac k2)!}$ and the women similarly, so the chance of $k$ mixed pairs is $$\frac{\left({100 \choose k}\frac {(100-k)!}{2^{k/2}(50-\frac k2)!}\right)^2}{\frac {200!}{2^{100}100!}}$$

$\endgroup$
  • $\begingroup$ What you did is absolutely fine, but I didn't get the answer to my doubt, Now i can't understand the way the m1 getting a woman is mutually exclusive to the situation when m2,m3,..m100 gets a woman. The way Xi has been defined , it is quite logical for the ith man to have the possibility of having all the rest of woman, but but i feel that is so when a sort of CHOOSING WITH REPLACEMENT IS THERE, but when we are dividing into groups there is a sort of conditional probability that comes into play,that when m1 takes up a woman, m2,m3,.. can't possibly take up that woman. $\endgroup$ – Abhishek Ghosh Apr 16 at 14:59
  • 1
    $\begingroup$ m1 getting a woman is not mutually exclusive to other men getting women. If you follow my second paragraph I select the men to be in mixed pairs simultaneously. It could be any $k$ of the men. If you try to say the first pair has a chance of $\frac {100}{199}$ of being mixed you run into the problem that the chance the second pair is mixed depends on whether the first is and it gets hard. My first paragraph ignores that problem by sampling with replacement. That is probably a reasonable approximation. $\endgroup$ – Ross Millikan Apr 16 at 15:11
  • $\begingroup$ The if as per the solution posted by me, is it wrong to say that for all I, Xi s have the same distribution? $\endgroup$ – Abhishek Ghosh Apr 16 at 15:21
  • 1
    $\begingroup$ If you define $X_i$ to be the chance man $i$ is in a mixed pair regardless of what the other men do, it is the same for all men as you say. It is $\frac {100}{199}$ to be $1$ and $\frac {99}{199}$ to be $0$. The chance the second man paired is in a mixed pair is the same as long as you don't look at what happened to the first and average over the possibilities. If you ask about the total number in mixed pairs you can't do that and you have to pay attention to the correlations. $\endgroup$ – Ross Millikan Apr 16 at 15:27
  • 1
    $\begingroup$ If you want $X_2$ to be the chance the second man is in a mixed pair depending on what the first man did it will change. You need to define which you mean. $\endgroup$ – Ross Millikan Apr 16 at 15:28

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.