This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.
Abstract- In this paper concept of multi-layer cellular automata and a novel neighborhood structure are introduced. According to these concepts, a novel approach for generating normal random numbers is proposed. First layer consists of binary cellular automata which are responsible for activating and inactivating cells in next layers. A cellular automaton with integer values is used for these layers. Interaction between layers of represented cellular automata leads to a dynamic and complex behavior of proposed model. Main idea of this model is based on central limit theorem to generate normal random numbers. To evaluate the quality of proposed model, several simulations are implemented. Results prove that multi-layer cellular automata generate better normal random numbers in comparison to MATLAB.
Keywords- Cellular Automata; Normal Random Variable; Random Number Generators
Dynamics of complex systems lead many processes in real world to be assumed stochastic and ambiguous . Due to this motivation in recent decades, scientists has paid attention to computer based random number generation in complex system simulations and attracted many researchers to introduce and develop these methods [2, 3].
Lottery, computer games, cryptography, calculation with Monte Carlo method, computer simulations, operational research and most of intelligent optimization methods such as genetic algorithm, particle swarm optimization, tabu search and other Meta-heuristics are some applications of random number generators [4, 5, 6, 7, 8]. Random numbers are generally classified into three categories as below.
Truly Random Numbers: In this category, all numbers have equal probability to be generated. This class is not periodic and the numbers don't follow any pattern. In addition, truly random numbers are not generated by specific algorithm and predicting the next element of sequence is not possible. Indeed there is no correlation among these kinds of random numbers .
Pseudo Random Numbers: Pseudo random numbers are generated by specific algorithms and it is possible to predict some subsequences by considering generated trajectory. To start the algorithm some of parameters need to be initialized. One of the most obvious problems about this category is existence of periodic sequences and specific patterns inside them .
Quasi Random Numbers: In fact, quasi random numbers are sequences of nonrandom numbers which are shuffled to be seemed random. Thus these types of random numbers are so suitable for calculation with Monte Carlo method [10, 11].
It is clear that random number generators must be adaptable with various statistical distributions due to application (e.g. uniform, normal, exponential, Poisson, Erlang). In spite of special characteristics of normal distribution, this type of distribution is less considered. According to outstanding role of normal random numbers in computer simulations, represented approach is introduced for normal random number generation.
Long periodic sequences, low computational space and time order for random number generating and low correlation among random numbers are some of the most important factors which determine the performance of a typical random number generator .
In section two random number generators will be discussed, section three is about cellular automata and then, a novel approach for normal random number generation will be introduced in section four. Section five includes results of simulations and evaluation of proposed model and finally the last section contains final conclusion and future works.
Random Number Generators
In 1927, Tippet designed table of forty thousand random numbers to be used in various applications. One hundred thousand of random numbers were generated in a table designed by Kendall in 1939. Smith followed Kendall's work and designed mechanical random generator device in 1955. The exciting point about these tables is that they were filled without any specific algorithm. In 1951 Neumann proposed a computational method (however this method had low performance). In recent decades several algorithms are developed for random number generation as below .
Linear Congruential Generators
Linear Congruential methods use specific algorithms to generate random numbers. These algorithms are iterative and to start the algorithm, an initial state is required. An instance of these algorithms is indicated in equation (1).
Where is the generated random number in previous iteration, and are constant coefficients, is Congruential module (one unit more than maximum allowed random number) and is the output of algorithm. Generated random number by this method extremely depends on its previous value. Maximum length of periodic sequences for this algorithm is .
Multiple Recursive Generator
Multiple recursive generators are like linear congruential generator, whereas they use k random numbers from previous iterations. A multiple recursive generator is indicated in equation (2).
In equation (2), are constant coefficients of algorithm, is output of algorithm in (n-i)th iteration and m is congruential module (one unit more than maximum allowed random number). The advantage of this method is that the maximum period of algorithm is which is much more than period of linear congruential method .
Lagged Fibonacci Generator
Lagged Fibonacci Generator is a special case of famous Fibonacci sequence which uses two outputs of previous iterations. Equation (3) shows the general form of this method.
Where and are the same parameters as in multiple recursive generator method. and are the indexes of numbers which were generated in previous iterations. Performance of algorithm depends on selection of these values.
Summation operator in equation (3) can be replaced by any other operator (e.g. subtraction operator). Moreover it is possible to use binary logic operators to generate random bits. In this case if the operator is exclusive OR (XOR) the method will be called transfer register generator thus the congruential operator will be neglected from equation and equation (3) will be changed to equation (4).
Output of equation (1) up to equation (3) will be random numbers between zero and m.
Blum Blum Shub Random Generator
This generator was introduced by Blum and his team in 1986, but due to slow functionality of this method it was never used in computer simulations. This method is widely used in cryptography. By using this method, random numbers will be generated via equation (5).
Where m is congruential module and usually is considered as production of two big prime numbers 
Cellular automata (CA) are discrete computational models that contain networks of completely same cells which have interaction with together within a neighborhood structure. Various neighborhood structures are proposed till now. Some of the most popular models are: Neumann, Moore, Cole and Smith which are illustrated in Fig. 1. In Fig. 1, it is assumed that neighborhood radius equals one [1, 12].
Cells state (value) is selected from a finite set. These values are changing synchronously in iterations by using of some transition rules which are same for all cells. Next states will be determined according to current values of cells and current values of neighbors .
Common neighborhood structures in cellular automata
Binary cellular automata are one of the most common simulation tools where each cell can be stated as zero or one. Transition rules are determined by Boolean algebra rules (AND, OR and NOT). Wolfram proposed to use decimal value of bit sequence of next state to name the rules .
Some of the most useful Wolfram transition rules in linear binary cellular automata are illustrated in Table I where first row is current states of left neighbor, the cell and right neighbor respectively. Next state of cell is indicated in other rows by using of specified rules. Using transition rules in Table I and starting from a random configuration leads to generate pseudo random bits. Locality of rules leads to generate pseudo random bits with desirable period .
Transition Rules in Binary CA
Multi-Layer Cellular Automata for Random Number Generating
Generating sequence of binary bits and combining these bits is one of the most popular methods used in cellular automata based random number generators. It is clear that quality of generated random numbers in such methods depends on quality of sequence of random bits. Using wolfram transition rules 30, 90, 105, 110 and 165 in isolated or hybrid manner will cause generation of period pseudo random bits.
Framing the sequence of generated random bits-base mapping-will cause to appearance of various patterns in final sequence of random numbers. Obviously appearance of patterns among sequences of random numbers means low quality of random number generator. It is possible to compensate this problem by using parallel cellular automata to some extent. However range of generated random numbers can demand large number of needed bits. In this case using independent cellular automata per bit will extremely increase memory consumption and time order.
Mismatching between range of random numbers before and after base mapping is the other problem that will cause improper results. In binary numerical systems, a binary number with length n envelopes range of zero up to 2 n-1. Thus if it is impossible to map the desired range of random numbers to such range, mapping the range will increase the chance of numbers of specific sub range to be generated. For example, five bits are needed to generate random numbers in range [0,20] but five bits envelope range of [0,31].
The simplest way to handle this problem is to ignore random numbers bigger than 20. However this method may produce patterns and reduce the quality of generated random numbers. The other approach to compensate this problem is using of linear (or nonlinear) mapping. It is clear that if the length of origin range is bigger than length of destination range, chance of random numbers to be generated won't be the same. In such condition the uniformity will reduce.
Based on this issue, in this paper a novel structure of cellular automata is proposed to be used as random number generator. Proposed model is constructed from multiple various layers of heterogeneous cellular automata. Each layer contains a two dimensional cellular automata with same size.
Cells of first layer are binary and include zero or one bits. If the goal is to generate normal random numbers in range [0, n] and the pivot be n/2 then the cells of second up to mth layers will include integer numbers between zero and n. structure of proposed model is illustrated in Fig. 2.
Multi-Layer CA for generating normal random numbers
Each row of binary cellular automata-in first layer-is assumed to be independent linear binary cellular automata. Thus each cell is adjacent with one right neighbor cell and one left neighbor cell. Associated values of cells of each row will be updated using one of the transition rules 30, 90, 105, 110 or 165.
A novel neighborhood structure-named pseudo Neumann-is applied in other layers. In proposed model-like Moore standard neighborhood structure-eight neighbors of each cell are considered as adjacent. The difference between pseudo Neumann and Moore structure is that if cells with same positions from first layer equal one they will be active, otherwise they will be inactive. If the cells of first layer generate uniform random bits, the cells of other layers will activate/deactivate with same probability. In this case about half of cells in neighborhood structure-about four cells like Neumann structure-will be active. Interaction between first and other layers of cellular automata leads pseudo Neumann neighborhood structure to be assumed as Neumann neighborhood structure with dynamic adjacency.
State of each cell of second to mth layers of automata will be updated by dividing summation of cell value and active neighbors' values by n+1. Remainder of this division is the next value of cell. According to this rule, values of cells will be between zero and n. Initial configuration of automata must be uniform. In other words, chance of integer numbers between 0 to n to be generated must be equal.
Now each cell of second to mth layers of automata is a random integer with uniform distribution. To generate a normal random number, a cell is selected from each automaton (second to mth layers). Average of candidate cells will be the final normal random number.
According to central limit theorem, if each cell of second to mth layers is considered as independent random variable, final result will be a random variable with normal distribution.
If lower bound of needed random numbers is not zero, it is possible to map the generated random numbers to desired range by using a simple linear transformation. For example if desired range of random numbers is [-100,100] then n will be initialized with 200 and -100 will be added to output results.
In this method, standard deviation principal is controllable by number of layers. In fact, according to central limit theorem more layers will result in less standard deviation.
Simulation and Evaluation of Proposed Model
In this section, simulation results of multi-layer cellular automata in random number generation will be discussed. Each layer consists of a 1000-1000 cellular automaton. States of cells in first layer are updated by using rule 30.
In the following, capability of binary cellular automata to produce random bits by using rule 30 will be discussed. Second experiment will compare the uniformity of generated random numbers by each cellular automaton of second to mth layers with MATLAB. In third experiment quality of normality of final result will be discussed.
Aim of this experiment is evaluating capability of cellular automata to generate random bits. For this purpose, simulation of linear binary cellular automata with one hundred cells is performed. In this simulation neighborhood radius was one and rule 30 is used to change the cell values. 103 random bits are generated and total numbers of ones which appeared in sequence are computed. This simulation is run for one hundred times and statistical features such as average, standard deviation and scattering length are extracted. Table II contains simulation results.
Statistical Features of Experiment 1
Table II indicates that the quality of generated random bits by using of cellular automata is very desirable and output random bits of automata follow the uniform distribution. Thus if rule 30 is used to update the values of first layer of proposed model, then cells of other layers will activate and deactivate with approximately the same probability.
Purpose of this experiment is evaluating the uniformity of generated random numbers in each layer-two to m- of proposed model. Thus, sequence of random numbers is generated by specific layer of proposed model and integer random number generator of MATLAB. Then an experiment is implemented as below.
Generate N=104 random numbers in the range of [0,100].
Classify the generated numbers in c=10 classes with equal sizes.
Compute the frequency of numbers in each class (fi).
After running these steps for one hundred times, average, standard deviation and scattering length of frequencies of classes are computed. Table III contains the experiment results. Histogram of calculated frequencies of multi-layer cellular automata and MATLAB are illustrated in Fig. 3 and Fig. 4 respectively.
Comparing Fig. 3 and Fig. 4 shows that the generated random numbers by multi-layer cellular automata are more uniform than MATLAB.
Statistical Features of Experiment 2
Histogram diagram of classified generated random numbers by Multi-Layer CA
Histogram diagram of classified generated random numbers by MATLAB
5.3 Experiment 3
According to special characteristic of normal distribution, evaluating the normality of random numbers will be different. Many methods to evaluate the normality have been introduced till now [14, 15], such as:
Normal probability plot;
Spiegelhalter's omnibus test.
Most of these methods are experimental and are based on empirical information. Among these methods Kolmogorov-Smirnov method is more popular. In addition, most of these methods are driven from Kolmogorov-Smirnov method.
The Kolmogorov-Smirnov test for normality is based on the maximum difference between the sample cumulative distribution and the hypothesized cumulative distribution or between two samples .
An attractive feature of this test is that the distribution of the Kolmogorov-Smirnov test statistic does not depend on the underlying cumulative distribution function being tested. Another advantage is that it is an exact test.
The Kolmogorov-Smirnov test is based on the empirical distribution function (ECDF). Given N ordered data points X1, X2… XN, the ECDF is defined as equation (6).
Where n(i) is the number of points less than Xi and the Xi are in ascending order.
Hypothesized distribution function FH(X) could be computed from equation (7).
Maximum distance between two distribution functions is computed and evaluated by equation (10) which is illustrated in Fig. 5.
Maximum distance between distribution functions
In this experiment, maximum distance from set point is calculated for both MATLAB normal random number generator and proposed multi-layer cellular automata. In other words, FH(x) is assumed to be equal to desired normal probability distribution function. Results of this evaluation for 102, 103, 104, 105 and 106 normal random numbers generated by proposed model and MATLAB random number generator is shown in Table IV. Table IV shows that proposed multi-layer cellular automata in this paper generates more normal results than MATLAB.
Statistical Features of Experiment 3
In this paper multi-layer cellular automata and pseudo Neumann neighborhood structure are introduced. Based on these novel concepts, a novel approach to generate normal random numbers is proposed. In this model, cells of automata which are responsible to generate random numbers contain integer values and this is against previous random number generating approaches which were based on generating random bits by using cellular automata. These cells are activated and deactivated by cells of a binary automaton in first layer. This condition leads cellular automata to obtain dynamic neighborhood structure.
Simulation results of proposed method and comparing normality quality of this method with random number generator of MATLAB proved that multi-layer cellular automata generate random numbers with more normality. Main problem of this method is initial configuration which may cause Garden of Eden.
Applying hybrid transition rules, neighborhood structures and hardware implementation can improve the performance of multi-layer cellular automata model.