Hi Guys

Since there are a few good statisticians around here (and a bunch of really bad ones), I decided to post this question here.

Background:
I've decided to get started playing Magic: the Gathering again. I probably won't play tournaments so I don't need those expensive rares. A playset of commons and uncommons from M12 + the commons from the last block seems like a good way to get started (I still have some lands... from when I played during ravnica).

Data:
I've found an ebay deal for 700 random commons from the set.
There are 101 common cards in the set (all equally likely).
I want 4 of each card.

Statistics Questions:
What's the chance that I'll get at least 4 of every card with the 700 cards?
What's the expected amount of cards that I will have to buy later? (with this I can calculate if it's better to buy this and fill up to 4 at a local store, or to buy a 4 of every card deal on ebay)

I've thought about the problem already but I can't find a correct formula.
+ Show Spoiler [a good try] +

Prob of >=4 of everything = (Prob of >=4 of a certain card)^101
I'm assuming here this is all independent which it is not.
= (1- Prob(0) - Prob(1) - Prob(2) - Prob(3))^101
= + Show Spoiler [maple math] +

c:=101;
t:=700;
evalf(1 - ((c-1)/c)^t - t*1/c*((c-1)/c)^(t-1) - t*(t-1)/2 *(1/c)^2*((c-1)/c)^(t-2) - t*(t-1)*(t-2)/6 *(1/c)^3*((c-1)/c)^(t-3) )^c;

= 0.0136%

Actually now I have an idea to solve the second question.
> .00094 chance of getting 0 of a card (=Prob(0)) => 4 to buy
> .00660 chance of getting 1 of a card => 3 to buy
> .02309 chance of getting 2 of a card => 2 to buy
> .05374 chance of getting 3 of a card => 1 to buy
> = average * 101 = 12.5 cards on average. This is still based on the statistical independence though.

I'm not sure how accurate it is though since my very first assumption is already incorrect. You can clearly see this formula can give a solution for 400 instead of 700 although it should be impossible.

Ghin

United States2391 Posts

July 16 2011 16:34 GMT

How much does what you want to buy cost? Keep in mind you could buy a booster box from a new set for 100$ and get more commons than you'll ever know what to do with, and also be type2. You'll have so many commons that you'll have to use them to start a fire.

You'd also get the rares if you bought a box.

iSTime

1579 Posts

July 16 2011 16:37 GMT

I'm pretty sure that would be incredibly tedious to compute by hand. Just write a program to simulate it and estimate the values you want that way imo.

Seth_

Belgium184 Posts

July 16 2011 17:17 GMT

On July 17 2011 01:34 Ghin wrote:
How much does what you want to buy cost? Keep in mind you could buy a booster box from a new set for 100$ and get more commons than you'll ever know what to do with, and also be type2. You'll have so many commons that you'll have to use them to start a fire.

You'd also get the rares if you bought a box.

