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.

Ok let $Q$ denote the set $\{1,2,3,\ldots,100\}$. A subset $A$ containing $k$ elements is chosen at random from ­where element selection is conducted without replacement and $1 \leqslant k \leqslant 100$. Then the elements of $A$ are all replaced, and a second independent subset $B$ containing $k$ elements is chosen from ­ in the same way. Let $W$ denote the number of elements in the set $A$ or $B$. Find the outcome space for $W$ in terms of $k$, and and a formula for $P(W = i)$ for each appropriate value of $i$.

Okay, I hate asking questions on here when I have nothing figured out yet but I'm really stumped on this problem, can anyone get me started?

share|improve this question
    
Do you mean that $W$ is the number of elements in the union $A\cup B$, so that $k\le W\le 2k$? –  Brian M. Scott Apr 3 '12 at 1:22

2 Answers 2

A reasonable sample space is the set of all ordered pairs $(A,B)$, where $A$, the first set chosen, is a subset of $Q$ with $k$ elements, as is $B$, the second set chosen. This sample space has size $$\binom{100}{k}\binom{100}{k}$$ elements, and they are all equally likely. For easy comparison with the answer by JohnJamesSmith, we use his notation.

So given $i$, we want to find $P(W=i)$. Clearly $P(W=i)=0$ if $i<k$. Also, if $i>\min(2k,100)$, then $P(W=i)=0$. We need to deal with the remaining cases.

In how many ways can the cardinality of $A\cup B$ be $i$? Note that $A$ can be chosen in any one of $\binom{100}{k}$ ways. In order for $A\cup B$ to have cardinality $i$, the set $B$ must contain $i-k$ objects that are not in $A$, and the region of overlap between $A$ and $B$ must have cardinality $2k-i$.

Given $A$, we can choose $2k-i$ elements of $A$ in $\binom{k}{2k-i}$ ways. For every one of these ways, the elements of $B$ outside $A$ can be chosen in $\binom{100-k}{i-k}$ ways. So the number of elements in the sample space that give $W=i$ is equal to $$\binom{100}{k}\binom{k}{2k-i}\binom{100-k}{i-k}$$ ways. To find $P(W=i)$, divide. Note the cancellation of $\binom{100}{k}$. Thus $$P(W=i)=\frac{\binom{k}{2k-i}\binom{100-k}{i-k}}{\binom{100}{k}}.$$ We needn't have bothered with $A$, it was just introduced to provide a respectable-sounding sample space. For just calculating the probability, we can without loss of generality assume that $A$ consists of the first $k$ elements of $Q$.

share|improve this answer

$W$ is minimized when $A$ and $B$ exactly overlap, and maximized when $A$ and $B$ share as few elements as possible (this happens when they are disjoint, unless $2k > 100$). So $k \leq W \leq \min(2k, 100)$. Convince yourself that $W$ can attain any value in this range.

Now for the trickier part. To find $P(W=i)$, we will find the number of ways $W$ could be $i$ and divide that by the total number of possibilities for $A$ and $B$.

Two sets of size $k$ could potentially have $2k$ distinct elements between them (in their union). Therefore if they have $W = i$ elements in their union, they must share $2k - i$ elements, and each have $i-k$ elements to themselves. So, assuming $i$ is in the appropriate range, to ascertain $A$ and $B$, we need to pick $i$ elements to be in $A$ or $B$, then, of those $i$ elements, we need to pick $k$ elements to be in $A$ (the rest can be in $B$), and then we need to $2k-i$ of those $k$ elements for $A$ to share with $B$. The number of ways to do this is $$\binom{100}{i}\binom{i}{k}\binom{k}{2k-i}.$$ Now divide that by the number of ways to choose $A$ and $B$, $$\binom{100}{k}\cdot \binom{100}k,$$ and you have your answer. You may wish to simplify this quotient.

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.