We formalise the notion of those infinite binary sequences z that admit a single program P which expresses the entire algorithmical structure of z. Such a program P minimizes the information which must be used in a relative computation for z. We propose two concepts with different strength for this notion, the learnable and the super-learnable sequences. We establish three different equivalent characterizations of learnable (super-learnable, resp.) sequences. In particular, we prove that a sequences z is (...) learnable (super-learnable, resp.) if and only if there is a computable probability measure p such that p is Schnorr (Martin-Lof, resp.) p-random. There is a recursively enumerable sequence which is not learnable. The learnable sequences are invariant with respect to all total and effective transformations of infinite binary sequences. (shrink)

We review briefly the attempts to define random sequences. These attempts suggest two theorems: one concerning the number of subsequence selection procedures that transform a random sequence into a random sequence; the other concerning the relationship between definitions of randomness based on subsequence selection and those based on statistical tests.

Let ω be a Kolmogorov–Chaitin random sequence with ω1: n denoting the first n digits of ω. Let P be a recursive predicate defined on all finite binary strings such that the Lebesgue measure of the set {ω|∃nP(ω1: n )} is a computable real α. Roughly, P holds with computable probability for a random infinite sequence. Then there is an algorithm which on input indices for any such P and α finds an n such that P holds within (...) the first n digits of ω or not in ω at all. We apply the result to the halting probability Ω and show that various generalizations of the result fail. (shrink)

We show that standard statistical tests for randomness of finite sequences are language-dependent in an inductively pernicious way.

How to estimate the randomness in random sequence generation tasks? The aim of the paper was to discuss the accuracy of the multiple indexes used for random sequences generation results calculation. In the first part of the paper the models explaining deviations from randomness were presented. The key role of the structural limitations interpretation was suggested. Secondly, the multiple indexes of the deviation from randomness used in random sequence generation task studies were presented. The authors concluded (...) that too many indexes are used in the studies of deviation from randomness. In order to avoid such problems two indexes were proposed: entropy and correlation function. The last part of the paper presents the preliminary version of the mathematical of random sequences generation in which the limited capacity of the short-term memory assumption was introduce. (shrink)

Keystream sequences should look as random as possible, i.e. should present no logical pattern to be exploited in cryptographic attacks. The generalized self-shrinking generator, a sequence generator based on irregular decimation, produces a family of sequences with good cryptographic properties. In this work, we display a detailed analysis on the randomness of the sequences resulting from the concatenation of elements of this family. We apply the most important batteries of statistical and graphical tests providing powerful results (...) and a new method to construct sequences with good cryptographic properties. (shrink)

Recent studies have indicated that it is possible to protect individuals from HIV infection using passive infusion of monoclonal antibodies. However, in order for monoclonal antibodies to confer robust protection, the antibodies must be capable of neutralizing many possible strains of the virus. This is particularly challenging in the context of a highly diverse pathogen like HIV. It is therefore of great interest to leverage existing observational data sources to discover antibodies that are able to neutralize HIV viruses via residues (...) where existing antibodies show modest protection. Such information feeds directly into the clinical trial pipeline for monoclonal antibody therapies by providing information on whether and to what extent combinations of antibodies can generate superior protection and strategies for analyzing past clinical trials to identify in vivo evidence of antibody resistance. These observational data include genetic features of many diverse HIV genetic sequences, as well as in vitro measures of antibody resistance. The statistical learning problem we are interested in is developing statistical methodology that can be used to analyze these data to identify important genetic features that are significantly associated with antibody resistance. This is a challenging problem owing to the high-dimensional and strongly correlated nature of the genetic sequence data. To overcome these challenges, we propose an outcome-adaptive, collaborative targeted minimum loss-based estimation approach using random forests. We demonstrate via simulation that the approach enjoys important statistical benefits over existing approaches in terms of bias, mean squared error, and type I error. We apply the approach to the Compile, Analyze, and Tally Nab Panels database to identify AA positions that are potentially causally related to resistance to neutralization by several different antibodies. (shrink)

