Math FAQ

jarstar · 09-17-2009, 04:18 PM

I keep seeing the same questions over and over, so I decided to make this list.

Q: What's the probability of getting regular items (non-hats), and on what time interval?

A: Every 25 minutes, you have a 1/4 chance of getting an item. This means that you might expect (on average) getting 1 item drop every 100 minutes.

Q: What's the probability of getting a hat, and on what time interval?

A: Every 4 hours, 17 minutes, and 10 seconds of gametime you have about a 1/28 chance of getting a hat. (In DF we trust). From here on out, I will refer to these as "possible hat drops."

**NEW** Q: I know the time to get a possible hat drop is 4 hours and 17 minutes, but does the timer rollover between gaming sessions? i.e., if I play for 2 hours and 17 minutes, log off, then come back, does the timer resume with 2 hours left?

A: Yes! This way, you don't have to play for four hours at a stretch to get a hat, and why some people just log in and get a hat after 10 minutes.

Q: How long will it take me to get a hat?

A: The expected time to get a hat is 28 possible hat drops. That is, 28 * 4.3 hours ~ 120 hours. I'll call this an "actual hat drop."

Q: What's the probability of getting [insert hat here]?

A: I'm going to assume the probability is uniform across all hats, so (since there's 30 hats) at each possible hat drop, you have a (1/28)(1/30) = 1/840 chance of getting [hat].

Q: How long will it take me to get [insert hat here]?

A: The expected time to get [hat] is 840 possible hat drops. That is, 840 * 4.3 ~ 3,612 hours (around 5 months).

Q: How long will it take to have a 50% chance of having a hat?

A: The formula I'm using to calculate the probability is 1 minus the probability of NOT having a hat, raised to the power of number of possible hat drops. So, if x is drops, the probability of having a hat after x drops is given by p(x) = 1 - (27/28)^x.

You can plug in values and find out where p(x) ~ .5, or you can solve for the inverse function, and just plug in .5.

For example:
p(20) ~ .5 (after 20 possible hat drops, there is a 50% chance you have a hat)

p(60) ~ .9 (after 60 possible hat drops, there is a 90% chance you have a hat)

