Machine Learning News Hubb
Advertisement Banner
  • Home
  • Machine Learning
  • Artificial Intelligence
  • Big Data
  • Deep Learning
  • Edge AI
  • Neural Network
  • Contact Us
  • Home
  • Machine Learning
  • Artificial Intelligence
  • Big Data
  • Deep Learning
  • Edge AI
  • Neural Network
  • Contact Us
Machine Learning News Hubb
No Result
View All Result
Home Artificial Intelligence

A Study of the Most Famous Random Number Generator | by Ayoub Omari | Sep, 2022

admin by admin
September 13, 2022
in Artificial Intelligence


Explaining the linear congruential generator and its weaknesses

Photo by Edge2Edge Media on Unsplash

If you have been programming for a while, chances are you have worked on random number generation in some project or another.

I didn’t question how random number generation works the first time I worked with random numbers in a program. I have been assuming that the generated numbers are truly drawn randomly.

However, the question could be raised by a simple thought.

Any program is made up of a specific sequence of instructions. If we provide an input to it, we get the same output each time we provide that input. We call this property determinism. Trying to generate random numbers using a program is trying to get random behavior from a deterministic tool, which is kind of a paradox…

Realizing that it is not possible to get a truly random number generator with a computer, researchers had an idea: It is sufficient to get sequences that seem random.

After all, no one is able to tell if a sequence of numbers was drawn randomly or not. There is always a non-zero probability to get any sequence of numbers we can think of, provided that each of those numbers falls within the range this generator is working on.

For example, a random number generator may return the same number a thousand times in a row. The probability is indeed low, but it is still possible.

A regular person won’t be satisfied with a random number generator that returns the same number several times in a row, or with sequences such as:

  • 3 -> 4 -> 5 -> 6 -> 7 -> …
  • 2 -> 6 -> 18 -> 54 -> 162 -> …
  • 2 -> 4 -> 16 -> 256 -> 65536 -> …

What do such examples have in common that make us unsatisfied? They have an easy-to-detect pattern.

It may surprise you, but did you know that most random generators aren’t more complicated than that ?

Instead of returning the increment of the previous number, its multiplication by 3, or its square, the most famous random number generator, which had been widely used until recently, does the following:

Where a and b are chosen constants. M defines the range of numbers we generate.

With this function, we are able to generate sequences such as:

72 -> 5 -> 614 -> 37 -> 140 -> …

As users, we don’t see any pattern in this sequence. So we may say it is random. If someone is familiar enough with the function, this can be a pattern for them to say that the sequence was probably drawn using this specific function.

This random number generator is called the Linear Congruential Generator.

In the following sections, we shall discuss how bad this random generator is, and attempt to improve it.

Is the linear congruential generator a good random generator ?

To evaluate the quality of random number generators, we will use two visualizations: Bitmap and Random Walk. Both of these methods evaluate specific bits of the numbers we generate.

Let’s first choose a linear generator by fixing a, b, and M. It has been proven that the best linear congruential generators satisfy the following conditions:

  1. M and b are relatively prime
  2. a-1 is divisible by all prime factors of M
  3. a-1 is divisible by 4 if M is divisible by 4

Let’s choose the values that had been used in C language for the function rand (which obviously satisfy the conditions above).

The bitmap of the most significant bit gives the following:

Bitmap of the most significant bit

Each generated number Xn+1 is represented by a pixel. If the most significant bit of the number is equal to 0, the pixel is black, otherwise it’s white.

The bitmap is indeed random and we don’t have any pattern.

Let’s see what a 2D random walk gives.

Random walk using 31st and 30th bits

With a 2D random walk, we evaluate 2 bits at the same time. Two bits give four possible values. Based on the value, we move in one of the four directions up, down, left, right. Here we are evaluating the two most significant bits (31st and 30th) of Xn+1.

The random walk looks really random and shows no pattern. Shall we say this is a good random number generator ? Not before evaluating the other bits.

