Diablo® III

A Bayesian statistical analysis of key drops

90 Worgen Druid
3265
Posts: 172
TLDR:

If you play n games, and find k keys, and assume that you don't believe Blizzard's claims about drop rates, the Bayesian estimate of the drop rate is:

(1+k)/(2+n)

Beyond that, I also show how to calculate the probability that the drop rate is or is not within a particular range (i.e whats the chance the rate actually is between 0.2 and 0.4 as Blizzard claims for mp 3, given what you have observed).

Estimating key drop rates is a text-book example of Bayesian statistics in what is called the "Beta-Binomial" model.

---------------

In this post, I discuss the statistics of estimating key drop rates. This seems like a subject of interest to the players of diablo 3, so hopefully this post can help to clarify the discussion. I am a graduate student in computer science/statistics.

We will assume a player sets mp 3 (for example), then collects 5 stacks of NV, and kills the key warden, then records whether a key dropped or not. We will repeat this process over multiple games. First, note that the outcome from each game is independent of every other games (what happens in one game doesn't depend on what happened in any other games).

Let us define some random variables and parameters:

n = the number of games played (a known constant)
k = the number of keys found out of n games (a random variable, which we observe through the experiment)
p = the probability of a key dropping (an unknown parameter that we are trying to estimate)

An appropriate statistical model for this experiment is to say that

k ~ Binomial(n, p)

In words, the distribution of k is binomial with parameters n and p. For more info on a Binomial distribution, check out Wikipedia.

A simple way of estimating p which most people will find intuitive is to use a maximum likelihood estimator. That means we will predict the value p that gives the highest probability to the data we observe. The maximum likelihood estimator for a binomial distribution is

p_MLE = k / n

Its pretty simple; count the number of keys found and divide by the number of games- that is the frequentist/maximum likelihood estimate of the key drop rate.

Maximum likelihood is not the only way to estimate parameters. Another approach is to use Bayesian statistics. The advantage is it better accounts for issues like (1) estimation based on a small number of game, (2) incorporation of prior knowledge or belief about key drop rate, and (3) it gives a range of probable values rather than a single most probable value for the drop rate. So without further ado, lets get into the Bayesian analysis of key drop rates.

In Bayesian statistics, we typically associate a prior distribution with unknown parameters that represents our belief before running the experiment. In this case, an appropriate prior is:

p ~ Uniform(0,1)

This prior represents the belief that any value of p in the range (0,1) is equally likely before running the experiment (in other words, we don't believe Blizzard's claim that p = mp/10). If we wanted to do an analysis where we instead assume Blizzard is probably telling the truth, we might assume instead that

p ~ Normal(mean=mp/10, stddev=0.1)

This kind of prior roughly expresses the belief that the true drop rate is within +/- 0.1 of what they claim.

Generally speaking, it makes our calculations simpler if we assume that

p ~ Beta(a,b)

and note that when a = b = 1, the Beta(a,b) distribution is the same as the Uniform(0,1) distribution. So we will assume p~Beta(a=1,b=1).

Ok so lets take a step back- again we are going to play n games and we will observe that we collected k keys. Now we will see what Bayesian statistics has to say about the key drop rate p.

According to Bayes theorem and some well known calculations (see "Beta-Binomial Conjugate Prior"), the posterior distribution of p given k is:

p | k ~ Beta(1 + k, 1 + n - k)

To make this a bit more concrete, lets say I play 6 games and find 0 keys. Then k = 0, n = 6, and p | k ~ Beta(1, 7). Take a look at some analysis of this distribution through Wolfram Alpha: http://www.wolframalpha.com/input/?i=beta+distribution%2C+alpha%3D1%2C+beta%3D7

If you look at the "Plot of PDF" that is showing on the x-axis, a hypothetical key drop rate, and on the y-axis, the probability at that key rate (note the rate is a continuous parameter, so the probability of any particular value is 0; it is only meaningful to talk about the probability that it falls within a particular range, which is equal to the area under this plot through this range; that is why it is OK to have a number greater than 1 on the y-axis of this graph).

There is more relevant information on this page. For example, the mean is listed at 1/8 = 0.125. The mean refers to the mean of the posterior distribution, which is a beta distribution. For any beta distribution Beta(a, b), the mean is a/(a+b), therefore:

Suppose you play n games and find k keys. Then the Bayesian posterior estimate of the key drop rate (assuming a uniform prior) is:

p_posterior_mean = (1+k)/(2+n) (TLDR: this is the estimated key drop rate in a Bayesian analysis assuming a uniform prior)

Lets rage an example:
k = 0, n = 6 ----> p_posterior_mean = 1/8

Notice that is the same result we got on Wolfram Alpha. It is also worth comparing our estimate of the key rate using Bayesian statistics to the simpler maximum likelihood estimator. Recall

p_MLE = k/n

Notice that for large values of k and n, the +1 and +2 terms in p_posterior_mean are dominated by k and n. This means if you run enough repetitions, you will end up with very similar results in either analysis. Also note that if n = 0 and k = 0 (i.e. we haven't played a game yet), then p_posterior_mean = 1/2. This is a consequence of our assumed prior p~Uniform(0,1) - it is like saying that before we see any results, we believe the drop rate is 50-50.

Wrapping up, lets do one more analysis: what is the probability that Blizzard is stating the wrong values for key drop rates? Go back to the Wolfram Alpha page and look at the "Probability density function" panel. For our example here, it says:

7(1-x)^6 if 0<x<1

Note that x is actually p. Suppose we want to know the probability that the true key drop rate is between 0.2 and 0.4, given the observation of 0 keys in 6 games. You can compute this probability with Wolfram Alpha by entering

integral(7(1-p)^6, 0.2, 0.4)

The result is 0.181722. Thus given these observations, the posterior probability is 0.818278 that the key drop rate is NOT between 0.2 and 0.4.

Note that n = 6, k = 0, at mp3 (on act 3 not that it should matter) is my observation over the last couple of days. This is a very small sample and certainly not enough to draw a strong conclusion. However, I hope this analysis will be helpful to others on this form as we continue to asses key drop rates. I invite others to check my analysis and run through the calculations with their own numbers. If I have made a statistical mistake, feel free to point it out. Also, if anyone is feeling really savvy, it would be reasonable to do this calculation with a prior that this more generous to Blizzard than uniform.
Edited by Afar#1572 on 12/10/2012 7:15 PM PST
Reply Quote
Posts: 1,691
>('_')<

That's my brain exploding...
Reply Quote
Posts: 2,588
View profile
tldr
Reply Quote
I was so close to writing something like this up on Bayesian anaylsis a few weeks ago but realised it was going to take way too long.... cudos to you for getting in there and doing it.

I think the really interesting part of the whole thing is being able to give a number for the probability that the key drops are not as specified. This is what you have done right at the bottom of your post but I think it should have been the focus.

I think that whilst your post is awesome, it probably has too much detail for most people. I would ask for someone to let you know how many keys they have found in how many runs and then you can test the assumption that the key rate is as Blizzard has said and give a probability on the key rate not being as stated.

I think a lot of people would be interested in that :)
Reply Quote
It's like econtalk in here.

I like your theory, but as you said:

"This is a very small sample and certainly not enough to draw a strong conclusion."
Reply Quote
90 Worgen Druid
3265
Posts: 172
If people are willing, please post your own observations, i.e.:

n - the number of games you played
k - the number of keys you found
mp - the monster power level you played at

Assuming everyone is honest, we can add up all the results at the same mp and get a more significant sample. Also remember it only counts if you have 5 stacks of NV.
Edited by Afar#1572 on 12/10/2012 7:19 PM PST
Reply Quote
tldr but why would you set a uniform prior when haters think they have a lower than stated chance?

also, if you think "binomial" is a reasonable model, then you can straight up use it and estimate your parameter p.

bayesian analysis is useful in many cases, but this is not one of them.
Reply Quote
90 Worgen Druid
3265
Posts: 172
12/10/2012 07:25 PMPosted by haushinka
tldr but why would you set a uniform prior when haters think they have a lower than stated chance?


I used a uniform prior because it makes the calculations easy, however you could easily replace the Beta(1,1) prior with a different Beta(a,b) distribution which expresses either more or less belief in Blizzard's claims. Its a little bit tricky but suppose you want to express the believe that the true drop rate is d. Then using the known expectation of the Beta distribution, you must set a and b such that d = a / (a+b). That is 1 equation and 2 unknowns. You can get another equation to solve for appropriate values of a and b by assuming something about the variance (i.e. lots of variance = you don't trust them much, less variance = you trust them a lot).

