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!
Best Answer
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$.