Severian
Joined: Dec 12, 2003
|
Posted:
Jan 06, 2004 - 16:55 |
|
At my request, fellow coach DokMatrix put together a random number testing program that tested the distribution of the Java random.nextInt() and random.nextDouble() results. Correspondence is found at the bottom of this post, but for the impatient I'll post the results of using both d6 generators (int and double) after 10,000,000 rolls!
Here you go, 10,000,000 dice rolls:
Test ran on die implementation: Integer D6 Implementation
Number of rolls for this die : 10000000
Number of times each value appeared:
1: 1667055
2: 1666303
3: 1665862
4: 1666378
5: 1667096
6: 1667306
Test ran on die implementation: Double-Precision D6 Implementation
Number of rolls for this die : 10000000
Number of times each value appeared:
1: 1667349
2: 1665936
3: 1665004
4: 1668649
5: 1664529
6: 1668533
And, for illustrative purposes, 139 dice rolls:
Test ran on die implementation: Integer D6 Implementation
Number of rolls for this die : 139
Number of times each value appeared:
1: 25
2: 28
3: 29
4: 17
5: 17
6: 23
Test ran on die implementation: Double-Precision D6 Implementation
Number of rolls for this die : 139
Number of times each value appeared:
1: 19
2: 27
3: 32
4: 28
5: 19
6: 14
Conclusions
You can see that truely distributed random numbers are subject to natural streaks of "good" or "bad" luck. In fact, the best way to get a random distribution from such a small sample as 139 rolls is to fake it by having predetermined nubmers for each result. So let's say you'll roll 120 times, have your random number generator in fact pick results out of a bag that has 20 one's, 20 two's, and so on.
DokMatrix's Excellent Email
Severian and IG-72:
Granted, you can read all of this from the Java API documentation for the Random class that appears in the java.util package, I guess seeing is believing. So, for your pleasure, I have gone ahead and written up a command-line program that you can run to test the randomness of your Java random number generator. Attached to this e-mail is the JAVA source file, the CLASS files, and an output listing that the program generates when ran using the defaults.
To run the program yourself, just put all of the class files in the same directory and then open a command-line shell. Change the directory such that you are in the directory where the class files reside. Then, assuming your PATH environment variables are set correctly, type the following:
java TestRandomness
This will run the program with the default options of testing all the different die implementations I created by rolling each die 100,000 times. You can change which report(s) the program generates and the number of times each die is rolled. The usage instructions for the program are as follows:
java TestRandomness [-wrong|-intd6|-doubled6|-all] [rolls]
If no switches used, default runs all implementations of D6 for 100,000 rolls each.
If switch is used:
-wrong Displays wrong implementation of D6
-intd6 Displays integer implementation of D6
-doubled6 Displays double implementation of D6
-all (default) Displays all implementations
[rolls] Number of desired rolls for each test
Now, for a word on the randomness of a pseudo-random number generator: there is no such thing as random in a random number generator. A random number generator is a math function that just gives the appearance that the numbers the function returns look random. Obviously, because a math function is used to generate the numbers, the output of the generator is deterministic. Random number generators are programmed to use a math function that generates numbers with probabilities such that the numbers are normally distributed. That is, the probability a given number comes up in the sequence generated would be close to, if not equal to, its ideal probability. Java uses a linear congruential generator, which is basically a linear function that incorporates the upper and lower bound numbers and the seed.
Java's random number generator does the best job it can within hardware limitations to generate random number sequences that are normally
distributed. Because of the nature of floating-point numbers, which are inherently difficult to represent exactly (or at all) within the machine, some numbers cannot be generated by the random number generator almost at all. This limitation is spelled out in Java's documentation. The 0.0 (inclusive) to 1.0 (exclusive) range is something you see a lot in Java where the upper bound is excluded. I don't know why they do this, but they do.
In earlier versions of Java, the random number generator did not generate a normal distribution. The earlier generator was biased toward the lower end of the range. Today, however, there is nothing wrong with Java's random number generation according to its documentation. It does, in fact, generate an approximately normally distributed sequence of random numbers in the given range which is reproducible. It is only approximatley normally distributed because of the way Java generates the random bit sequence that it uses to eventually generate a random number and because of hardware limitations.
This does not mean that someone can't implement the random number generator incorrectly, which is why I coded up the WrongDie class. This implementation is incorrect because of the way Java implements nextDouble(). Someone writing code for this would expect the generation range to be between 0 and 1, inclusive for the whole range. However, nextDouble() will never return 1, so consequently, the expression will never return a 6. All of the other classes are implemented with a correct expression to generate random numbers from 1 to 6; WrongDie will only generate numbers from 0 to 5.
And that should be enough on the subject for now. Any other questions/discussion, fire away. Otherwise, I leave you the program to play with and the source code to peruse.
-Dok |
|
|
BadMrMojo
Joined: Aug 02, 2003
|
  Posted:
Jan 06, 2004 - 17:38 |
|
|
Rampage76
Joined: Aug 02, 2003
|
  Posted:
Jan 07, 2004 - 13:17 |
|
Just as I´ve thought all along.
The random dice generator is random. |
|
|
Carl_Stoneyard
Joined: Nov 14, 2003
|
  Posted:
Jan 08, 2004 - 11:00 |
|
Randomness? Can somebody please tell me what randomness really is?
In 1927, Albert Einstein and Niels Bohr debated the issue for several days. At this physisist conferance in Belgium, they stayed up all nights thinking about new arguments until they both were completely exhausted. Most physisists today would say that Bohr was right, but the issue is not completely settled even in this day.
Personally, I am on Einsteins side, and I like his statement: "God does not play dice". I, however, play a lot of dice, both normal ones and electronic ones on the net. The normal and electronic dice have much in common: the outcome of the rolls are completely deterministic. If you know all the fact that the roll is based on, then you know the outcome of it. I don't know all the facts (and hopefully the people I play aganist don't know them either) so to me, the outcome is random. I think randomness is simply lack of knowledge. |
|
|
Severian
Joined: Dec 12, 2003
|
  Posted:
Jan 08, 2004 - 15:48 |
|
Carl_Stoneyard wrote: | The normal and electronic dice have much in common: the outcome of the rolls are completely deterministic. If you know all the fact that the roll is based on, then you know the outcome of it. |
I used to think this as well, but aren't physical dice considered part of a chaos system, like the weather? Chaos systems aren't deterministic. I guarantee that computer random number generators are, but chaos systems can have the same number input two times in a row and get different results. That's weird to me, and probably weird to Einstein and Bohr. It was weird to the first people who designed weather software, too. They thought something was wrong with their machines...
I don't want to debate about the "true" meaning of randomness or anything. This thread is about a "sufficiently random" Java generator. But this web page has some interesting information on Chaos Systems if you want to read about it: Chaos and non-linear dynamics, and The Butterfly Effect
We must be careful that we don't wander too far into the theoretical. Suffice it to say that Java is Sufficiently Random, and us hummies can't tell the difference. |
|
|
Jugular
Joined: Aug 02, 2003
|
  Posted:
Jan 08, 2004 - 16:00 |
|
ARGH Chaos Theory. The universe is deterministic, a chaotic system is just an unstable one. Two slightly differing inputs give wildly different results. The Maths following that just helps us classify, isolate patterns and glean all the info possible from the fact that it is sufficiently chaotic. Either way it is irrelevant the randomness of the number generator is impenetrable to mild analysis and therefore is sufficiently random and noone is being cheated nor could anyone cheat with it. |
|
|
Severian
Joined: Dec 12, 2003
|
  Posted:
Jan 08, 2004 - 16:08 |
|
Jugular wrote: | The universe is deterministic, a chaotic system is just an unstable one. |
That's a bold statement. If it's impossible to know enough facts to completely describe the initial state of a system, you're only assuming it's deterministic in the first place, right? Because you'll never prove it.
And I'm curious what you mean by an "unstable deterministic system?" |
|
|
Jugular
Joined: Aug 02, 2003
|
  Posted:
Jan 08, 2004 - 17:26 |
|
It is a bold statement I know. It's not proved nor could it ever be proved. It's my one and only belief system unstable deterministic system......a system in which the slightest difference in inputs provides a seemingly unrelated result. It's 'stability' (probably the wrong word to use) is seperate from the fact that its deterministic. Whether or not you know it's deterministc doesn't change whether or not it provides choatic results. I'm sorry i cant explain this satisfactorily nor am I certain about my statements. I have read a few books on Chaos Theory I'm not an authority |
|
|
Guest
|
  Posted:
Jan 10, 2004 - 20:24 |
|
I would like to add something to your RNG discussions. It depends on how the RNG system is implemented as to whether the results will hold above.
1. There are statistical tests for randomness: Chi-Square and Kolmogorov-Smirnov Test. I would use empirical results from these to validate your randomness claims then by eyeballing frequencies.
2. Is a team really using 10 million numbers in a single game? I highly doubt it. Which would leave me to believe that the model used above is flawed. I would bet is more likely thousands or tens of thousands.
3. Are both teams are using the same random number generator? Let's say a team got every other number. If you look at the frequencies and do a proper statistical analysis test for randomness (Chi-Square Test) the random number generator fails the statistical randomness test.
4. The results shown above by Dok and Severian are correct, and would probably pass the statistical tests mentioned. By the real question is that model appropriate for the game at hand? I don't know without input from the games creator. What you'll need is to know approximately the number of random dice throws per turn per person, and how the random number generators are distributed within the game. Ideally, everything that requires a random number generator should have their own, and each should be seeded (i.e. initialized) differently. |
|
|
Fudge
Joined: Sep 29, 2003
|
  Posted:
Jan 10, 2004 - 21:18 |
|
But you can say that random as such can not excist, every outcome of everything is brought on from a series of events.
If random as a fenomena excisted, statisticly the universe should have run into a reality pharadox and sized to excist.
Following this resoning with all variables gven everything can be calculated.
The other way to look at it is there is a divine power that can override the laws of physics, and thus prevent a paradox.
So if randomness excists so does God, and then there should be no randomness since he decides all so in conclution total randomness does not excist |
|
|
cyric2121
Joined: Jan 01, 2004
|
Posted:
Feb 18, 2004 - 19:48 |
|
Sorry sev, but it would seem that you and Dok have way too much free time on your hands |
|
|
BadMrMojo
Joined: Aug 02, 2003
|
  Posted:
Feb 18, 2004 - 21:12 |
|
Fudge_it wrote: | ...So if randomness excists so does God, and then there should be no randomness since he decides all so in conclution total randomness does not excist |
Ah, can God roll dice and not know the outcome?
If he can then he's not omniscient and therefore not God.
If he can't then he's not omnipotent and therefore not God.
Therefore, God does not exist. (Unless you're a Nuffle worshiper and then you know that there will always be a 1 when you least expect it.)
Happy? Are you?! Three thousand years of monotheism down the toilet thanks to a stupid random number generator algorithm.
|
_________________ Ta-Ouch! of BloodBowl
Condensed Guide for Newbies |
|
Michael_Warblade
Joined: Aug 02, 2003
|
  Posted:
Feb 18, 2004 - 23:32 |
|
Chaos Theory (also refered to as Hyper-sensitive Dependence on Initial Conditions) is Determininsitc in that the same input returns the same output however 2 slightly different inputs produces wildly differing outputs. The reason why chaotic systems are called unstable is because of the dependence on the initial conditions
Here is a short paper on Chaos theory
http://www.duke.edu/~mjd/chaos/chaosh.html |
|
|
shadow46x2
Joined: Nov 22, 2003
|
  Posted:
Feb 19, 2004 - 00:04 |
|
jeez louise...i go away from 2 weeks, and all you people go freaking intelligent on me...chaos theory this deterministic that....
darn it when are you people going to realize that NUFFLE RULES ALL!!!
NUFFLE DETERMINES YOUR DICE ROLLS!!!! WORSHIP NUFFLE!!!
if nuffle hates you then you're going to roll 1's.....DON'T BE THE TARGET OF NUFFLE'S IRE!!!
*grin*
--jase |
_________________
origami wrote: | There is no god but Nuffle, and Shadow is his prophet. |
|
|
Haska
Joined: Feb 09, 2004
|
  Posted:
Feb 19, 2004 - 23:18 |
|
Walks in.
*peers at the Java, gets interested, peers at the maths....*
walks out. |
|
|
|
| |