A playset of commons is less than €10 (2.5 cent per card). Uncommons are a bit more expensive at ~€25-28. The 700 commons would be about €10 added to the €25. (not including shipping)
Even a box would only give me about 360 commons and 108 uncommons, not even enough for a playset (although I'd get 36 rares as well of course)

On July 17 2011 01:37 vVvTime wrote:
I'm pretty sure that would be incredibly tedious to compute by hand. Just write a program to simulate it and estimate the values you want that way imo.

That would be the next thing I'd to, to find out if my calculations were correct. There might be a simple way to calculate this though.

APurpleCow

United States1372 Posts

July 16 2011 17:39 GMT

I'm absolutely terrible at programming, but I just wrote a quick program to do this. Says you'll have about 18 cards that you won't have four of.

Here's python program in case I did something really dumb [edit: I did, had <5 instead of <4]:
+ Show Spoiler +

import random

notfour = 0

for aa in range(1,1001):

    cards = []

    for nn in range(0,701):
        cards.append(random.randint(1,101))

    for ii in range(1,102):
        if cards.count(ii) < 5:
            notfour += 1

print(notfour/1000)

Ran it three times, output has been 17.869, 17.856, and 17.821.

McFortran

United States79 Posts

July 16 2011 17:39 GMT

Performed a million trials:
There's about a .0023% chance of not having to purchase another card.
On average, you will have to purchase a total of about 12.5 cards.

Below is my source code written in c++. It's poorly written and the formatting isn't working for whatever reason, but it should be valid.
+ Show Spoiler +

#include <iostream>
#include <cstdlib>
using namespace std;

int main()
{
int trials=1000000;
int totalcard=0;
int totalbuy=0;
for (int j=0;j<trials;j++)
{
int Card[101];
for (int i=0;i<101;i++)
{
Card[i]=0;
}
for (int i=0;i<700;i++)
{
Card[rand()%101]++;
}
int More[101],more=0;
bool buy=false;
for (int i=0;i<101;i++)
{
if (Card[i]-4<0)
{
More[i]=4-Card[i];
more+=More[i];
buy=true;
}
else
{
More[i]=0;
}
}
totalcard+=more;
if (buy) {totalbuy++;}
}
cout<<totalcard<<"\n"<<float(totalcard)/float(trials)<<"\n"<<trials-totalbuy;
cin.get();
}

Edit: @APurpleCow, you need to use <4 not <5. If the number of cards is less than 5 it can still equal 4 which is perfectly acceptable. Also when my program is changed to record the number of card types which have fewer than 4 elements, the answer then becomes 8.5. So you'll have 8.5 card types that you'll need to buy with a total of 12.5 cards needed, on average.

APurpleCow

United States1372 Posts

July 16 2011 17:46 GMT

Oops.

I did do something really dumb. I had a <5 instead of a <4.

Except now I'm getting like 8.46 cards you'll have to rebuy, which is still not what mcfortran had...uh...

EDIT: Okay, now that mcfortran edited his post I see what I did wrong. My program gives card types, not cards.

new program:
+ Show Spoiler +

import random

notfour = 0

for aa in range(1,10001):

    cards = []

    for nn in range(0,701):
        cards.append(random.randint(1,101))

    for ii in range(1,102):
        if cards.count(ii) < 4:
            notfour += 4 - cards.count(ii)

print(notfour/10000)

Gives me ~12.4, which is pretty much what mcfortran had. Also, c++ looks a lot harder than python >_>

EDIT2: Don't know if this is useful for you, but assuming I didn't do anything stupid again you should have about 310 cards left over that you already have 4 of.

+ Show Spoiler +

import random

notfour = 0

for aa in range(1,10001):

    cards = []

    for nn in range(0,701):
        cards.append(random.randint(1,101))

    for ii in range(1,102):
        if cards.count(ii) > 4:
            notfour += cards.count(ii) - 4

print(notfour/10000)

AntiLegend

Germany247 Posts

July 16 2011 19:18 GMT

jesus christ, i've been thinking about this question about an hour now, but i can't wrap my head around how to calculate the odds.

so basically the problem could be rephrased as: if you roll a 101-sided die 700 times, what is the probability of rolling each side at least 4 times.

maybe i should draw a tree for a smaller die and less #rolls, and find a way to calculate from there, but i'd really appreciate if someone could present the proper way to solve that question.

McFortran

United States79 Posts

July 16 2011 22:21 GMT

On July 17 2011 04:18 AntiLegend wrote:
jesus christ, i've been thinking about this question about an hour now, but i can't wrap my head around how to calculate the odds.

so basically the problem could be rephrased as: if you roll a 101-sided die 700 times, what is the probability of rolling each side at least 4 times.

maybe i should draw a tree for a smaller die and less #rolls, and find a way to calculate from there, but i'd really appreciate if someone could present the proper way to solve that question.

The distribution of cards follows a Multinomial Distribution. Let X1,X2,...,X101 denote the number of each card with corresponding index that he receives. Then we need to calculate:

P(X1>4 n X2>4 n ... n X101>4) [n denotes intersection]

This can be solved using repeated Discrete Convolution.

The end result is the sum of approximately 101^2*300=3million numbers (maybe significantly more, I'm not sure)**, each of which requires the calculation of P(X1,X2,X4,...,X101), which involves taking 102 factorials and the product of 101 integers***.

Here's one way to apply this:

with 1 degree of freedom (my own term, it seems to fit here)

P(4,4,4,4,...,300) is a way to satisfy the condition (X1>4 n X2>4,..., X101>4) where X1,X2,...,X100 are all fixed
Similarly, P(4,4,4,4,...,300,4) also works where X1,X2,...,X99,X101 are all fixed.
In general we have 101C1=101 ways to rearrange this, so, due to the uniform distribution we have
P(4,4,4,4,...,300)*(101C1)
is the sum of all solutions with 1 degree of freedom (that is, the intersection of all X1,X2,...,X101 that satisfy (X1>4,X2>4,...,X101>4) where 100 of the variables are fixed at Xj=4)

With 2 degrees of freedom

P(4,4,4,4,...,5,300-(4*99+5))+P(4,4,4,4,...,6,300-(4*99+6))+...+P(4,4,4,4,...,300-(4*99+5),5) satisfies the condition
By similar argument,
P(4,4,4,4,...,5,300-(4*99+5))+P(4,4,4,4,...,6,300-(4*99+6))+...+P(4,4,4,4,...,300-(4*99+5),5)*(101C2)
is the sum of all solutions with 2 degrees of freedom...

with n degrees of freedom

[P(4,4,4,...,5,...,5,300-(4*(100-n)+5n))+P(4,4,4,...,5,...,5,6,300-(4*(100-n)+5(n-1)+6))+...
+P(4,4,4,...,5,...,300-(4*(100-n)+5n),5)+...
+P(4,4,4,...,300-(4*(100-n)+5n),5,...,5)]*(101Cn)
is the sum of all solutions with n degrees of freedom... ****

The sum of all 101 of these sums would then be equal to P(X1>4,X2>4,...,X101>4). Note that there is no overlap in these due to the fact that the degrees of freedom with k>1 start with free variables set at 5 and 101*5<700.

**Notice that 101C0+101C1+101C2+...+101C101 is 2^101 (It's the size of all subsets of a set with 101 elements). So this is actually way larger than my initial 3 million assessment (I did 101^2 by accident), but we don't need to directly sum these. As is apparent from the above, however, it's pretty much impossible to do this problem by hand.

***The product of 101 integers is actually quite trivial since it's the same each time [101^(-101)], but the factorials are different in general.

****I think my brain just exploded. In practice I have no way of testing if this is true because even if I were to program this the precision of anything I have access to would be too low and would fail, and even if I could there's a good chance it would still take an unreasonably long amount of time to compute.*****

*****My annotation system doesn't seem to be very efficient.

McFortran

United States79 Posts

July 16 2011 23:23 GMT

#10

It appears that symmetry could significantly help here as well.

Not that P(4,4,4,...,5,300-(4*99+5))=P(4,4,4,...,300-(4*99+5),5).
So with 2 degrees of freedom, we can use half as many calculations by only going half way.

With n degrees of freedom I believe you can divide the number of computations by n, but I've done too much math today to verify this. Time to study some more abstract algebra

Kiarip

United States1835 Posts

July 17 2011 05:27 GMT

#11

Well the probability that you get 4 of each of the 101 cards is easily represented arithmetically.

First you need total amount of ways that you can get 4 of each cards.

so 404 of the cards needs to be the 101 quadruples, so you can arrange that (404!)/((4!)^101)

Then you have 296 cards left over.

you don't care what they are but they also needs to be arranged in some way with the first 404 cards so that's.

700!/((404!)*(296!)) * (404!)/((4!)^101) = (700!)/((296!)*((4!)^101)

then you have the total number of arrangements in total: (101)^(700)

so you have ((700!)/((296!)*((4!)^101) / (101)^(700))

Now good luck getting a calculator that will actually compute this for you lol.

simulation would prolly be best >_>.

edit:

now that I think about it, this may not be right, but this is definitely solvable using generating functions, the question is it calculable?

Please or register to reply.

Live Events Refresh