A quasi-Monte Carlo scheme for Smoluchowski's coagulation equation

This paper analyzes a Monte Carlo algorithm for solving Smoluchowski's coagulation equation. A finite number of particles approximates the initial mass distribution. Time is discretized and random numbers are used to move the particles according to the coagulation dynamics. Convergence is proved when quasi-random numbers are utilized and if the particles are relabeled according to mass in every time step. The results of some numerical experiments show that the error of the new algorithm is smaller than the error of a standard Monte Carlo algorithm using pseudo-random numbers without reordering the particles.

     

Search heuristics and the influence of non-perfect randomness: examining Genetic Algorithms and Simulated Annealing

Simulated Annealing and Genetic Algorithms are important methods to solve discrete optimization problems and are often used to find approximate solutions for diverse NP-complete problems. They depend on randomness to change their current configuration and transition to a new state. In Simulated Annealing, the random choice influences the construction of the new state as well as the acceptance of that new state. In Genetic Algorithms, selection, mutation and crossover depend on random choices. We experimentally investigate the robustness of the two generic search heuristics when using pseudorandom numbers of limited quality. To this end, we conducted experiments with linear congruential generators of various period lengths, a Mersenne Twister with artificially reduced period lengths as well as quasi-random numbers as the source of randomness. Both heuristics were used to solve several instances of the Traveling Salesman Problem in order to compare optimization results. Our experiments show that both Simulated Annealing and the Genetic Algorithm produce inferior solutions when using random numbers with small period lengths or quasi-random numbers of inappropriate dimension. The influence on Simulated Annealing, however, is more severe than on Genetic Algorithms. Interestingly, we found that when using diverse quasi-random sequences, the Genetic Algorithm outperforms its own results using quantum random numbers.     

Optimal Multipliers for Linear Congruential Pseudo-Random Number Generators with Prime Moduli: Parallel Computation and Properties

Two systematic search methods are employed to find multipliers for linear congruential pseudo-random number generation which are optimal with respect to an upper bound for the discrepancy of pairs of successive pseudo-random numbers. The efficiency of these search procedures when executed on parallel systems is assessed by experimental results of a MIMD parallel implementation on a Meiko CS-2 and a workstation cluster. Furthermore the quality of the computed multipliers is evaluated by using the spectral test in dimensions 2–8 and by calculating the actual discrepancy of pairs of the resulting full-period sequences.     

On randomization of Halton quasi-random sequences

The problem of estimating the error of quasi-Monte Carlo methods by means of randomization is considered. The well known Koksma–Hlawka inequality enables one to estimate asymptotics for the error, but it is not useful in computational practice, since computation of the quantities occurring in it, the variation of the function and the discrepancy of the sequence, is an extremely timeconsuming and impractical process. For this reason, there were numerous attempts to solve the problem mentioned above by the probability theory methods. A common approach is to shift randomly the points of quasi-random sequence. There are known cases of the practical use of this approach, but theoretically it is scantily studied. In this paper, it is shown that the estimates obtained this way are upper estimates. A connection with the theory of cubature formulas with one random node is established. The case of Halton sequences is considered in detail. The van der Corput transformation of a sequence of natural numbers is studied, and the Halton points are constructed with its help. It is shown that the cubature formula with one free node corresponding to the Halton sequence is exact for some class of step functions. This class is explicitly described. The obtained results enable one to use these sequences more effectively for calculating integrals and finding extrema and can serve as a starting point for further theoretical studies in the field of quasi-random sequences.     

Parallelization of random number generators and long-range correlations

Summary Partitions of pseudo-random sequences generated by congruential schemes are investigated for use on computer systems where multiple processing units run in parallel for the solution of a Monte Carlo problem. A special partition is suggested which ensures independence between the units working simultaneously, and yields reproducible sequences. The analysis performed has brought out the existence of strong autocorrelations between terms located far apart in the sequences, dependent only on the congruential nature of the generators. The study of these correlations — carried out in a number theoretic framework — points out that only small fractions of the sequences can be safely used.     

The sub-lattice structure of linear congruential random number generators

Sequences of pseudo-random numbers are discussed which are generated by the linear congruential method where the period is equal to the modulus m. Such sequences are divided into non-overlapping vectors with n components. In this way for each initial number exactly m/gcd(n, m) different vectors are obtained. It is shown that the periodic continuation (with period m) of these vectors forms a grid which is a sub-grid of the familiar grid generated by all m overlapping vectors. A sub-lattice structure also exists for certain multiplicative congruential generators which are often used in practice.     

Quasi-random sequences by power residues

