Non-cupping and randomness

Let be Martin-Löf-random. Then there is a promptly simple set such that for each Martin-Löf-random set , . When , one obtains a c.e. non-computable set which is not weakly Martin-Löf cuppable. That is, for any Martin-Löf-random set , if , then .

     

A minimal pair of -degrees

We construct a minimal pair of -degrees. We do this by showing the existence of an unbounded nondecreasing function which forces -triviality in the sense that is -trivial if and only if for all , .

     

Quasi‐Random Oriented Graphs

We show that a number of conditions on oriented graphs, all of which are satisfied with high probability by randomly oriented graphs, are equivalent. These equivalences are similar to those given by Chung, Graham, and Wilson [5] in the case of unoriented graphs, and by Chung and Graham [3] in the case of tournaments. Indeed, our main theorem extends to the case of a general underlying graph G, the main result of [3] which corresponds to the case that G is complete. One interesting aspect of these results is that exactly two of the four orientations of a four cycle can be used for a quasi‐randomness condition, i.e., if the number of appearances they make in D is close to the expected number in a random orientation of the same underlying graph, then the same is true for every small oriented graph H.     

用类同余法产生随机数及其检验

模拟随机过程的各种模型都需要用到大量随机数 ,而各种分布的随机样本又可以由U(0 ,1)来产生 ,所以如何产生性能好、成本低、使用方便的随机数具有重要意义。本文介绍了一种随机数的产生方法并对其进行了严格的检验。     

On Schnorr and computable randomness,martingales, and machines

We examine the randomness and triviality of reals using notions arising from martingales and prefix‐free machines. (© 2004 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim)     

The quasi‐randomness of hypergraph cut properties

Let satisfy and suppose a k‐uniform hypergraph on n vertices satisfies the following property; in any partition of its vertices into k sets of sizes , the number of edges intersecting is (asymptotically) the number one would expect to find in a random k‐uniform hypergraph. Can we then infer that H is quasi‐random? We show that the answer is negative if and only if . This resolves an open problem raised in 1991 by Chung and Graham [J AMS 4 (1991), 151–196]. While hypergraphs satisfying the property corresponding to are not necessarily quasi‐random, we manage to find a characterization of the hypergraphs satisfying this property. Somewhat surprisingly, it turns out that (essentially) there is a unique non quasi‐random hypergraph satisfying this property. The proofs combine probabilistic and algebraic arguments with results from the theory of association schemes. © 2011 Wiley Periodicals, Inc. Numer Methods Partial Differential Eq, 2011     

Multivariate rank statistics for testing randomness concerning some marginal distributions

In the present paper there is proposed a rank statistic for multivariate testing of randomness conceriing some marginal distributions. The asymptotic distribution of this statistic under hypothesis and “near” alternatives is treated.     

Locally most powerful rank tests for testing randomness and symmetry

Let X _i, 1 i N, be N independent random variables (i.r.v.) with distribution functions (d.f.) F _i(x,), 1 i N, respectively, where is a real parameter. Assume furthermore that F _i(·,0) = F(·) for 1 i N. Let R = (R ₁,R _N) and R ⁺,...,R _N ⁺ be the rank vectors of X = (X ₁,X _N) and |X|=(|X ₁|,...,|X _N|), respectively, and let V = (V ₁,V _N) be the sign vector of X. The locally most powerful rank tests (LMPRT) S = S(R) and the locally most powerful signed rank tests (LMPSRT) S = S(R ⁺, V) will be found for testing = 0 against > 0 or < 0 with F being arbitrary and with F symmetric, respectively.     

The semi-analytical method for time-dependent wave problems with uncertainties

This paper provides a constructive procedure for the computation of approximate solutions of random time-dependent hyperbolic mean square partial differential problems. Based on the theoretical representation of the solution as an infinite random improper integral, obtained via the random Fourier transform method, a double approximation process is implemented. Firstly, a random Gauss-Hermite quadrature is applied, and then, the evaluations at the nodes of the integrand are approximated by using a random Störmer numerical method. Numerical results are illustrated with examples.     

How useful randomness for cryptography can emerge from multicore-implemented complex networks of chaotic maps

This article is devoted to the study of several topologies of complex networks of chaotic maps, in order to design new Chaotic Pseudo Random Number Generators for cryptographic purpose in a bottom up approach of doing mathematics. We examine topologies of special 2 -D coupled maps which are built combining piecewise linear and logistic maps. We present also a family of p -Dimensional networks whose we study numerically a particular realization, up to one hundred trillion iterates using multicores computers. From those topologies emerges useful randomness for cryptographic purpose.     

C0复杂度的数学基础