The charge that the limit-frequency theory of probability is inconsistent due to incompatibility between the required features of randomness and limit convergence is inapplicable when probability sequences are taken to be empirically (i.e., extensionally) generated, as they must be on a strictly empirical conception of probability. All past attempts to meet this charge by formulating constructive definitions of randomness that would still allow for a demonstrable limit-convergence have, in their exclusive concern with logically (i.e., intensionally) prescribed sequences, left (...) the logic of extensional classes essentially untouched. In the light of a strict differentiation between intensional and extensional classes a generalized approach is possible under which several closely connected senses of randomness, i.e., the formal, material, restricted and unrestricted senses may be easily distinguished and related to the notion of relevance. (shrink)

Belief in free will is widespread. The present research considered one reason why people may believe that actions are freely chosen rather than determined: they attribute randomness in behavior to free will. Experiment 1 found that participants who were prompted to perform a random sequence of actions experienced their behavior as more freely chosen than those who were prompted to perform a deterministic sequence. Likewise, Experiment 2 found that, all else equal, the behavior of animated agents was perceived to (...) be more freely chosen if it consisted of a random sequence of actions than if it consisted of a deterministic sequence; this was true even when the degree of randomness in agents’ behavior was largely a product of their environments. Together, these findings suggest that randomness in behavior—one’s own or another’s—can be mistaken for free will. (shrink)

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 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. (shrink)

Early work on the frequency theory of probability made extensive use of the notion of randomness, conceived of as a property possessed by disorderly collections of outcomes. Growing out of this work, a rich mathematical literature on algorithmic randomness and Kolmogorov complexity developed through the twentieth century, but largely lost contact with the philosophical literature on physical probability. The present chapter begins with a clarification of the notions of randomness and probability, conceiving of the former as a property of a (...) sequence of outcomes, and the latter as a property of the process generating those outcomes. A discussion follows of the nature and limits of the relationship between the two notions, with largely negative verdicts on the prospects for any reduction of one to the other, although the existence of an apparently random sequence of outcomes is good evidence for the involvement of a genuinely chancy process. (shrink)

If is a random sequence, then the sequence is clearly not random; however, seems to be “about half random”. L. Staiger [Kolmogorov complexity and Hausdorff dimension, Inform. and Comput. 103 159–194 and A tight upper bound on Kolmogorov complexity and uniformly optimal prediction, Theory Comput. Syst. 31 215–229] and K. Tadaki [A generalisation of Chaitin’s halting probability Ω and halting self-similar sets, Hokkaido Math. J. 31 219–253] have studied the degree of randomness of sequences or reals (...) by measuring their “degree of compression”. This line of study leads to various definitions of partial randomness. In this paper we explore some relations between these definitions. Among other results we obtain a characterisation of Σ1-dimension in terms of strong Martin-Löf ε-tests , and we show that ε-randomness for ε is different than the classical 1-randomness. (shrink)

This paper investigates aspects of measure and randomness in the context of locale theory . We prove that every measure μ, on the σ-frame of opens of a fitted σ-locale X, extends to a measure on the lattice of all σ-sublocales of X . Furthermore, when μ is a finite measure with μ=M, the σ-locale X has a smallest σ-sublocale of measure M . In particular, when μ is a probability measure, X has a smallest σ-sublocale of measure 1. All (...) σ prefixes can be dropped from these statements whenever X is a strongly Lindelöf locale, as is the case in the following applications. When μ is the Lebesgue measure on the Euclidean space Rn, Theorem 1 produces an isometry-invariant measure that, via the inclusion of the powerset P in the lattice of sublocales, assigns a weight to every subset of Rn. When μ is the uniform probability measure on Cantor space {0,1}ω, the smallest measure-1 sublocale, given by Theorem 2, provides a canonical locale of random sequences, where randomness means that all probabilistic laws are satisfied. (shrink)

