[JAVA] The end of catastrophic programming # 02 "Dice 5 and 6 are hard to come out ... I feel like random numbers are considered"

The end of catastrophic programming # 02 "Dice 5 and 6 are hard to come out ... I feel like random numbers are considered"

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.

1. Random number

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.

2. For the time being, I tried to get random values 10 billion times with Java.

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.

3. Careful adjustment of the generated values can have disastrous consequences.

ʻ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.

4. Why didn't the 5 and 6 of Sagami appear so much ...

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.

5. End

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.

6. Countermeasures

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.

  1. ʻint group = (1000/6); `to find out how many fair groups there are.
  2. Find the unfair minimum value with ʻint unfairValueMin = (group * 6); `.
  3. Check the value generated by ʻint value = rand.nextInt (1000); 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.
  4. Find (value% 6) using the value that is judged to be fair.

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

The end of catastrophic programming # 02 "Dice 5 and 6 are hard to come out ... I feel like random numbers are considered"
The End of Catastrophic Programming # 04 "Mistaken Exception Catch Range"
I checked out the versions of Blender and Python
I want to know the features of Python and pip
[Introduction to Python] I compared the naming conventions of C # and Python.
I summarized how to change the boot parameters of GRUB and GRUB2
I investigated the behavior of the difference between hard links and symbolic links
I tried hard to understand Spectral Normalization and singular value decomposition, which contribute to the stability of GAN.