Characterizing strong randomness via Martin-Löf randomness

We introduce two methods for characterizing strong randomness notions via Martin-Löf randomness. We apply these methods to investigate Schnorr randomness relative to 0?^′.     

Defining a randomness notion via another

To compare two randomness notions with each other, we ask whether a given randomness notion can be defined via another randomness notion. Inspired by Yu's pioneering study, we formalize our question using the concept of relativization of randomness. We give some solutions to our formalized questions. Also, our results include the affirmative answer to the problem asked by Yu in a discussion with the second author, i.e., whether Schnorr randomness relative to the halting problem is equivalent to Martin‐Löf randomness relative to all low 1‐generic reals.     

When van Lambalgen's Theorem fails

We prove that van Lambalgen's Theorem fails for both Schnorr randomness and computable randomness.

     

Schnorr trivial reals: a construction

A real is Martin-Löf (Schnorr) random if it does not belong to any effectively presented null ${\Sigma^0_1}A real is Martin-L?f (Schnorr) random if it does not belong to any effectively presented null (recursive) class of reals. Although these randomness notions are very closely related, the set of Turing degrees containing reals that are K-trivial has very different properties from the set of Turing degrees that are Schnorr trivial. Nies proved in (Adv Math 197(1):274–305, 2005) that all K-trivial reals are low. In this paper, we prove that if , then h contains a Schnorr trivial real. Since this concept appears to separate computational complexity from computational strength, it suggests that Schnorr trivial reals should be considered in a structure other than the Turing degrees. This material is based upon work supported under a National Science Foundation Graduate Research Fellowship and appears in the author’s Ph.D. thesis. A preliminary version of this paper appeared in Electronic Notes in Theoretical Computer Science     

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)     

Extending and interpreting Post’s programme

Computability theory concerns information with a causal-typically algorithmic-structure. As such, it provides a schematic analysis of many naturally occurring situations. Emil Post was the first to focus on the close relationship between information, coded as real numbers, and its algorithmic infrastructure. Having characterised the close connection between the quantifier type of a real and the Turing jump operation, he looked for more subtle ways in which information entails a particular causal context. Specifically, he wanted to find simple relations on reals which produced richness of local computability-theoretic structure. To this extent, he was not just interested in causal structure as an abstraction, but in the way in which this structure emerges in natural contexts. Post’s programme was the genesis of a more far reaching research project.In this article we will firstly review the history of Post’s programme, and look at two interesting developments of Post’s approach. The first of these developments concerns the extension of the core programme, initially restricted to the Turing structure of the computably enumerable sets of natural numbers, to the Ershov hierarchy of sets. The second looks at how new types of information coming from the recent growth of research into randomness, and the revealing of unexpected new computability-theoretic infrastructure. We will conclude by viewing Post’s programme from a more general perspective. We will look at how algorithmic structure does not just emerge mathematically from information, but how that emergent structure can model the emergence of very basic aspects of the real world.     

Computable randomness and betting for computable probability spaces

Unlike Martin‐Löf randomness and Schnorr randomness, computable randomness has not been defined, except for a few ad hoc cases, outside of Cantor space. This paper offers such a definition (actually, several equivalent definitions), and further, provides a general method for abstracting “bit‐wise” definitions of randomness from Cantor space to arbitrary computable probability spaces. This same method is also applied to give machine characterizations of computable and Schnorr randomness for computable probability spaces, extending the previously known results. The paper contains a new type of randomness—endomorphism randomness—which the author hopes will shed light on the open question of whether Kolmogorov‐Loveland randomness is equivalent to Martin‐Löf randomness. The last section contains ideas for future research.     

Lowness properties and randomness

The set A is low for (Martin-Löf) randomness if each random set is already random relative to A. A is K-trivial if the prefix complexity K of each initial segment of A is minimal, namely . We show that these classes coincide. This answers a question of Ambos-Spies and Ku?era in: P. Cholak, S. Lempp, M. Lerman, R. Shore, (Eds.), Computability Theory and Its Applications: Current Trends and Open Problems, American Mathematical Society, Providence, RI, 2000: each low for Martin-Löf random set is . Our class induces a natural intermediate ideal in the r.e. Turing degrees, which generates the whole class under downward closure.Answering a further question in P. Cholak, S. Lempp, M. Lerman, R. Shore, (Eds.), Computability Theory and Its Applications: Current Trends and Open Problems, American Mathematical Society, Providence, RI, 2000, we prove that each low for computably random set is computable.     

Quasi‐randomness of graph balanced cut properties

