Orbits and Lattices for Linear Random Number Generators with Composite Moduli

In order to analyze certain types of combinations of multiple recursive linear congruential generators (MRGs), we introduce a generalized spectral test. We show how to apply the test in large dimensions by a recursive procedure based on the fact that such combinations are subgenerators of other MRGs with composite moduli. We illustrate this with the well-known RANMAR generator. We also design an algorithm generalizing the procedure to arbitrary random number generators.

     

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.     

常见随机数发生器的缺陷及组合随机数发生器的理论与实践

随机数是蒙特卡罗 Monte- Carlo方法的基础 .本文首先指出线性同余法和移位寄存器 (亦称 Tausworthe)序列等常见随机数发生器的一些缺陷 ;在此基础上介绍可产生具有优良品质随机数的组合发生器。本文既介绍理论结果 ,用以证明组合发生器确实可以优于单个发生器 ;也具体构造了几个可供实际使用的组合随机数发生器。严格而全面的统计检验表明 ,它们可以产生具有优良品质的随机数     

Distribution Properties of Multiply-with-Carry Random Number Generators

We study the multiply-with-carry family of generators proposed by Marsaglia as a generalization of previous add-with-carry families. We define for them an infinite state space and focus our attention on the (finite) subset of recurrent states. This subset will, in turn, split into possibly several subgenerators. We discuss the uniformity of the -dimensional distribution of the output of these subgenerators over their full period. In order to improve this uniformity for higher dimensions, we propose a method for finding good parameters in terms of the spectral test. Our results are stated in a general context and are applied to a related complementary multiply-with-carry family of generators.

     

Tables of linear congruential generators of different sizes and good lattice structure

We provide sets of parameters for multiplicative linear congruential generators (MLCGs) of different sizes and good performance with respect to the spectral test. For , we take as a modulus the largest prime smaller than , and provide a list of multipliers such that the MLCG with modulus and multiplier has a good lattice structure in dimensions 2 to 32. We provide similar lists for power-of-two moduli , for multiplicative and non-multiplicative LCGs.

     

On the Linear Complexity Profile of Nonlinear Congruential Pseudorandom Number Generators with Dickson Polynomials

Linear complexity and linear complexity profile are important characteristics of a sequence for applications in cryptography and Monte-Carlo methods. The nonlinear congruential method is an attractive alternative to the classical linear congruential method for pseudorandom number generation. Recently, a weak lower bound on the linear complexity profile of a general nonlinear congruential pseudorandom number generator was proven by Gutierrez, Shparlinski and the first author. For most nonlinear generators a much stronger lower bound is expected. Here, we obtain a much stronger lower bound on the linear complexity profile of nonlinear congruential pseudorandom number generators with Dickson polynomials.     

Uniform random number generation

In typical stochastic simulations, randomness is produced by generating a sequence of independent uniform variates (usually real-valued between 0 and 1, or integer-valued in some interval) and transforming them in an appropriate way. In this paper, we examine practical ways of generating (deterministic approximations to) such uniform variates on a computer. We compare them in terms of ease of implementation, efficiency, theoretical support, and statistical robustness. We look in particular at several classes of generators, such as linear congruential, multiple recursive, digital multistep, Tausworthe, lagged-Fibonacci, generalized feedback shift register, matrix, linear congruential over fields of formal series, and combined generators, and show how all of them can be analyzed in terms of their lattice structure. We also mention other classes of generators, like non-linear generators, discuss other kinds of theoretical and empirical statistical tests, and give a bibliographic survey of recent papers on the subject.     

On the Linear Complexity and Multidimensional Distribution of Congruential Generators over Elliptic Curves

We show that the elliptic curve analogue of the linear congruential generator produces sequences with high linear complexity and good multidimensional distribution.communicated by: A. MenezesAMS Classification: 11T23, 14H52, 65C10     

非均匀随机数产生

本文详细介绍了产生非均匀随机数的一般方法,常用连续分布(正态分布,Gamma分布,Beta分布,χ2分布和F分布)的抽样法及利用R软件产生随机数的方法。     

An analysis of linear congruential random number generators when multiplier restrictions exist

This research conducts an exhaustive search for the best spectral test performance in a full period linear congruential generator (LCG) with the largest prime modulus smaller than 2^b, for bit sizes b = 8, 9, … , 31. Three types of restrictions on multipliers are presented and some full period LCGs are presented for use in three different spectral test dimensions. According to the exhaustive searches we perform, the results indicate differences exist among the numbers of possible multipliers for the three types of multiplier restrictions. We demonstrate that these differences can affect the performance of spectral tests for different dimensions.     