It is time for a new paper about open questions in the currently very active area of randomness and computability. Ambos-Spies and Kučera presented such a paper in 1999 [1]. All the question in it have been solved, except for one: is KL-randomness different from Martin-Löf randomness? This question is discussed in Section 6.Not all the questions are necessarily hard—some simply have not been tried seriously. When we think a question is a major one, and therefore likely to be hard, (...) we indicate this by the symbol ▶, the criterion being that it is of considerable interest and has been tried by a number of researchers. Some questions are close contenders here; these are marked by ▷. With few exceptions, the questions are precise. They mostly have a yes/no answer. However, there are often more general questions of an intuitive or even philosophical nature behind. We give an outline, indicating the more general questions.All sets will be sets of natural numbers, unless otherwise stated. These sets are identified with infinite strings over {0, 1}. Other terms used in the literature are sequence and real. (shrink)

Almost everyone has an intuitive notion of what a random number is. For example, consider these two series of binary digits: 01010101010101010101 01101100110111100010 The first is obviously constructed according to a simple rule; it consists of the number 01 repeated ten times. If one were asked to speculate on how the series might continue, one could predict with considerable confidence that the next two digits would be 0 and 1. Inspection of the second series of digits yields no such (...) comprehensive pattern. There is no obvious rule governing the formation of the number, and there is no rational way to guess the succeeding digits. The arrangement seems haphazard; in other words, the sequence appears to be a random assortment of 0's and 1's. (shrink)

We study the sets that are computable from both halves of some (Martin–Löf) random sequence, which we call 1/2-bases. We show that the collection of such sets forms an ideal in the Turing degrees that is generated by its c.e. elements. It is a proper subideal of the K-trivial sets. We characterize 1/2-bases as the sets computable from both halves of Chaitin’s Ω, and as the sets that obey the cost function c(x,s)=Ωs−Ωx−−−−−−−√. Generalizing these results yields a dense hierarchy (...) of subideals in the K-trivial degrees: For k<n, let Bk/n be the collection of sets that are below any k out of n columns of some random sequence. As before, this is an ideal generated by its c.e. elements and the random sequence in the definition can always be taken to be Ω. Furthermore, the corresponding cost function characterization reveals that Bk/n is independent of the particular representation of the rational k/n, and that Bp is properly contained in Bq for rational numbers p<q. These results are proved using a generalization of the Loomis–Whitney inequality, which bounds the measure of an open set in terms of the measures of its projections. The generality allows us to analyze arbitrary families of orthogonal projections. As it turns out, these do not give us new subideals of the K-trivial sets; we can calculate from the family which Bp it characterizes. We finish by studying the union of Bp for p<1; we prove that this ideal consists of the sets that are robustly computable from some random sequence. This class was previously studied by Hirschfeldt [D. R. Hirschfeldt, C. G. Jockusch, R. Kuyper and P. E. Schupp, Coarse reducibility and algorithmic randomness, J. Symbolic Logic81(3) (2016) 1028–1046], who showed that it is a proper subclass of the K-trivial sets. We prove that all such sets are robustly computable from Ω, and that they form a proper subideal of the sets computable from every (weakly) LR-hard random sequence. We also show that the ideal cannot be characterized by a cost function, giving the first such example of a Σ03 subideal of the K-trivial sets. (shrink)

A Martin-Löf random sequence is an infinite binary sequence with the property that every initial segment $\sigma$ has prefix-free Kolmogorov complexity $K$ at least $|\sigma| - c$, for some constant $c \in \omega$. Informally, initial segments of Martin-Löf randoms are highly complex in the sense that they are not compressible by more than a constant number of bits. However, all Martin-Löf randoms necessarily have contiguous substrings of arbitrarily low complexity. If we demand that all substrings of a sequence be (...) uniformly complex, then we arrive at the notion of shift-complex sequences. In this paper, we collect some of the existing results on these sequences and contribute two new ones. Rumyantsev showed that the measure of oracles that compute shift-complex sequences is zero. We strengthen this result by proving that the Martin-Löf random sequences that do not compute shift-complex sequences are exactly the incomplete ones, in other words, the ones that do not compute the halting problem. In order to do so, we make use of the characterization by Franklin and Ng of the class of incomplete Martin-Löf randoms via a notion of randomness called difference randomness. Turning to the power of shift-complex sequences as oracles, we show that there are shift-complex sequences that do not compute Martin-Löf random sequences. (shrink)