Quasi‐random graphs can be informally described as graphs whose edge distribution closely resembles that of a truly random graph of the same edge density. Recently, Shapira and Yuster proved the following result on quasi‐randomness of graphs. Let k ≥ 2 be a fixed integer, α₁,…,α_k be positive reals satisfying \begin{align*}\sum_{i} \alpha_i = 1\end{align*} and (α₁,…,α_k)≠(1/k,…,1/k), and G be a graph on n vertices. If for every partition of the vertices of G into sets V ₁,…,V _k of size α₁n,…,α_kn, the number of complete graphs on k vertices which have exactly one vertex in each of these sets is similar to what we would expect in a random graph, then the graph is quasi‐random. However, the method of quasi‐random hypergraphs they used did not provide enough information to resolve the case (1/k,…,1/k) for graphs. In their work, Shapira and Yuster asked whether this case also forces the graph to be quasi‐random. Janson also posed the same question in his study of quasi‐randomness under the framework of graph limits. In this paper, we positively answer their question. © 2011 Wiley Periodicals, Inc. Random Struct. Alg., 2011     

Martin–Löf random generalized Poisson processes

Martin–Löf randomness was originally defined and studied in the context of the Cantor space $2^{\omega }$. In [2] probability theoretic random closed sets (RACS) are used as the foundation for the study of Martin–Löf randomness in spaces of closed sets. We use that framework to explore Martin–Löf randomness for the space of closed subsets of $\mathbb{R}$ and a particular family of measures on this space, the generalized Poisson processes. This gives a novel class of Martin–Löf random closed subsets of $\mathbb{R}$. We describe some of the properties of these Martin–Löf random closed sets; one result establishes that a real number is Martin–Löf random if and only if it is contained in some Martin–Löf random closed set.     

Randomness notions and partial relativization

We study the computational complexity of an oracle set using a number of notions of randomness that lie between Martin-L?f randomness and 2-randomness in terms of strength. These notions are weak 2-randomness, weak randomness relative to ???, Demuth randomness and Schnorr randomness relative to ???. We characterize the oracles A such that ML[A] ? C, where C is such a randomness notion and ML[A] denotes the Martin-L?f random reals relative to A, using a new meta-concept called partial relativization. We study the reducibility associated with weak 2-randomness and relate it with LR-reducibility.     

Higher Kurtz randomness

A real x is -Kurtz random (-Kurtz random) if it is in no closed null set ( set). We show that there is a cone of -Kurtz random hyperdegrees. We characterize lowness for -Kurtz randomness as being -dominated and -semi-traceable.     

The distribution of ITRM-recognizable reals

Infinite Time Register Machines (ITRM's) are a well-established machine model for infinitary computations. Their computational strength relative to oracles is understood, see e.g. ,  and . We consider the notion of recognizability, which was first formulated for Infinite Time Turing Machines in [6] and applied to ITRM's in [3]. A real x is ITRM-recognizable iff there is an ITRM-program P   such that P^y$P^y$ stops with output 1 iff y=x$y=x$, and otherwise stops with output 0. In [3], it is shown that the recognizable reals are not contained in the ITRM-computable reals. Here, we investigate in detail how the ITRM  -recognizable reals are distributed along the canonical well-ordering _<L${<}_L$ of Gödel's constructible hierarchy L  . In particular, we prove that the recognizable reals have gaps in _<L${<}_L$, that there is no universal ITRM in terms of recognizability and consider a relativized notion of recognizability.     

The computable Lipschitz degrees of computably enumerable sets are not dense

The computable Lipschitz reducibility was introduced by Downey, Hirschfeldt and LaForte under the name of strong weak truth-table reducibility (Downey et al. (2004) [6]). This reducibility measures both the relative randomness and the relative computational power of real numbers. This paper proves that the computable Lipschitz degrees of computably enumerable sets are not dense. An immediate corollary is that the Solovay degrees of strongly c.e. reals are not dense. There are similarities to Barmpalias and Lewis’ proof that the identity bounded Turing degrees of c.e. sets are not dense (George Barmpalias, Andrew E.M. Lewis (2006) [2]), however the problem for the computable Lipschitz degrees is more complex.     

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     

Lowness of higher randomness notions

We study randomness notions given by higher recursion theory, establishing the relationships Π ₁ ¹ -randomness ? Π ₁ ¹ -Martin-Löf randomness ? Δ ₁ ¹ -randomness = Δ ₁ ¹ -Martin-Löf randomness. We characterize the set of reals that are low for Δ ₁ ¹ randomness as precisely those that are Δ ₁ ¹ -traceable. We prove that there is a perfect set of such reals.     

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     

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.