Today, pseudo-random number sequence generators are actively used to solve a large number of applied problems of statistical and simulation modeling in such areas as telecommunications networks, automated control systems for production processes and infrastructure, security systems and others. Such generators have serious requirements for the sequence of numbers that they generate at their outputs. These are, first of all, the requirements for their randomness. The original sequences should be almost indistinguishable from the truly random ones. And, most importantly, they must also ensure a high uniformity of probability distribution of the original numbers. It is shown that the non-uniformity of numbers at the output of the primary generator significantly affects the quality of modeling of stochastic processes that take place in systems for which computer models are built. Tests on a linear congruent generator and a Mersenne twister (MT) generator have shown that the flow of decimal real numbers at their outputs does not fully meet the needs of modern computer modeling. The vast majority of tests of such flows using the Pearson chi-square test gives an unsatisfactory result. Based on the analysis of post-processing methods of numerical sequences, it is proposed to perform preliminary thinning of the input in relation to the model of the numerical flow by removing elements that do not fit into the uniform distribution. The expected sum of random real numbers to be included in each of the segments of the random number distribution histogram is chosen as the thinning criterion. It is shown that the use of this method of post-processing of the primary generator does not require extra computing resources of the system.
If in the second half of the last century modeling was considered a secondary stage in the design of complex systems, today the modern development of computer technology significantly increases its importance in the study of stochastic processes that occur in modern production, infrastructure management and economic activity.
Usually the modeling of random processes
takes place in two stages: first a sequence of
random variables evenly distributed on the
interval [
Libraries of modern programming languages
already contain PRN generators with a uniform
distribution law, which return the number from
the finite set {0, 1, … , − 1}. It is also possible to
connect external libraries offered by different
developers. Most traditional PRN generators are
well described by Donald Knuth in [
The vast majority of PRN cryptographic
generators developed in recent decades have been
described in detail by Bruce Schneier in [
Recently, an algorithm known as the Mersenne
Twister (MT) has been proposed for modeling
purposes, which provides an extremely long
repetition period 219937 − 1 [
The two-stage modeling scheme is very sensitive to the uniform distribution of numbers at the output of the selected generator. As shown by checking the flow of real numbers generated by LCG and MT using Pearson's 2-test, up to half of the samples, regardless of their size, are not tested for uniformity.
Since the choice of PRN generator is extremely limited for researchers, this problem should be solved by upgrading the numerical flow at the output of the PRN generator.
To check the quality of pseudo-random
number generators, a large number of test packets
were created [
The general idea of additional processing of
numbers at the output of the generator was
formulated long ago, when the main source of
random numbers were physical noise occurring in
electronic devices, such as electronic lamps,
quantum generators and the like. Its essence is to
sacrifice a certain number of numbers at the
output of the generator for the sake of obtaining
an output stream that would satisfy the conditions.
Later, von Neumann remarked on the
inadmissibility of using physical generators in
computer technology, because due to technical
difficulties the possibility of re-implementing the
obtained sample of random numbers at that time
was absent and, therefore, proposed algorithms
for generating pseudo-random numbers as the
method of mean squares [
At the moment, we can identify the following
four methods of post-processing: [
1. Ad hoc simple correctors. 2. Whitening with hash functions. 3. Extractor algorithms. 4. Resilient functions.
The general requirement for all methods of post-processing is the minimization of resources for their implementation.
An example of a simple corrector is the
corrector described by von Neumann in [
Later, other, more advanced versions of similar correctors were proposed, but they also work at the bit level.
Whitening is a
method that reduces the correlation of symbols at the output of the entropy source and increases the homogeneity and uniformity of the distribution of symbols in the output stream. It is usually performed using hash algorithms, such as MD5, SHA-1, SHA-2, SHA256 or
SHA-512.
This
processing
is
a
deterministic algorithm that converts input blocks
of characters of arbitrary length into a fixed size
string. In [
extractors are
algorithms that
convert a low-quality stream of input values into
an almost uniform stream of numeric characters
with a small number of guaranteed random bits.
Formally, the method of such a transformation is
described in the work of Luke Trevisan [
| [ ( ) = 1]| − | [ ( ) = 1]| ≤
In the general case, the ( , ) -extractor converts the flow of random variables X into an almost uniform flow by the rule: ∶ {0,1} × {0,1} → {0,1} , (1) (2) where the random variable X has a minimum entropy , and is a uniformly distributed quantity on {0,1} . The mechanism of operation of the randomness extractor is shown in Figure 1.
In [
From the above we can conclude that the work on creating generators of random and pseudorandom numbers is mainly focused on cryptographic needs. At the heart of such generators is a complex computational process, the implementation of which requires significant computing resources. For modeling purposes, either LCG or MT generators are typically used, which have unsatisfactory uniformity in the distribution of the source symbols, but can be subject to post-processing methods such as combining streams from multiple sources and thinning them by removing symbols that look like “ not random enough ”.
Computer simulation of random processes
such as request flows in telecommunication
systems [
Such systems are understood as arithmetic generators of pseudorandom numbers, which are based on recurrent relations. This
means that each subsequent
number at the output of the generator is
determined by one or more pre-formed numbers
and the flow of such numbers will be repeated
regularly with period . Despite this dependence,
the numbers generated by the generator should
look independent throughout the period. only in
the case of their absolutely uniform distribution.
Such numbers, evenly distributed on the interval
[
have the properties of uniform
The first condition is not met by the definition of PRN, but this shortcoming developers are trying to compensate by creating algorithms for generating numbers with too long a repetition period. Both LCG and MT generators have fairly long periods. The problem for them is the need to initialize them with a real random number, but it is quite simply solved by forming such a number from the current time.
The second condition can be formally described as follows. The general sequence 1, 2, … can be considered completely uniformly distribute (CUD), if for any ≥ 1 part of this sequence ( , +1, … , + +1) = 1, 2, … will also be evenly distributed.
In [
with the optimal ratio of the coefficients , , of the recurrent ratio +1 = ( + ) .
(3)
As practice shows, the function rand() is built into most modern programming environments and uses as a module
32-bit machine bit word, which provides a period of repetition of numbers T at the output of the generator, which does not exceed the value of
= 232. As for the uniformity of the distribution of the output stream, it remains extremely low. the distribution of numbers at the output of the LCG, obtained using the function rand(), which is part of the library C ++. The value of the sample N is 1024 numbers, and the number of intervals of the histogram is 16. the 2 −test showed that more than two-thirds of the samples do not meet the requirements of uniformity. Figure 3 shows the distribution of the number of hits in each of the 16 intervals of the histogram, Figure 2. Here are the limits of the intervals of the histogram (Xmin, Xmax), the probability of hitting the number in the interval (Pi), the number of hits in the interval (Ni) and components indicator 2 −-test (Hi), for each specific interval of the histogram. distribution of sample numbers between them
The total quality index according to Pearson's 2 −-test is calculated by the formula 2 = ∑ =1 ( − ∗)2 ∗ where – this is the number of segments of the histogram, and ∗ – the number of random numbers of the output stream that actually fell in the i-th interval and their expected number, respectively. The expected number with uniform (4) example is 64. distribution ∗ is defined as / and for the given
Similar tests were performed for the MT
generator. Unlike the LCG generator, it has a
much longer repetition period, which is equal to
= 219937 − 1 bits, and the algorithm embedded
in it provides very little correlation between two
samples from the original sequence of numbers.
The developers of the generator claim that it
passes the tests of the DIEHARD package [
To evaluate the numbers distribution uniformity
influence at the output of the MT generator on the quality of the simulation, consider the example of creating a numerical flow, which is described by the Weibull function with two parameters. It looks like this: (5) (6) (7) (8) ( , , ) = 1 − −( / ) . where
– is a scale parameter, – form parameter, а – variable. і – are fixed values for which the conditions > 0, > 0 must be met. In case if = 1,
= 1 + ⌊ 2 ⌋ where number of histogram segments, and – the number of characters in the random number sample. This formula is derived from the binomial distribution and implicitly assumes work with the normal distribution.
There are other formulas that also allow you to
determine the approximate number of segments.
A good option is the formula proposed in 1981 by
Freedman and Diaconis [
We assume that at the output of the MT generator there is a flow of numbers 1, 2, … which express the probability of events of the random Weibull process. Then, using relation (6), we can obtain a stream of numbers 1, 2, …, which in accordance
with this principle, is determined by relation (5) and expresses the argument of the distribution function.
Next, we construct a histogram, on the basis of which we calculate the quality index by the 2test. The choice of this criterion is determined by the fact that, firstly, its use is not limited to the type of distribution and, secondly, if this criterion is not met, then all other criteria, too, are unlikely to be met.
A separate issue in the special literature is the choice
number of segments of the histogram. They should be sufficient so that the shape of the histogram in its form as close as possible to the form of the Weibull distribution density function described by the expression: ( ) =
−1 −( / ) .
On the other hand, the number of segments should
not be too large so as not to lose the filtering
capabilities of the histogram, as is the case with
signal quantization. Today there are several
different ways to determine their number and the
most popular is the formula proposed in 1926 by
Sturges [
(9) (10) (Pi), the number of hits in the interval (ni), the expected number of hits in the interval (Ni) and the component indicator 2-test (Hi). where and are, respectively, the maximum and minimum values of the members of the sample variation series.
All the proposed methods for calculating the number of segments of the histogram were determined based on the problem of finding the type of distribution based on the accumulated statistical material and, each time, the researchers proceeded from the features of the process to be evaluated. That is why there are so many ways to determine the value of k. As for the simulation, the inverse problem is solved here, when the method of distribution of random variables is known and, therefore, the value of the number of segments is not so critical and can be determined arbitrarily.
method converts a sequence of random numbers from the
MT
generator into a random Weibull process with the
parameters = 1.3, = 0.1, it will look like
(4), very few random numbers fall into the last
segments of the “tails” of the distribution and,
therefore, these components of the indicator
2test contributes the lion's share to the error, which
brings its value closer to the critical value к2р. In
[
with less than 6 numbers into one common interval. For the example shown in and therefore they are combined into one interval, for which = 9, and ∗ = 8. At the level of five percent error (λ = 0.05) for the given example, its value is 2 = 17.723577, which is more than the critical value к2р = 7.290644, and this means dissatisfaction with the simulation result. This result is confirmed in the vast majority of subsequent tests and, thus, it can be concluded that it is necessary to correct the numerical flux at the output of the MT generator by post-processing.
As can be seen from the above analysis of postprocessing methods, the vast majority of them were developed for cryptography and, therefore, are unacceptable for the correction numerical flow at the output of the MT generator due to their excessive complexity. The solution to the problem should not burden the computer system with significant additional resources.
Given the admissibility of such operations as combining numerical streams, their "bleaching" or "sieving", as well as the use of Pearson's 2-test to assess the uniformity of number distribution, we will try to "align" it by removing from its composition "extra" elements . obtained at the output of the MT generator after post-processing
It is expected that in the case of uniform distribution in each segment of the histogram should fall the same number of random numbers equal to ∗ = / . The mathematical expectation of a quantity to be included in a segment bounded by the conditions = ( + )/2.
≤ < Then
is defined as the number of numbers that fall into the i-th segment , will be approximately equal to the value of ∗ = ∗ . Of course, each time this sum will be either less than ∗, or more than ∗, but there will be no significant difference. This makes it possible to formulate such an algorithm. If the sum of the numbers that fall into the i-th segment of the histogram exceeds the value of ∗, then all other numbers that fall into it are skipped. Of course, the number of numbers in the segments will remain different, but the unevenness of the sample will be smaller. their filling with numbers from the output of the MT generator after post-processing λ = 0.05 2 = 0.3438, which is less than critical value к2р = 7.2609.. shown in Figure 9 and the components of the 2distribution of numbers between them for Weibull distribution after post-processing For the given example for λ = 0.05 , 2 = 4.10807, which is less than the critical value к2р = 7.260944.
Subsequent tests showed that the use of the proposed method of "thinning" the input stream from the MT generator, gives significantly better simulation results in terms of their reliability.
The experience of modern computer modeling shows that the use of specialized software packages such as Boost, Glib, C ++, Python, Ruby, R, PHP, MATLAB and Autoit requires significant computing resources and therefore the simulation of stochastic processes is better performed using common tools programming in languages that allow you to create economical program code. Modern C ++ programming environments, such as Visual Studio and QT5, are a good option. They include a large number of additional libraries containing various PRN generators.
Such generators are built on the basis of recurrent algorithms and do not provide a given level of uniformity of distribution of real numbers in the output stream and, therefore, their use for modeling significantly affects its quality.
The problem of improving the quality of modeling can be solved by supplementing the algorithm for calculating operations that provide pre-randomization of the input stream. As such operations, you can use the removal of the original numbers, the presence of which violates the uniformity of the distribution of the primary generator. One way to implement such an algorithm is to limit the number of characters in each segment of the histogram by the value of the expected sum of random numbers, which is determined by the mathematical expectation of the number in the segment and the expected number of numbers in the segment. Tests show that the unevenness of the primary generator with this method of post-processing has almost no effect on the quality of modeling.