Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

A set of 200 people, consisting of 100 men and 100 women, is randomly divided into 100 pairs of 2 each. Give an upper bound to the probability that at most 30 of these pairs will consist of a man and a woman.

I intend to use the Chebyshev Inequality to solve it but it turns out that the prob. dist. for # of pairs consisting of a man and a woman is hard to find.

Anyone have any thought on it? Thanks a lot!

share|improve this question
    
A bit over $50$. The probability that $X_i=1$ is $100/199$. The probabilities are not so bad to get expressions for, so with suitable program we could compute. Would have to work for variance. Intuition is that variance is less than variance if the $X_i$ were independent. Let's get rid of some earlier comments so as not to upset the system! –  André Nicolas Aug 10 '11 at 15:34
2  
If you are just looking for an upper bound, $1$ will suffice. –  Ross Millikan Aug 10 '11 at 16:12
    
@Ross: this is nasty... :-) –  Did Aug 10 '11 at 16:14
    
The value of Chebyshev's inequality is in getting upper bounds without finding the probability distribution of the random variable. All you need are the first two moments, and in many situations these are relatively easy to find. –  Byron Schmuland Aug 10 '11 at 19:45

4 Answers 4

up vote 10 down vote accepted

Chebyshev's inequality is the way to go here, though it is overly conservative. Following André's suggestion, the number of couples $X$ is written as $X=\sum_{i=1}^{100}X_i$ where $X_i$ is the indicator of whether woman $i$ is paired with a man. These random variables are exchangeable, which reduces the computations somewhat.

It is easy to see that $\mathbb{E}(X_i)=100/199$ since there are 100 men out of 199 people to choose as the partner of woman $i$. Therefore, the average number of couples is $$\mathbb{E}(X)=100\times {100 \over 199}=50.251.$$

To get the variance we first calculate $\mathbb{E}(X_i X_j)=(100/199)(99/197)$ when $i\neq j$. Therefore $$ \mathbb{E}(X^2)=\sum_i \mathbb{E}(X_i)+\sum_{i\neq j} \mathbb{E}(X_i X_j) =\left(100\times {100 \over 199}\right)+\left(100\times 99\times {100\over199}{99\over 197}\right).$$ This gives us $$\mbox{Var}(X)=\mathbb{E}(X^2)- \mathbb{E}(X)^2= {196020000\over 7801397}= 25.12626905.$$

By Chebyshev's inequality we get $$\mathbb{P}(X\leq 30)\leq {\mathbb P}(|X-\mathbb{E}(X)|\geq 30-50.251)\leq {\mbox{Var}(X)\over(30-50.251)^2}=.0612.$$ This gives you an upper bound.


In fact you can calculate the exact probability as follows. First for $1\leq m \leq 100$ we have $$\mathbb{E}(X_{1}X_{2}\cdots X_{m})={100\over 199}\times{99\over 197}\times \cdots\times{101-m\over 201-2m}.$$ By exchangeability, the probability is the same for any set of $m$ distinct indices.

Using the inclusion exclusion formula $$\mathbb{P}(X\geq k)=\sum_{m=k}^{100}(-1)^{m-k}{m-1\choose m-k}{100\choose m}\mathbb{E}(X_{1}X_{2}\cdots X_{m}),$$ we find that the probability that there are 31 or more couples is $$\mathbb{P}(X\geq 31)={41119425293581046683159071975854440009966486028288 \over 41121343590504031983862003937481222553223476334365}=.9999533503.$$ The exact probability that there are no more than 30 couples is thus only $.0000466497$.

share|improve this answer
    
My answer now matches yours. I was not weighting the $\binom{100}{k}$ cases properly. –  robjohn Aug 11 '11 at 0:22
    
@robjohn Beautifully done! –  Byron Schmuland Aug 11 '11 at 3:06

Making two columns, one for the left element of each pair, one for the right, there are $\binom{100}{k}$ ways to have $k$ men and $100-k$ women in the left column.

For each arrangement of $k$ men on the left, there are $\binom{k}{n}$ ways to match $n$ men and $k-n$ women in the right column with the $k$ men in the left column. There are $\binom{100-k}{n}$ ways to match $n$ women and $100-k-n$ men in the right column with the $100-k$ women in the left column.