外p-自同构对p-群生成元个数的一个限制

阶为某素数p的方幂的非内自同构,称为外p-自同构.研究了有限p-群G的任意外p-自同构φ满足|C_G(φ)|≤p^k时群G生成元的个数.     

线性同余人字映射组合产生均匀随机数

研究了线性同余法与人字映射组合随机数发生器 :xn=Axn-1(mod M) ,wn=2 xn,　 xn≤ 0 .5 M,wn=2 (M-xn) +1 ,　 xn>0 .5 M,yn=wn/ M.该组合发生器比相应的线性同余法在空间结构上有明显改善 ,并通过统计检验     

完备赋准范空间上一类无界线性随机算子的谱分解定理

本文利用随机内积空间方法给出了完备赋准范空间上一类无界线性随机算子的谱分解定理。此结果不仅推广了对称随机线性算子的谱分解定理，而且限于原情形也使其处理简明、清晰。     

Genetic and Random Search Methods in Optimal Shape Design Problems

We describe the application of two global optimization methods, namely of genetic and random search type algorithms in shape optimization. When the so-called fictitious domain approaches are used for the numerical realization of state problems, the resulting minimized function is non-differentiable and stair-wise, in general. Such complicated behaviour excludes the use of classical local methods. Specific modifications of the above-mentioned global methods for our class of problems are described. Numerical results of several model examples computed by different variants of genetic and random search type algorithms are discussed.     

Optimal Sequential Sampling Policy of Partitioned Random Search and Its Approximation

The paper studies the optimal sequential sampling policy of the partitioned random search (PRS) and its approximation. The PRS is a recently proposed approach for function optimization. It takes explicitly into consideration computation time or cost, assuming that there exist both a cost for each function evaluation and a finite total computation time constraint. It is also motivated at improving efficiency of the widely used crude random search. In particular, the PRS considers partitioning the search region of an objective function into K subregions and employing an independent and identically distributed random sampling scheme for each of K subregions. A sampling policy decides when to terminate the sampling process or which subregion to be sampled next.     

舍选法几何解释及曲边梯形概率密度随机数生成算法

本文首先从几何概率角度看舍选法的直观意义,找出改进舍选法的途径;然后讨论梯形和曲边梯形概率密度随机数生成算法,给出若干简单概率密度随机数生成实例。     

一种产生广义高斯分布随机数的新算法

本文提出了一种生成广义高斯分布 (GGD)随机数的通用算法 .该算法针对GGD密度函数衰减性的特点 ,采用变步长的方法 ,综合运用了逆函数法、近似复合抽样法及变换抽样法 .通过调整分布参数的数值 ,就能产生具有任何形状参数和任何方差的GGD随机数 ,简单易于实现 .最后将仿真实验结果与已有算法的结果做比较 ,并用 χ2检验法和Kolmogorov Smirnov检验法 (K S检验法 )验证该方法的有效性 .     

Asymptotic Expansions for the Distribution of the Crossing Number of a Strip by Sample Paths of a Random Walk

The complete asymptotic expansions are obtained for the distribution of the crossing number of a strip in n steps by sample paths of an integer-valued random walk with zero mean. We suppose that the Cramer condition holds for the distribution of jumps and the width of strip increases together with n; the results are proven under various conditions on the width growth rate. The method is based on the Wiener–Hopf factorization; it consists in finding representations of the moment generating functions of the distributions under study, the distinguishing of the main terms of the asymptotics of these representations, and the subsequent inversion of the main terms by the modified saddle-point method.     

Random spectral theorems of self-adjoint random linear operators on complete complex random inner product modules

The purpose of this article is to give two random spectral theorems of self-adjoint random linear operators on complete complex random inner product modules.     

Efficient lattice assessment for LCG and GLP parameter searches

In the present paper we show how to speed up lattice parameter searches for Monte Carlo and quasi-Monte Carlo node sets. The classical measure for such parameter searches is the spectral test which is based on a calculation of the shortest nonzero vector in a lattice. Instead of the shortest vector we apply an approximation given by the LLL algorithm for lattice basis reduction. We empirically demonstrate the speed-up and the quality loss obtained by the LLL reduction, and we present important applications for parameter selections.