Noah
2009-03-22, 06:45 AM
Have you ever wondered how a computer creates random numbers? Are you interested in finding out whether a lot of dark scrolls or white scrolls is the way to go in order to earn the most money? Or maybe you're just interested in mathematics, probability and combinatorics.
If any of these applies to you, I'd like to welcome you to my little document. In this document, I will be discussing and explaining the following:
How random numbers are created inside a computer, and how MapleStory works with these numbers in order to simulate random events.
How you find the probability of certain scroll-events, such as the probability of working 4 scrolls out of 7, or the probability of working 6 scrolls in a row if you have a limited amount of scrolls
What is the most efficient in terms of earning/saving money? Dark scrolls, or white scrolls?
I am Noah, a person who is interested in mathematics, especially probability and number theory. Through studies from both university and own will, I have found quite a lot of interesting facts about maths, and I would like to share some of it with you. Please keep in mind that this document will require knowledge or interest in mathematics in order to understand everything.
Table of Contents:
Random Number Theory
§1 - Completely Random Events (http://www.southperry.net/forums/showthread.php?p=170677#§1)
§2 - Completely Random vs. Random (http://www.southperry.net/forums/showthread.php?p=170677#§2)
Binomial Probability
§3 - Basic Binomial Probability (http://www.southperry.net/forums/showthread.php?p=170677#§3)
§4 - Scrolls in a Row (http://www.southperry.net/forums/showthread.php?p=170677#§4)
§5 - General Formula - Scroll percentages (http://www.southperry.net/forums/showthread.php?p=170677#§5)
§6 - Dark scrolls and Scroll Percentages (http://www.southperry.net/forums/showthread.php?p=170677#§6)
§7 - Scrolls in a Row - Expectation Value (http://www.southperry.net/forums/showthread.php?p=170677#§7)
§8 - Scrolls in a Row - Probability (http://www.southperry.net/forums/showthread.php?p=170677#§8)
§9 - Dark Scrolls vs. White Scrolls (http://www.southperry.net/forums/showthread.php?p=170677#§9)
Appendices
Appendix A - Binomial Statistic (http://www.southperry.net/forums/showthread.php?p=170677#ApA)
Appendix B - Scroll-Probabilities (http://www.southperry.net/forums/showthread.php?p=170677#ApB)
Other
Notes (http://www.southperry.net/forums/showthread.php?p=170677#Notes)
To-do List - Changes (http://www.southperry.net/forums/showthread.php?p=170677#To-do)
Credits (http://www.southperry.net/forums/showthread.php?p=170677#Credits)
§1 - Completely Random Events
In our real world today, no events apart from events within quantum physics are completely random. We assume the servers MapleStory uses aren't "quantum-servers", because most computers doesn't have this possibility as of right now. Thus, we have to accept that the probabilities and events, such as a working scroll or a dropping drop from a monster, is based on a function that creates random numbers, but not completely random numbers. Does this mean that scrolls and monster drops aren't random? Both yes and no. I will explain in the next section.
§2 - Completely Random vs. Random
The fact that the events MapleStory creates aren't completely random do not mean that they are not random enough. Roughly speaking, all values from the function returning an integer from 0 to n will produce on average the same amount of all the numbers it is possible to generate.[1]
So, how does this function work? It's a specialized function [2] which contains a seed, a number which changes constantly whenever you call to the function and want a random number. The reason this number is called a seed, is because the number generated is a part of the seed.
If you understand me correctly, it's theoretically possible to calculate whether a scroll or a drop will drop, given the following conditions:
The right algorithm is known
The droprate, or scroll-rate, is known
The seed is known
Now, that is not a lot of information collecting! But, why is it that this is next to, if not completely, impossible in practice? Remember that every time a monster in-game is killed and a scroll is scrolled, the seed changes. I would assume for channel 1 in Scania alone, the seed would change up to 1 000 times per second, if not more. Therefore, it's not possible to make a scroll work or not by clicking at the right time when you have the right seed, because by then, the seed would have changed already.
By looking at MapleStory's wz-data, I will assume that the following computation is done within the server:
For drops:
If nextInt(a) is lower than b, drop item. (Given that a > b and a is relatively high for some drops in-game)
The drop will now have a probability of dropping http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq.gif times on average.
For scrolls:
If nextInt(100) is lower than successRate (either 100, 70, 60, 30 or 10. Or anything else, 15 and 65?), scroll will work.
The scroll will now have a probability of working http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-1.gif times on average.
As a brief summary, we could say the following:
It's close to impossible to calculate whether a scroll will work or not (ignore 100% scrolls).
The algorithm made to create random numbers have the same probability to create any of the numbers it is possible to generate.
So, what's the algorithm behind this function?[3]
import time
import math
class RandomNumGen:
def __init__ (self, seed = -1):
if seed == -1:
seed = time.time()
seed = math.trunc(seed)
self.seed = (seed ^ 0x5DEECE66D) & ((1 << 48) - 1)
def next (self, bits):
self.seed = (self.seed * 0x5DEECE66D + 0xB) & ((1 << 48) - 1)
return self.seed >> (48 - bits)
def nextInt (self, n):
if n & -n == n: # If n is a power of 2
return (n * self.next(32)) >> 32
bits = self.next(32)
val = bits % n
return val
Using the code works as follows:
>>> from FileName import *
>>> x = RandomNumGen()
# Creates a new random number generator
>>> x.nextInt(100)
54
# Creates a random number between 0 and 99. Uniformly distributed.
>>> i = 0
>>> for y in range(10000)
... i += x.nextInt(101)
...
>>> i
500718
# Is somewhere very close to 500 000
>>> i/10000
50.0718
Please keep in mind that the code can only create random numbers up to 2^32 - 1. To extend this range, concatenate two 32-bit random numbers like this:
>>> (x.next(32) << 32) | x.next(32)
8361958762996320579
# Creates a random number between 0 and 2^64 - 1
§3 - Basic Binomial Probability
As explained above, these random number generators are used to define whether a drop will drop, or if a scroll will work.
From §2 we are allowed to state that in practice, the probability of drawing any number within our wanted range will be the same. That means every scroll and drop can be handled as an independent event. (But keep in mind that it is NOT an independent event.) Now, by stating that, we also know that we have two possible outcomes: Success or fail. Success would be that the item is dropped, or that the scroll worked. Fail would be that it won't.
For dark scrolls, you may question yourself if it is reasonable to say that we have two possible outcomes. Do we? We may work the scroll, we may fail the scroll, and we may blow up the item. I'll let you dwell on this for a while until this will be an issue.
By having two possible outcomes and that each event can be handled as independent, we have a set of laws that we're allowed to use:
We state that
p is the probability for success
q is the probability for fail. http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-2.gif
n is the amount of trials.
X is the amount of times A occurs. (http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-3.gif)
Out from this, we can state simple formulas from probability.
§4 - Scrolls in a Row
What is the probability that we will get n scroll with the probability of working p in a row? Now, this is:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-4.gif
You can thus just put in p and n to your liking.
Want an example, maybe? Well, let's try out this:
What is the probability that we will get 3 60% scrolls working in a row? That is:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatexP30.gif, which equals to 0.216. Or, in percent, 21.6%. Now, that's not as much as I'd like it to be, sadly. :(
For people not understanding this function, please take a look at the spoiler beneath:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/Probability.png
Let's say we have 100 000 trials here (Sorry, one 0 was left out!), all with 3 60%-scrolls each. As you see, 60 000 of these trials will get the scroll to work on first scroll! Out of these 60 000 trials (, 36 000 of them will hit the next 60% as well. Finally, out of those 36 000 trials, 21 600 of them will come out with 3 60% in a row.
§5 - General Formula - Scroll percentages
Let's look at that picture again, shall we? (Keep in mind, we start off with 100 000 trials, not 10 000.)
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/Probability.png
I want now to find out the probability to get exactly 2 60% scrolls to work out of 3 60% scrolls. As you see, there are actually three different ways of getting 2 60% to work out of these 3 scrolls we have. We can do
SSF
FSS
SFS
Where S is success, and F is fail.
Interestingly enough, all these ways of getting 2 60% to work have the same probability. Hmm, interesting, but not really shocking for a mathematician:
0.6 * 0.6 * 0.4 = 0.4 * 0.6 * 0.6 = 0.6 * 0.4 * 0.6, and that's all the ways they are described here.
For easier notation, one tend to write
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-5.gif
instead, where x is the amount of successes one want, and y is the amount of fails one "want".
But that is not really the problem here. The big problem, is most how to count all the different possibilities. How do one do that?
Count all the ways of getting to 0. Then count all the ways of getting to +1, +2 and finally +3. This is 1, 3, 3, 1, right? Now, look at this triangle:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/pascal.gif
Hmm, interesting, interesting. The fourth row matches our result perfectly!
This triangle is called Pascal's triangle, for those interested in it. What one does, is to sum the two (or one) numbers above itself, and that's the value for any hexagon in the triangle. Apart from the hexagon at top, which is 1.
So, this triangle matches our need. But hey, we can't go around with this triangle if we want to find the probability of, uh, say 60 60% scrolls working out of 100 scrolls. That would require one giant triangle! And it wouldn't be that cheap to calculate on a computer either. For those who knows, this function is a recursive function and would require a lot of space to remember each number. Luckily for us, there's another way of finding these numbers. This way is called the binomial coefficient. There is actually a way to show that the pascal's triangle and the binomial coefficient work the same way, but I'll not go into that now.
The binomial coefficient is defined like this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-6.gif
For some of you, this may look quite weird. "What is '!'? Is it like, uh, an exclamation number?"
Heh. Well, this "!" is what we call faculty/factorial in combinatorics within mathematics.
Imagine yourself multiplying the first 6 natural numbers. That would be
1 * 2 * 3 * 4 * 5 * 6
right? The result is 720. Another way of expressing
1 * 2 * 3 * 4 * 5 * 6
is through faculty:
6! = 1 * 2 * 3 * 4 * 5 * 6
Handy eh, now we don't have to write it all out! A general way of writing factorial is this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatexn1times2times3times.gif
Oh and yeah, please keep in mind the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-7.gif
So, humm, I want to write the number 11 * 12 * 13 * 14 * 15 as easy as possible. How do you do that? It's not that hard really, you do it like this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatexfrac1510frac1times2timestime.gif
Actually, it looks like this seems to be somewhat similar with the function
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-6.gif
correct, eh? Even though it's a little off, it seems to be quite similar.
Now, back to the Pascal's triangle. Say we index both row and column on this triangle from 0. Then, we can say the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-8.gif
Now, let's try this out:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-9.gif
(Note that 0 chance 0 is 1)
It actually works! Now, another way of stating it:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-10.gif
This is also correct. Out from this, we can finalize the "general" formula for scroll percentages:
n is the amount of trials, k is the amount of successes, p is the probability of success:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-11.gif
So, if you want to find out the probability of having between 70 and 80 60% scrolls working out of 110 scrolls, you add the probability of having 70 scrolls working with 71 scrolls working, 72, 73, etc. We usually shorten this to the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatexsum_xabbinomnxtimespxtimes1-.gif
Which turns out to be 24.7%.
def choose (n, k):
if 0 <= k <= n:
p = 1
k = max(k, n - k)
# The Pascal's triangle is symmetrical, and we take advantage of that
for t in range(k):
p = (p * (n - t)) // (t + 1)
# This is taking advantage of cancelling factors in the expression
return p
else:
return 0
def binom (n, k, p):
return choose(n, k) * p**k * (1 - p)**(n - k)
def binomRange (a, b, n, p):
sum = 0
b = b + 1
for k in range(a, b):
sum += binom(n, k, p)
return sum
For testing, one could do the following:
>>> from FileName import *
>>> choose(5,3)
10
# Different combinations to obtain 3 successes on 5 trials
>>> binom(5, 3, 0.6)
0.3456
# Probability of having 3 60%-scrolls work on a total of 5 scrolls.
>>> binomRange(3, 5, 5, 0.6)
0.68356
# Probability of having 3 to 5 60% scrolls work on a total of 5 scrolls.
Now, what you have to be careful with, is that for large values of n, the probability will possibly create a code overflow/underflow, depending on what programming language you use. In Python, you may get this error if you want to checkout what the chances are for getting at least 3000 60% scrolls working out of a total of 5000 scrolls:
>>> binomRange(3000, 5000, 5000, 0.6)
Traceback (most recent call last):
File "<pyshell#5>", line 1, in <module>
binomRange(3000, 5000, 5000, 0.6)
File "FileName", line 20, in binomRange
sum += binom(n, k, p)
File "FileName", line 14, in binom
return choose(n, k) * p**k * (1 - p)**(n - k)
OverflowError: Python int too large to convert to C double
(The exact value for this calculation is 50.61%, by the way.)
I'll be explaining a way to avoid this issue by using binomial distribution. This technique will be described in an appendix at the end of this guide. Other ways of fixing this problem, is to create a fraction-class and use that class during calculations. Another way of fixing this is also possible. If wanted/needed, I will add in these implementations.
§6 - Dark Scrolls and Scroll Percentages
Now, we've gone through and explained scroll percentages. But this is binomial probability. That is, two possible outcomes. But hey, what happens if three possible outcomes were to happen?
First of all, binomial probability can't be used if we're going to have three possible outcomes. That's obvious! bi equals to two, as mono equals to one. What does this mean? Do we have to go over to trinomic probability? Oh no, that's actually what we're going to avoid. Let's look at this sheet of 3 70% slashed on an item:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/boom-example.png
Total probabilities:
Boom|+ 0|+ 1|+ 2|+ 3
385 875|3 375|47 250|220 500|343 000
Interestingly, this example shows us the following:
There are just as many ways of getting +0, +1, +2 and +3 as without the boom-rate. Look at §5.
Let's take a closer look at +2-chances:
SSF
FSS
SFS
Interestingly, they have all the same probability.
Looking further into it, the probability fits perfectly if you divide q by 2, and use the binomial formula. [4]
Wah, that's easy, eh? Just divide q by 2. Hmm, that doesn't give us the probability of blowing up the item though. How do one do that?
It's not that hard, really. We just sum up all the different possibilities for n scrolls from +0 to +n. Now, this is all the possibilities that exist which doesn't blow up the item. Hmm..
I told you in §5 that when you have a binomic probability, p + q = 1. We have a binomic probability here: The chance of blowing the item, and the chance of not blowing the item. We already know p, but we don't know q. However, by the p + q = 1 equation, you can just easily put p over on the other side, and get the probability of blowing up an item: q = 1 - p. That wasn't hard, was it?
Now, I have a theory that this code may be simplified. I'll be looking at it the next weeks, maybe I'll find something which will ease the way of calculating this probability. At least, I hope so. We'll see.
Now, on to another Python-implementation of mine:
#taken from §5, and slightly modified binom + binomRange, so one could change the q if wanted.
def choose (n, k):
if 0 <= k <= n:
p = 1
k = max(k, n - k)
# The Pascal's triangle is symmetrical, and we take advantage of that
for t in range(k):
p = (p * (n - t)) // (t + 1)
# This is taking advantage of cancelling factors in the expression
return p
else:
return 0
def binom (n, k, p, q = -1):
if q == -1:
q = (1 - p)
return choose(n, k) * p**k * q**(n - k)
def binomRange (a, b, n, p, q = -1):
if q == -1:
q = (1 - p)
sum = 0
b = b + 1
for k in range(a, b):
sum += binom(n, k, p, q)
return sum
def boomProb (n, p):
q = (1 - p) / 2
pNotBoom = binomRange(0, n, n, p, q)
pBoom = 1 - pNotBoom
return pBoom
The code works just as the code in §5. If you have any questions concerning it, feel free to ask.
§7 - Scrolls in a Row - Expectation Value
So far, we've only handled normal "issues" with scrolling: probability that is learnt at school. However, what's the probability that you hit, say 7 60% scrolls, in a row, when you have 100 scrolls? This is more interesting than the stuff above, as this may give calculations about how much it would cost to hit 7 30% on an item compared to using white scrolls. It may also lead you into calculating when you should start white scrolling your items, in order to earn/save the most money on scrolls. Nifty, eh?
In this section, we will not find the probability of having 7 60% scrolls working in a row out of 100 scrolls. However, we are going to checkout how many scrolls it would require on average.
The expectation value for one scroll is calculated the following way:
Say the scroll has p chance of hitting, and q chance of failing. We can thus extend this into an infinite converging series like this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-1.gif
Because, you know, there's a chance that you get the scroll working on first try. You multiply that by the amount of scrolls you used (1). When you're at the second try, you multiply the chance of one failing scroll, one working scroll, and the amount of scrolls used (2). You keep doing this forever. Finally, you'll get the expectation-value of having 1 scroll working.
Another way of expressing this expectation value is done by this function: (We let x = E(1))
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex.gif
So uh, how did we get there? The fact that the series up there converges to the value of the expression right above this text, does not simply mean that the equations are related. However, they are, and I'll explain why:
I stated earlier that x is the expected value of getting 1 scroll working in a row. That means, on average, it will take x trials in order to get one scroll working. So, what's the probability of getting the scroll to work on first attempt? That probability is p. Now, we take p and multiply with the amount of trials it took to get there: 1. That is the last part of the expression:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-2.gif
The first part of the expression on the right side is what I would call a beauty:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-3.gif
What happens if we don't work the scroll on first attempt? It's obvious that we fail, alright. But what also happens is that we're going back to the first part again: We start off, and have no scrolls that worked. The probability of getting the next scroll working is p, and you have to multiply that by 1 + 1, right? This is exactly what this expression does. Let me substitute x on the right side of the equation:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-4.gif
I could go on and on and on, but there's really no need for that. Eventually, it would lead out to the series we started with[5]:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-1.gif
That's for one scroll only. Let's see how this works in practice, for a 60% scroll[6]:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-5.gif
As expected, (you got it? The expected value was expected...) the scroll will on average hit every 5/3 scroll. For 5 scrolls, that is 5/(5/3) = 5 * 3/5 = 3 scrolls on average. As 60% will hit 6 scrolls every 10 scrolls, that's exactly what we wanted as an answer.
But we're not here to discuss E(1 60%), we're here for several scrolls in a row, so let's get going:
Let's base ourselves on the previous formula: If we fail a scroll, we have wasted a trial and have to start over again. Thus we still have the
q(x + 1)
as a part in the function. But this time, having one success doesn't hold. If the next scroll fails, we have wasted two scrolls, and have to start over again. This may be expressed as
pq(x + 2)
However, if we do get two scrolls working in a row, then we've used two scrolls without wasting them.
This may be expressed as
pp(2) = 2p^2
Finally, to the expression:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-6.gif
So yeah, let's try to use this expression with 60% scrolls once more. Now, two in a row:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-7.gif
Over to 3 scrolls in a row. How do we do this? It's not that hard, actually. We still keep the same function going, and use the same method as we did on E(2):
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-8.gif
Again, for our little 60% scroll. E(3 60%):
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-9.gif
If you're sharp-sighted, you notice that the x-value always turn up as
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-12.gif
yet it doesn't contain anything like that! How come? Let's base ourself on this assumption:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-11.gif
We know that p + q = 1, which means that 1 - q = p and that 1 - p = q. Out from that, we can divide everything away! [7]
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-10.gif
Amazing, eh? It also seems like we can make a general formula out of this.
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-12.gif
And we're able to shorten it even more by doing this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-13.gif
And add it into the equation like this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn.gif
Oh wow. For people knowing stuff about series, they'll see it now. This is a geometric series which will evualuate to the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn2.gif
Apart from the fact, it's going to start at the end and end at the start. If you get me.
For any geometric row, the sum of it will be the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn3.gif
And, turning in our values in the equation:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn4.gif
Thus, we get:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn5.gif
Finally, this may be expanded into this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn6.gif
Why expanding? It's to ease the mathematic shortening I'm going to do. In fact, I had to split it up like this to shorten it the most:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn7.gif| |http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn8.gif
Now, adding them back again:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn-1.gif
And, finally, if needed, swapping (1 - p) for q:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn2-1.gif
Whoa, that was a long way to get our answer. However, proving stuff like this seems to be harder than expected, eh? Oh well.
With this formula, I've collected a table of the average amount of scrolls needed in order to hit n scrolls in a row, for 10%, 30%, 60% and 70% scrolls:
|10%|30%|60%|70%
1|10|3.33|1.67|1.43
2|110|14.44|4.44|3.47
3|1110|51.48|9.07|6.38
4|11110|174.94|16.79|10.55
5|111110|586.46|29.65|16.5
6|1111110|1958.2|51.08|25.0
7|11111110|6530.68|86.81|37.14
8|111111110|21772.26|146.34|54.49
9|1111111110|72577.52|245.57|79.27
10|11111111110|241928.4|410.95|114.67
And as usual, I've made a Python-implementation for those who's interested in it:
def inaRow (n, p):
q = 1 - p
pn = p**n
return (1 - pn)/(q * pn)
(I think this one is easy enough, so I'll avoid comments. It's just the math that will be hard to grab for common maplers.)
§8 - Scrolls in a Row - Probability
What is the probability of having 7 scroll working in a row when you only have 100 scrolls? The answer lies within this section.
...When this section is finished, that is.
§9 - Dark Scrolls vs. White Scrolls
What is better? Fully scroll an item with dark scrolls until you have it perfect, only using white scrolls until you have it perfect, or a combination? A lot of people have questioned themselves this question without a good answer. Hopefully this will happen no more.
TODO (This section will definetly be the marketer's love-section...)
Appendix A - Binomial Statistic
For large values, certain functions does just not last. We either get an overflow due to the incredibly high values the binomial coefficient creates, or we get an underflow due to the incredibly low probabilities the http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-5.gif-part of the expression creates. We have thus to change into an easier way of calculating these values. Binomial Statistic is the key, and will be added as an appendix later on.
Appendix B - Scroll-Probabilities
Without much further ado due to lack of time, I'll add in this section partly as a request. In the future, upcoming information about Slate Scrolls and Chaos Scrolls may appear.
For the following tables, you may encounter some weird numbers, such as 5.651174E-4%. The E-4 means you have to move the period 4 places to the left. In this example, 5.651174E-4% turns out to be 00005.651174E-4% = 0.0005651174%. I may decide whether to remove or keep this scientific notation, based on requests/protests. Comments why/why not are appreciated!
As a last notice, (thanks for pointing out, KajitiSouls), the probability these rows show how many scrolls that work. An example:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/probwork.png
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/70percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
!|15.0%|27.75%|38.5875%|47.799374%|55.629467%|62.2 8505%|67.94229%|72.750946%|76.8383%|80.31256%
0|15.0%|2.25%|0.3375%|0.050625%|0.00759375%|0.0011 390625%|1.7085938E-4%|2.5628906E-5%|3.844336E-6%|5.766504E-7%
1|70.0%|21.0%|4.725%|0.945%|0.1771875%|0.03189375% |0.0055814064%|9.568125E-4%|1.6146211E-4%|2.6910351E-5%
2||49.0%|22.05%|6.615%|1.65375%|0.37209374%|0.0781 39685%|0.015627937%|0.0030139594%|5.651174E-4%
3|||34.3%|20.58%|7.7175%|2.31525%|0.6077531%|0.145 86075%|0.032818668%|0.007032572%
4||||24.01%|18.0075%|8.103375%|2.8361812%|0.850854 4%|0.22973068%|0.05743267%
5|||||16.807%|15.1263%|7.9413075%|3.176523%|1.0720 766%|0.32162297%
6||||||11.7649%|12.353145%|7.411887%|3.335349%|1.2 507559%
7|||||||8.23543%|9.882516%|6.670698%|3.335349%
8||||||||5.764801%|7.782481%|5.836861%
9|||||||||4.035361%|6.053041%
10||||||||||2.8247526%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/65percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
0|35.0%|12.25%|4.2875%|1.500625%|0.5252187%|0.1838 2657%|0.064339295%|0.022518754%|0.007881564%|0.002 7585474%
1|65.0%|45.5%|23.8875%|11.1475%|4.8770313%|2.04835 32%|0.8364109%|0.33456436%|0.13173471%|0.051230166 %
2||42.25%|44.3625%|31.05375%|18.114687%|9.510211%| 4.660003%|2.1746683%|0.9786007%|0.4281378%
3|||27.4625%|38.4475%|33.641563%|23.549093%|14.423 82%|8.077339%|4.240603%|2.1203015%
4||||17.850624%|31.238594%|32.80052%|26.787094%|18 .750965%|11.813108%|6.89098%
5|||||11.602906%|24.366102%|29.848476%|27.858578%| 21.93863%|15.357041%
6||||||7.541889%|18.477629%|25.86868%|27.162113%|2 3.76685%
7|||||||4.902228%|13.726238%|21.618826%|25.221962%
8||||||||3.186448%|10.037312%|17.565296%
9|||||||||2.0711913%|7.2491693%
10||||||||||1.3462744%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/60percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
0|40.0%|16.0%|6.4%|2.56%|1.024%|0.4096%|0.16384%|0 .065536%|0.0262144%|0.01048576%
1|60.0%|48.0%|28.8%|15.36%|7.68%|3.6864%|1.72032%| 0.786432%|0.3538944%|0.1572864%
2||36.0%|43.2%|34.56%|23.04%|13.824%|7.74144%|4.12 8768%|2.1233664%|1.0616832%
3|||21.6%|34.56%|34.56%|27.648%|19.3536%|12.386304 %|7.4317822%|4.2467327%
4||||12.96%|25.92%|31.104%|29.0304%|23.22432%|16.7 2151%|11.147674%
5|||||7.776%|18.6624%|26.12736%|27.869184%|25.0822 66%|20.065813%
6||||||4.6656%|13.06368%|20.901888%|25.082266%|25. 082266%
7|||||||2.79936%|8.957952%|16.124313%|21.499084%
8||||||||1.679616%|6.0466175%|12.093235%
9|||||||||1.0077696%|4.0310783%
10||||||||||0.60466176%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/30percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
!|35.0%|57.75%|72.5375%|82.149376%|88.397095%|92.4 58115%|95.09777%|96.81355%|97.92881%|98.653725%
0|35.0%|12.25%|4.2875%|1.500625%|0.5252187%|0.1838 2657%|0.064339295%|0.022518754%|0.007881564%|0.002 7585474%
1|30.0%|21.0%|11.025%|5.145%|2.2509375%|0.94539374 %|0.38603577%|0.15441431%|0.060800634%|0.023644691 %
2||9.0%|9.45%|6.615%|3.85875%|2.0258439%|0.9926634 4%|0.46324295%|0.20845932%|0.091200955%
3|||2.7%|3.78%|3.3075%|2.31525%|1.4180906%|0.79413 074%|0.41691864%|0.20845932%
4||||0.81%|1.4175%|1.488375%|1.2155062%|0.8508544% |0.5360383%|0.31268898%
5|||||0.243%|0.5103%|0.6251175%|0.583443%|0.459461 36%|0.32162297%
6||||||0.0729%|0.178605%|0.250047%|0.26254934%|0.2 2973068%
7|||||||0.02187%|0.061236%|0.0964467%|0.11252115%
8||||||||0.006561%|0.02066715%|0.036167514%
9|||||||||0.0019683%|0.00688905%
10||||||||||5.9049E-4%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/15percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
0|85.0%|72.25%|61.4125%|52.200626%|44.370533%|37.7 1495%|32.05771%|27.249052%|23.161695%|19.68744%
1|15.0%|25.5%|32.5125%|36.8475%|39.150467%|39.9334 8%|39.6007%|38.46925%|36.78622%|34.742542%
2||2.25%|5.7375%|9.75375%|13.817813%|17.61771%|20. 965076%|23.76042%|25.966743%|27.589666%
3|||0.3375%|1.1475%|2.4384375%|4.145344%|6.1661987 %|8.38603%|10.692189%|12.983372%
4||||0.050625%|0.21515626%|0.5486484%|1.0881528%|1 .8498596%|2.8302853%|4.0095706%
5|||||0.00759375%|0.038728125%|0.11521617%|0.26115 665%|0.4994621%|0.84908557%
6||||||0.0011390625%|0.006777422%|0.023043234%|0.0 58760248%|0.124865524%
7|||||||1.7085938E-4%|0.0011618438%|0.0044440525%|0.012591481%
8||||||||2.5628906E-5%|1.9606113E-4%|8.3325984E-4%
9|||||||||3.844336E-6%|3.2676857E-5%
10||||||||||5.766504E-7%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/10percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
0|90.0%|81.0%|72.9%|65.61%|59.049%|53.1441%|47.829 69%|43.046722%|38.74205%|34.867844%
1|10.0%|18.0%|24.3%|29.16%|32.805%|35.4294%|37.200 87%|38.263752%|38.74205%|38.74205%
2||1.0%|2.7%|4.86%|7.29%|9.8415%|12.40029%|14.8803 48%|17.218689%|19.371025%
3|||0.1%|0.36%|0.81%|1.458%|2.29635%|3.306744%|4.4 64104%|5.739563%
4||||0.01%|0.045%|0.1215%|0.25515%|0.45927%|0.7440 174%|1.116026%
5|||||0.001%|0.0054%|0.01701%|0.040824%|0.0826686% |0.14880349%
6||||||1.0E-4%|6.3E-4%|0.002268%|0.0061236%|0.0137781%
7|||||||1.0E-5%|7.2E-5%|2.916E-4%|8.748E-4%
8||||||||1.0E-6%|8.1E-6%|3.645E-5%
9|||||||||1.0E-7%|9.0E-7%
10||||||||||1.0E-8%
Notes
[1] -> There may be a 0.001% error-margin on this.
[2] -> Take a look at The Art of Computer Programming - Donald Knuth if you're more interested.
[3] -> I am not sure whether this function is used or not, but this function is one of the most precise ways in order to generate random numbers, and does not require a lot of computer power when it's called.
[4] ->
http://mathurl.com/yg86ukv.png
Out from this, we see that a trinomial probability with the probabilities p, q and r is equal to:
http://mathurl.com/ykm47su.png
If we then want x scrolls to work (p) and 0 scrolls to boom (r), we get the expression:
http://mathurl.com/yf7tyj8.png
[5] -> You have to move over, divide and multiply a lot to see the expression coming up.
[6] -> This is actually a long expression for the E(1). We base ourselves on p + q = 1, q - 1 = p, and p - 1 = q:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-13.gif
The thing is, I want you to understand how to get to the formula I got to. By shortening the expression into this, I can't really explain it that well.
[7] -> This is not a proof for any given E(n in a row)-value. It's "easy" to prove it though, so here is the actual proof:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn3-1.gif
To-do List - Changes
To-do:
Some equations aren't in LaTeX. Whether this will be an issue or not, is at the current moment not decided. Most likely not.
Some LaTeX-equations makes it hard to read the text. I should be finding another way so it will be easier to read the text.
Some parts may contain heavy language, or may be hard to understand without proper knowledge. I want everyone to be able to understand without any additional knowledge, as long you're interested.
Illustrations may ease the reading, so it would be a good idea to find illustrations.
Some equations may be lead out in the Notes-section, for those who are interested.
Add in §8 - Scrolls in a Row - Probability.
Add in §9 - Dark Scrolls vs. White Scrolls.
Add in Appendix A - Binomial Statistic.
Changes:
March 22, 2009 - Creation of the document.
March 23, 2009 - Appendix B created and included. Appendix B is not 100% complete. Chaos Scrolls will be added in the future, if information enough is gained.
April 2, 2009 - Added in section §6 - Dark scrolls and Scroll Percentages. Also further shortened the expression leaded out in §7 in order to ease the time it takes to calculate the result. Finally, fixed certain mathematical expressions and added some more.
September 22, 2009 - Added urls, and will possibly have time to add in more data in the future.
Credits
As of today, a lot of my work has been independent of anyone. I'd however like to thank the following:
My Physics/Mathematics teacher, for being so interested and professional with the stuff he's working with.
The Online LaTeX Equation Editor (http://www.codecogs.com/components/equationeditor/equationeditor.php)
KajitiSouls - for commenting and coming up with several handy things for the document. Such as examples and stuff.
If any of these applies to you, I'd like to welcome you to my little document. In this document, I will be discussing and explaining the following:
How random numbers are created inside a computer, and how MapleStory works with these numbers in order to simulate random events.
How you find the probability of certain scroll-events, such as the probability of working 4 scrolls out of 7, or the probability of working 6 scrolls in a row if you have a limited amount of scrolls
What is the most efficient in terms of earning/saving money? Dark scrolls, or white scrolls?
I am Noah, a person who is interested in mathematics, especially probability and number theory. Through studies from both university and own will, I have found quite a lot of interesting facts about maths, and I would like to share some of it with you. Please keep in mind that this document will require knowledge or interest in mathematics in order to understand everything.
Table of Contents:
Random Number Theory
§1 - Completely Random Events (http://www.southperry.net/forums/showthread.php?p=170677#§1)
§2 - Completely Random vs. Random (http://www.southperry.net/forums/showthread.php?p=170677#§2)
Binomial Probability
§3 - Basic Binomial Probability (http://www.southperry.net/forums/showthread.php?p=170677#§3)
§4 - Scrolls in a Row (http://www.southperry.net/forums/showthread.php?p=170677#§4)
§5 - General Formula - Scroll percentages (http://www.southperry.net/forums/showthread.php?p=170677#§5)
§6 - Dark scrolls and Scroll Percentages (http://www.southperry.net/forums/showthread.php?p=170677#§6)
§7 - Scrolls in a Row - Expectation Value (http://www.southperry.net/forums/showthread.php?p=170677#§7)
§8 - Scrolls in a Row - Probability (http://www.southperry.net/forums/showthread.php?p=170677#§8)
§9 - Dark Scrolls vs. White Scrolls (http://www.southperry.net/forums/showthread.php?p=170677#§9)
Appendices
Appendix A - Binomial Statistic (http://www.southperry.net/forums/showthread.php?p=170677#ApA)
Appendix B - Scroll-Probabilities (http://www.southperry.net/forums/showthread.php?p=170677#ApB)
Other
Notes (http://www.southperry.net/forums/showthread.php?p=170677#Notes)
To-do List - Changes (http://www.southperry.net/forums/showthread.php?p=170677#To-do)
Credits (http://www.southperry.net/forums/showthread.php?p=170677#Credits)
§1 - Completely Random Events
In our real world today, no events apart from events within quantum physics are completely random. We assume the servers MapleStory uses aren't "quantum-servers", because most computers doesn't have this possibility as of right now. Thus, we have to accept that the probabilities and events, such as a working scroll or a dropping drop from a monster, is based on a function that creates random numbers, but not completely random numbers. Does this mean that scrolls and monster drops aren't random? Both yes and no. I will explain in the next section.
§2 - Completely Random vs. Random
The fact that the events MapleStory creates aren't completely random do not mean that they are not random enough. Roughly speaking, all values from the function returning an integer from 0 to n will produce on average the same amount of all the numbers it is possible to generate.[1]
So, how does this function work? It's a specialized function [2] which contains a seed, a number which changes constantly whenever you call to the function and want a random number. The reason this number is called a seed, is because the number generated is a part of the seed.
If you understand me correctly, it's theoretically possible to calculate whether a scroll or a drop will drop, given the following conditions:
The right algorithm is known
The droprate, or scroll-rate, is known
The seed is known
Now, that is not a lot of information collecting! But, why is it that this is next to, if not completely, impossible in practice? Remember that every time a monster in-game is killed and a scroll is scrolled, the seed changes. I would assume for channel 1 in Scania alone, the seed would change up to 1 000 times per second, if not more. Therefore, it's not possible to make a scroll work or not by clicking at the right time when you have the right seed, because by then, the seed would have changed already.
By looking at MapleStory's wz-data, I will assume that the following computation is done within the server:
For drops:
If nextInt(a) is lower than b, drop item. (Given that a > b and a is relatively high for some drops in-game)
The drop will now have a probability of dropping http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq.gif times on average.
For scrolls:
If nextInt(100) is lower than successRate (either 100, 70, 60, 30 or 10. Or anything else, 15 and 65?), scroll will work.
The scroll will now have a probability of working http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-1.gif times on average.
As a brief summary, we could say the following:
It's close to impossible to calculate whether a scroll will work or not (ignore 100% scrolls).
The algorithm made to create random numbers have the same probability to create any of the numbers it is possible to generate.
So, what's the algorithm behind this function?[3]
import time
import math
class RandomNumGen:
def __init__ (self, seed = -1):
if seed == -1:
seed = time.time()
seed = math.trunc(seed)
self.seed = (seed ^ 0x5DEECE66D) & ((1 << 48) - 1)
def next (self, bits):
self.seed = (self.seed * 0x5DEECE66D + 0xB) & ((1 << 48) - 1)
return self.seed >> (48 - bits)
def nextInt (self, n):
if n & -n == n: # If n is a power of 2
return (n * self.next(32)) >> 32
bits = self.next(32)
val = bits % n
return val
Using the code works as follows:
>>> from FileName import *
>>> x = RandomNumGen()
# Creates a new random number generator
>>> x.nextInt(100)
54
# Creates a random number between 0 and 99. Uniformly distributed.
>>> i = 0
>>> for y in range(10000)
... i += x.nextInt(101)
...
>>> i
500718
# Is somewhere very close to 500 000
>>> i/10000
50.0718
Please keep in mind that the code can only create random numbers up to 2^32 - 1. To extend this range, concatenate two 32-bit random numbers like this:
>>> (x.next(32) << 32) | x.next(32)
8361958762996320579
# Creates a random number between 0 and 2^64 - 1
§3 - Basic Binomial Probability
As explained above, these random number generators are used to define whether a drop will drop, or if a scroll will work.
From §2 we are allowed to state that in practice, the probability of drawing any number within our wanted range will be the same. That means every scroll and drop can be handled as an independent event. (But keep in mind that it is NOT an independent event.) Now, by stating that, we also know that we have two possible outcomes: Success or fail. Success would be that the item is dropped, or that the scroll worked. Fail would be that it won't.
For dark scrolls, you may question yourself if it is reasonable to say that we have two possible outcomes. Do we? We may work the scroll, we may fail the scroll, and we may blow up the item. I'll let you dwell on this for a while until this will be an issue.
By having two possible outcomes and that each event can be handled as independent, we have a set of laws that we're allowed to use:
We state that
p is the probability for success
q is the probability for fail. http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-2.gif
n is the amount of trials.
X is the amount of times A occurs. (http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-3.gif)
Out from this, we can state simple formulas from probability.
§4 - Scrolls in a Row
What is the probability that we will get n scroll with the probability of working p in a row? Now, this is:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-4.gif
You can thus just put in p and n to your liking.
Want an example, maybe? Well, let's try out this:
What is the probability that we will get 3 60% scrolls working in a row? That is:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatexP30.gif, which equals to 0.216. Or, in percent, 21.6%. Now, that's not as much as I'd like it to be, sadly. :(
For people not understanding this function, please take a look at the spoiler beneath:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/Probability.png
Let's say we have 100 000 trials here (Sorry, one 0 was left out!), all with 3 60%-scrolls each. As you see, 60 000 of these trials will get the scroll to work on first scroll! Out of these 60 000 trials (, 36 000 of them will hit the next 60% as well. Finally, out of those 36 000 trials, 21 600 of them will come out with 3 60% in a row.
§5 - General Formula - Scroll percentages
Let's look at that picture again, shall we? (Keep in mind, we start off with 100 000 trials, not 10 000.)
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/Probability.png
I want now to find out the probability to get exactly 2 60% scrolls to work out of 3 60% scrolls. As you see, there are actually three different ways of getting 2 60% to work out of these 3 scrolls we have. We can do
SSF
FSS
SFS
Where S is success, and F is fail.
Interestingly enough, all these ways of getting 2 60% to work have the same probability. Hmm, interesting, but not really shocking for a mathematician:
0.6 * 0.6 * 0.4 = 0.4 * 0.6 * 0.6 = 0.6 * 0.4 * 0.6, and that's all the ways they are described here.
For easier notation, one tend to write
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-5.gif
instead, where x is the amount of successes one want, and y is the amount of fails one "want".
But that is not really the problem here. The big problem, is most how to count all the different possibilities. How do one do that?
Count all the ways of getting to 0. Then count all the ways of getting to +1, +2 and finally +3. This is 1, 3, 3, 1, right? Now, look at this triangle:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/pascal.gif
Hmm, interesting, interesting. The fourth row matches our result perfectly!
This triangle is called Pascal's triangle, for those interested in it. What one does, is to sum the two (or one) numbers above itself, and that's the value for any hexagon in the triangle. Apart from the hexagon at top, which is 1.
So, this triangle matches our need. But hey, we can't go around with this triangle if we want to find the probability of, uh, say 60 60% scrolls working out of 100 scrolls. That would require one giant triangle! And it wouldn't be that cheap to calculate on a computer either. For those who knows, this function is a recursive function and would require a lot of space to remember each number. Luckily for us, there's another way of finding these numbers. This way is called the binomial coefficient. There is actually a way to show that the pascal's triangle and the binomial coefficient work the same way, but I'll not go into that now.
The binomial coefficient is defined like this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-6.gif
For some of you, this may look quite weird. "What is '!'? Is it like, uh, an exclamation number?"
Heh. Well, this "!" is what we call faculty/factorial in combinatorics within mathematics.
Imagine yourself multiplying the first 6 natural numbers. That would be
1 * 2 * 3 * 4 * 5 * 6
right? The result is 720. Another way of expressing
1 * 2 * 3 * 4 * 5 * 6
is through faculty:
6! = 1 * 2 * 3 * 4 * 5 * 6
Handy eh, now we don't have to write it all out! A general way of writing factorial is this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatexn1times2times3times.gif
Oh and yeah, please keep in mind the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-7.gif
So, humm, I want to write the number 11 * 12 * 13 * 14 * 15 as easy as possible. How do you do that? It's not that hard really, you do it like this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatexfrac1510frac1times2timestime.gif
Actually, it looks like this seems to be somewhat similar with the function
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-6.gif
correct, eh? Even though it's a little off, it seems to be quite similar.
Now, back to the Pascal's triangle. Say we index both row and column on this triangle from 0. Then, we can say the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-8.gif
Now, let's try this out:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-9.gif
(Note that 0 chance 0 is 1)
It actually works! Now, another way of stating it:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-10.gif
This is also correct. Out from this, we can finalize the "general" formula for scroll percentages:
n is the amount of trials, k is the amount of successes, p is the probability of success:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-11.gif
So, if you want to find out the probability of having between 70 and 80 60% scrolls working out of 110 scrolls, you add the probability of having 70 scrolls working with 71 scrolls working, 72, 73, etc. We usually shorten this to the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatexsum_xabbinomnxtimespxtimes1-.gif
Which turns out to be 24.7%.
def choose (n, k):
if 0 <= k <= n:
p = 1
k = max(k, n - k)
# The Pascal's triangle is symmetrical, and we take advantage of that
for t in range(k):
p = (p * (n - t)) // (t + 1)
# This is taking advantage of cancelling factors in the expression
return p
else:
return 0
def binom (n, k, p):
return choose(n, k) * p**k * (1 - p)**(n - k)
def binomRange (a, b, n, p):
sum = 0
b = b + 1
for k in range(a, b):
sum += binom(n, k, p)
return sum
For testing, one could do the following:
>>> from FileName import *
>>> choose(5,3)
10
# Different combinations to obtain 3 successes on 5 trials
>>> binom(5, 3, 0.6)
0.3456
# Probability of having 3 60%-scrolls work on a total of 5 scrolls.
>>> binomRange(3, 5, 5, 0.6)
0.68356
# Probability of having 3 to 5 60% scrolls work on a total of 5 scrolls.
Now, what you have to be careful with, is that for large values of n, the probability will possibly create a code overflow/underflow, depending on what programming language you use. In Python, you may get this error if you want to checkout what the chances are for getting at least 3000 60% scrolls working out of a total of 5000 scrolls:
>>> binomRange(3000, 5000, 5000, 0.6)
Traceback (most recent call last):
File "<pyshell#5>", line 1, in <module>
binomRange(3000, 5000, 5000, 0.6)
File "FileName", line 20, in binomRange
sum += binom(n, k, p)
File "FileName", line 14, in binom
return choose(n, k) * p**k * (1 - p)**(n - k)
OverflowError: Python int too large to convert to C double
(The exact value for this calculation is 50.61%, by the way.)
I'll be explaining a way to avoid this issue by using binomial distribution. This technique will be described in an appendix at the end of this guide. Other ways of fixing this problem, is to create a fraction-class and use that class during calculations. Another way of fixing this is also possible. If wanted/needed, I will add in these implementations.
§6 - Dark Scrolls and Scroll Percentages
Now, we've gone through and explained scroll percentages. But this is binomial probability. That is, two possible outcomes. But hey, what happens if three possible outcomes were to happen?
First of all, binomial probability can't be used if we're going to have three possible outcomes. That's obvious! bi equals to two, as mono equals to one. What does this mean? Do we have to go over to trinomic probability? Oh no, that's actually what we're going to avoid. Let's look at this sheet of 3 70% slashed on an item:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/boom-example.png
Total probabilities:
Boom|+ 0|+ 1|+ 2|+ 3
385 875|3 375|47 250|220 500|343 000
Interestingly, this example shows us the following:
There are just as many ways of getting +0, +1, +2 and +3 as without the boom-rate. Look at §5.
Let's take a closer look at +2-chances:
SSF
FSS
SFS
Interestingly, they have all the same probability.
Looking further into it, the probability fits perfectly if you divide q by 2, and use the binomial formula. [4]
Wah, that's easy, eh? Just divide q by 2. Hmm, that doesn't give us the probability of blowing up the item though. How do one do that?
It's not that hard, really. We just sum up all the different possibilities for n scrolls from +0 to +n. Now, this is all the possibilities that exist which doesn't blow up the item. Hmm..
I told you in §5 that when you have a binomic probability, p + q = 1. We have a binomic probability here: The chance of blowing the item, and the chance of not blowing the item. We already know p, but we don't know q. However, by the p + q = 1 equation, you can just easily put p over on the other side, and get the probability of blowing up an item: q = 1 - p. That wasn't hard, was it?
Now, I have a theory that this code may be simplified. I'll be looking at it the next weeks, maybe I'll find something which will ease the way of calculating this probability. At least, I hope so. We'll see.
Now, on to another Python-implementation of mine:
#taken from §5, and slightly modified binom + binomRange, so one could change the q if wanted.
def choose (n, k):
if 0 <= k <= n:
p = 1
k = max(k, n - k)
# The Pascal's triangle is symmetrical, and we take advantage of that
for t in range(k):
p = (p * (n - t)) // (t + 1)
# This is taking advantage of cancelling factors in the expression
return p
else:
return 0
def binom (n, k, p, q = -1):
if q == -1:
q = (1 - p)
return choose(n, k) * p**k * q**(n - k)
def binomRange (a, b, n, p, q = -1):
if q == -1:
q = (1 - p)
sum = 0
b = b + 1
for k in range(a, b):
sum += binom(n, k, p, q)
return sum
def boomProb (n, p):
q = (1 - p) / 2
pNotBoom = binomRange(0, n, n, p, q)
pBoom = 1 - pNotBoom
return pBoom
The code works just as the code in §5. If you have any questions concerning it, feel free to ask.
§7 - Scrolls in a Row - Expectation Value
So far, we've only handled normal "issues" with scrolling: probability that is learnt at school. However, what's the probability that you hit, say 7 60% scrolls, in a row, when you have 100 scrolls? This is more interesting than the stuff above, as this may give calculations about how much it would cost to hit 7 30% on an item compared to using white scrolls. It may also lead you into calculating when you should start white scrolling your items, in order to earn/save the most money on scrolls. Nifty, eh?
In this section, we will not find the probability of having 7 60% scrolls working in a row out of 100 scrolls. However, we are going to checkout how many scrolls it would require on average.
The expectation value for one scroll is calculated the following way:
Say the scroll has p chance of hitting, and q chance of failing. We can thus extend this into an infinite converging series like this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-1.gif
Because, you know, there's a chance that you get the scroll working on first try. You multiply that by the amount of scrolls you used (1). When you're at the second try, you multiply the chance of one failing scroll, one working scroll, and the amount of scrolls used (2). You keep doing this forever. Finally, you'll get the expectation-value of having 1 scroll working.
Another way of expressing this expectation value is done by this function: (We let x = E(1))
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex.gif
So uh, how did we get there? The fact that the series up there converges to the value of the expression right above this text, does not simply mean that the equations are related. However, they are, and I'll explain why:
I stated earlier that x is the expected value of getting 1 scroll working in a row. That means, on average, it will take x trials in order to get one scroll working. So, what's the probability of getting the scroll to work on first attempt? That probability is p. Now, we take p and multiply with the amount of trials it took to get there: 1. That is the last part of the expression:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-2.gif
The first part of the expression on the right side is what I would call a beauty:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-3.gif
What happens if we don't work the scroll on first attempt? It's obvious that we fail, alright. But what also happens is that we're going back to the first part again: We start off, and have no scrolls that worked. The probability of getting the next scroll working is p, and you have to multiply that by 1 + 1, right? This is exactly what this expression does. Let me substitute x on the right side of the equation:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-4.gif
I could go on and on and on, but there's really no need for that. Eventually, it would lead out to the series we started with[5]:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-1.gif
That's for one scroll only. Let's see how this works in practice, for a 60% scroll[6]:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-5.gif
As expected, (you got it? The expected value was expected...) the scroll will on average hit every 5/3 scroll. For 5 scrolls, that is 5/(5/3) = 5 * 3/5 = 3 scrolls on average. As 60% will hit 6 scrolls every 10 scrolls, that's exactly what we wanted as an answer.
But we're not here to discuss E(1 60%), we're here for several scrolls in a row, so let's get going:
Let's base ourselves on the previous formula: If we fail a scroll, we have wasted a trial and have to start over again. Thus we still have the
q(x + 1)
as a part in the function. But this time, having one success doesn't hold. If the next scroll fails, we have wasted two scrolls, and have to start over again. This may be expressed as
pq(x + 2)
However, if we do get two scrolls working in a row, then we've used two scrolls without wasting them.
This may be expressed as
pp(2) = 2p^2
Finally, to the expression:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-6.gif
So yeah, let's try to use this expression with 60% scrolls once more. Now, two in a row:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-7.gif
Over to 3 scrolls in a row. How do we do this? It's not that hard, actually. We still keep the same function going, and use the same method as we did on E(2):
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-8.gif
Again, for our little 60% scroll. E(3 60%):
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-9.gif
If you're sharp-sighted, you notice that the x-value always turn up as
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-12.gif
yet it doesn't contain anything like that! How come? Let's base ourself on this assumption:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-11.gif
We know that p + q = 1, which means that 1 - q = p and that 1 - p = q. Out from that, we can divide everything away! [7]
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-10.gif
Amazing, eh? It also seems like we can make a general formula out of this.
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-12.gif
And we're able to shorten it even more by doing this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-13.gif
And add it into the equation like this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn.gif
Oh wow. For people knowing stuff about series, they'll see it now. This is a geometric series which will evualuate to the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn2.gif
Apart from the fact, it's going to start at the end and end at the start. If you get me.
For any geometric row, the sum of it will be the following:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn3.gif
And, turning in our values in the equation:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn4.gif
Thus, we get:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn5.gif
Finally, this may be expanded into this:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn6.gif
Why expanding? It's to ease the mathematic shortening I'm going to do. In fact, I had to split it up like this to shorten it the most:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn7.gif| |http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn8.gif
Now, adding them back again:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn-1.gif
And, finally, if needed, swapping (1 - p) for q:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn2-1.gif
Whoa, that was a long way to get our answer. However, proving stuff like this seems to be harder than expected, eh? Oh well.
With this formula, I've collected a table of the average amount of scrolls needed in order to hit n scrolls in a row, for 10%, 30%, 60% and 70% scrolls:
|10%|30%|60%|70%
1|10|3.33|1.67|1.43
2|110|14.44|4.44|3.47
3|1110|51.48|9.07|6.38
4|11110|174.94|16.79|10.55
5|111110|586.46|29.65|16.5
6|1111110|1958.2|51.08|25.0
7|11111110|6530.68|86.81|37.14
8|111111110|21772.26|146.34|54.49
9|1111111110|72577.52|245.57|79.27
10|11111111110|241928.4|410.95|114.67
And as usual, I've made a Python-implementation for those who's interested in it:
def inaRow (n, p):
q = 1 - p
pn = p**n
return (1 - pn)/(q * pn)
(I think this one is easy enough, so I'll avoid comments. It's just the math that will be hard to grab for common maplers.)
§8 - Scrolls in a Row - Probability
What is the probability of having 7 scroll working in a row when you only have 100 scrolls? The answer lies within this section.
...When this section is finished, that is.
§9 - Dark Scrolls vs. White Scrolls
What is better? Fully scroll an item with dark scrolls until you have it perfect, only using white scrolls until you have it perfect, or a combination? A lot of people have questioned themselves this question without a good answer. Hopefully this will happen no more.
TODO (This section will definetly be the marketer's love-section...)
Appendix A - Binomial Statistic
For large values, certain functions does just not last. We either get an overflow due to the incredibly high values the binomial coefficient creates, or we get an underflow due to the incredibly low probabilities the http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eq-5.gif-part of the expression creates. We have thus to change into an easier way of calculating these values. Binomial Statistic is the key, and will be added as an appendix later on.
Appendix B - Scroll-Probabilities
Without much further ado due to lack of time, I'll add in this section partly as a request. In the future, upcoming information about Slate Scrolls and Chaos Scrolls may appear.
For the following tables, you may encounter some weird numbers, such as 5.651174E-4%. The E-4 means you have to move the period 4 places to the left. In this example, 5.651174E-4% turns out to be 00005.651174E-4% = 0.0005651174%. I may decide whether to remove or keep this scientific notation, based on requests/protests. Comments why/why not are appreciated!
As a last notice, (thanks for pointing out, KajitiSouls), the probability these rows show how many scrolls that work. An example:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/probwork.png
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/70percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
!|15.0%|27.75%|38.5875%|47.799374%|55.629467%|62.2 8505%|67.94229%|72.750946%|76.8383%|80.31256%
0|15.0%|2.25%|0.3375%|0.050625%|0.00759375%|0.0011 390625%|1.7085938E-4%|2.5628906E-5%|3.844336E-6%|5.766504E-7%
1|70.0%|21.0%|4.725%|0.945%|0.1771875%|0.03189375% |0.0055814064%|9.568125E-4%|1.6146211E-4%|2.6910351E-5%
2||49.0%|22.05%|6.615%|1.65375%|0.37209374%|0.0781 39685%|0.015627937%|0.0030139594%|5.651174E-4%
3|||34.3%|20.58%|7.7175%|2.31525%|0.6077531%|0.145 86075%|0.032818668%|0.007032572%
4||||24.01%|18.0075%|8.103375%|2.8361812%|0.850854 4%|0.22973068%|0.05743267%
5|||||16.807%|15.1263%|7.9413075%|3.176523%|1.0720 766%|0.32162297%
6||||||11.7649%|12.353145%|7.411887%|3.335349%|1.2 507559%
7|||||||8.23543%|9.882516%|6.670698%|3.335349%
8||||||||5.764801%|7.782481%|5.836861%
9|||||||||4.035361%|6.053041%
10||||||||||2.8247526%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/65percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
0|35.0%|12.25%|4.2875%|1.500625%|0.5252187%|0.1838 2657%|0.064339295%|0.022518754%|0.007881564%|0.002 7585474%
1|65.0%|45.5%|23.8875%|11.1475%|4.8770313%|2.04835 32%|0.8364109%|0.33456436%|0.13173471%|0.051230166 %
2||42.25%|44.3625%|31.05375%|18.114687%|9.510211%| 4.660003%|2.1746683%|0.9786007%|0.4281378%
3|||27.4625%|38.4475%|33.641563%|23.549093%|14.423 82%|8.077339%|4.240603%|2.1203015%
4||||17.850624%|31.238594%|32.80052%|26.787094%|18 .750965%|11.813108%|6.89098%
5|||||11.602906%|24.366102%|29.848476%|27.858578%| 21.93863%|15.357041%
6||||||7.541889%|18.477629%|25.86868%|27.162113%|2 3.76685%
7|||||||4.902228%|13.726238%|21.618826%|25.221962%
8||||||||3.186448%|10.037312%|17.565296%
9|||||||||2.0711913%|7.2491693%
10||||||||||1.3462744%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/60percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
0|40.0%|16.0%|6.4%|2.56%|1.024%|0.4096%|0.16384%|0 .065536%|0.0262144%|0.01048576%
1|60.0%|48.0%|28.8%|15.36%|7.68%|3.6864%|1.72032%| 0.786432%|0.3538944%|0.1572864%
2||36.0%|43.2%|34.56%|23.04%|13.824%|7.74144%|4.12 8768%|2.1233664%|1.0616832%
3|||21.6%|34.56%|34.56%|27.648%|19.3536%|12.386304 %|7.4317822%|4.2467327%
4||||12.96%|25.92%|31.104%|29.0304%|23.22432%|16.7 2151%|11.147674%
5|||||7.776%|18.6624%|26.12736%|27.869184%|25.0822 66%|20.065813%
6||||||4.6656%|13.06368%|20.901888%|25.082266%|25. 082266%
7|||||||2.79936%|8.957952%|16.124313%|21.499084%
8||||||||1.679616%|6.0466175%|12.093235%
9|||||||||1.0077696%|4.0310783%
10||||||||||0.60466176%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/30percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
!|35.0%|57.75%|72.5375%|82.149376%|88.397095%|92.4 58115%|95.09777%|96.81355%|97.92881%|98.653725%
0|35.0%|12.25%|4.2875%|1.500625%|0.5252187%|0.1838 2657%|0.064339295%|0.022518754%|0.007881564%|0.002 7585474%
1|30.0%|21.0%|11.025%|5.145%|2.2509375%|0.94539374 %|0.38603577%|0.15441431%|0.060800634%|0.023644691 %
2||9.0%|9.45%|6.615%|3.85875%|2.0258439%|0.9926634 4%|0.46324295%|0.20845932%|0.091200955%
3|||2.7%|3.78%|3.3075%|2.31525%|1.4180906%|0.79413 074%|0.41691864%|0.20845932%
4||||0.81%|1.4175%|1.488375%|1.2155062%|0.8508544% |0.5360383%|0.31268898%
5|||||0.243%|0.5103%|0.6251175%|0.583443%|0.459461 36%|0.32162297%
6||||||0.0729%|0.178605%|0.250047%|0.26254934%|0.2 2973068%
7|||||||0.02187%|0.061236%|0.0964467%|0.11252115%
8||||||||0.006561%|0.02066715%|0.036167514%
9|||||||||0.0019683%|0.00688905%
10||||||||||5.9049E-4%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/15percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
0|85.0%|72.25%|61.4125%|52.200626%|44.370533%|37.7 1495%|32.05771%|27.249052%|23.161695%|19.68744%
1|15.0%|25.5%|32.5125%|36.8475%|39.150467%|39.9334 8%|39.6007%|38.46925%|36.78622%|34.742542%
2||2.25%|5.7375%|9.75375%|13.817813%|17.61771%|20. 965076%|23.76042%|25.966743%|27.589666%
3|||0.3375%|1.1475%|2.4384375%|4.145344%|6.1661987 %|8.38603%|10.692189%|12.983372%
4||||0.050625%|0.21515626%|0.5486484%|1.0881528%|1 .8498596%|2.8302853%|4.0095706%
5|||||0.00759375%|0.038728125%|0.11521617%|0.26115 665%|0.4994621%|0.84908557%
6||||||0.0011390625%|0.006777422%|0.023043234%|0.0 58760248%|0.124865524%
7|||||||1.7085938E-4%|0.0011618438%|0.0044440525%|0.012591481%
8||||||||2.5628906E-5%|1.9606113E-4%|8.3325984E-4%
9|||||||||3.844336E-6%|3.2676857E-5%
10||||||||||5.766504E-7%
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/10percent.png|1 scroll|2 scrolls|3 scrolls|4 scrolls|5 scrolls|6 scrolls|7 scrolls|8 scrolls|9 scrolls|10 scrolls
0|90.0%|81.0%|72.9%|65.61%|59.049%|53.1441%|47.829 69%|43.046722%|38.74205%|34.867844%
1|10.0%|18.0%|24.3%|29.16%|32.805%|35.4294%|37.200 87%|38.263752%|38.74205%|38.74205%
2||1.0%|2.7%|4.86%|7.29%|9.8415%|12.40029%|14.8803 48%|17.218689%|19.371025%
3|||0.1%|0.36%|0.81%|1.458%|2.29635%|3.306744%|4.4 64104%|5.739563%
4||||0.01%|0.045%|0.1215%|0.25515%|0.45927%|0.7440 174%|1.116026%
5|||||0.001%|0.0054%|0.01701%|0.040824%|0.0826686% |0.14880349%
6||||||1.0E-4%|6.3E-4%|0.002268%|0.0061236%|0.0137781%
7|||||||1.0E-5%|7.2E-5%|2.916E-4%|8.748E-4%
8||||||||1.0E-6%|8.1E-6%|3.645E-5%
9|||||||||1.0E-7%|9.0E-7%
10||||||||||1.0E-8%
Notes
[1] -> There may be a 0.001% error-margin on this.
[2] -> Take a look at The Art of Computer Programming - Donald Knuth if you're more interested.
[3] -> I am not sure whether this function is used or not, but this function is one of the most precise ways in order to generate random numbers, and does not require a lot of computer power when it's called.
[4] ->
http://mathurl.com/yg86ukv.png
Out from this, we see that a trinomial probability with the probabilities p, q and r is equal to:
http://mathurl.com/ykm47su.png
If we then want x scrolls to work (p) and 0 scrolls to boom (r), we get the expression:
http://mathurl.com/yf7tyj8.png
[5] -> You have to move over, divide and multiply a lot to see the expression coming up.
[6] -> This is actually a long expression for the E(1). We base ourselves on p + q = 1, q - 1 = p, and p - 1 = q:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/eqlatex-13.gif
The thing is, I want you to understand how to get to the formula I got to. By shortening the expression into this, I can't really explain it that well.
[7] -> This is not a proof for any given E(n in a row)-value. It's "easy" to prove it though, so here is the actual proof:
http://i565.photobucket.com/albums/ss91/Noah_TM/MapleStory/Scroll-probability/CodeCogsEqn3-1.gif
To-do List - Changes
To-do:
Some equations aren't in LaTeX. Whether this will be an issue or not, is at the current moment not decided. Most likely not.
Some LaTeX-equations makes it hard to read the text. I should be finding another way so it will be easier to read the text.
Some parts may contain heavy language, or may be hard to understand without proper knowledge. I want everyone to be able to understand without any additional knowledge, as long you're interested.
Illustrations may ease the reading, so it would be a good idea to find illustrations.
Some equations may be lead out in the Notes-section, for those who are interested.
Add in §8 - Scrolls in a Row - Probability.
Add in §9 - Dark Scrolls vs. White Scrolls.
Add in Appendix A - Binomial Statistic.
Changes:
March 22, 2009 - Creation of the document.
March 23, 2009 - Appendix B created and included. Appendix B is not 100% complete. Chaos Scrolls will be added in the future, if information enough is gained.
April 2, 2009 - Added in section §6 - Dark scrolls and Scroll Percentages. Also further shortened the expression leaded out in §7 in order to ease the time it takes to calculate the result. Finally, fixed certain mathematical expressions and added some more.
September 22, 2009 - Added urls, and will possibly have time to add in more data in the future.
Credits
As of today, a lot of my work has been independent of anyone. I'd however like to thank the following:
My Physics/Mathematics teacher, for being so interested and professional with the stuff he's working with.
The Online LaTeX Equation Editor (http://www.codecogs.com/components/equationeditor/equationeditor.php)
KajitiSouls - for commenting and coming up with several handy things for the document. Such as examples and stuff.