# Probability of an outcome space problem

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?

-
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

$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.

-

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$.

-