F# and Markov Chains, oh my!

  • Article

Edit 2/8/2010: Updated syntax for latest F# language.

 

Recently I started playing a collectable card game after some friends got me into it. (Who themselves got back into it after some friends of theirs started playing. Witness the economic potential of viral card games!) As it turns out, I am a pretty poor card player I figured I would get into the business of collecting cards. Which is fun, you can do alone, and requires no skill.

 

Since I like Interesting Problems, I figured I would answer the question “If I started from scratch, how many booster packs would it take for me to collect the whole set”. Well, since booster packs give you cards randomly the best you can shoot for is a confidence interval.

 

Framing the Problem

The current expansion set of this card game has 80 rare cards, 80 uncommon cards, and 121 common cards. In a given booster pack you get 1 rare, 3 uncommon, and 11 common cards. As you can see Rare cards are the gating factor, so by the time we have collected all of those it is safe to assume you have all the uncommon and commons as well. So to state our problem formally: after buying X booster packs, each containing 1 rare card, what is the probability that you have all 80 unique rare cards?

 

Fortunately this problem can be easily solved using a Finite State Machine and a Markov Chain.

 

The Solution

Consider a Finite State Machine with 81 nodes. Node i will represent having i of the 80 rare cards. We start at node 0, meaning we have 0 rare cards. We open a pack of cards and get one rare, and transition to node 1. So far so good. Now if we open the second pack of cards there are two possible outcomes. With probability 1/80 we will get the same card and remain at state 1; or with probability 79/80 we will get a new card and move onto state 2. You can generalize all node transitions all the way up to node 80, where there is a 0/80 percent chance to get a new card and an 80/80 percent change to get a dupe.

 

Now that we have a probabilistic model to mimic what happens when we buy booster packs, we can simply put that into a Markov Chain to get our confidence interval. In short, we keep an array of probabilities corresponding to each state of our FSM. So initially each of our array’s has 81 elements have value of 0.0 except for element 0, which has a value of 1.0. Since initially you have a 100% chance of having zero rare cards. After our first iteration our array will be equal to [0.0; 1.0; 0.0; 0.0; …] since there is a 100% chance of transitioning from the ‘0 rares’ state to the ‘1 rares’ state after opening your first pack. After than the array will be [0.0; (1/80); (79/80); 0.0; …] since there is a 1/80 percent chance to get a dupe of the same card, and a 79/80 percent chance to get a new one.

 

Now onto the code!

 

Code in F#

open System

let probOfNewCard (numAlready : int) (numOfType : int) =

    let dNumer = float (numOfType - numAlready)

    let dDenom = float numOfType

    dNumer / dDenom

   

// uniqueCardDist[i] = current probability to have i cards

let mutable startingCardDist = Array.create 81 0.0

startingCardDist.[0] <- 1.0

let mutable itteration = 1

while startingCardDist.[80] < 0.50 do

    Console.WriteLine("Opening pack [" + itteration.ToString() + "]...")

    let mutable updatedCardDist = Array.create 81 0.0

    for i = 0 to 80 do

        let probOfNew = probOfNewCard (i - 1) 80

        let probNotNew = 1.0 - (probOfNewCard i 80)

        updatedCardDist.[i] <-

                probNotNew * startingCardDist.[i] +

                probOfNew * (if i - 1 >= 0 then startingCardDist.[i - 1] else 0.0)

    itteration <- itteration + 1

for j = 0 to 80 do

        startingCardDist.[j] <- updatedCardDist.[j]

   

    printfn "Distribution %A" startingCardDist

   

Console.WriteLine("Finished! Took " + itteration.ToString() + " packs of cards.")

Console.ReadKey(true)

Conclusion

(Barring any flaws in my math or logic) it takes 381 booster packs in order to get a 50% likely hood of getting all 80 rares and 450 for 75% confidence! And, of course no math problem is complete without a graph:

 

Card Probability Chart

 

Probability to have specific number of unique, rare cards.

 

Analysis

It is much easier to get the first 40 or even 70 rare cards than the last 10. (That probability of drawing the last one alone is 1/80 or 1.25%.) From this then, we can conclued that collectable card games are a monkey sink (somewhat true) and that collecting the whole set is neigh impossible (false).

 

Though it is true to have a high confidence of completing your set by buying booster packs alone you would need to buy literally hundreds and hundreds of cards. What this model neglects to include is the impact of trading. Let’s say you purchased 160 packs and only have 70 of the rare cards. That means you have 90 rare cards as trading stock. Certainly not every rare is equally valuable but if even if you traded those away at a rate of 9:1 you would be in good shape.

 

Edit: Resized the photo, fixed a typeo.

Comments

  • Anonymous
    January 05, 2008
    Tell me more about the economic potential of viral card games.  Do you have any examples?

  • Anonymous
    January 05, 2008
    Recently I started playing a collectable card game after some friends got me into it. (Who themselves