An ordinary programmer understands intuitively and reflexively, I would like to write an article about a rudimentary and simple story. It's rudimentary, but I'm a heavy programmer, so I often do it. I will write a small story as a commandment to myself.
If there are any mistakes or inappropriate content, please comment We will consider corrections and adjustments to the content.
Like Random.nextInt (),
I'm sure many programmers have used methods to get random values.
For example, a function or method that obtains a random number with an integer value of 0 or more and 9 or less
For Java Random.nextInt (10),
For C #, Random.Next (10),
For Python, it would be random.randint (0, 9).
For many programmers, the way random numbers are scattered and their periodicity is At times, the more frustrating you may feel, the more biased the values are.
Most of the time we usually deal with pseudo-random numbers, Random values are generated by the algorithm. There are various quirks depending on the algorithm used (internally used), This time, I will leave that point for now.
(** If not for encryption, ** Due to its variation and the length of the periodicity, my personal recommendation is A random number generated by Mersenne Twister. )
The following article is an example of Java, but I think it is ** the same for other languages **.
The part of rand.nextInt (10)
If you read it as rand.Next (10) for C #, random.randint (0, 9) for Python, etc., you can probably imagine it.
For the time being, let's get the random value 10 billion times with Java.
Use Random.nextInt (10) to get the random values from 0 to 9 10 billion times,
The number of appearances of each was counted.
Random rand = new Random();
long[] numCounter = new long[10];
for(long count = 0; count < 10000000000L; count++) {
int value = rand.nextInt(10);
numCounter[value]++;
}
** The result is as follows. ** **
| value of value | Number of appearances |
|---|---|
| 0 | 1,000,017,191 |
| 1 | 999,943,364 |
| 2 | 999,983,662 |
| 3 | 1,000,012,905 |
| 4 | 1,000,049,567 |
| 5 | 1,000,001,706 |
| 6 | 999,982,619 |
| 7 | 1,000,068,926 |
| 8 | 999,966,928 |
| 9 | 999,973,132 |
Regarding the variation, it may be better to analyze it mathematically, This time it's not a math session, so let's make a quick decision. Focusing only on the simple ** occurrences ** of each number for 10 billion trials, There seems to be no big problem.
In the standard Java implementation, random numbers are generated by the linear congruential method, Regarding those characteristics, I will put them on the shelf this time.
ʻInt value = rand.nextInt (10); for value of Let's calculate so that the result is the result of rolling 6 dice. The reason why you should set it torand.nextInt (6)` is ** this time, none ** tied up play.
ʻInt sainome = (value% 6) + 1; It looks like you can roll 1 to 6 on the dice. In the part of(value% 6), it changes from 0 to 5`, so after that, just add one according to the dice.
If you don't get enough sleep after the game all night long, it seems that this will be okay, but This calculation is not fair at all.
| value of sainome | Number of appearances |
|---|---|
| 1 | 1,999,999,810 |
| 2 | 2,000,012,290 |
| 3 | 1,999,979,833 |
| 4 | 1,999,986,037 |
| 5 | 1,000,049,567 |
| 6 | 1,000,001,706 |
The 1st to 4th eyes have appeared about 2 billion times, The 5th and 6th eyes have appeared only about 1 billion times, There is about a double difference.
This time, I tried it with a small number, so I think it was easy to notice.
You can easily find out by arranging the value value and the (value% 6) value side by side.
| value of value | (value % 6)The value of the |
|---|---|
| 0 | 0 |
| 1 | 1 |
| 2 | 2 |
| 3 | 3 |
| 4 | 4 |
| 5 | 5 |
| 6 | 0 |
| 7 | 1 |
| 8 | 2 |
| 9 | 3 |
In the table above, there are two 0, 1, 2, 3 as the (value% 6) value,
There is only one 4, 5.
This is not fair.
Random values sometimes frustrately vary, It can be even more disastrous, depending on how you add your care (if you want to calculate more random numbers).
This example emphasizes ease of image, and it is a fairly extreme example, so Actually, there may be few cases where you are addicted to something similar to this time, I think it's a good idea to always be vigilant when using random numbers.
In this example,
ʻInt value = rand.nextInt (6); is fine, but Let's think about ** tied up play ** that rand.nextInt (6)` cannot be done.
The borderline for fairness is likely to be whether the value value is 5 or less.
Other than that, it seems quite so by judging that it is unfair and ignoring the unfair value.
Consider the case of ʻint value = rand.nextInt (1000); . The value is a random number from 0 to 999. In this case, judge whether the value value is 5 or less, If you ignore 5 or less as unfair`, a considerable number will be ignored,
It's going to be a pretty inefficient algorithm.
What should be ignored is likely to be near 999.
| value of value | (value % 6)The value of the |
|---|---|
| ... | ... |
| 990 | 0 |
| 991 | 1 |
| 992 | 2 |
| 993 | 3 |
| 994 | 4 |
| 995 | 5 |
| 996 | 0 |
| 997 | 1 |
| 998 | 2 |
| 999 | 3 |
In this case, up to 995 is fair and from 996 is unfair.
It looks like this when it is incorporated into the algorithm.
and If value <unfairValueMin is true`, it is judged to be fair and adopted.
Other than that, as unfair
Generate a random value again and repeat the check to see if it is fair.(value% 6) using the value that is judged to be fair.Random.nextInt () etc. also have this kind of fair countermeasure.By the way, there are many cases where it is not necessary to find an excessively fair value, Using an example like this one, On the contrary, there is also a method to easily generate a biased random number value by your own will.
For example, in the example of issuing 0 to 5,
for(int i = 0; i < 100; i++) {
int value = (rand.nextInt(6) + rand.nextInt(6)) / 2;
System.out.println(value);
}
And,
for(int i = 0; i < 100; i++) {
int value = rand.nextInt(3) + rand.nextInt(4);
System.out.println(value);
}
And,
for(int i = 0; i < 100; i++) {
int value = (rand.nextInt(6) + rand.nextInt(6) + rand.nextInt(6)) / 3;
System.out.println(value);
}
It may be fun to actually move it or think about what is happening.
(In the last code, 5 rarely appears, but 2 and 3 should appear messed up.)
How much you bias depends on how you do it. In practice, you may need a more rigorous method.
Recommended Posts