Algorithmic randomness and monotone complexity on product space

We study algorithmic randomness and monotone complexity on product of the set of infinite binary sequences. We explore the following problems: monotone complexity on product space, Lambalgen’s theorem for correlated probability, classification of random sets by likelihood ratio tests, decomposition of complexity and independence, and Bayesian statistics for individual random sequences. Formerly Lambalgen’s theorem for correlated probability is shown under a uniform computability assumption in [H. Takahashi Inform. Compt. 2008]. In this paper we show the theorem without the assumption.     

On semimeasures predicting Martin-Löf random sequences

Solomonoff’s central result on induction is that the prediction of a universal semimeasure M$M$ converges rapidly and with probability 1 to the true sequence generating predictor μ$\mu$, if the latter is computable. Hence, M$M$ is eligible as a universal sequence predictor in the case of unknown μ$\mu$. Despite some nearby results and proofs in the literature, the stronger result of convergence for all (Martin-Löf) random sequences remained open. Such a convergence result would be particularly interesting and natural, since randomness can be defined in terms of M$M$ itself. We show that there are universal semimeasures M$M$ which do not converge to μ$\mu$ on all μ$\mu$-random sequences, i.e. we give a partial negative answer to the open problem. We also provide a positive answer for some non-universal semimeasures. We define the incomputable measure D$D$ as a mixture over all computable measures and the enumerable semimeasure W$W$ as a mixture over all enumerable nearly measures. We show that W$W$ converges to D$D$ and D$D$ to μ$\mu$ on all random sequences. The Hellinger distance measuring closeness of two distributions plays a central role.     

On generalized computable universal priors and their convergence

Solomonoff unified Occam's razor and Epicurus’ principle of multiple explanations to one elegant, formal, universal theory of inductive inference, which initiated the field of algorithmic information theory. His central result is that the posterior of the universal semimeasure M   converges rapidly to the true sequence generating posterior μ$\mu$, if the latter is computable. Hence, M   is eligible as a universal predictor in case of unknown μ$\mu$. The first part of the paper investigates the existence and convergence of computable universal (semi) measures for a hierarchy of computability classes: recursive, estimable, enumerable, and approximable. For instance, M is known to be enumerable, but not estimable, and to dominate all enumerable semimeasures. We present proofs for discrete and continuous semimeasures. The second part investigates more closely the types of convergence, possibly implied by universality: in difference and in ratio, with probability 1, in mean sum, and for Martin-Löf random sequences. We introduce a generalized concept of randomness for individual sequences and use it to exhibit difficulties regarding these issues. In particular, we show that convergence fails (holds) on generalized-random sequences in gappy (dense) Bernoulli classes.     

A comparison of tests for randomness

This paper compares five distance-based statistics (Hopkins, Cox-Lewis, Eberhardt and two T-square statistics) which reflect the degree to which a set of d-dimensional points is random. The objectives are to identify the most promising statistic for intensive study and to establish performance bounds for situations involving little prior information. The sizes and powers of tests of several aggregation models vs. randomness and several regularity models vs. randomness are estimated using theoretical thresholds to define tests of hypothesis. Both hypercubic and hyperspherical sampling windows are examined with a sampling frame of uniform thickness. The Hopkins statistic is the best overall statistic, but the thresholds must be established by Monte Carlo means for more than five dimensions. The sampling window has a greater effect on tests for regularity than on tests for aggregation.     

网构软件的随机性资源自适应性的形式化分析与验证

因特网上的资源具有不确定性、随机性,需要考虑如何保证网构软件系统在运行中满足资源需求。使用随机性资源接口自动机对软件构件的行为进行形式化建模,并使用随机性资源接口自动机网络描述构件组装系统的组合行为;在资源不确定的情况下,检验组合系统是否满足资源约束,并提出基于可达图的相应算法。给出了一个实例网上书店系统,并用模型检测工具Spin验证了模型的正确性。     

基于随机性分析的虚假趋势时间序列判别

