Mulligans in the Bazaar

Several competitive decks in Vintage Magic: The Gathering are powered by the card Bazaar of Baghdad.

Deck construction rules mandate at least 60 total cards in a deck with at most four copies of any given card. The game starts by each player drawing seven cards then performing, if he wishes, a series of “mulligans” in which the current hand is reshuffled and a new hand drawn until a desirable hand is drawn (there are reasons related to the nature of the game for why mulligans are allowed, but these are not relevant to this post). After keeping a hand, the player puts a card on the bottom of his deck for each mulligan taken. So a player can opt to keep taking mulligans until a specific card happens to be drawn, and it so happens that decks featuring Bazaar of Baghdad tend to be so reliant on that card that players will do exactly that. Now, there is an odd duck of a card, Serum Powder, that such decks also play:

To “exile” cards means to remove them from the game, so they do not get shuffled back into the deck before drawing a new hand. Serum Powder thus increases the probability of finding a Bazaar by removing non-Bazaar cards from the deck with each use. Accounting for Serum Powders, the whole process for beginning the game is as follows:

1. Set $H=7$, which is the number of cards that will be kept from among the drawn cards.
2. Draw 7 cards
3. Decide which $H$ cards to keep (keep any Bazaars, since that is the point) and put the others on the bottom of the deck
4. If the hand has Bazaar, stop. Otherwise…
5. If the hand has Serum Powder, exile the $H$ cards kept, then draw $H$ cards and go to step 4. Otherwise…
6. Decrement $H$ by one and go to step 2

Players are naturally interested in the probability of eventually finding a hand with at least one Bazaar, and in the expected number of cards in the hand that is finally kept. Finding these numbers is a complicated process because:

• The probability of finding a Bazaar depends on how many cards have been removed by Serum Powders, which depends on how late in the process each Serum Powder was drawn
• If a Bazaar-less hand has multiple Serum Powders, they all get removed

The flowchart sketched below shows the relevant branches of the mulligan process:

Branches have been labeled with probabilities, with the usual notation for binomial coefficients:

$$\displaystyle \left(\begin{matrix}a \\ b\end{matrix}\right) = \frac{a!}{b!(a-b)!} $$

All the probability expressions involve subtractions of 4, because we are considering hands that do not have Bazaar (that’s why we’re taking mulligans in the first place), and we assume the deck has the maximum allowed four Bazaars in it.

The big loop in the flowchart is repeated until either a hand with Bazaar is drawn or a minimum hand size is reached. This minimum size is usually 1, because if you mulligan down to one card your only options are to mulligan again to zero cards (stupidly bad) or keep the one card and pray (slightly less bad). Rather than figure out by hand all the possible branches one could take on these passes through the loop, here’s a Python program that does the work for you:

#!/usr/bin/env python

from math import comb as nck

class State:
    def __init__(self, cards, powders, draws, handsize, probability):
        self.N = cards
        self.P = powders
        self.D = draws
        self.H = handsize
        self.probability = probability


    # Form new states from this one for each possible number of Serum Powders
    # in the hand represented by this state, and calculate probabilities for
    # each.
    def fork(self, minhandsize):
        p0bazaars = nck(self.N-4, self.D)/nck(self.N, self.D)
        pbazaar = 1.0 - p0bazaars

        if (self.H == minhandsize):
            return pbazaar, []

        denom = nck(self.N-4, self.D)

        newstates = []
        for npowders in range(min(self.P, self.D)+1):
            # The -4 here is for the four Bazaars that are in the deck but not
            # in the hand, since we are assuming this is a hand we will mulligan.
            prob = p0bazaars * nck(self.P,npowders)*nck(self.N-4-self.P, self.D-npowders)/denom
            if (npowders == 0):
                # Natural mulligan
                newN = self.N  # No cards removed from the deck
                newP = self.P  # Number of Powders in the deck does not change
                newD = 7  # Will draw 7 new cards
                newH = self.H - 1  # Hand size reduced by 1
            else:
                # Powder redraw
                newN -= self.D  # Cards drawn are removed from the deck
                newP = self.P - npowders  # All powders in this hand are removed from the deck
                newD = self.H  # Will draw cards equal to the number of cards currently in hand
                newH = self.H  # Hand size is not altered

            newstates.append(State(newN, newP, newD, newH, prob*self.probability))

        return pbazaar*self.probability, newstates

# For a given number of Serum Powders and a minimum hand size below which you
# will not mulligan, get the probabilities of keeping hands of each size,
# assuming you mulligan strictly to Bazaar.
def get_probabilities(npowders, minhandsize):
    pbazaar_vs_handsize = [0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0, 0.0]
    # Set up the state for the first draw
    start = State(cards=60, powders=npowders, draws=7, handsize=7, probability=1)

    states = [start]
    # Fork states until all states end in either a hand with Bazaar or a hand
    # of the minimum hand size.
    while states:
        newstates = []
        for s in states:
            pbazaar, forkedstates = s.fork(minhandsize)
            pbazaar_vs_handsize[s.H] += pbazaar
            newstates.extend(forkedstates)
        states = newstates

    return pbazaar_vs_handsize

if (__name__ == "__main__"):
    # Table column headers
    print('| Powders | %6d | %6d | %6d | %6d | %6d | %6d | %6d | Avg hand size |' % (1,2,3,4,5,6,7))

    for npowders in range(5):
        pbazaar_vs_handsize = get_probabilities(npowders, minhandsize=1)
        pbazaar_vs_handsize[1] = 1.0 - sum(pbazaar_vs_handsize[2:])

        expected_handsize = 0.0
        for k,p in enumerate(pbazaar_vs_handsize):
            expected_handsize += k*p
        print('| %7d | %1.4f | %1.4f | %1.4f | %1.4f | %1.4f | %1.4f | %1.4f | %1.4f |' % (npowders, *pbazaar_vs_handsize[1:], expected_handsize))

Which produces the following table for the probabilities of finding Bazaar in a hand of given size, and the average number of cards in the kept hands, for each possible number of Serum Powders.

Powders	P(keep 1)	P(keep 2)	P(keep 3)	P(keep 4)	P(keep 5)	P(keep 6)	P(keep 7)	Average hand size
0	0.0469	0.0312	0.0519	0.0865	0.1441	0.2399	0.3995	5.5674
1	0.0355	0.0259	0.0451	0.0787	0.1382	0.2438	0.4327	5.7207
2	0.0258	0.0208	0.0381	0.0703	0.1308	0.2460	0.4681	5.8698
3	0.0179	0.0161	0.0313	0.0613	0.1219	0.2461	0.5055	6.0134
4	0.0117	0.0119	0.0246	0.0519	0.1113	0.2437	0.5450	6.1503