Inversive congruential pseudorandom numbers: distribution of triples

This paper deals with the inversive congruential method with power of two modulus for generating uniform pseudorandom numbers. Statistical independence properties of the generated sequences are studied based on the distribution of triples of successive pseudorandom numbers. It is shown that, on the average over the parameters in the inversive congruential method, the discrepancy of the corresponding point sets in the unit cube is of an order of magnitude between and . The method of proof relies on a detailed discussion of the properties of certain exponential sums.

     

Average equidistribution and statistical independence properties of digital inversive pseudorandom numbers over parts of the period

This article deals with the digital inversive method for generating uniform pseudorandom numbers. Equidistribution and statistical independence properties of the generated pseudorandom number sequences over parts of the period are studied based on the distribution of tuples of successive terms in the sequence. The main result is an upper bound for the average value of the star discrepancy of the corresponding point sets. Additionally, lower bounds for the star discrepancy are established. The method of proof relies on bounds for exponential sums.

     

On a problem of D.H. Lehmer and pseudorandom binary sequences

Let p be an odd prime, and f(x), g(x) ∈ [x]. Define

Long cycles in subgraphs of (pseudo)random directed graphs

We study the resilience of random and pseudorandom directed graphs with respect to the property of having long directed cycles. For every 08γ81/2 we find a constant c = c(γ) such that the following holds. Let G = (V, E) be a (pseudo)random directed graph on n vertices and with at least a linear number of edges, and let G′ be a subgraph of G with (1/2 + γ)|E| edges. Then G′ contains a directed cycle of length at least (c ? o(1))n. Moreover, there is a subgraph G′′of G with (1/2 + γ ? o(1))|E| edges that does not contain a cycle of length at least cn. © 2011 Wiley Periodicals, Inc. J Graph Theory 70: 284–296, 2012     

基于不同作用体制的激光引信探测技术

随着激光技术的飞速发展,半导体激光传感器已被广泛应用于近炸引信领域。对目前广泛使用的激光近炸引信体制中的几何截断定距、距离选通定距、脉冲鉴相定距以及伪随机编码定距的原理、特点进行了分析,指出了每种体制的局限性,为应用在具体背景下的激光近炸探测体制的选择提供了一定的参考价值。     

Proving the deterministic period breaking of linear congruential generators using two tile quasicrystals

We describe the design of a family of aperiodic PRNGs (APRNGs). We show how a one-dimensional two tile cut and project quasicrystal (2TQC) used in conjunction with LCGs in an APRNG generates an infinite aperiodic pseudorandom sequence. In the suggested design, any 2TQC corresponding to unitary quadratic Pisot number combined with either one or two different LCGs can be used.

     

On the complexity of a family related to the Legendre symbol

Ahlswede, Khachatrian, Mauduit and A. Sárközy introduced the notion of family-complexity of families of binary sequences. They estimated the family-complexity of a large family related to Legendre symbol introduced by Goubin, Mauduit and Sárközy. Here their result is improved, and apart from the constant factor the best lower bound is given for the family-complexity.     

相关变量随机数序列产生方法

当采用蒙特卡罗方法对很多问题进行研究时,有时需要对多维相关随机变量进行抽样.之前的研究表明:在协方差矩阵满足正定条件时,可以采用Cholesky分解方法产生多维相关随机变量.本文首先对产生多维相关随机变量的理论公式进行了推导,发现采用Cholesky分解并不是产生多维相关随机变量的唯一方法,其他的矩阵分解方法只要能满足协方差矩阵的分解条件,同样可以用来产生多维相关随机变量.同时给出了采用协方差矩阵、相对协方差矩阵和相关系数矩阵产生多维随机变量的公式,以方便以后使用.在此基础上,利用一个简单测试题和Jacobi矩阵分解方法对上述理论进行了验证.通过对大亚湾中微子能谱进行抽样分析,Jacobi矩阵分解和Cholesky矩阵分解结果一致.针对核工程中的不确定性分析常用的~(238)U辐射俘获截面协方差矩阵进行分解时,由于协方差矩阵的矩阵本征值有负值,导致很多矩阵分解方法无法使用,在引入置零修正以后发现,与Cholesky对角线置零修正相比,Jacobi负本征值置零修正的误差更小.     

On the structure of digital explicit nonlinear and inversive pseudorandom number generators

We analyze the lattice structure and distribution of the digital explicit inversive pseudorandom number generator introduced by Niederreiter and Winterhof as well as of a general digital explicit nonlinear generator. In particular, we extend a lattice test designed for this class of pseudorandom number generators to parts of the period and arbitrary lags and prove that these generators pass this test up to very high dimensions. We also analyze the behavior of digital explicit inversive and nonlinear generators under another very strong lattice test which in its easiest form can be traced back to Marsaglia and provides a complexity measure essentially equivalent to linear complexity.     

On a Pseudorandom Property of Binary Sequences

C. Mauduit and A. Sárközy proposed the use of well-distribution measure and correlation measure as measures of pseudorandomness of finite binary sequences. In this paper we will introduce and study a further measure of pseudorandomness: the symmetry measure. First we will give upper and lower bounds for the symmetry measure. We will also show that there exists a sequence for which each of the well-distribution, correlation and symmetry measures are small. Finally we will compare these measures of pseudorandomness.