For given Boolean algebras$\mathbb {A}$and$\mathbb {B}$we endow the space$\mathcal {H}(\mathbb {A},\mathbb {B})$of all Boolean homomorphisms from$\mathbb {A}$to$\mathbb {B}$with various topologies and study convergence properties of sequences in$\mathcal {H}(\mathbb {A},\mathbb {B})$. We are in particular interested in the situation when$\mathbb {B}$is a measure algebra as in this case we obtain a natural tool for studying topological convergence properties of sequences of ultrafilters on$\mathbb {A}$in random extensions of the set-theoretical universe. This appears to have strong connections with Dow and (...) Fremlin’s result stating that there are Efimov spaces in the random model. We also investigate relations between topologies on$\mathcal {H}(\mathbb {A},\mathbb {B})$for a Boolean algebra$\mathbb {B}$carrying a strictly positive measure and convergence properties of sequences of measures on$\mathbb {A}$. (shrink)

Recently, a connection has been established between two branches of computability theory, namely between algorithmic randomness and algorithmic learning theory. Learning-theoretical characterizations of several notions of randomness were discovered. We study such characterizations based on the asymptotic density of positive answers. In particular, this note provides a new learning-theoretic definition of weak 2-randomness, solving the problem posed by (Zaffora Blando, Rev. Symb. Log. 2019). The note also highlights the close connection between these characterizations and the problem of convergence on (...) class='Hi'>random sequences. (shrink)

We present a faithful axiomatization of von Mises' notion of a random sequence, using an abstract independence relation. A byproduct is a quantifier elimination theorem for Friedman's "almost all" quantifier in terms of this independence relation.

A convenient and practical method is presented for the generation of unbiased random sequences. The method is based on combining discrete outputs and does not require either precisely specified and unbiased input or complex procedures and equipment.

We investigate the role of continuous reductions and continuous relativization in the context of higher randomness. We define a higher analogue of Turing reducibility and show that it interacts well with higher randomness, for example with respect to van Lambalgen’s theorem and the Miller–Yu/Levin theorem. We study lowness for continuous relativization of randomness, and show the equivalence of the higher analogues of the different characterizations of lowness for Martin-Löf randomness. We also characterize computing higher [Formula: see text]-trivial sets by higher (...) random sequences. We give a separation between higher notions of randomness, in particular between higher weak 2-randomness and [Formula: see text]-randomness. To do so we investigate classes of functions computable from Kleene’s [Formula: see text] based on strong forms of the higher limit lemma. (shrink)

An infinite binary sequence X is Kolmogorov–Loveland random if there is no computable non-monotonic betting strategy that succeeds on X in the sense of having an unbounded gain in the limit while betting successively on bits of X. A sequence X is KL-stochastic if there is no computable non-monotonic selection rule that selects from X an infinite, biased sequence.One of the major open problems in the field of effective randomness is whether Martin-Löf randomness is the same as KL-randomness. Our (...) first main result states that KL-random sequences are close to Martin-Löf random sequences in so far as every KL-random sequence has arbitrarily dense subsequences that are Martin-Löf random. A key lemma in the proof of this result is that for every effective split of a KL-random sequence at least one of the halves is Martin-Löf random. However, this splitting property does not characterize KL-randomness; we construct a sequence that is not even computably random such that every effective split yields two subsequences that are 2-random. Furthermore, we show for any KL-random sequence A that is computable in the halting problem that, first, for any effective split of A both halves are Martin-Löf random and, second, for any computable, nondecreasing, and unbounded function g and almost all n, the prefix of A of length n has prefix-free Kolmogorov complexity at least n−g. Again, the latter property does not characterize KL-randomness, even when restricted to left-r.e. sequences; we construct a left-r.e. sequence that has this property but is not KL-stochastic and, in fact, is not even Mises–Wald–Church stochastic.Turning our attention to KL-stochasticity, we construct a non-empty class of KL-stochastic sequences that are not weakly 1-random; by the usual basis theorems we obtain such sequences that in addition are left-r.e., are low, or are of hyperimmune-free degree.Our second main result asserts that every KL-stochastic sequence has effective dimension 1, or equivalently, a sequence cannot be KL-stochastic if it has infinitely many prefixes that can be compressed by a factor of α<1. This improves on a result by Muchnik, who has shown that were they to exist, such compressible prefixes could not be found effectively. (shrink)

