Saturday, December 4, 2010

Why are some calculations slow?

Deck-u-lator calculates card combo probabilities using multivariate hypergeometric distribution.  This calculation is relatively fast if the number of cards you draw is the same as the size of your combo.  However, things slow down when you try calculating results for big combinations when you draw about half your deck.  Why is that?

The problem is what to do with the extra cards.  If you want to know the chances of drawing a four card combo in the first twenty cards, there are sixteen extra cards.  Deck-u-lator tries all the different ways to choose those extra cards.  For each way to choose those extra cards from your deck, add them to your combination and then calculate the multivariate hypergeometric distribution.

How many different ways are there to choose those extra cards?  Our Black Lotus Mana Vault combination uses a deck with five types of cards.  The combination has five cards from four of those types.  If we want to calculate results for drawing thirty cards, we have twenty-five extra cards to work with.  How many ways are there to choose twenty-five cards from five different types?  In mathematical terms these twenty-five cards are a multiset and an upper bound on the number of different ways to choose them can be calculated as the number of combinations with repetition.  For this example there are 23,751 different multisets of twenty-five cards from five types.
$$\binom{25+5-1}{25} = \binom{29}{25} = 23,751$$
Deck-u-lator is fast enough that generating these multisets and then calculating the hypergeometric distributions only takes about half a second.  But if we try something similar with fifteen different types of cards, the number of multisets is much larger.  At the same speed this will take about four hours.
$$\binom{15+15-1}{15} = \binom{29}{15} = 77,558,760$$
Decks with eight types of cards are about the limit.  Calculations for drawing thirty cards from a deck like this will require 1,560,780 multisets and can be done in under ten minutes
$$\binom{22+8-1}{22} = \binom{29}{22} = 1,560,780$$