12/10/2012 07:25 PMPosted by haushinka
also, if you think "binomial" is a reasonable model, then you can straight up use it and estimate your parameter p.


There is absolutely no subjectivity in the choice of the binomial model. The binomial model is an accurate representation of this experiment with no oversimplification or approximation whatsoever. The reason is that in each game, you either get a key or not. You could say that for one game, you get either 0 or one keys. In this case let k_i = the number of keys you get. Then k_i ~ Bernoulli(p) (the Bernoulli distribution just says you get k=1 with probability p and k=0 with probability 1-p; therefore the Bernoulli distribution exactly describes the outcome of 1 game). Repeating this experiment n times, and adding up the results, we have the the total number of keys found is k = sum from i = 1 to n of k_i. In this case, it can be proven that the distribution of k is Binomial(n,p).

TLDR: I don't just think binomial is a reasonable model. It is the correct model.

Also, I think what you mean by "you can straight up use it and estimate your parameter p" is that you can estimate p_MLE = k / n using frequentist statistics. I explained that is another way of estimating the parameter, but that the Bayesian way has advantages.

12/10/2012 07:25 PMPosted by haushinka
bayesian analysis is useful in many cases, but this is not one of them.


Actually, Bayesian analysis does something in this case that frequentist analysis cannot. It allows us to give a probability that the rate is or is not within +/- 0.1 of what Blizzard claims.
Reply Quote
why not run a Hypothesis test?