We analyze the pointwise convergence of a sequence of computable elements of L1 in terms of algorithmic randomness. We consider two ways of expressing the dominated convergence theorem and show that, over the base theory RCA0, each is equivalent to the assertion that every Gδ subset of Cantor space with positive measure has an element. This last statement is, in turn, equivalent to weak weak Königʼs lemma relativized to the Turing jump of any set. It is also equivalent to the (...) conjunction of the statement asserting the existence of a 2-random relative to any given set and the principle of Σ2 collection. (shrink)

Using randomly generated sequences of binary events we asked participants to make predictions about the next event. It turned out that while predicting uncertain events, people do not behave unsystematically. Our research identifies four types of relatively consistent strategies for predicting uncertain binary events: a strategy immune to short-run sequential dependencies consisting of the persistent prediction of long-run majority events, hereafter called the long-run momentum strategy ; a strategy immune to short-run sequential dependencies consisting of the persistent prediction of (...) long-run minority events, called the long-run contrarian strategy ; a strategy sensitive to short-run sequential dependencies consisting of the prediction of short-run majority events, called the short-run momentum strategy ; and a strategy sensitive to short-run sequential dependencies consisting of the prediction of short-run minority events, called the short-run contrarian strategy . When the character of events remains unknown, the most common strategy is the short-run momentum strategy. With the increase of a perceived randomness of the situation, people tend more often to use the short-run contrarian strategy. People differ in their general beliefs about the continuation or reversal of a trend in various natural and social processes. Trend believers, when facing sequences of binary events commonly perceived as random, tend to use momentum strategies, whereas those who believe in the trend's reversal tend to use contrarian strategies. (shrink)

1. Characterizing randomness. Consider a physical process that, if suitably idealized, generates an indefinite sequence of independent random bits. One such process might be radioactive decay of a lump of uranium whose mass is kept at just the level needed to ensure that the probability is one-half that no alpha particle is emitted in the nth microsecond of the experiment. Let us think of the bits as drawn from {0, 1} and denote the resulting sequence by x with coordinates (...) x0, x1, . . .. Now wouldn’t it be odd if there were a computer program P with the following property? (shrink)

We give a model-theoretic account for several results regarding sequences of random variables appearing in Berkes and Rosenthal [12]. In order to do this,•We study and compare three notions of convergence of types in a stable theory: logic convergence, i.e., formula by formula, metric convergence (both already well studied) and convergence of canonical bases. In particular, we characterise א0-categorical stable theories in which the last two agree.•We characterise sequences that admit almost indiscernible sub-sequences.•We apply these tools (...) to the theory of atomless random variables (ARV). We characterise types and notions of convergence of types as conditional distributions and weak/strong convergence thereof, and obtain, among other things, the Main Theorem of Berkes and Rosenthal. (shrink)

Salmon genomics is an emerging field that represents a convergence between socially important scientific innovation and a politically volatile topic of significant interest to the public. These factors provide a strong rationale for public input. This report describes such input from a public engagement event based on the principles of deliberative democracy. The event involved a random, demographically stratified sample of 25 British Columbians (Canada). While some participants opposed sequencing the salmon genome on principle, on the whole participants responded (...) favourably, citing the value of increased knowledge of human impacts on salmon, potentially slowing or reversing this impact, and assisting sustainable management of salmon resources. Participants discussed many of the potential implications of the sequencing project and formulated recommendations pertaining to regulations, international treaties, public education and engagement. Overall, the project illustrates that the specific design and implementation of this event is capable of producing sound policy advice from the general public on genomic-related issues. (shrink)

