Expected number of card draws until one of several given deck multisubsets is obtained?

Question

This question is easiest illustrated with a non-standard card deck, since cards can have more than one occurence.

Let $T=\{A, B, C, ...\}$ be the finite set of card types, and $n : T \mapsto \mathbb{N}$ be the function that gives the number of occurences $n(x)$ for any $x \in T$. It should be obvious that the total number of cards in the deck is then $\sum_{x\in T} n(x)$.

You are given finitely many multisets (meaning repetitions matter but order doesn't). They will be referred to as your goals, e.g.: $\{A, A, B\}$, $\{B, C, E\}$ and $\{B, B, C, D\}$.

Starting with no cards and with a complete deck, what is the expected number of times that you need to draw a card until your hand allows you to complete at least one of the goals?

In other words, what is the expected card number that you need to draw until at least one of the goals is a multi-subset of your hand?

I explained the problem again in this four minute video for those to whom it is still unclear.

I want to solve this problem because of my involvement in a project of creating a card game as an internship. Any help is appreciated.

Answer 1

My Icepool Python package can compute exact solutions to problems of this type with runtime jointly polynomial in the number of unique cards, hand size, and deck size, though exponential in the number of combos. Here's an example script to compute the number of cards needed to get any combo from a hypothetical deck:

from icepool import Deck, multiset_function, from_cumulative

deck = Deck({
    'A' : 11,
    'B' : 12,
    'C' : 13,
    'D' : 14,
    'E' : 15,
})

@multiset_function
def find_combos(hand):
    return (
        hand >= ['A', 'A', 'B'],
        hand >= ['B', 'C', 'E'],
        hand >= ['B', 'B', 'C', 'D'],
    )

hand_sizes = list(range(deck.denominator() + 1))
cdf = [find_combos(deck.deal(hand_size)).map(any) for hand_size in hand_sizes]
output(from_cumulative(hand_sizes, cdf).trim())

(API subject to change. This script is based on Icepool v0.25.6.)

Brief explanation:

• deck represents, well, the deck. The keys are the unique cards and the values are how many copies of each card are in the deck.
• The multiset_function allows us to define a function using some simple multiset operations. In this case, the >= operator represents the superset comparison, and the tuple produces a joint evaluation. So this will jointly evaluate whether each of the combos have been met.
• find_combos(deck.deal(hand_size)) jointly evaluates the combos over hand sizes. The result is a distribution over tuples of booleans, each element indicating whether the corresponding combo was met.
• .map(any) then collapses the outcomes to just whether any of the combos have been met. (Unfortunately I have not come up with a good way to allow this to be expressed inside the multiset_function itself.) This gives the CDF over the number of draws, i.e. the chance that it will take at most hand_size cards to get any combo.
• from_cumulative then takes successive differences to find the PMF, i.e. the chance it will take exactly hand_size cards to get any combo. .trim() prunes all zero-probability outcomes.

You can try the script out in your browser here.

The algorithm uses dynamic programming and the decomposition of the hypergeometric distribution into binomials to find the distribution efficiently. If you are curious to learn more, you can read my paper here.

@inproceedings{liu2022icepool,
    title={Icepool: Efficient Computation of Dice Pool Probabilities},
    author={Albert Julius Liu},
    booktitle={Eighteenth AAAI Conference on Artificial Intelligence and Interactive Digital Entertainment},
    volume={18},
    number={1},
    pages={258-265},
    year={2022},
    month={Oct.},
    eventdate={2022-10-24/2022-10-28},
    venue={Pomona, California},
    url={https://ojs.aaai.org/index.php/AIIDE/article/view/21971},
    doi={10.1609/aiide.v18i1.21971}
}