like

Z= (P - Po) / (Po(1-Po) / n) ^ .5
.5 five is a power
P is the sample proportion and Po is one Blizzard claims
n = number of runs
you will need a Z table

kinda hard to write these in Type
and if what you say is true i hope you know what a Hypothesis Test is
learned that in my first Business Statistics class

either the drop rate Blizzard claims is correct or it is not
you may need to make like 100 runs to decrease error
Edited by Mike276#1423 on 12/10/2012 8:18 PM PST
Reply Quote
Posted by haushinka
bayesian analysis is useful in many cases, but this is not one of them.

Actually, Bayesian analysis does something in this case that frequentist analysis cannot. It allows us to give a probability that the rate is or is not within +/- 0.1 of what Blizzard claims.


so you introduced a framework that defines probability differently so that you can talk about new probabilities derived from the framework. brilliant.
Reply Quote
The Central Limit Theorem proves this to be......

...oh binomial distribution....
Reply Quote
Posted by haushinka
bayesian analysis is useful in many cases, but this is not one of them.

Actually, Bayesian analysis does something in this case that frequentist analysis cannot. It allows us to give a probability that the rate is or is not within +/- 0.1 of what Blizzard claims.


so you introduced a framework that defines probability differently so that you can talk about new probabilities derived from the framework. brilliant.


It's called a random variable. It's not invented. Pick up a stat book.
Reply Quote
I have to agree with haushinka 100%. This is nothing more than an elegantly written statistical application that chooses an unnecessarily complicated means to NOT solve the problem.

The footing of your analysis rests on a constant drop rate, p. I don't find that believable enough to shoehorn it into a formula to prove whether or not Blizzard has misled you.

It seems a lot more believable to fit the data to a pdf assuming a Rayleigh distribution where the end result is that the user gets a key at a mean = 10/mp games.
Reply Quote
90 Worgen Druid
3265
Posts: 172
12/10/2012 08:17 PMPosted by Troutsabre
I have to agree with haushinka 100%. This is nothing more than an elegantly written statistical application that chooses an unnecessarily complicated means to NOT solve the problem.


Here's the problem I'm trying to solve. I keep seeing posts where people say something like this:

I did 8 runs at mp 5 and got 0 keys. The probability of that happening is .5^8 = 0.00390625. Therefore Blizzard must be lying about drop rates.

I am not saying I think Blizzard is incorrect for sure- I don't have enough data to make such a claim yet. I am saying people should stop making the analysis above and start using a more meaningful analysis such as the one I explained. With enough data, we could come to Blizzard and say something more rigorous such as: based on n = 1000 games, we conclude there is a 99% chance that drop rates are not as stated. Or maybe we do n=1000 games and conclude there is a 99% chance that drop rates are within 1% of what they claim. Thats the kind of result you can get with the Bayesian analysis I described. You can't get that same result with frequentist analysis.

12/10/2012 07:53 PMPosted by Mike276
why not run a Hypothesis test?


That is a totally reasonable idea too. Most likely the results would be very similar to the Bayesian analysis. Similarly, you could use a confidence interval along side the ML estimation approach. However, most people don't know enough about frequentist hypothesis testing to understand the result. It has been said that Bayesian statistics is harder to do the calculation, but easier to understand the result. Consider these three statements:

(a) Based on n = 1000 games, there is 99% probability that the key drop rate is between .2 and .4 [Bayesian]
(b) Based on n = 1000 games, the mean key drop rate is .3 with a 95% confidence interval of (.2, .4) [Frequentist]
(c) Based on n = 1000 games, we reject the null hypothesis that the key drop rate is .3 at a significance level of p = 0.05 [Frequentist]

In my personal opinion, (a) is the simplest statement to understand as it involves the least jargon (and those jargon terms are not as simply defined as some people think). For example, statement (b) is not equivalent to statement (a).


It seems a lot more believable to fit the data to a pdf assuming a Rayleigh distribution where the end result is that the user gets a key at a mean = 10/mp games.


I think a forum moderator stated that results are independent between games. Therefore the Binomial model is the correct one, not a Rayleigh distribution. If it really is as you suggest a Rayleigh distribution, that would essentially mean RNG is not RNG in the sense that most people think it is.
Edited by Afar#1572 on 12/10/2012 9:23 PM PST
Reply Quote
Dogcat,

I believe you're on the right track with this however I believe Blizzard is using a slight variation on this and has more parameters but I like what you've posted thus far. Keep it up!
Reply Quote
I did 8 runs at mp 5 and got 0 keys. The probability of that happening is .5^8 = 0.00390625. Therefore Blizzard must be lying about drop rates. True or false?


I take a different approach in answering this question without doing any empirical data collection. Try to think about this question in different way: What is the probability that I do 8 consecutive runs at mp5 but got 0 keys at least 1 time in my entire d3 career? Let's say I farm the same key 100 times and my friend farm the same key 500 times in our entire 3d career, what is our probability to encounter such a losing streak?

No doubt this can be answered with binomial distribution and you can do the calculation manually or with excel. If you want to do it with excel here is my formula:


1 - binomdist(0, x - y + 1, z^y, false)

where,
x = number of total runs
y = number of consecutive run with 0 key.
z = probability of getting 0 key in a single run.



So in this case, x = 100, y = 8, z = 0.5, therefore

1 - binomdist(0, 100 - 8 + 1, 0.5^8, false) = 30.5%

So for my friend who do the key 500 times, his chance of getting at least 1 time of bad luck is

1 - binomdist(0, 500 - 8 + 1, 0.5^8, false) = 85.5%

So judging from the results, I could conclude that sooner or later you could be one of the poor souls as long as you still farming keys at mp5.

Now let's see what is my chance of becoming such a poor soul if i farm keys on mp7.

So in this new scenario, x = 100, y = 8, z = 0.3, therefore

1 - binomdist(0, 100 - 8 + 1, 0.3^8, false) = 0.6%

if x = 500, then 1 - binomdist(0, 500 - 8 + 1, 0.3^8, false) = 3.2%

Now you know exactly why you shouldnt farm keys below mp7. Blizzard doesnt need to fool you, math will do it on their behalf.
Edited by Sephiroth#6628 on 12/11/2012 1:21 AM PST
Reply Quote
12/10/2012 09:21 PMPosted by Dogcat
I am not saying I think Blizzard is incorrect for sure- I don't have enough data to make such a claim yet. I am saying people should stop making the analysis above and start using a more meaningful analysis such as the one I explained. With enough data, we could come to Blizzard and say something more rigorous such as: based on n = 1000 games, we conclude there is a 99% chance that drop rates are not as stated. Or maybe we do n=1000 games and conclude there is a 99% chance that drop rates are within 1% of what they claim. Thats the kind of result you can get with the Bayesian analysis I described.


Just make sure that you are using a truly RANDOM sample of games(ie deciding beforehand that you will have a group of people do 1000 runs and report the results regardless of what they are) and not simply taking all the posts you see with people saying "I did n runs and didn't get a key." and adding them up.

The problem with all of these types of posts is the only ones complaining on here about it will be the ones who DID have an unusual run of bad luck, while the ones who got about the expected number of keys or even the ones who got drops on 5 MP1 runs in a row probably won't say anything most of the time. And of course, given the number of people playing the game, it's entirely reasonable that a few of them WILL have very long runs of bad luck.
Reply Quote

Please report any Code of Conduct violations, including:

Threats of violence. We take these seriously and will alert the proper authorities.

Posts containing personal information about other players. This includes physical addresses, e-mail addresses, phone numbers, and inappropriate photos and/or videos.

Harassing or discriminatory language. This will not be tolerated.

Forums Code of Conduct

Report Post # written by

Reason
Explain (256 characters max)

Reported!

[Close]