Let’s evaluate a bit in the middle, such as the 15th. Following are the bitmap and the random walk for that bit.

Bitmap of 15th bit
Random walk using 15th and 16th bits

This time it’s a different story, and we can see some patterns. In the bitmap, you can see some lines of the same color. In the random walk, you can see that the shape is symmetric on a diagonal axis and repeats forever… This is not good news for supposedly “random” behavior.

Let’s see what happens with the first bit (the rightmost bit).

Bitmap of 1st bit
Random walk using 1st and 2nd bit

Well, there is nothing random in these two results. If you zoom in the bitmap, you find alternating black and white pixels. In the random walk, it goes up, down, right, left and repeats forever. Why does that happen ?

The first bit is the parity bit, the one that indicates if the number is even or odd. If you take any sequence with this random number generator you will see that every odd number is followed by an even number, and every even number is followed by an odd number, like the sequence we saw earlier in this article. Hence, the first bit is alternating between the values 0 and 1. This explains the bitmap figure. For the random walk, the direction is determined by the first and second bit. As we will see in the next sections, there is a cycle after four steps.

If you do the same for the remaining bits, you will conclude that the pattern gets clearer and the randomness gets worse as we go to the right in the bits.

In the following section, we will study why this happens.

With the linear congruential generator, the first bit of X{n+1} is solely determined by the first bit of a, Xn, and b. For odd a and odd b, we get from the equation:

  • if Xn is odd then X{n+1} is even
  • if Xn is even then X{n+1} is odd

This justifies the result of the bitmap in the last section.

So maybe a different parity of a or b may solve our issue with the first bit ? Let’s see that in the following table.

From this table, only odd a and odd b are able to give us all possible numbers. Hence, we can’t do better than the result we got. We say that the period of the first bit is of length 2, because we have a sequence of length 2 that repeats forever.

Similarly, let’s examine the conditions on a and b that allow to get all possible values of the second bit. This time, the second bit of X{n+1} depends both on the first and the second bit of a, b, and Xn. The following table gives the sequence of values of the first two bits of X{n+1} depending on the first two bits of a and b.

Here as well, the sequence of the first two bits repeats itself. But only a ending with 01 gives all possible four values for X{n+1} before the cycle. Hence, that’s a new condition on a to get all possible values of the first two bits.

  1. a and b should be odd
  2. a should end with 01.
    In other words
    a mod 4 = 1.
    In other words a-1 should be a multiple of 4

We retrieve here one of the conditions of the theorem we saw earlier about optimal linear congruential generators (condition n°3). Because M=2³¹ is a multiple of 4, a-1 should be a multiple of 4.

What we’ve got so far:

  • 1st bit: period of length 2
  • 2nd bit: period of length 4

And if you iterate on the following bits, you get similarly:

  • 3rd bit: period of length 8 at most
  • 4th bit: period of length 16 at most
  • ….
  • 31st bit: period has length 2³¹ at most

Moreover, the two conditions we fixed above on the first two bits of a and b are sufficient to get the maximum period for all the remaining bits. This is why the condition “a-1 should be a multiple of 4 if M is a multiple of 4” appears in the final theorem.

To sum up, because they have a greater period, the upper bits get better randomness than the lower bits.

From the previous section, we understand the reason why the ith bit has a period of length 2^i. It’s because the ith bit of X{n+1} depends only on the first i bits of Xn. 2^i is the maximum number of combinations we can get with i bits.

So, we need a way to make the first bit depend on the other bits as well. Addition and multiplication only propagate bits to the left. Is there any operation that propagates bits to the right ? A division !

For example, if we want to make the 1st bit of X{n+1} depend on the 3rd bit of Xn. We divide Xn by 4, this is equivalent to shifting the bits of Xn two steps to the right.

So let’s update our linear congruential generator with this:

Let’s now see if this improves the randomness of the 1st bit.

Bitmap of 1st bit for aX + b + (X >> 2)
Random walk using 1st and 2nd bit for aX + b + (X >> 2)