For any primep, quasi-random sequences are constructed whose elements progressively divide the unit interval intop,p ²,p ³, ... equal parts. This property of uniformity is obtained by a slight modification of the multiplicative congruential scheme for the generation of random numbers. The extension to the unit square is also discussed and comparison with other quasi-random and random sequences is made through examples.     

The serial test for pseudo-random numbers generated by the linear congruential method

Summary We consider the linear congruential method for pseudo-random number generation and establish effective criteria for the choice of parameters in this method which guarantee statistical almost-independence of successive pseudo-random numbers. Applications to numerical integration are also discussed.     

On the adequacy of pseudo-random number generators (or: How big a period do we need?)

Generating pseudo-random number sequences is central to discrete-event computer simulations. Traditionally, generators are used only after they have passed several statistical tests. We propose a new, easy-to-implement test of randomness based upon the ‘birthday problem’, which has certain optimal properties. When applied to a broad class of generators (which includes linear congruential generators) the test illuminates a previously unknown relationship between the period of the generator and the number of pseudo-random observations which can be safely used.     

More on quasi-random graphs,subgraph counts and graph limits

We study some properties of graphs (or, rather, graph sequences) defined by demanding that the number of subgraphs of a given type, with vertices in subsets of given sizes, approximatively equals the number expected in a random graph. It has been shown by several authors that several such conditions are quasi-random, but that there are exceptions. In order to understand this better, we investigate some new properties of this type. We show that these properties too are quasi-random, at least in some cases; however, there are also cases that are left as open problems, and we discuss why the proofs fail in these cases.The proofs are based on the theory of graph limits; and on the method and results developed by Janson (2011), this translates the combinatorial problem to an analytic problem, which then is translated to an algebraic problem.     

The additive congruential random number generator—A special case of a multiple recursive generator

This paper considers an approach to generating uniformly distributed pseudo-random numbers which works well in serial applications but which also appears particularly well-suited for application on parallel processing systems. Additive Congruential Random Number (ACORN) generators are straightforward to implement for arbitrarily large order and modulus; if implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.     

Pseudo random number generator based on quantum chaotic map

For many years dissipative quantum maps were widely used as informative models of quantum chaos. In this paper, a new scheme for generating good pseudo-random numbers (PRNG), based on quantum logistic map is proposed. Note that the PRNG merely relies on the equations used in the quantum chaotic map. The algorithm is not complex, which does not impose high requirement on computer hardware and thus computation speed is fast. In order to face the challenge of using the proposed PRNG in quantum cryptography and other practical applications, the proposed PRNG is subjected to statistical tests using well-known test suites such as NIST, DIEHARD, ENT and TestU01. The results of the statistical tests were promising, as the proposed PRNG successfully passed all these tests. Moreover, the degree of non-periodicity of the chaotic sequences of the quantum map is investigated through the Scale index technique. The obtained result shows that, the sequence is more non-periodic. From these results it can be concluded that, the new scheme can generate a high percentage of usable pseudo-random numbers for simulation and other applications in scientific computing.     

A block encryption algorithm based on dynamic sequences of multiple chaotic systems

A block encryption algorithm using dynamic sequences generated by multiple chaotic systems is proposed in this paper. In this algorithm, several one-dimension chaotic maps generate pseudo-random sequences, which are independent and approximately uniform. After a series of transformations, the sequences constitute a new pseudo-random sequence uniformly distributing in the value space, which covers the plaintext by executing Exclusive-OR and shifting operations some rounds to form the cipher. This algorithm makes the pseudo-random sequence possess more concealment and noise like characteristic, and overcomes the periodic malpractice caused by the computer precision and single chaotic system. Simulation results show that the algorithm is efficient and useable for the security of communication system.     

On the spanning tree packing number of a graph: a survey

The spanning tree packing number or STP number of a graph G is the maximum number of edge-disjoint spanning trees contained in G. We use an observation of Paul Catlin to investigate the STP numbers of several families of graphs including quasi-random graphs, regular graphs, complete bipartite graphs, cartesian products and the hypercubes.     

Theoretical and empirical convergence results for additive congruential random number generators

