I had a discussion with my friend regarding an old WOW quest from 2007...

Oh shit I forgot to multiply the 5 by 13 going from the first line to the second. I was wondering why everyone got such a big answer compared to me

The problem is overly complicated, the only important question seems to be: How many mobs does a player need to kill to get 20 scourge stones if we assume that 40% of all kills leads to a 1 stone drop.

If we assume 40% of all kills drop 1 stone, that means 20 stones is 50 kills.

Right? RIGHT?!

1636,36

How do you arrive at that number?

...

I don't get it. According to that equation, how many mobs need to be killed to get 20 scourge stones?

20/0.4 = 50

In the equation i just calculate how much rep each mob gives which is 5 rep for the kill, and then 25/20 (the value of the tokens) times the drop chance.

>50 mobs for 20 scourge stones.
So In that case. 50 mobs gives us 20 scourge stones which give us 1 token which in turn gives us 25 reputation
50/25 = 2
2 reps per mob plus the 5 rep kill-bonus gives us 7 rep per mob.
9000 / 7 = 1285 mobs.
Right?

Why are you dividing 50 with 25? You are doing its 2 mob per rep, not 2 rep per mob.

For 50 kills you can also put it like this (5*50+25) * x/50 = 9000, solve, x -> 1636

50 mobs / 25 rep = 2 mobs / rep
Not 2 rep / mob like you said.
Thus each mobs is 5 + 0.5

Oh shit you are right, I am retarded. It's 25/50 not the other way around. So each mob is 0.5 + 5. 9000 / 5.5 = 1636,363636363636

You guys are awesome. Thanks for enlightening me.

This problem can be modeled as the stochastic difference equation [math]x(k) = x(k - 1) + 5 + 1.25\ w(k)[/math] where [math]w[/math] is a Bernoulli process with p = 0.4 and [math]x(k)[/math] represents the amount of reputation after [math]k[/math] kills.

I don't know how to solve this, but I did write a little piece of code to show that you get to 9000 at around 1637 kills.

The answer is actually -1/12

Impressive, but way too advanced for me to grasp!

ignore the words and think about what the formula is saying

it's defining it recursively where the kth term is the (k-1)th term plus 5, plus 1.25 multiplied by some probability and some weight

What part? Did you ever learn Bernoulli trials? Probability has always been my weak point but I've always understood them.

Fixed it:
2 stones and 25 rep per 5 mobs
>times 13 to get the required stones for a token
26 stones and 325 rep per 65 mobs
350 rep and 1 stone per 65 mobs
>times 25 to get the required stones for a token
8750 rep and 25 stone per 1625 mobs
8775 rep per 1625 mobs
9000-8775=225 rep still needed
225/25=9 lots of 5 mobs=45 mobs
1670 mobs total will give you the required rep plus an additional 18 tokens.

I don't think you can just multiply 25*1/25 because you need to get a full 25 stones before trading it in for a token. You can't have fractional tokens, if that makes any sense.

If that's the case, then:
2 stones and 25 rep per 5 mobs
>times 10 to get the required stones for a token
20 stones and 250 rep per 50 mobs
275 rep per 50 mobs
>times 31 to get as close to 9000 rep as possible
8525 rep per 1550 mobs
9000-8525=475 rep still needed
475-275=200 rep still needed, 1600 mobs now
200/25=8 lots of 5 mobs=40 more mobs
Which means you need to kill 1640 mobs for the required rep plus an additional 16 stones.

Again, I don't think you can have fractional mobs or fractional tokens. This is the reason you guys have slightly lower numbers than me, because you took into account the "remainder" of stones I got at the end of the problem.

I'm . I assumed that 2 stones will come drop every 5 kills, but there's a nonzero chance that this won't happen. In fact after 5 kills, the chance of having 2 stones is 34.56% not 40% (found using the binomial distribution). Maybe this is why my answer is off from everyone else's. Is this what your Bernoulli process simulates?

This whole thing makes me think that the required number of mobs to get 9000 is actually a probability distribution. It's obvious that the maximum number of mobs you need is 9000/5=1800 (if none of them drop any stones). The minimum occurs when everyone drops a stone and is a bit harder to find:

5 rep and 1 stone per 1 mob
>times 20
100 rep and 20 stone per 20 mobs
125 rep per 20 mobs
9000/125=72 lots of 20 mobs=1440 mobs

I wonder what the shape of the distribution is. If it's a bell curve, symmetry would dictate that the average number of mobs needed to get 9000 is (1800+1440)/2=1620 mobs. But the fact that the probability of dropping is not 50% means it can't be a symmetric bell curve, that means that the chances of getting the maximum number is greater than our chances of getting the minimum number, boosting up the average closer to my our values of 1637 and 1640.

