Drexel dragonThe Math ForumDonate to the Math Forum

Ask Dr. Math - Questions and Answers from our Archives
_____________________________________________
Associated Topics || Dr. Math Home || Search Dr. Math
_____________________________________________

Advanced Probability as Used in a MAGIC


Date: 15 Feb 1995 20:49:56 -0500
From: Anonymous
Subject: Re: Math Problem - advanced probability

Here is the problem
we'd like to solve, with the goal of writing a visual basic program to solve
the problem for various conditions:

   A MAGIC deck is componsed of numerous subsets of
   cards that fall into specific categories.  A card
   can be in several categories, but that isn't part
   of this problem.  We would like to know how to
   calculate the probability of having pulled a card
   from a subgroup in the deck by the 'Xth' turn,
   where 'X' increases from 1 to whatever.
   The known items are:

       Deck Size:   'M' cards
       Subset size: 'N' cards  (N always less than M)
       Turn Count:  for each of the first 'Tth' turns
       The game starts off with you drawing 7 cards
       into your hand.  After that, the cards are
       drawn one at a time, without replacement.

   We would view this in a table where each cell in
   the table represents the probability at that point
   in time.  The columns represent the likelihood of
   pulling 1 card from this subset, 2 cards from this
   subset, 3 cards from this subset, etc.  The rows
   represent each turn.

   Example:  Today, you decide to play just Black and
   Green cards from your collection of cards.  You
   have a total of 100 cards and in this deck you
   have placed exactly 65 creature cards.  You now
   want to know the probability of having a creature
   card when the game starts, and for each turn for
   the next 10 turns.  You'd also want to know the
   probability of having 2 creatures, or 3 creatures,
   etc, for each turn.

   The table would look something like this:

                Probability of having this many cards
                from the subset of cards in this deck
                for each turn:

                     1     2     3     4     5      6     7
                 |===============================
                0|  3%    2.7%  2.1%  1.2%  .1%   .01%   etc
                1|  4%    3.7%  etc...
                2|  6%    5.1%  etc...
                3|  8%
    Turn        4|10%
    Number      5|13%
                6|
                7| etc...


    The way we would read this table is:

         given the previous deck, there is about a
         3% chance of being dealt one creature card,
         a 1.2% chance of being dealt 4 creature
         cards, etc.  Also, there is a 10% chance of
         having one creature card by the 4th turn,
         etc.

    Other questions coming from this are:

         If we calculate that there is a 4% chance
         of having a creature card by turn 5 and
         (from another run of the program for the
         same deck) a 3% chance of drawing a spell
         by turn 5, then what is the probability of
         having both by turn 5?

Thanks for your help.


Denis --

This game seems to be taking the country by storm!  Dr. Math is happy
to help out with your probability calculations, provided this
information doesn't spur you to spend your hard-earned cash on
massive amounts of new cards.

First for some exact calculations: the simplest thing to compute is
the first column of your table.  Let's say the deck has M cards and
the subset you're interested in has N cards (your notation).
The probability you'll have no cards at all from your subset on your
"zeroth" turn is the probability that you'll pick 7 cards one by one,
with no luck, so that's

        (M-N)/M times (M-N-1)/(M-1) times ... times (M-N-6)/(M-6).

The chance of total failure after your first turn is gotten by
multiplying this number by (M-N-7)/(M-7) (that's the chance of
failing to get a card in the desired set on your first turn, given
that you weren't dealt one).  So for each turn 0 , 1 , 2 , ...
you can figure out the chance of having no careds at all from
the subset by that turn.  This information doesn't appear in the
table you asked about, but it's worth having, right?  Make a
note of it: on turn k-7 you have picked k total cards, and
your failure probability is

(1)     (M-N)/M times (M-N-1)/(M-1) times ... times (M-N-(k-1))/(M-(k-1)).

OK, a small variation on this will compute the first column, as follows.
You want the probability of picking exactly one card from your
subset out of k total cards, where k = 7 for the first row (your
zeroth turn), k = 8 for the second row (your first turn) and so on.
Well, imagine picking up these cards one at a time.  The probability
of failing to pick a card from your set for k-1 turns has
already been calculated.  Now the probability that you succeed on
your kth turn is N / (M - (k-1)).  See why?  There are now
M - (k-1) cards left in the deck and all N good cards are still there.
Multiplying this together with the quantity computed above in (1) gives

(2)     (M-N)/M (M-N-1)/(M-1) ... (M-N-(k-1))/(M-(k-1)) times N/(M-(k-1)) .

Now remember, this is the probability that the one good card you picked
was the very last one.  But it could have been the 2nd to last, or 3rd to
last, or in fact any of k possibilities, but all these possibilities are
equally likely, so if you multiply equation (2) by k you get the
entry in the first column corresponding to k total cards (turn
number k-7).

Now for the second column, third column, etc.  You just repeat the
same trick.  Say you're computing the rth column.  Then you first
compute the probability of failing to get a good card in your
first k-r picks, which you already computed in (1), then multiply
by the probability of succeeding in your next r picks, which is

(3)     N/(M-N-(k-r)) (N-1)/(M-N-(k-r)-1) ... (N-(r-1))/(M-N-(k-1)) .

You have to multiply by the number of ways you could have succeeded,
that is, not just the last r cards out of k could have been the good ones,
but any r of the k could have been the good ones.  The number of
ways of choosing r things from among k is called "k choose r" and
is equal to k! / (r! (k-r)!) , where the "!" represents "factorial",
meaning what you get when you multiply all the numbers from that number
down to 1 (example: 5! = 5 times 4 times 3 times 2 times 1 = 120).
OK - you're done, you've computed every column of the table.

Now for some short-cuts.  The above computations can be very
time-consuming, and when both N and M are large, and the number of
turns isn't too large, there is a short-cut to get an approximate
answer.  The idea behind the approximation is to pretend that you're
sampling with replacement rather than without replacement.  Also,
pretend that the successes (the times at which you pick good cards)
are not integers between 1 and k but are any real numbers between
0 and k.  Then you gets what's called a Poisson process of rate N/M.
The probability of r successes in time k for a rate N/M Poisson
process is

(4)     (kN/M)^r  e^(-kN/M)  /  r!  .

This is probably quicker to compute than the exact table entries,
but you can compare a few to see how far off they are and whether
you want to use the approximation or do the exact computation.
By the way, the e in the formula is approximately 2.71828, and in
case you've never seen e before, whatever calculator you do this
on will have a button that computes e to any power you put in.

I admit I didn't really explain how you get (4), and I didn't answer
the last part of your question with the simultaneous probabilities,
but if you want further explanation, I suggest you digest this first.
I'd be happy to clarify any part of the above that doesn't make sense.
Happy Magic playing...

Dr. Math (Robin Pemantle)
    
Associated Topics:
High School Probability

Search the Dr. Math Library:


Find items containing (put spaces between keywords):
 
Click only once for faster results:

[ Choose "whole words" when searching for a word like age.]

all keywords, in any order at least one, that exact phrase
parts of words whole words

Submit your own question to Dr. Math

[Privacy Policy] [Terms of Use]

_____________________________________
Math Forum Home || Math Library || Quick Reference || Math Forum Search
_____________________________________

Ask Dr. MathTM
© 1994-2013 The Math Forum
http://mathforum.org/dr.math/