针对符合一定数据模式或规律的虚假数据识别问题，提出一种基于随机性分析的虚假趋势时间序列判别方法。该方法在分析时间序列组成的基础上，首先探索虚假趋势时间序列的简单伪造和复杂伪造方式，并将其分解为虚假趋势和虚假随机两部分；然后通过基函数逼近进行时间序列虚假趋势部分的提取，采用随机性理论开展虚假随机部分的分析；最终借助单比特频数和块内频数对虚假随机部分是否具备随机性进行检测，为具有一定趋势特征的虚假时间序列的判别提供了一个解决方案。实验结果表明：该方法能够有效地分解虚假时间序列和提取虚假趋势部分，实现简单伪造数据和复杂伪造数据的判别，支持对通过观测手段或者检测设备所获取的数值型数据的真伪分析，进一步提高了虚假数据可判别范围，平均判别正确率可达74.7%。     

A test of randomness based on the minimal spanning tree

We present a test of randomness based on the edge length distribution of the Minimal Spanning Tree.     

混沌密码系统弱密钥随机性分析

弱密钥问题是混沌密码系统设计中的关键问题,已有研究主要从混沌序列退化角度进行分析.然而,本文指出保证混沌序列不退化的密钥参数仍可能构成混沌密码的弱密钥.本文提出以混沌密码序列随机性作为评价标准,应用严格的统计检验方法对混沌密码的弱密钥进行检测.进一步,对一类混沌密码系统进行了弱密钥研究,检测出了该系统大量未被发现的弱密钥.这确证了所提出方法的有效性.另一方面,虽然已有较多研究采用统计检验对混沌比特序列进行测试,但将统计检验用于分析混沌密码弱密钥或弱序列的研究还很少见.本文给出的统计检验弱序列分析,对当前混沌密码统计检验研究是一个很好的补充.     

信息安全中序列随机性测试系统的研究与设计

在密码技术中,随机序列是非常重要的,序列的随机性测试一直是信息安全领域重要的研究方向.针对当前随机性测试系统存在的不足,在Visual C .NET下研究并设计了一个随机性测试系统.根据流密码和分组密码的不同,该系统分开进行测试.在流密码中提出一种新的测试序列的划分和组织方式,而在分组密码中则设计了3种数据模式来构造待检序列.该系统经过严格测试,证明可以快速,准确的进行流密码、分组密码以及随机数发生器的随机性测试.     

基于随机性检测的数字稳像算法评价方法*

提出了一种基于随机性检测的数字稳像算法客观评价方法。该方法首先估计出数字稳像算法输出视频的全局运动向量;然后将估计结果编码为二进制序列;最后利用随机性检测的方法来检验此二进制序列的随机性,并且根据序列随机性的强弱程度来衡量数字稳像算法的效果。最后的实验表明,提出的方法能够准确地评价常用的数字稳像算法。     

Common randomness and distributed control: A counterexample

When agents collaborate to perform a control task, it is of interest to characterize the set of joint probability distributions they can achieve on their joint action space when they are passively provided with external common randomness. We give a simple counterexample to a natural conjecture about this class of joint distributions.     

Safety assessment of structures in view of fuzzy randomness

Structural safety can be realistically assessed only if the uncertainty in the structural parameters is appropriately taken into consideration and realistic computational models are applied. Uncertainty must be accounted for in its natural form. Stochastic models are not always capable of fulfilling this task without restrictions, as uncertainty may also be characterized by fuzzy randomness or fuzziness. On the basis of the theory of the fuzzy random variables the fuzzy probabilistic safety concept is introduced and formulated as the fuzzy first order reliability method (FFORM). This concept permits fuzziness, randomness and fuzzy randomness to be accounted for simultaneously. FFORM is illustrated by way of an example; hereby, the influence of the computational model is also demonstrated.     

基于随机性检测的链路层加密数据识别研究