>In fact after 5 kills, the chance of having 2 stones is 34.56% not 40% (found using the binomial distribution).
Meant to say 100% instead of 40% but you get the idea.

>1670 mobs total will give you the required rep plus an additional 18 tokens.
Shit I meant 18 stones not 18 tokens haha so many mistakes today.

And to answer OP's original question, you're definitely wrong about the 1107 but you could both be right about the quest being a nasty grind or not. It's just a matter of chance, he could have gotten lucky and needed less mobs than you.

>I wonder what the shape of the distribution is
I'm interested in this as well.

If you think about it a plot of this process looks like a staircase where most of the steps are 5 inches in height but about 40% of them are 6.25 inches in height.

What this question is asking is after how many steps do these staircases tend to become 9000 inches tall.

It reminds me of this plot except the histogram is horizontal at the y = 9000 line and all the functions are going up and crashing into it.

Okay here it is for 1000 staircases. Looks normally distributed to me.

>I'm interested in this as well.
Is there any way to find out what the distribution would be without resorting to calculating every single situation? There have to be some shortcuts but I haven't been thinking about this hard enough to find anything practical.

>If you think about it a plot of this process looks like a staircase where most of the steps are 5 inches in height
I don't know about that. You can use the binomial distribution to find out the probability of a given number of steps being 5 inches tall (meaning that given number of mobs nothing got dropped) for any given total number of mobs. I did this for a few different percentage values (100%, 90%, 50%) for total mobs=1640 and got extremely low values for them all (I used binomial distribution). So either there is some specific percentage value where the probability spikes up, or maybe having a step height of exactly 5 is actually pretty uncommon.

>but about 40% of them are 6.25 inches in height.
As I said in my previous posts, you cannot have a fractional number of tokens or mobs (or rep), so you shouldn't be able to have a fractional step height either. You'd more likely have something like ~25% 6 inches and ~15% 7 inches but those percentages depend on the number of mobs needed, which will can span from 1440 to 1800. I think that with the number of mobs being this high, the percentage values for 6 and 7 inches would actually be much lower.

>It reminds me of this plot
What exactly is that a plot of? I think if I knew what information it's trying to portray I can more accurately understand how it relates to this problem.

I'm not quite sure it is normal. There seems to be 2 maximums here, or in other words two possible averages. Why did you choose 1000 as your number of staircases? Shouldn't the number of staircases be the total set of "paths" to get to 9000 rep? And wouldn't each staircase have it's own distinct probability of occurring? Maybe I'm just misunderstanding what you did but it seems oversimplified.

Let me explain my model. Since 7200 stones = 9000 rep through this convoluted exchange process that we don't want to concern ourselves with, we can approximate the value of one stone as 9000/7200 = 1.25 rep. This is a simplification that makes the situation easier to model. This is fine as long as we understand the consequences of the simplification, namely that our answer will be a little lower than the real answer since you might need to kill a few more mobs to reach the number of stones necessary for an exchange (you'd need at most 19 stones which would takes some number of mob kills that we can also find the probability of).

From here it's easy to see that the amount of reputation you get from killing a mob is going to be either 5 or 6.25, and that it will be the latter with 0.4 probability. So a plot of reputation with respect to number of kills made will be a series of jumps upwards of height 5 or 6.25. This is where that stochastic difference equation came from.

What I did in that figure is simulate 1000 processes whose evolutions were governed by this SDE until they reached [math]\ge[/math]9000, and then make a histogram of how many kills it took them. I didn't choose 1000 for any particular reason, that's just the sample size.

>Is there any way to find out what the distribution would be without resorting to calculating
Probably but I think it'd involve solving that SDE which I don't know how to do.

What exactly are you doing for the binomial thing?

25 tokens = 25 rep
25 stones = 1 rep per stone
1*0.4= 0.4 , which is average rep per mob
9000honor /0.4honor/mob= 22 500 mobs

25 stones = 1 token = 25 honor = 1 honor per stone, average. so 22 500 mobs on average, with a minimum of 9000 mobs and infinity upwards mobs, almost with exponentially less chance of more than 22 500.

problem is that mobs didn't give reputation after honored or revered, so you'd have to account for that
t. neckbeard

scratch that. i guess the goal of 9000 should make it clear that you'd want to go from neutral to honored

