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.

  • $\begingroup$ What's the distribution for the random number of cards drawn? $\endgroup$ – joriki Oct 21 '15 at 8:49
  • $\begingroup$ 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? $\endgroup$ – Henry Oct 21 '15 at 9:00
  • $\begingroup$ @joriki there is equal probability for each random number between 0 and M $\endgroup$ – rahul Oct 21 '15 at 14:38
  • $\begingroup$ @joriki I would really appreciate it if the answer also contains what happens if each choice of draw is equally probable. $\endgroup$ – 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
    $\begingroup$ +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}$ $\endgroup$ – Henry Oct 21 '15 at 9:08
  • $\begingroup$ @cr001 Thank you, could you please explain the components of (2) a little? $\endgroup$ – rahul Oct 21 '15 at 14:59
  • $\begingroup$ 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. $\endgroup$ – cr001 Oct 22 '15 at 4:32

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.