为识别链路层加密数据,提出了基于码元频数检测、游程检测、块内频数检测的链路层加密数据识别方案.针对链路层比特序列的分块长度影响块内频数检测识别率的问题,提出了基于信息熵原理的比特序列分块长度值选择方案.针对块内频数检测对长度较短比特序列识别能力有限的问题,提出了基于随机抽样原理的比特序列信息提取方法,以提高块内频数检测对未加密比特序列的识别率.以某无线网络链路层的比特序列识别为例,对提出方案的有效性进行了验证.结果表明,提出的方案具有较高的识别率,相关成果可为进一步的协议识别技术研究打下基础.     

信道随机性对传感器网络连续渗流密度的影响

为同时保证无线传感器网络的覆盖与连通,探索连续渗流密度对网络覆盖与连通性的影响,设计了改进的吉尔伯特圆盘感知模型来研究传感器网络的连续渗流问题。该方法同时考虑了无线传感器网络节点的空间分布特征及信道传输特性,用等效半径与连续渗流填充因子的依赖关系,研究了信道随机性对网络连续渗流密度λc的影响。实验结果表明,信道随机性条件下,节点等效半径增大的衰落环境可增加网络的连通性,减小网络的连续渗流密度λc。     

Comparing the notions of optimality in CP-nets,strategic games and soft constraints

The notion of optimality naturally arises in many areas of applied mathematics and computer science concerned with decision making. Here we consider this notion in the context of three formalisms used for different purposes in reasoning about multi-agent systems: strategic games, CP-nets, and soft constraints. To relate the notions of optimality in these formalisms we introduce a natural qualitative modification of the notion of a strategic game. We show then that the optimal outcomes of a CP-net are exactly the Nash equilibria of such games. This allows us to use the techniques of game theory to search for optimal outcomes of CP-nets and vice-versa, to use techniques developed for CP-nets to search for Nash equilibria of the considered games. Then, we relate the notion of optimality used in the area of soft constraints to that used in a generalization of strategic games, called graphical games. In particular we prove that for a natural class of soft constraints that includes weighted constraints every optimal solution is both a Nash equilibrium and Pareto efficient joint strategy. For a natural mapping in the other direction we show that Pareto efficient joint strategies coincide with the optimal solutions of soft constraints.      

Generalized notions of mind change complexity

Gold introduced the notion of learning in the limit where a class S is learnable iff there is a recursive machine M which reads the course of values of a function f and converges to a program for f whenever f is in S. An important measure for the speed of convergence in this model is the quantity of mind changes before the onset of convergence. The oldest model is to consider a constant bound on the number of mind changes M makes on any input function; such a bound is referred here as type 1. Later this was generalized to a bound of type 2 where a counter ranges over constructive ordinals and is counted down at every mind change. Although ordinal bounds permit the inference of richer concept classes than constant bounds, they still are a severe restriction. Therefore the present work introduces two more general approaches to bounding mind changes. These are based on counting by going down in a linearly ordered set (type 3) and on counting by going down in a partially ordered set (type 4). In both cases the set must not contain infinite descending recursive sequences. These four types of mind changes yield a hierarchy and there are identifiable classes that cannot be learned with the most general mind change bound of type 4. It is shown that existence of type 2 bound is equivalent to the existence of a learning algorithm which converges on every (also nonrecursive) input function and the existence of type 4 is shown to be equivalent to the existence of a learning algorithm which converges on every recursive function. A partial characterization of type 3 yields a result of independent interest in recursion theory. The interplay between mind change complexity and choice of hypothesis space is investigated. It is established that for certain concept classes, a more expressive hypothesis space can sometimes reduce mind change complexity of learning these classes. The notion of mind change bound for behaviourally correct learning is indirectly addressed by employing the above four types to restrict the number of predictive errors of commission in finite error next value learning (NV′′)—a model equivalent to behaviourally correct learning. Again, natural characterizations for type 2 and type 4 bounds are derived. Their naturalness is further illustrated by characterizing them in terms of branches of uniformly recursive families of binary trees.     

Algorithmic randomness and splitting of supermartingales

Randomness in the sense of Martin-Löf can be defined in terms of lower semicomputable supermartingales. We show that such a supermartingale cannot be replaced by a pair of supermartingales that bet only on even bits (the first one) and on odd bits (the second one) knowing all the preceding bits.