Thus, there are $\binom{100}{k} \binom{k}{n} \binom{100-k}{n}$ ways to get $100-2n$ man-woman couples with $k$ men in the left column. Considering the permutations of the $200$ taken $100$ at a time, the total number of arrangements should be $\binom{200}{100}$. Let's check $$ \begin{align} \sum_k\sum_n \binom{100}{k} \binom{k}{n} \binom{100-k}{n} &= \sum_k \binom{100}{k} \binom{100}{k}\\ &= \binom{200}{100} \end{align} $$ Now the number of arrangements with $100-2n$ man-woman couples is $$ \begin{align} \sum_k \binom{100}{k} \binom{k}{n} \binom{100-k}{n} &= \sum_k \binom{100}{2n} \binom{2n}{n} \binom{100-2n}{k-n}\\ &= \binom{100}{2n} \binom{2n}{n} 2^{100-2n} \end{align} $$ Thus, the probability of getting exactly $100-2n$ man-woman couples is $$ \frac{\binom{100}{2n} \binom{2n}{n} 2^{100-2n}}{\binom{200}{100}} $$ Summing for $n=35\dots50$ yields the probability of getting at most $30$ man-woman couples to be $p=.000046649665489730847082$.

Interestingly, the probability of matching at most $48$ man-woman couples is $p=.40103407701938908115$ and the probability of matching at most $50$ man-woman couples is $p=.55961680234890506571$.

share|improve this answer

Let there be $n$ men and $n$ women. Consider a pairing with $k_{m,m}$ man-man pairs, $k_{w,w}$ woman-woman pairs, $k_{m,w}$ and $k_{w,m}$ opposite gender pairs. Total number of pairs $k_{m,m}+k_{w,w}+k_{m,w}+k_{w,m} = n$. Total number of men and women respectively $2 k_{m,m} + k_{m,w}+k_{w,m} = n$ and $2 k_{w,w} + k_{m,w}+k_{w,m} = n$. It follows that $k_{m,m}=k_{w,w}$. This configuration can be built by splitting $n$ men into $\binom{n}{2 k_{m,m}}$ partitions of $2 k_{m,m} + (n-2k_{m,m})$, likewise for women. $2 k_{m,m}$ men are permuted in $(2k_{m,m})!$ ways, and remaining men permuted in $(n-2k_{m,m})!$ ways. Resulting $n$ pairs can be rearranged in $\mathrm{multinom}(k_{m,m},k_{w,w}, k_{m,w}, k_{w,m})$ ways.

So we have

$$ (2n)! = \sum_{k_{m,m}, k_{m,w}, k_{w,m} >=0 } \chi_{2 k_{m,m}+k_{m,w}+k_{w,m}=n} \left( \binom{n}{2 k_{m,m}} (2k_{m,m})! (n- 2k_{m,m})! \right)^2 \mathrm{multinom}(k_{m,m},k_{w,w}, k_{m,w}, k_{w,m}) $$

Which is

$$ 1 = \frac{1}{\binom{2n}{n}} \sum_{k_{m,m}, k_{m,w}, k_{w,m} >=0 } \chi_{2 k_{m,m}+k_{m,w}+k_{w,m}=n} \mathrm{multinom}(k_{m,m},k_{w,w}, k_{m,w}, k_{w,m}) $$

Now to find the requested probability we restrict the summation to $k_{m,w}+k_{w,m} <= 30$. This gives

In[114]:= With[{n = 100}, (n!)^2/(2 n)! Sum[
   Boole[2 k + m + w == n] Boole[m + w <= 30] Multinomial[k, k, m, 
     w], {k, 0, n}, {m, 0, n}, {w, 0, n}]]

Out[114]= \
1918296922985300702931961626782543256990306077/\
41121343590504031983862003937481222553223476334365

which approximately is $0.0000466497$.

share|improve this answer
    
Small but not that small! –  André Nicolas Aug 10 '11 at 16:13

One may also use Cantelli inequality (one-sided version of Chebyshev): $$P(X\leq 30)\leq \frac{Var(X)}{Var(X)+(E(X)-30)^2}\approx \frac{25.12}{25.12+410.10}\approx 0.0577$$ However it's not much better than Chebyshev :)

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.