>Let me explain my model. Since 7200 stones = 9000 rep through this convoluted exchange process that we don't want to concern ourselves with, we can approximate the value of one stone as 9000/7200 = 1.25 rep.
Okay, this approximation seems valid because we know the consequences. The part I'm having a bit more of an issue with is:
>amount of reputation you get from killing a mob is going to be either 5 or 6.25, and that it will be the latter with 0.4 probability.
It only has a probability of .4 for a sample of n=1 mob. As the total number of mobs increases, the probability changes. For example, if you kill 100 mobs, then the number of stones you get is NOT .4*100=40. The probability of this happening can be found from the binomial distribution, and it happens to be only 8%. So basically as you go up to higher and higher steps, there will be more and more 5 inch steps.

For a total of n mobs, the probability of there being .4n stones dropped is [math] \frac{n!}{(.4n)!(.6n)!} (.4)^{.4n} (.6)^{.6n} [/math]
I just use .4n stones because that's the value that one would intuitively expect to drop without taking into account the binomial distribution. I think this is what you used when making your model, but I'm not an expert. In fact, this is the first time I've ever heard of SDE's, so you might have already taken this into account.

The difficult thing about this is that we are trying to find a probability for a given number of mobs needed, yet this depends on the number of stones dropped which in turn depends on (but at the same time affects) the total number of mobs. So lets say we want to find the probability it takes 1776 mobs. Then there is a non zero chance that the amount of stones dropped by this many mobs is enough to push the number of mobs down to 1775 or up to 1777. So this means when you are calculating the probability for 1777 mobs, you need to add in this extra term that came from the 1776 calculation.

>It only has a probability of .4 for a sample of n=1 mob
Yes. You are killing one mob at a time. Each time you kill one mob there is a 40% probability that it will drop a stone.

I think you are VERY confused about the binomial distribution. It's true that if X~Bin(100, 0.4), P(X = 40) is only 8%, but X = 40 is NOT the only situation we are interested in. You're essentially throwing out all of the stones you get in a batch of 100 mob kills if the number of stones you got isn't exactly 40.

>You're essentially throwing out all of the stones you get in a batch of 100 mob kills if the number of stones you got isn't exactly 40.
This is precisely what I'm trying to avoid, and I wasn't sure if your model did this or not. That's why I was asking about it.

But I think you are right about me being confused. If you look at my example in the previous post, if it took us 1776 mobs to get to 9000 rep, then that specific situation will come with a certain amount of stones. They are tied together, because a different amount of stones dropped would have resulted in a different number of mobs. Actually now that I think about it, each number of mobs would have a particular range of stones dropped. So the first step to creating the model is finding a way to associate the number of mobs with the amount of stones dropped. I did this using brute force for the min and max values, but it's much more complicated for the other values. If we use the approximation of 1 stone=1.25 rep, then the general formula for stones dropped in a situation with n mobs is (9000-5n)/1.25.

The next step in creating our model would be to use this number of stones along with the number of mobs in question n in the binomial distribution to find the probability that this situation occurs. So the general form would be:
[eqn] \frac{n!}{(n- \frac{9000-5n}{1.25})!( \frac{9000-5n}{1.25})!}(.4)^{ \frac{9000-5n}{1.25}}(.6)^{n- \frac{9000-5n}{1.25}} [/eqn]
I think this is equivalent to your SDE but I don't know enough about them to be sure. Now the real hard part is fixing that pesky 1 stone=1.25 rep approximation. I'll leave that for the morning.

If no stones are dropped, it takes 1800 mobs. But it would also take 1800 mobs if 19 or less stones are dropped. Then for 20 stones dropped, we get 25 rep, so we need 5 less mobs or 1795. So for 20-39 stones dropped, 1795 mobs are needed. This is interesting, it turns out the number of mobs needed to get to 9000 will always be a multiple of 5. I'm struggling to find a way to mathematically write this relationship though. I'm going to denote x as number of stones and n as number of mobs.

1440 mobs 1469-1440 stones
1445 mobs 1439-1420 stones
1450 mobs 1419-1400 stones
(n-1440)/5 will be our index i, starting at 0 and going to 72. Then the number of stones will be between 1469-20i and 1440-20i. So we have a formula for the range of x values for a given n. We can simplify these values by plugging in i and get 7229-4n and 7200-4n.

Now, for a given n, we need to sum the binomials over the possible x values in order to give the true probability of the event. This changes my formula in the last post to:
[eqn] \sum_ {x=7200-4n} ^{x=7229-4n} \frac{n!}{(n-x)!x!} (.4)^{x} (.6)^{n-x} [/eqn]
For [math] 1440 \leq n \leq 1800 [/math] and n=5k for some integers k. This should be the true solution to the OP, and it surprisingly looks neater than the approximation formula. The next step I guess is to graph this distribution, to see the shape and if it actually is normal. Any CS anons out there willing to whip up some code for this? Because I honestly have no idea how I'd go about it.