This article explores the connection between objective chance and the randomness of a sequence of outcomes. Discussion is focussed around the claim that something happens by chance iff it is random. This claim is subject to many objections. Attempts to save it by providing alternative theories of chance and randomness, involving indeterminism, unpredictability, and reductionism about chance, are canvassed. The article is largely expository, with particular attention being paid to the details of algorithmic randomness, a topic relatively unfamiliar to (...) philosophers. (shrink)

One recursively enumerable real α dominates another one β if there are nondecreasing recursive sequences of rational numbers (a[n] : n ∈ ω) approximating α and (b[n] : n ∈ ω) approximating β and a positive constant C such that for all n, C(α − a[n]) ≥ (β − b[n]). See [R. M. Solovay, Draft of a Paper (or Series of Papers) on Chaitin’s Work, manuscript, IBM Thomas J. Watson Research Center, Yorktown Heights, NY, 1974, p. 215] and [G. (...) J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. We show that every recursively enumerable random real dominates all other recursively enumerable reals. We conclude that the recursively enumerable random reals are exactly the Ω-numbers [G. J. Chaitin, IBM J. Res. Develop., 21 (1977), pp. 350–359]. Second, we show that the sets in a universal Martin-Lof test for randomness have random measure, and every recursively enumerable random number is the sum of the measures represented in a universal Martin-Lof test. (shrink)

This paper sketches a way of supplementing classical mathematics with a motivation for a Brouwerian theory of free choice sequences. The idea is that time is unending, i.e. that one can never come to an end of it, but also indeterminate, so that in a branching time model only one branch represents the ‘actual’ one. The branching can be random or subject to various restrictions imposed by the creating subject. The fact that the underlying mathematics is classical makes (...) such perhaps delicate issues as the fan theorem no longer problematic. On this model, only intuitionistic logic applies to the Brouwerian free choice sequences, and there it applies not because of any skepticism about classical mathematics, but because there is no ‘end of time’ from the standpoint of which everything about the sequences can be decided. (shrink)

Early work on the frequency theory of probability made extensive use of the notion of randomness, conceived of as a property possessed by disorderly collections of outcomes. Growing out of this work, a rich mathematical literature on algorithmic randomness and Kolmogorov complexity developed through the twentieth century, but largely lost contact with the philosophical literature on physical probability. The present chapter begins with a clarification of the notions of randomness and probability, conceiving of the former as a property of a (...) sequence of outcomes, and the latter as a property of the process generating those outcomes. A discussion follows of the nature and limits of the relationship between the two notions, with largely negative verdicts on the prospects for any reduction of one to the other, although the existence of an apparently random sequence of outcomes is good evidence for the involvement of a genuinely chancy process. (shrink)

We present a Chinese word segmentation system submitted to the closed track of Sighan bakeoff 2005. Our segmenter was built using a conditional random field sequence model that provides a framework to use a large number of linguistic features such as character identity, morphological and character reduplication features. Because our morphological features were extracted from the training corpora automatically, our system was not biased toward any particular variety of Mandarin. Thus, our system does not overfit the variety of Mandarin (...) most familiar to the system's designers. Our final system achieved a F-score of.. (shrink)

In this paper, we study the power and limitations of computing effectively generic sequences using effectively random oracles. Previously, it was known that every 2-random sequence computes a 1-generic sequence and every 2-random sequence forms a minimal pair in the Turing degrees with every 2-generic sequence. We strengthen these results by showing that every Demuth random sequence computes a 1-generic sequence and that every Demuth random sequence forms a minimal pair with every pb-generic sequence. (...) Moreover, we prove that for every comeager${\cal G} \subseteq {2^\omega }$, there is some weakly 2-random sequenceXthat computes some$Y \in {\cal G}$, a result that allows us to provide a fairly complete classification as to how various notions of effective randomness interact in the Turing degrees with various notions of effective genericity. (shrink)