By Cal Henderson, March 4th 2010.
One of the hardest bosses to fight is the RNG, or Random Number Generator. While the tactics are fairly straight forward (try, try, try again), defeating this boss can take a lot of patience. Lots of players don't understand quite how this boss fight works, so i'll attempt to explain.
A few months back, I created a World of Warcraft addon called BunnyHunter, to help you track your progress when farming for rare pets.
The rarest pet of all is the Hyacinth Macaw which drops from Bloodsail Pirates off the south coast of Stranglethorn Vale. Each pirate has a 1 in 10,000 chance of dropping this rare pet. I built the addon especially to help me in my quest to find the macaw.
Quite a few people have misunderstood how BunnyHunter calculates its percentage score. For instance, a BunnyHunter user posted this message to one of my favorite WoW blogs:
1. The app lets you know that there is a 1/1000 chance of an Azure Whelp dropping per kill when you are farming specific mobs in Aszhara.
2. The app lets you track "progress" toward getting a better chance of your drop because it lets you know how many whelp carriers you have killed. If you kill 150 mobs, it lets you know you have approximately a 15% chance "so far" of getting the whelp.
3. It has a tracking bar that shows you your progress - so after 1000 kills, you have a 100% chance so far of getting your drop.
This shows a real fallacy in the RNG analysis which is that successive kills actually increase your chance of getting a rare drop. Despite the multiple attempts, you have the same chance of getting the drop on your first kill as you do on your 999th kill which is 1/1000.
Of course, BunnyHunter doesn't work this way at all. This is an all-too-common misconception, however. The thing which governs this is called Probabilistic Independence - the fact that whether one mob dropped the loot or not, this has no bearing on whether a second mob will drop the loot. By extension, having looted 1000 consecutive mobs which did not drop the loot has no effect on the next mob you loot. If the drop chance is 1 in 100, there will still be a 1 in 100 chance that the next mob you loot will drop the item.
But if you use BunnyHunter and loot 1000 mobs that drop the Azure Whelp, it wont say 100%; it'll say 63.2%. The reason we can come up with any number at all, is because we can derive the probability that a piece of loot will drop at least once in a given sequence of lootings.
Say that we have 3 mobs and each has a 50% chance to drop the thing we're looking for. There's an 87.5% chance we'll get the item (7/8ths) after looting all 3. To see why, we'll construct all of the possible outcomes, which are all equally likely (we're cheating by using a 50% drop chance, to make the example easier):
first mob / second mob / third mob 1) no drop / no drop / no drop 2) no drop / no drop / drop 3) no drop / drop / no drop 4) no drop / drop / drop 5) drop / no drop / no drop 6) drop / no drop / drop 7) drop / drop / no drop 8) drop / drop / drop
In only one of these 8 possible outcomes did we fail to get the item, so the chance we'll get it is 7/8 = 87.5%. The trick here is that we care about the chance to have gotten the drop one or more times, from 3 mobs. Another way to look at it is that the chance of getting the drop is 100% minus the chance of none of the 3 mobs dropping it.
This last part is the important bit. The chance of having gotten the Azure Whelp after 1000 loots is the same as one minus the chance to have not seen it. We can calculate the chance to have not gotten it, 1000 times in a row, by taking the chance to not get it once (1 - 0.001 = 0.999) and multiplying it by itself 1000 times (for the 1000 mobs we looted). This gives us a 36.8% chance of not seeing it drop once, so the inverse is that there's a 63.2% chance (100 - 36.8) that we will have seen it drop. Easy!
The generalized formula is:
chance to have dropped at least once = 1 - ((1 - per-loot drop chance) ^ loots)
That little symbol is the power operation.
BunnyHunter uses this formula to give you a percentage score of how likely you are to have gotten the drop so far. It won't tell you when that drop will happen - it could be the next mob or 1000 mobs from now - but it will tell you how (un)lucky you have been.
Not all drop rates in World of Warcraft actually exhibit probabilistic independence. Since WotLK, quest item drops actually use a progressive drop rate. This is to avoid the situation where you grind and grind but are the unlucky person who kills 50 mobs and doesn't get a single quest item.
Blizzard probably did this for two reasons. Firstly, unlike vanity drops (such as the mythical macaw), you get stuck if you can't get the item. This is bad game design, since you need the items to continue the quest. Secondly, and probably more importantly, is that until you start getting drops you are not sure you're doing the right thing. Having a quest item only drop after 50 loots gives you 49 chances to think you're doing the wrong thing and give up.
But we're farming pets here, so it doesn't apply to us!
The problem with probability calculations is that not only are they confusing, but people often use the wrong calculation and then stand behind their results. Rather than try and convince you with math, I'll use good old brute force.
I created a simple PHP script which runs a number of 'drop trials', which simulate looting mobs in WoW. The script 'loots' a mob by creating a random number between 1 and the inverted drop chance - for the Hyacinth Macaw, this is 1 in 10,000, so the script will generate a random number between 1 and 10,000 (inclusive). If the random number is 10,000, then we count it as a drop - the mob dropped our parrot. If the number is anything else, we count it as the mob dropping something else (or nothing at all). In this case, we roll another number and start over. We keep rolling numbers until we get a drop, and then we note down how many times we rolled a random number. This is how many loots it took to get our drop. So far, simple.
Because computers are nice and fast, we'll take this trial and perform it 10,000 times, noting down each time how many loots it took before we saw a drop. This will give us a big picture of how many loots it generally takes to get our drop. So let's run the script!
World of dropcraft Drop chance is 1/10000, running 10000 trials .................................................................................................... Mean loots per drop: 9958.6041 Median loots per drop: 6888 Luckiest loots: 2 Unluckiest loots: 106335
After running 10,000 trials (it takes about 30 seconds on my PC), we're left with a list of 10,000 numbers - each of them how many loots it took on that trial to find our item. So, some analysis!
We can take the biggest and the smallest numbers and call them the luckiest and the unluckiest. Of our 10,000 trials (the equivalent of farming 10,000 Hyacinth Macaws in the game, and noting down how many loots it took you each time), the quickest we ever saw the item drop was after 2 loots. Wow! I'd be pretty damn happy if that happened to me in game. I'd be very very lucky. At the other end of the scale, one of the trials took 106,335 loots (over one hundred thousand!) before they got the drop. That would really suck. At my farming speed, that would take almost 2 solid weeks of farming.
We can see the average (mean) loots taken, by adding together all of the numbers and dividing them by the number of trials. When we do this, we get 9958.6, which is pretty close to 10,000. We would expect this, since the drop rate is 1 in 10,000. If we ran more trials, we would expect this number to get closer to 10,000 (this is called convergence).
We can also calculate the median, which is the number of loots at which 50% of players would have gotten the drop. This is different to the mean, but can be a little confusing, so I'll explain with an example.
Say you had a drop that was very common - most people got it on the first loot. If 9 players got it after the first loot, but 1 poor player took 10 loots, the average would be 1.9 ([1+1+1+1+1+1+1+1+1+10]/10). However, we can easily see that more the half of the players would have gotten the drop after the first loot. That's because the median is 1. We calculate the median by sorting the list into order and picking the middle value. The mode is another kind of similar average, but we'll ignore that here because it gets hard to calculate once we use big numbers and can be misleading.
So in this trial, the median is 6888. Why do 50% of trials get the drop after 6888 loots, while the average is 10,000? The answer lies in the way drops work. The fewest number of loots you can get a drop in is 1; you have to loot at least one corpse to get a drop. But the highest number of loots is infinite. You could loot one million pirates and never get the parrot. It's unlikely, but it's possible. So while there's a chance it will take one million loots, which throws off the mean, very few players will take this long, so the median stays lower.
So what is the median good for? Well, it can tell us at what point we go from being lucky to unlucky. Someone who is lucky gets the drop in less loots than the majority of other players. Someone who is unlucky gets the drop after more loots. While drop probabilities can't tell us when we will get a drop, they can tell us who unlucky we have been to not get it so far, or how lucky we would have to be to get it by a certain number of loots.
So how do we calculate the median? Let's run another 10,000 trials against my favorite pet, the Hyacinth Macaw.
World of dropcraft Drop chance is 1/10000, running 10000 trials .................................................................................................... Mean loots per drop: 10082.6048 Median loots per drop: 6996 Luckiest loots: 2 Unluckiest loots: 91637
So after 10,000 trial sequences, it took an average of 10,082 loots to get the item. If we ran a lot more trials, this number would approach 10,000 (since it's a 1 in 10,000 drop chance).
The median, however, is around 7000, as before. This is the number of loots at which 50% of trials had found the drop. If you took less than 7k, you were lucky. If you took more than 7k, you were unlucky. But where does this number come from?
Take our formula for drop chance in a sequence of n loots:
dropped_at_least_once_chance = 1 - ((1 - drop_chance) ^ loots)
We can rebalance this formula using logarithms into this:
loots = log(1 - dropped_at_least_once_chance) / log(1 - drop_chance)
If we plug in our numbers, 50% chance to have dropped at least once and a 1/10,000 drop chance, we get 6931, which is pretty close to the 6888 and 6996 results we saw in our tests.
We can confirm this by using higher drop rates, since the trials will converge faster. Using the formula, we can make the following predictions:
1/100 -> 50% after 69 loots 1/1000 -> 50% after 692 lootsSo let's run the trials again with these drop rates and see what we get...
World of dropcraft Drop chance is 1/1000, running 10000 trials .................................................................................................... Mean loots per drop: 994.0178 Median loots per drop: 689 Luckiest loots: 1 Unluckiest loots: 11067
World of dropcraft Drop chance is 1/100, running 10000 trials .................................................................................................... Mean loots per drop: 100.116 Median loots per drop: 70 Luckiest loots: 1 Unluckiest loots: 915
Yup, that pretty much seals it. If you take less than 6931 loots to get the Hyacinth Macaw, you're lucky. If you took more than 6931 loots, you're unlucky. If you took exactly 6931 loots, well, you're Mr Average.
So, earlier I said that the mode is an odd measure of 'averageness' for drop chances, but it can be used to point out something pretty strange. We can use some simple math to calculate the probability that a drop will happen on a given loot. We'll generalize a little here - let's say that p is the chance to drop the loot we want.
drops on 1st loot = p drops on 2nd loot = p * (1-p) drops on 3rd loot = p * (1-p) * (1-p) drops on 4th loot = p * (1-p) * (1-p) * (1-p)
A strange thing happens when we plug in the numbers. Let's use the good old macaw's 1/10000 drop rate.
drops on 1st loot = 0.0001 = 0.00010000 drops on 2nd loot = 0.0001 * 0.9999 = 0.00009999 drops on 3rd loot = 0.0001 * 0.9999 * 0.9999 = 0.00009998 drops on 4th loot = 0.0001 * 0.9999 * 0.9999 * 0.9999 = 0.00009997
Yes, that's right - the chance goes down over time. Remember, this is not the chance that we will have gotten the drop by now (the cumulative chance), but the chance we'll get it exactly now. This means that the loot in which you are the most likely to see a drop, regardless of the drop chance, is always the first loot. More people will get the macaw on their first loot than on their second. The mode is always 1. Yeah, that's weird.
Loot drops are a form of binomial distribution, inverted with a k of zero.
So we know that 50% of players will have gotten the Hyacinth Macaw after looting 6931 mobs, and the average number of loots is 10,000.
BunnyHunter tells me how long I've spent farming a particular mob. It does this by noting down each time I loot the relevant kind of mob. If the time between loots was less than a limit (5 minutes), then the time between them is added to my total time. If the time between them was greater than this limit, by total is left as-is. This means that it measures the time spent running between mobs and fighting, but not the 10 minute break I took to get coffee or check the auction house. There's a little bit of under estimation, since it doesn't include the time spent to find and kill the first mob in each "session", but so long as you farm a few mobs at a time and not one every now and then it's fairly accurate.
After I killed my 3600th pirate, I saw that my timer just ticked off 11 hours. Wow. I'm wasting my life. However, this also tells me that I loot roughly 327 mobs for every hour I spend farming (3600 / 11). I can use this to calculate how long it should take me on average to get the macaw and after how much farming I'll start to be unlucky for not having seen it.
3600 loots / 11hrs = 327 loots/hr median 6931 loots -> 21.2 hrs mean 10,000 loots -> 30.6 hrs
Ok, so I probably have quite a bit of farming ahead of me.
I might be a bit of a math nerd, but I make mistakes too. If you spot any glaring mistakes or omissions, drop me an email and teach me: cal [at] iamcal.com
BunnyHunter can be downloaded here, or installed through the Curse Client.
The source code for World of Dropcraft can be found here.
Copyright © 2010 Cal Henderson.
The text of this article is all rights reserved. No part of these publications shall be reproduced, stored in a retrieval system, or transmitted by any means - electronic, mechanical, photocopying, recording or otherwise - without written permission from the publisher, except for the inclusion of brief quotations in a review or academic work.
All source code in this article is licensed under a Creative Commons Attribution-ShareAlike 3.0 License. That means you can copy it and use it (even commerically), but you can't sell it and you must use attribution.