What is the probability of picking items out of many small sets versus one large set.

Say you have 100 objects that come in pairs (set of two) and you must randomly pick one from each set so in the end you have 50 items -- one representative from each set. The chances of any item being picked would seem to be 50/50 and so the chances of an item never being picked after multiple passes would decay by half every time: 50%, 25%, 12.5% etc. But what about if you simply pick 50 items out of a pool of 100? It seems again that there is a 50/50 chance for any item to be picked, but my intuition is telling me that some items would have a better chance in the long run of never being picked in this second scenario. Am I just crazy? If I am not crazy then what is the math to explain this? Mind you, I only have high school math experience.

For your first method, imagine lining up the people in *couples. There are $2$ choices for the person you will choose from the first couple. For every way of choosing the representative of the first couple, there are $2$ ways of choosing the representative of the second couple. So there are $2\times 2$ ways of choosing who will represent the first two couples.

For each of these $2\times 2$ ways, there are $2$ ways to choose who will represent the third couple. So there are $2\times\times 2$ ways to choose who will represent the first three couples. Continue. There are in total $2^{50}$ ways to choose $50$ people, one from each couple. Note that this is the same number as the number of binary stringss ($0$'s and/or $1$'s) of length $50$.

All these $2^{50}$ ways are equally likely. So the probability that any particular bunch of $50$ is chosen is $\frac{1}{2^{50}}$.

If we are simply choosing $50$ people, with no restrictions, there is an enormously larger number of ways to do the job.

The number of ways is $\binom{100}{50}$. (In high school, this is often called something like $\text{C}_{50}^{100}$, or sometimes ${}^{100}\text{C}_{50}$. It has several other names! It turns out that in general $$\binom{n}{m}=\frac{n!}{m!(n-m)!}.\tag{1}$$ So in our case, we have $\frac{100!}{50!50!}$ equally likely ways to choose $50$ people. The probability that a particular group of $50$ is chosen is $\frac{50!50!}{100!}$.

Formula (1) is often useful It takes a little while to prove. If you would like a sketch, I can provide it. You might also want to look at the Wikipedia article on Binomial Coefficients. You probably have met these before, as the numbers in Pascal's Triangle.

It looks as if you were also asking about the probability a particular person, say Alicia, is chosen. In either case, the probability is $\frac{1}{2}$.

For the couples situation, one person will be chosen at random from each couple, so the probability is clearly $\frac{1}{2}$. For the second way, the chances that Alicia is among the $50$ chosen is $\frac{50}{100}$, again $\frac{1}{2}$.

• I'm not sure it takes so long to prove; there are $n \cdot (n-1) \cdot \ldots \cdot (n-m+2) \cdot (n-m+1) = \frac{n!}{(n-m)!}$ ways to choose $m$ people from $n$ people, and there are $m!$ different orders in which the same group of $m$ could have been chosen. That establishes the identity with a moderate level of rigor. – Eric Tressler Aug 17 '13 at 1:24
• At my level of wordiness, it takes a while! Also, I was trying to encourage OP to look at the Wikipedia article. I guess a link would provide further encouragement, – André Nicolas Aug 17 '13 at 1:26
• So you are saying that any individual card has the same chance over time of getting picked in either scenario, but there are far more unique sets of 50 that could be picked in the second scenario. So if these couples were guys and girls you could get an equally lopsided selection either way, but if the couples were people of similar age then you would get a more even representation of all age groups in the first scenario. That is probably what my intuition was trying to tell me about. – Moss Aug 17 '13 at 7:23
• The remark about people of similar age is right, and plays a role in sampling. The idea behind stratified sanpling is kind of based on this. Suppose you know that $50\%$ are make and $50\%$ are female. You could take a random sample of $1200$ people. But it is often more reliable to take a random sample of $600$ males, and a random sample of $600$ females. (Real world stratified sampling uses more than two strata.) – André Nicolas Aug 17 '13 at 7:33