Looking for help with a question of probability.

September 1, 2006 12:47 PM

MathFilter: Okay, I've got this gumball machine, which contains an infinite amount of gumballs, evenly distributed between 100 different flavors...

Unfortunately, the machine is broken, and three-quarters of the time I turn the crank, I get nothing. When the machine does deliver, it has a 1 in 20 chance of giving two gumballs instead of just one.

After how many cranks would I have a 50% chance of having at least one gumball of every flavor? How many for a 99% chance?

Please show your work, as I'm trying to learn how to answer questions like this for myself. :)

posted by rifflesby to education (10 comments total)

I'll provide hints. Maybe somebody else will do your homework answer your question directly.
How many gumballs will it take have a 50% likelihood that you will have one of each flavor?
How many cranks does it take to get that many gumballs?
posted by forforf at 1:17 PM on September 1, 2006

http://www.gomath.com/htdocs/lesson/probability_lesson9.htm
via http://www.google.com
posted by feloniousmonk at 1:20 PM on September 1, 2006

First: the number of cranks required to get a gumball, on average.

- A crank has a probability p_nada = .75 chance of producing nothing.
- A crank has a p_ball = .25 chance of producing one or two gumballs.
- p_ball is broken down into p_one and p_two, the chances respectively of getting one gumball or two.
- 1 in 20 successful (p_ball = 0.25) cranks produces two balls, so p_two = 0.25 * 0.05 = 0.0125, and p_one = 0.25 * 0.95 = 0.2375.

In summary:
p_nada = 0.75
p_one = 0.2375
p_two = 0.0125

Now, multiply the gumballs yielded for each possibility by it's probability value p:

0 * 0.75 = 0
1 * 0.2375 = 0.2375
2 * 0.0125 = 0.025

Sum those up, and you get the long term average rate of gumballs per crank: 0.2675. To restate that as the number of cranks required to get a gumball, take the inverse of the value: 1 / 0.2675 ~ 3.738.

Now you know how many cranks it takes to produce a gumball. You've safely partitioned the problem into two parts, and you can proceed to step two: how many gumballs do you need to produce to hit the 50% chance of having one of each flavor? 99%?
posted by cortex at 1:24 PM on September 1, 2006

I'm reluctant to provide a complete solution because this does smack of homework (although insanely difficult homework).

Unfortunately, it isn't enough to calculate the average number of cranks per gumball, because we're talking about at least 100 gumballs, and thus on the order of 400 cranks. With that many cranks, the standard deviation will be high. If you want to get the correct number of cranks exactly, you will have to account for the distribution of cranks.

Thus you must ask, what is the probability of getting N gumballs with C cranks, and multiply that by the probability of getting at least one of each type given that you have N total. Since N is a free variable, you must then sum this answer over N, and see this sum meets your threshold probabilities.

This problem is quite challenging if it is a homework assignment. Although there is the possibility of there being a closed-form solution, it would be far faster to have a computer check this out numerically (i.e. calculate the probability for a given number of cranks, and see if it's sufficient), than it would be to try to find a formula that spits out the answer.
posted by Humanzee at 1:42 PM on September 1, 2006

This doesn't make a good "learning probability" question. What Humanzee said above, plus the second part of finding the number of gumballs needed to give you an X% probability of having found them all is not an easy problem, relying on messy sums of permutations.
posted by vacapinta at 1:52 PM on September 1, 2006

I'm reluctant to provide a complete solution because this does smack of homework (although insanely difficult homework).

Nope, I'm well out of school. This is a restatement of a mechanic I'm working on for the online game I write for, and I wanted to get some solid numbers to see if I might need to tweak the rate at which the "gumballs" drop.

Incidentally, can anyone recommend a good textbook on probability? Preferably one I can order from Amazon?
posted by rifflesby at 2:03 PM on September 1, 2006

This leaves me to wonder about the probability that carefully watching your Ask Mefi questions can help advance my KoL character when the new content hits. (likely very, very small.)
posted by leapfrog at 2:20 PM on September 1, 2006

Oh, so your homepage really is the Kingdom of Loathing?

Since this is just for a game, I'm assuming that rough approximations should be good enough for now, in which case one can approximate that the number of cranks is just N times the averge number of cranks per gumball.

Some further approximations yield a decent rough formula:

Cranks = 3.7 * log(1 - Prob^.01) / log .99
where Prob is the threshold you set (.5 or .99)

If you decide to mess with your formula to make it easier to get meat-flavored gumballs, or whatever, the .01 is just 1/ #types, and the .99 is 1 - 1/#types, so alter them accordingly.
posted by Humanzee at 2:25 PM on September 1, 2006

[few comments removed, take speculations about homework to metatalk or email]
posted by jessamyn at 4:46 PM on September 1, 2006

FWIW I knocked up a quick MATLAB script to simulate your machine and the results from this do correspond well with Humanzee's expression.
posted by teleskiving at 4:23 AM on September 2, 2006