(For a few more, see http://forums.steampowered.com/forum...0&postcount=12)

Q: How long will it take to get all the hats?

A: I answered this one before, but I estimated using the average running time, and I really shouldn't have done that, because it's too rough with only 30 hats. So, properly calculated, this is equal to (30/1 + 30/2 + 30/3 + ... + 30/29 + 30/30) actual hat drops. That's about 120.

So, after getting about 120 hats, you might expect to have at least one of each. But that's about 120 * 28 = 3360 possible hat drops, which is approximately 20 months of gametime.

Q: True randomness is impossible to simulate with a computer, right? Every "random" computer program has an algorithm behind it.

A: Well, try reading this: http://www.random.org/randomness/, especially concerning Pseudo-random number generators, versus True-random number generators. I'm not saying I think this is what Valve implements, but it is possible to simulate true randomness.

Does anyone have any other questions?

Does anyone have any corrections? Feel free to discuss.

TatersChoice · 09-17-2009, 04:24 PM

I love you.

*VeLeRoN* · 09-17-2009, 04:28 PM

Would be nice if you could add some more in-depth math explanation too.

Grim Tuesday · 09-17-2009, 04:32 PM

Good guide anyways...

Zephyrlot · 09-17-2009, 04:35 PM

My question is, is a possible hat drop accumulated game time, or would you have to play for 4+ hours straight just to get a single chance?

Hashmir · 09-17-2009, 04:38 PM

Quote:

Originally Posted by Zephyrlot

My question is, is a possible hat drop accumulated game time, or would you have to play for 4+ hours straight just to get a single chance?

It is accumulated. You can start and stop at will without disrupting your chances.

Abyss · 09-17-2009, 04:42 PM

The significant increase was from 1/84 to 1/28.

forceNet · 09-17-2009, 04:44 PM

Spoiler:
these numbers are not correct anymore, unless valve lied about "significantly increaseing the chance of finding any of the existing hats"

yes I somehow managed to accidentally delete my post

Fox McCloud · 09-17-2009, 04:44 PM

Quote:

Originally Posted by forceNet

Spoiler:
these numbers are not correct anymore, unless valve lied about "significantly increasing the drop rates"

the 3.57% is the increased rate--it was formerly 1.19%.

Either way 20 months eh? We can translate that to "never" as no one can play 24/7 for 20 months straight...you could idle, but, even then, I wouldn't be surprised if the system gets changed, by then.

jarstar · 09-17-2009, 04:46 PM

Veleron, I wanted to keep it relatively brief for those who don't want the in-depth explanations, but I'll work on a write-up of some of the deeper workings.

forceNet · 09-17-2009, 04:46 PM

nevermind for some reason my long-time-no-sleep brain thought that when the interval is the same, then the chance is the same (yes makes sense, doesn't it) so when I saw familiar "4 hours, 17 minutes, and 10 seconds" I made that re/tarded post

brb sleep

RedDot · 09-17-2009, 04:57 PM

Quote:

Originally Posted by *VeLeRoN*

Would be nice if you could add some more in-depth math explanation too.

You gotta pay for math courses.

jarstar · 09-17-2009, 05:31 PM

This is for Veleron.

Behind the scenes - What does expected value mean?

The 'expected value' of a random variable is (colloquially) the average value one would expect by repeating the same experiment several times. For example, if I roll two dice over and over, and average all the values, I would probably get something like 7 (those who play Settlers of Catan already guessed this!). Mathematically, it's the integral of the random variable's probability density function, but you don't really need to understand that to understand expected value. The point is: it does not tell you exactly what number you will roll on a die, or exactly how long it will take to get the Vintage Tyrolean... just the average.

Behind the scenes - How do you calculate probabilities?

I made a brief pass at this in the original post. How do I find the probability that I have a hat, given 43 drops? Well, suppose in all of those 43 drops, you didn't get a hat every single time. Since the probability of getting no hat is 27/28 (and these hat rolls are independent events), we can multiply the probabilities and see that the probability of not getting a hat in 43 rolls is (27/28)^43.

Now, since probabilities are out of 1, we can easily see that the probability of [getting at least one hat] is one minus the probability of [getting no hats at all] in x drops. So, we have our probability function y(x) = 1 - (27/28)^x.

To invert this we solve for y:
y = 1 - (27/28)^x
1 - y = (27/28)^x
ln(1 - y) / ln(27/28) = x
x(y) = ln(1-y)/ln(27/28) (I use ln() out of convention)

Now, x(y) is a function that takes a probability, and returns the number of possible hat drops needed to obtain that probability.

Behind the scenes - How long will it take to get all the hats?

Keep in mind, we're finding the expected time to get all the hats, not necessarily the exact time (which is impossible to predict). To do this, we start with finding the expected time (in actual hat drops) to get one hat. We add to that the expected time to get a hat that ISN'T the first one, and from there we just iterate over the 30 hats.

So, counting in actual hat drops, the expected time to get the first hat is... one drop. Now, on your next hat drop, there is a 29/30 chance that it will not be the same hat. I need to weave a little magic here, by saying that the probability of hats dropping has a geometric distribution, so the expected time to getting a different hat on your second hat is the reciprocal of 29/30, AKA 30/29.

Like I said, we iterate from there: the expected time to get a third different hat is 30/28, and on down to 30/1. Then we just add it all up, and it's 119.84.

Was there anything specific that you wanted to see, Veleron?

habhead · 09-17-2009, 06:02 PM

What this means is that we will be seeing another Presidental election before even the idlers of average luck will have a hat for each of the classes.

bluenigma · 09-18-2009, 01:46 AM

The math checks out on my end. The expected time grows on the order of O(n log n), where n is # of hats, correct?

I wonder, since we also have the variance bounded, could we make some assumptions and calculate the expected time to be 25%, 75%, 90%, and 95% likely to have all the hats?

And for the "Why the hell not" kind of problem: what's the expected time to have 1 hat for every class? If there were an equal number of hats for every class, it'd be the coupon collector problem with n=9. But the hatless hats throws it into tricky territory.
Ignoring the hatless issue, I get an estimate of around 128 days.

09-17-2009, 04:18 PM	#1
jarstar Join Date: Aug 2009 Reputation: 69 Posts: 271	Math FAQ I keep seeing the same questions over and over, so I decided to make this list. Q: What's the probability of getting regular items (non-hats), and on what time interval? A: Every 25 minutes, you have a 1/4 chance of getting an item. This means that you might expect (on average) getting 1 item drop every 100 minutes. Q: What's the probability of getting a hat, and on what time interval? A: Every 4 hours, 17 minutes, and 10 seconds of gametime you have about a 1/28 chance of getting a hat. (In DF we trust). From here on out, I will refer to these as "possible hat drops." NEW Q: I know the time to get a possible hat drop is 4 hours and 17 minutes, but does the timer rollover between gaming sessions? i.e., if I play for 2 hours and 17 minutes, log off, then come back, does the timer resume with 2 hours left? A: Yes! This way, you don't have to play for four hours at a stretch to get a hat, and why some people just log in and get a hat after 10 minutes. Q: How long will it take me to get a hat? A: The expected time to get a hat is 28 possible hat drops. That is, 28 * 4.3 hours ~ 120 hours. I'll call this an "actual hat drop." Q: What's the probability of getting [insert hat here]? A: I'm going to assume the probability is uniform across all hats, so (since there's 30 hats) at each possible hat drop, you have a (1/28)(1/30) = 1/840 chance of getting [hat]. Q: How long will it take me to get [insert hat here]? A: The expected time to get [hat] is 840 possible hat drops. That is, 840 * 4.3 ~ 3,612 hours (around 5 months). Q: How long will it take to have a 50% chance of having a hat? A: The formula I'm using to calculate the probability is 1 minus the probability of NOT having a hat, raised to the power of number of possible hat drops. So, if x is drops, the probability of having a hat after x drops is given by p(x) = 1 - (27/28)^x. You can plug in values and find out where p(x) ~ .5, or you can solve for the inverse function, and just plug in .5. For example: p(20) ~ .5 (after 20 possible hat drops, there is a 50% chance you have a hat) p(60) ~ .9 (after 60 possible hat drops, there is a 90% chance you have a hat) (For a few more, see http://forums.steampowered.com/forum...0&postcount=12) Q: How long will it take to get all the hats? A: I answered this one before, but I estimated using the average running time, and I really shouldn't have done that, because it's too rough with only 30 hats. So, properly calculated, this is equal to (30/1 + 30/2 + 30/3 + ... + 30/29 + 30/30) actual hat drops. That's about 120. So, after getting about 120 hats, you might expect to have at least one of each. But that's about 120 * 28 = 3360 possible hat drops, which is approximately 20 months of gametime. Q: True randomness is impossible to simulate with a computer, right? Every "random" computer program has an algorithm behind it. A: Well, try reading this: http://www.random.org/randomness/, especially concerning Pseudo-random number generators, versus True-random number generators. I'm not saying I think this is what Valve implements, but it is possible to simulate true randomness. Does anyone have any other questions? Does anyone have any corrections? Feel free to discuss. Last edited by jarstar : 09-29-2009 at 04:26 PM.

09-17-2009, 04:44 PM	#8
forceNet Join Date: Apr 2007 Reputation: 16 Posts: 1,259	Spoiler: these numbers are not correct anymore, unless valve lied about "significantly increaseing the chance of finding any of the existing hats" yes I somehow managed to accidentally delete my post

09-17-2009, 05:31 PM	#13
jarstar Join Date: Aug 2009 Reputation: 69 Posts: 271	This is for Veleron. Behind the scenes - What does expected value mean? The 'expected value' of a random variable is (colloquially) the average value one would expect by repeating the same experiment several times. For example, if I roll two dice over and over, and average all the values, I would probably get something like 7 (those who play Settlers of Catan already guessed this!). Mathematically, it's the integral of the random variable's probability density function, but you don't really need to understand that to understand expected value. The point is: it does not tell you exactly what number you will roll on a die, or exactly how long it will take to get the Vintage Tyrolean... just the average. Behind the scenes - How do you calculate probabilities? I made a brief pass at this in the original post. How do I find the probability that I have a hat, given 43 drops? Well, suppose in all of those 43 drops, you didn't get a hat every single time. Since the probability of getting no hat is 27/28 (and these hat rolls are independent events), we can multiply the probabilities and see that the probability of not getting a hat in 43 rolls is (27/28)^43. Now, since probabilities are out of 1, we can easily see that the probability of [getting at least one hat] is one minus the probability of [getting no hats at all] in x drops. So, we have our probability function y(x) = 1 - (27/28)^x. To invert this we solve for y: y = 1 - (27/28)^x 1 - y = (27/28)^x ln(1 - y) / ln(27/28) = x x(y) = ln(1-y)/ln(27/28) (I use ln() out of convention) Now, x(y) is a function that takes a probability, and returns the number of possible hat drops needed to obtain that probability. Behind the scenes - How long will it take to get all the hats? Keep in mind, we're finding the expected time to get all the hats, not necessarily the exact time (which is impossible to predict). To do this, we start with finding the expected time (in actual hat drops) to get one hat. We add to that the expected time to get a hat that ISN'T the first one, and from there we just iterate over the 30 hats. So, counting in actual hat drops, the expected time to get the first hat is... one drop. Now, on your next hat drop, there is a 29/30 chance that it will not be the same hat. I need to weave a little magic here, by saying that the probability of hats dropping has a geometric distribution, so the expected time to getting a different hat on your second hat is the reciprocal of 29/30, AKA 30/29. Like I said, we iterate from there: the expected time to get a third different hat is 30/28, and on down to 30/1. Then we just add it all up, and it's 119.84. Was there anything specific that you wanted to see, Veleron? Last edited by jarstar : 09-27-2009 at 11:41 AM.

09-18-2009, 01:46 AM	#15
bluenigma Join Date: Jul 2008 Reputation: 3 Posts: 125	The math checks out on my end. The expected time grows on the order of O(n log n), where n is # of hats, correct? I wonder, since we also have the variance bounded, could we make some assumptions and calculate the expected time to be 25%, 75%, 90%, and 95% likely to have all the hats? And for the "Why the hell not" kind of problem: what's the expected time to have 1 hat for every class? If there were an equal number of hats for every class, it'd be the coupon collector problem with n=9. But the hatless hats throws it into tricky territory. Ignoring the hatless issue, I get an estimate of around 128 days. Last edited by bluenigma : 09-18-2009 at 01:51 AM.

Thread Tools
Show Printable Version Email this Page
Display Modes	Rate This Thread
Linear Mode Switch to Hybrid Mode Switch to Threaded Mode	Rate This Thread:

09-17-2009, 04:24 PM	#2
TatersChoice Banned Join Date: Mar 2009 Reputation: 35 Posts: 653	I love you.

09-17-2009, 04:28 PM	#3
VeLeRoN Volunteer Moderator Join Date: Dec 2007 Reputation: 862 Posts: 7,692	Would be nice if you could add some more in-depth math explanation too.

09-17-2009, 04:32 PM	#4
Grim Tuesday Join Date: Jun 2009 Reputation: 39 Posts: 1,203	Good guide anyways...

09-17-2009, 04:35 PM	#5
Zephyrlot Join Date: Aug 2009 Reputation: 3 Posts: 15	My question is, is a possible hat drop accumulated game time, or would you have to play for 4+ hours straight just to get a single chance?

09-17-2009, 04:42 PM	#7
Abyss Join Date: Dec 2008 Reputation: 69 Posts: 768	The significant increase was from 1/84 to 1/28.

09-17-2009, 04:46 PM	#10
jarstar Join Date: Aug 2009 Reputation: 69 Posts: 271	Veleron, I wanted to keep it relatively brief for those who don't want the in-depth explanations, but I'll work on a write-up of some of the deeper workings.

09-17-2009, 06:02 PM	#14
habhead Join Date: May 2009 Reputation: 12 Posts: 175	What this means is that we will be seeing another Presidental election before even the idlers of average luck will have a hat for each of the classes.