>The next step I guess is to graph this distribution, to see the shape and if it actually is normal. Any CS anons out there willing to whip up some code for this? Because I honestly have no idea how I'd go about it.
I would also be interested in seeing this!

I've been awake all night trying to learn enough matlab to make a simple bar graph of this but I fucking suck. For some reason I can't put variables into the lower bound of the summation and I'm way too tired to effectively create a for loop to fill the array I just keep ending up with syntax errors. If anyone figures this out I will be so fucking happy.

wrote some shitty matlab script for farming until you get 9000 rep 10000 times in a row and the average number of mobs it took was 1668.9, so that guy seems pretty close for 20 stones per token I get 1638.7, which is again pretty close to can't be bothered to run it more often, since 10k loops already take a minute and matlab sucks for for loops

Bro, get some rest. This is exciting, but not worth losing sleep over.

>I don't think you can just multiply 25*1/25 because you need to get a full 25 stones before trading it in for a token. You can't have fractional tokens, if that makes any sense.
Saying you need 25 stone/token is mathematically exactly the same as 1/25 token/stone.

Welp, I must admit that I do not understand your derivation but plugging in everything exactly as you've laid out gives pic related.

n is between 1440 and 1800 increasing in steps of 5. It does seem to give something reasonable as a mean but I'd hesitate to call it a probability distribution though since the sum over the prescribed values is greater than 1.

Working a little more I came up with an improvement for that seems to validate your model.

[math]
\texttt{rep[kills_] := 5 kills + 25 Quotient[stones[kills], 20]} \\
\texttt{stones[kills_] := RandomVariate[BinomialDistribution[kills, 0.4]]}
[/math]

This ensures that stones only count towards reputation in the proper manner, i.e. that groups of 20 stones gives you 25 reputation, and stones beyond this but less than another group of 20 do nothing.

Doing some simulations gave this. As you can see the reputation takes on discrete values in such a way that only multiples of 5 kills gives 9000 reputation, as you predicted. The number of kills that maximizes the 9000 bar is 1640 which is consistent with (though I still can't say why the total isn't 1).

In the end this is only a couple of kills off of what the simplified models predicted, but it did give more interesting results.

Thank you so much that looks beautiful.
>I'd hesitate to call it a probability distribution though since the sum over the prescribed values is greater than 1.
Then maybe using the binomial distribution is not the correct route to use. Binomial should only be used when there are two possible outcomes (success or failure), here there are (1800-1440)/5 different outcomes (one for each number of mobs). But then again, when invoking the binomial distribution we only did it for one particular number of mobs at a time then took the sum, so there shouldn't be an issue. I wonder if you just divide the whole thing by 1.36364 to normalize it would it result in the correct probability.

Doing this for the most interesting values (I'm estimating the probability of each based on your plot):
>1640 mobs
p=.55, renormalized p=.40
>1635 mobs
p=.35, renormalized p=.26
>1645 mobs
p=.31, renormalized p=.23
>1630 mobs
p=.08, renormalized p=.06
>1650 mobs
p=.06, renormalized p=.04

This also looks pretty good, and it's pretty consistent with the renormalized values I calculated above:
>1640 mobs
p=.38
>1635 mobs
p=.32
>1645 mobs
p=.14
>1630 mobs
p=.07
>1650 mobs
p=.02
It seems like my model correctly approximates the probabilities for the average and for the end behavior, but fails in between. My function appears to overshoot your values to the right of the mean and undershoot your values to the left, meaning the graph is slightly skewed. Maybe this information can help pinpoint the problem.

and by "pinpoint the problem" I mean find a function we can divide by to correctly normalize it. Maybe the problem came in this step:
>1440 mobs 1469-1440 stones
I only did this because I was looking for a pattern to find a non approximate relationship between x and n, but looking at it I realize that for 1440 mobs, it's impossible to have greater than 1440 stones. The function is actually a bit more specific:
[eqn](.4)^{1440} , n=1440[/eqn]
[eqn] \sum_{x=7200-4n}^{x=7229-4n} \frac{n!}{(n-x)!x!} (.4)^x (.6)^{n-x} ,1440

This thread is a prime example why Veeky Forums is one of the best boards on Veeky Forums.

Correction: The best board on Veeky Forums.