This greatly improves the randomness of the 1st bit! There are some patterns in the bitmap (see the black dots), but it’s much better than alternating black and white.

Let’s see if we are still good with the 31st bit.

Bitmap of 31st bit for aX + b + (X >> 2)
Random walk using 31st and 30th bits for aX + b + (X >> 2)

Well, not so good, now we get patterns in the bitmap (see the black dots), and you can see a shape repeating indefinitely in the random walk.

We can try another amount to shift with. For that, I wrote a program that returns the period for different shift amounts. Here is the result:

No amount gives the maximum period of 2³¹. Hence, this form of functions does not solve our issue without impacting the period of the random number generator.

It’s not easy to study variants of the linear congruential generator that solve the issue of lower bits and at the same time achieve a maximum period length. The tuning of a and b has been proven for aX+b and any variant should be studied well enough so as not to fall into a short cycle. I tried different versions of the function such as the following. Each time I get a shorter cycle:

  • X{n+1} = (aXn + b + X >> 2) mod M
  • X{n+1} = (aXn + b + sum i from 1 to N (X >> i)) mod M
  • X{n+1} = (aXn + b + xor i from 1 to N (X >> i)) mod M
  • X{n+1} = (aXn + b + sum of N-1 most significant bits) mod M
  • …

If you give it a try, perhaps you may find a variant that solves both period and lower bits issues!

It was quite surprising for me to find out that one of the most famous random number generators was not random at all. In this article, we have seen how the linear congruential generator fails to get seemingly random sequences for the lower bits of the numbers it generates. We also used two methods of visualizations that help evaluate a random number generator with the naked eye.

Today, there are more advanced random generators that don’t have the issue of lower bits such as Mersenne Twister, which is not as simple as the linear congruential generator, but would definitely deserve the time to understand how it works.



Source link

Previous Post

Why is Data Represented with Vectors / Matrices? | by Nabib Ahmed | Sep, 2022

Next Post

We need to know if it is worth it — privacy-preserving AI for drug discovery | by Miquel Duran-Frigola | ersiliaio | Sep, 2022

Next Post

We need to know if it is worth it — privacy-preserving AI for drug discovery | by Miquel Duran-Frigola | ersiliaio | Sep, 2022

3 Tested Techniques to Recover Your Failing Models

AI in Renewable Energy. AI and ML in Renewable Energy | by Tech in 3 | Sep, 2022

Related Post

Artificial Intelligence

Exploring TensorFlow Model Prediction Issues | by Adam Brownell | Feb, 2023

by admin
February 2, 2023
Machine Learning

Different Loss Functions used in Regression | by Iqra Bismi | Feb, 2023

by admin
February 2, 2023
Machine Learning

How to organize bills? – 3 ways to track bills

by admin
February 2, 2023
Artificial Intelligence

How to decide between Amazon Rekognition image and video API for video moderation

by admin
February 2, 2023
Artificial Intelligence

The Future of AI: GPT-3 vs GPT-4: A Comparative Analysis | by Mohd Saqib | Jan, 2023

by admin
February 2, 2023
Deep Learning

6 Ways To Streamline Tech Hiring With A Recruitment Automation Platform

by admin
February 2, 2023

© 2023 Machine Learning News Hubb All rights reserved.

Use of these names, logos, and brands does not imply endorsement unless specified. By using this site, you agree to the Privacy Policy and Terms & Conditions.

Navigate Site

  • Home
  • Machine Learning
  • Artificial Intelligence
  • Big Data
  • Deep Learning
  • Edge AI
  • Neural Network
  • Contact Us

Newsletter Sign Up.

No Result
View All Result
  • Home
  • Machine Learning
  • Artificial Intelligence
  • Big Data
  • Deep Learning
  • Edge AI
  • Neural Network
  • Contact Us

© 2023 JNews - Premium WordPress news & magazine theme by Jegtheme.