Say that you have a deck of cards that contains O cards. You want to be able to take at least M cards out of a deck that fit a certain criteria (i.e. they need to be aces or they need to be spades). Let's say that there are N such cards that fit the criteria (where N >= M) in the deck.

During a showing of cards, someone takes Z cards from the deck and places them face up. If you see a card that you want during this showing, you will take it into your possession and remove it from the deck. After the showing, the unclaimed cards will be shuffled back into the deck. Any removed cards are permanently gone from the deck for future showings.

If there are Y of these showings of Z cards, what are the odds that you will have at least X cards that fit the criteria at the end?

  • $\begingroup$ If I’m not mistaken, more constraints are necessary. For example, if X cards referred to three spades vs. three fours, then the general equation changes. There also appears to be an inconsistency in the last line. “At least X specific cards” is not compatible with “to take X cards” in sentence two. Perhaps you mean “at least W of specific cards from set X” or “all of X cards”. $\endgroup$ – Cardinal Jul 14 '20 at 0:52
  • $\begingroup$ @Cardinal Thanks. I have updated the question to clarify that there are N such cards in the deck of O cards. $\endgroup$ – Jim Liu Jul 14 '20 at 2:55
  • $\begingroup$ What happens if at some stage you have collected $\ c<X\ $ of your targeted cards and $\ O-c<Z\ $, when there will be insufficient cards left in the deck for $\ Z $ of them to be shown? If there have been fewer than $\ Y\ $ showings will I next be shown all the $\ O-c\ $ remaining cards (and hence collect all the remaining targeted cards)? $\endgroup$ – lonza leggiera Jul 14 '20 at 3:43
  • $\begingroup$ Also, is $\ M=X\ $? If not, what is the role of $\ M\ $? $\endgroup$ – lonza leggiera Jul 14 '20 at 4:12
  • $\begingroup$ Assume that you will always have enough cards in the deck to display a showing of Z cards. $\endgroup$ – Jim Liu Jul 14 '20 at 4:14

For it to be always possible for $\ Z\ $ cards to be shown, we have to assume that $\ X\le O-Z+1\ $, so that the number of cards collected before the final showing can never exceed $\ O-Z\ $.

If, at any stage, you have collected $\ c< X\ $ of the cards satisfying the given criteria, then the probability that you will collect $\ k\le N-c\ $ more on the next showing is $$ \frac{{N-c\choose k}{O-N\choose Z-k}}{O-c\choose Z}\ . $$ You can thus treat $\ c\ $ as the state of a time-homogeneous Markov chain whose initial state is $\ c=0\ $, and the entries of whose $\ (N+1)\times(N+1)\ $ transition matrix $\ P\ $ are given by $$ p_{cd}=\cases{0& if $\ 0\le d<c<X\ $, $\ d>c+Z\ $,\\ & or $\ c\ge X\ $ and $\ d\ne c$\\ \frac{{N-c\choose d-c}{O-N\choose Z-d+c}}{O-c\choose Z} & if $\ 0\le c\le d\le c+Z\ $ and $\ c<X\ $\\ 1& if $\ c=d\ge X\ $,} $$ with states $ X,X+1, \dots,N\ $ being absorbing.

After $\ Y\ $ showings, the state of the chain will be $$ f=\pmatrix{1&0&\dots&0}P^Y $$ and the probability that at least $\ X\ $ of the desired cards have been collected is $\ \displaystyle\sum_{k=X}^Nf_k\ $, so the odds in favour are $$ \frac{\displaystyle\sum_{k=X}^Nf_k}{1-\displaystyle\sum_{k=X}^Nf_k}\ . $$


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.