Additive Congruential Random Number (ACORN) generators represent an approach to generating uniformly distributed pseudo-random numbers that is straightforward to implement efficiently for arbitrarily large order and modulus; if it is implemented using integer arithmetic, it becomes possible to generate identical sequences on any machine.This paper briefly reviews existing results concerning ACORN generators and relevant theory concerning sequences that are well distributed mod 1 in k dimensions. It then demonstrates some new theoretical results for ACORN generators implemented in integer arithmetic with modulus M=2^μ showing that they are a family of generators that converge (in a sense that is defined in the paper) to being well distributed mod 1 in k dimensions, as μ=log₂M tends to infinity. By increasing k, it is possible to increase without limit the number of dimensions in which the resulting sequences approximate to well distributed.The paper concludes by applying the standard TestU01 test suite to ACORN generators for selected values of the modulus (between 2⁶⁰ and 2¹⁵⁰), the order (between 4 and 30) and various odd seed values. On the basis of these and earlier results, it is recommended that an order of at least 9 be used together with an odd seed and modulus equal to 2^30p, for a small integer value of p. While a choice of p=2 should be adequate for most typical applications, increasing p to 3 or 4 gives a sequence that will consistently pass all the tests in the TestU01 test suite, giving additional confidence in more demanding applications.The results demonstrate that the ACORN generators are a reliable source of uniformly distributed pseudo-random numbers, and that in practice (as suggested by the theoretical convergence results) the quality of the ACORN sequences increases with increasing modulus and order.     

An exact determination of serial correlations of pseudo-random numbers

Summary Exact expressions for serial correlations of sequences of pseudo-random numbers are derived. The reduction to generalized Dedekind sums is of optimum simplicity and covers all cases of the linear congruential method. The subsequent evaluation of the generalized Dedekind sums is based on a modified Euclidean algorithm whose quotients are recognized as the main contributors to the size of the serial correlations. This leads to the establishment of bounds as well as of fast computer programs. Moreover, some light is thrown upon the general question of quality in random number generation.Dedicated to Prof. H. Schubert, Kiel on the occasion of his 50th birthdayResearch supported by the DFG (Deutsche Forschungsgemeinschaft) and Nova Scotia Technical College, Halifax, N.S. Canada.     

Pseudo-random numbers for comparative Monte Carlo calculations

To compare the results of two slightly different situations in a given problem solved by the Monte Carlo method it is convenient to use the same random numbers in both cases. To facilitate the reproducibility of the random numbers used a method based on two pseudo-random number generators may be adopted. In this paper the method is discussed with reference to multiplicative congruential generators, the influence of the initial value on a random sequence obtained by a given multiplier being examined first.     

A NEW FAMILY OF BINARY SEQUENCES WITH OPTIMAL AUTOCORRELATION VALUES AND NICE PSEUDO-RANDOM PROPERTIES

In this paper we present a series of binary sequences which is a generalization of GMW sequences constructed by Scholtz and Welch. Our sequences have optimal autocorrelation values as m -sequences, and nice pseudo-random property. The number of such sequences is counted and the linear span of such sequences is evaluated.     

Extended substitution–diffusion based image cipher using chaotic standard map

This paper proposes an extended substitution–diffusion based image cipher using chaotic standard map [1] and linear feedback shift register to overcome the weakness of previous technique by adding nonlinearity. The first stage consists of row and column rotation and permutation which is controlled by the pseudo-random sequences which is generated by standard chaotic map and linear feedback shift register, second stage further diffusion and confusion is obtained in the horizontal and vertical pixels by mixing the properties of the horizontally and vertically adjacent pixels, respectively, with the help of chaotic standard map. The number of rounds in both stage are controlled by combination of pseudo-random sequence and original image. The performance is evaluated from various types of analysis such as entropy analysis, difference analysis, statistical analysis, key sensitivity analysis, key space analysis and speed analysis. The experimental results illustrate that performance of this is highly secured and fast.     

Catalan-like number sequences and Hausdorff moment sequences

Many well-known Catalan-like sequences turn out to be Stieltjes moment sequences (Liang et al. (2016)). However, a Stieltjes moment sequence is in general not determinate; Liang et al. suggested a further analysis about whether these moment sequences are determinate and how to obtain the associated measures. In this paper we find necessary conditions for a Catalan-like sequence to be a Hausdorff moment sequence. As a consequence, we will see that many well-known counting coefficients, including the Catalan numbers, the Motzkin numbers, the central binomial coefficients, the central Delannoy numbers, are Hausdorff moment sequences. We can also identify the smallest interval including the support of the unique representing measure. Since Hausdorff moment sequences are determinate and a representing measure for above mentioned sequences are already known, we could almost complete the analysis raised by Liang et al. In addition, subsequences of Catalan-like number sequences are also considered; we will see a necessary and sufficient condition for subsequences of Stieltjes Catalan-like number sequences to be Stieltjes Catalan-like number sequences. We will also study a representing measure for a linear combination of consecutive terms in Catalan-like number sequences.