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.     

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?^′.     

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.     

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 .

     

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.     

The perception of randomness

Psychologists have studied people's intuitive notions of randomness by two kinds of tasks: judgment tasks (e.g., “is this series like a coin?” or “which of these series is most like a coin?”), and production tasks (e.g., “produce a series like a coin”). People's notion of randomness is biased in that they see clumps or streaks in truly random series and expect more alternation, or shorter runs, than are there. Similarly, they produce series with higher than expected alternation rates. Production tasks are subject to other biases as well, resulting from various functional limitations. The subjectively ideal random sequence obeys “local representativeness”; namely, in short segments of it, it represents both the relative frequencies (e.g., for a coin, 50%–50%) and the irregularity (avoidance of runs and other patterns). The extent to which this bias is a handicap in the real world is addressed.     

Truth‐table Schnorr randomness and truth‐table reducible randomness

Schnorr randomness and computable randomness are natural concepts of random sequences. However van Lambalgen’s Theorem fails for both randomnesses. In this paper we define truth‐table Schnorr randomness (defined in 6 too only by martingales) and truth‐table reducible randomness, for which we prove that van Lambalgen's Theorem holds. We also show that the classes of truth‐table Schnorr random reals relative to a high set contain reals Turing equivalent to the high set. It follows that each high Schnorr random real is half of a real for which van Lambalgen's Theorem fails. Moreover we establish the coincidence between triviality and lowness notions for truth‐table Schnorr randomness. © 2011 WILEY‐VCH Verlag GmbH & Co. KGaA, Weinheim     

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.     

Algorithmic randomness over general spaces

The study of Martin‐Löf randomness on a computable metric space with a computable measure has seen much progress recently. In this paper we study Martin‐Löf randomness on a more general space, that is, a computable topological space with a computable measure. On such a space, Martin‐Löf randomness may not be a natural notion because there is no universal test, and Martin‐Löf randomness and complexity randomness (defined in this paper) do not coincide in general. We show that SCT₃ is a sufficient condition for the existence and coincidence, and study how much we can weaken this condition.     

Elementary and middle grade students’ constructions of typicality

This study addresses the measures chosen by students when selecting or constructing indices to properties of distributions of data. A series of individual teaching experiments were conducted to provide insight into the development of five 4th to 8th grade students’ conceptualizations of distribution over the course of 8 weeks of instruction. During the course of the teaching experiment (emergent) statistical tasks and analogous teacher activities were created and refined in an effort to support the development of understanding. In the process of development, attempts were made by students to coordinate center and variability when constructing measures to index properties of distributions. The results indicate that consideration of representativeness was a major factor that motivated modification of approaches to constructing indices of distributions, and subsequent coordination of indices of variation and center. In particular, the defining features of student's self-constructed “typical” values and notions of spread were examined, resulting in a model of development constituting eight “categories” ranging from the construction of values that did not reflect properties of the data (Category 1) to measures employing conceptual use of the mean in combination with other indices of center and spread (Category 8).     

The notion of chronicle as an epistemological obstacle to the concept of function

Variables are an important class of functions. In this article, the notion of chronicle is introduced as a variable that changes implicitly with time. It is argued that chronicles form a basic interpretation framework used to deal with phenomena involving changes. The results of a written test show that 16% of a group of college science-oriented students made use of a chronicle to sketch a graph representing a situation featuring a time vs. speed relation. As epistemological obstacles, chronicles appear to prompt major difficulties, and special care should be taken to develop students' competence in handling non-chronicle relations. This goes against the natural inclination to describe changes predominantly through a chronicle framework.     

Algorithmic randomness of continuous functions

We investigate notions of randomness in the space ${{\mathcal C}(2^{\mathbb N})}We investigate notions of randomness in the space of continuous functions on . A probability measure is given and a version of the Martin-L?f test for randomness is defined. Random continuous functions exist, but no computable function can be random and no random function can map a computable real to a computable real. The image of a random continuous function is always a perfect set and hence uncountable. For any , there exists a random continuous function F with y in the image of F. Thus the image of a random continuous function need not be a random closed set. The set of zeroes of a random continuous function is always a random closed set. Research partially supported by the National Science Foundation grants DMS 0532644 and 0554841 and 00652732. Thanks also to the American Institute of Mathematics for support during 2006 Effective Randomness Workshop; Remmel partially supported by NSF grant 0400307; Weber partially supported by NSF grant 0652326. Preliminary version published in the Third International Conference on Computability and Complexity in Analysis, Springer Electronic Notes in Computer Science, 2006.     

On Russell's method of controllability via stabilizability

Russell has observed that a linear system is controllable provided it is stabilizable in both positive and negative time. We give a version of this result valid for nonlinear systems, and illustrate its use by giving new proofs of two classical results from control theory, the first involving bounded perturbations of controllable linear systems, and the second involving controllability of linear systems by bounded controls.This research was supported by the Natural Sciences and Engineering Research Council of Canada.