对于许多同时具有强烈非线性和非平稳性的连续生物医学信号来说，计算其复杂度往往要求：1）在数据长度比较短的情况下也可以得出比较鲁棒的估计值；2）无需对原始信号作像二值化这样的过分的粗粒化，我们以前所提出的C0复杂度就是这样的一种度量，但是这种度量缺乏严格的数学基础，因而影响到它的应用，提出了一种改进形式，并严格证明了它的重要性质。从而表明这个量在一定条件下可以作为时间序列随机程度的指标，因而在随机性复杂度的意义下也可作为复杂性的一个定量指标，由于这个量有计算速度快的优点，因此特别适合于一些需要大量计算复杂度的场合，例如计算长时间过程中滑动窗口中复杂度的动态变化。     

SLIDING MODE CONTROL OF A CLASS OF ITO^ TYPE DISTRIBUTED PARAMETER SYSTEMS WITH DELAY

Sliding mode control problem of a class of Ito type partial differential equations with delay is probed. The variable structure controller is designed. The existence of motion of sliding mode is shown. And the character of invariance of sliding control system about uncertainty on the sliding switching surface and stability are analyzed.     

Quasi‐carousel tournaments

A tournament is called locally transitive if the outneighborhood and the inneighborhood of every vertex are transitive. Equivalently, a tournament is locally transitive if it avoids the tournaments W₄ and L₄, which are the only tournaments up to isomorphism on four vertices containing a unique 3‐cycle. On the other hand, a sequence of tournaments  with  is called almost balanced if all but  vertices of  have outdegree . In the same spirit of quasi‐random properties, we present several characterizations of tournament sequences that are both almost balanced and asymptotically locally transitive in the sense that the density of W₄ and L₄ in  goes to zero as n goes to infinity.     

韧脆转变的一种细观随机模糊统计分析

对不同温度和应力状态下40Cr材料进行大子样宏观试验和细观观测,提出了一种新的材料断裂韧脆转变统计随机模糊模型。该模型认为,在统计意义上,材料的韧性断裂为空穴机制,临界空穴扩张比参数可以作为韧性断裂的判据;材料的脆性断裂可以用内嵌币状裂纹的脆性断裂模型来模拟,为此测量断裂特征长度,提出并具体计算了控制币状裂纹失稳扩张的细观临界应力强度因子;在韧脆转变区域内,这两种机理并存并相互竞争,为此提出了模糊准则。对模型参数进行了测量和统计分析,给出分布规律,给出了计算断裂特征的概率模型。计算了韧脆转变区域内的细观机制变化和宏观响应。结果表明,该模型及分析方法可以很好地模拟应力状态及温度对韧脆转变的影响。     

Spectra of Anderson type models with decaying randomness

In this paper we consider some Anderson type models, with free parts having long range tails and with the random perturbations decaying at different rates in different directions and prove that there is a.c. spectrum in the model which is pure. In addition, we show that there is pure point spectrum outside some interval. Our models include potentials decaying in all directions in which case absence of singular continuous spectrum is also shown.     

基于谱密度评价随机性

为了评价一个平稳过程的随机性, 我们基于谱密度提出了一个图方法. 当图中的散点呈现线性关系的时候, 我们可以判定这个序列是随机的. 为了说明这个思想, 我们用模拟的办法来检验伪随机数的随机性. 另外, 我们也用了一个实际数据来考察数据的相关性. 这两个例子都说明了我们的图方法是非常有效的.     

Simple Constructions of Almost k-wise Independent Random Variables

We present three alternative simple constructions of small probability spaces on n bits for which any k bits are almost independent. The number of bits used to specify a point in the sample space is (2 + o(1)) (log log n + k/2 + log k + log 1/?), where ? is the statistical difference between the distribution induced on any k bit locations and the uniform distribution. This is asymptotically comparable to the construction recently presented by Naor and Naor (our size bound is better as long as ? < 1/(k log n)). An additional advantage of our constructions is their simplicity.     

关于渐近随机的GFSR序列的设计

Ｔｏｏｔｉｌｌ等人提出了一种渐近的随机Ｔａｕｓｗｏｒｔｈｅ序列,并给出了一个偶然发现的此种序列,但直到现在尚未有人提出一个寻求此种序列的系统性的方法,本文中我们将给出一种设计ＧＦＳＲ序 算法,所产生的序列近似地满足渐近随机性,我们的算法基于反复地运用由Ｆｕｓｈｉｍｉ提出的算法,由现在的算法所设计出来的序列不有一种附加的好处,即其十中抽一的序列也是近似地渐近随机的,文中给出了一些数字例子。     

Weak quasi‐randomness for uniform hypergraphs

We study quasi‐random properties of k‐uniform hypergraphs. Our central notion is uniform edge distribution with respect to large vertex sets. We will find several equivalent characterisations of this property and our work can be viewed as an extension of the well known Chung‐Graham‐Wilson theorem for quasi‐random graphs. Moreover, let K_k be the complete graph on k vertices and M(k) the line graph of the graph of the k‐dimensional hypercube. We will show that the pair of graphs (K_k,M(k)) has the property that if the number of copies of both K_k and M(k) in another graph G are as expected in the random graph of density d, then G is quasi‐random (in the sense of the Chung‐Graham‐Wilson theorem) with density close to d. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011