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)
Search the Dr. Math Library:
Ask Dr. MathTM
© 1994-2013 The Math Forum