# The probability that a card is not chosen after a number of draws

I have a deck of cards with M cards. I draw a random number (between 0 and M) of cards in each draw, note all cards drawn, and replace it.

So, after T draws,

1. What is the probability that a card would never have been drawn?
2. What is the probability that a card would have been drawn at least n times?

I see that there are $2^{M-1} - 1$ choices for choosing a random number of cards. But I am stuck how to proceed.

It would be great if the answer considers both (1) when the random number drawn is a number between 0 and M, equally probable and (2) when each draw has equal probability (i.e $\frac{M}{2}$ cards on average.

• What's the distribution for the random number of cards drawn? – joriki Oct 21 '15 at 8:49
• I would have thought there were $2^M$ possible choices of cards, as each card can be chosen or not. Are these equally probable (making $\lfloor M/2\rfloor$ a most likely number of cards)? Or are the numbers of cards chosen equally probable from $0$ to $M$? Or something else? – Henry Oct 21 '15 at 9:00
• @joriki there is equal probability for each random number between 0 and M – rahul Oct 21 '15 at 14:38
• @joriki I would really appreciate it if the answer also contains what happens if each choice of draw is equally probable. – rahul Oct 21 '15 at 14:48

1. For each draw, a card $C$ belongs to half of all possible subsets of all $M$ cards as there is a trivial bijection between subsets that contains $C$ and subsets not containing $C$. Also each draw is independent, so the probability is $({1\over2})^T$.
2. Similarly the probability is $\sum_{i=0}^{T-n}({1\over2})^{n+i}({1\over2})^{T-n-i}{T\choose n+i}=({1\over2})^T\sum_{i=0}^{T-n}{T\choose n+i}$
• +1. This assumes that a particular card is equally likely to be drawn or not, but does not need a more detailed assumption about the mechanism of the draw. The final result could also be written $\displaystyle \frac{1}{2^T} \sum_{i=n}^T {T \choose i}$ – Henry Oct 21 '15 at 9:08
• Basically we are adding up the probability of all cases that a card is drawn at least $n$ times. Those cases are $n,n+1,n+2,...,T$ so we are summing up all those cases. For each case we first choose which $n+i$ draws contain the card, and for those $n+i$ draws we have $({1\over2})^{n+1}$ chance of drawing the card, for the remaining draws we have $({1\over2})^{T-n-i}$ chance of not drawing the card. – cr001 Oct 22 '15 at 4:32