The definition of random sequences

DOI10.1016/S0019-9958(66)80018-9zbMath0244.62008WikidataQ29395007 ScholiaQ29395007MaRDI QIDQ5656214

Per Martin-Löf

Publication date: 1966

Published in: Information and Control (Search for Journal in Brave)

Mathematics Subject Classification ID

Foundations and philosophical topics in statistics (62A01) Axioms; other general questions in probability (60A05)

Related Items

A Quest for Algorithmically Random Infinite Structures, II, [https://portal.mardi4nfdi.de/wiki/Publication:5581622 Eine Bemerkung zum Begriff der zuf�lligen Folge], Probabilistic Algorithmic Randomness, European Summer Meeting of the Association for Symbolic Logic, Unnamed Item, Unnamed Item, Some Aspects of the Relationship between Mathematical Logic and Physics. I, Schnorr randomness, On the construction of effectively random sets, Every 2-random real is Kolmogorov random, Complexity oscillations in infinite binary sequences, [https://portal.mardi4nfdi.de/wiki/Publication:5617399 �ber die Definition von effektiven Zufallstests], A unified approach to the definition of random sequences, Bayesian definition of random sequences with respect to conditional probabilities, Bernoulli randomness and Bernoulli normality, On local times of Martin-Löf random Brownian motion, Did Jean Ville Invent Martingales?, Martingales in the Study of Randomness, Dimension and the structure of complexity classes, Projection theorems using effective dimension, Randomness as an invariant for number representations, Two-Way Non-Uniform Finite Automata, Turing degrees and randomness for continuous measures, A LEARNING-THEORETIC CHARACTERISATION OF MARTIN-LÖF RANDOMNESS AND SCHNORR RANDOMNESS, Growth and irreducibility in path-incompressible trees, Statistical Study of Digits of Some Square Roots of Integers in Various Bases, Unnamed Item, A basis theorem for Π₁⁰ classes of positive measure and jump inversion for random reals, An incomplete set of shortest descriptions, WORD COMPLEXITY AND REPETITIONS IN WORDS, Unnamed Item, Randomness, relativization and Turing degrees, Random reals and possibly infinite computations Part I: Randomness in ∅′, On the computability of a construction of Brownian motion, Algorithmic randomness over general spaces, Translating the Cantor set by a random real, ON ANALOGUES OF THE CHURCH–TURING THESIS IN ALGORITHMIC RANDOMNESS, Shannon entropy: a rigorous notion at the crossroads between probability, information theory, dynamical systems and statistical physics, Kolmogorov complexity and the geometry of Brownian motion, Recursively enumerable reals and Chaitin \(\Omega\) numbers, Kolmogorov complexity and cellular automata classification, Predictability: a way to characterize complexity, A characterization of c. e. random reals, Computability and information in models of randomness and chaos, Transparallel processing by hyperstrings, Computing a Glimpse of Randomness, On a conjecture of Dobrinen and Simpson concerning almost everywhere domination, Martin-Löf random quantum states, A computational definition of financial randomness, Measures and their random reals, Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness, The Perils of Balance Testing in Experimental Design: Messy Analyses of Clean Data, Continuous higher randomness, Lowness for genericity, Kolmogorov complexity arguments in combinatorics, Computational depth and reducibility, The sum \(2^{KM(x)-K(x)}\) over all prefixes \(x\) of some binary sequence can be infinite, When does randomness come from randomness?, Towards a new theory of confirmation, On collapsing the polynomial-time hierarchy, Characterising the Martin-Löf random sequences using computably enumerable sets of measure one, Computability versus exact computability of martingales, On the problem of stable image restoration, On the notion of infinite pseudorandom sequences, On fairness and randomness, Perfect necklaces, Genericity and measure for exponential time, Incompleteness theorems for random reals, Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers, Well-calibrated predictions from on-line compression models, Randomness and universal machines, Random problems, The discovery of algorithmic probability, An unpredictability approach to finite-state randomness, Nonstandard (non-\(\sigma\)-additive) probabilities in algebraic quantum field theory, An improved zero-one law for algorithmically random sequences, Undecidability of the structure of the Solovay degrees of c.e. reals, Extracting information is hard: a Turing degree of non-integral effective Hausdorff dimension, Universal computably enumerable sets and initial segment prefix-free complexity, Functions that preserve p-randomness, Resource bounded randomness and weakly complete problems, A divergence formula for randomness and dimension, Strict process machine complexity, Do stronger definitions of randomness exist?, Towards a theory of chance - Part II, Random elements in effective topological spaces with measure., Algorithmic randomness and monotone complexity on product space, The generalized universal law of generalization., Oscillation in the initial segment complexity of random reals, Complexity of algorithms and computations, Some theorems on the algorithmic approach to probability theory and information theory (1971 dissertation directed by A. N. Kolmogorov), Theory construction in psychology: The interpretation and integration of psychological data, Chaos out of order: quantum mechanics, the correspondence principle and chaos, Probabilistic issues in statistical mechanics, Constraints placed on random sequences by their compressibility, Measure, randomness and sublocales, Algorithmic randomness of continuous functions, Schnorr trivial reals: a construction, The descriptive complexity of stochastic integration, The Arnol'd cat: Failure of the correspondence principle, Random languages for nonuniform complexity classes, On independent random oracles, Random sequences with respect to a measure defined by two linear fractional transformations, Prefix and plain Kolmogorov complexity characterizations of 2-randomness: simple proofs, Groups and dynamical systems. Discrete time dynamics on the E(2) group, Universal forecasting algorithms, The EM algorithm for graphical association models with missing data, Unreasonable effectiveness of symmetry in physics, Almost everywhere high nonuniform complexity, Inductive reasoning and Kolmogorov complexity, Pure quantum states are fundamental, mixtures (composite states) are mathematical constructions: An argument using algorithmic information theory, Leading strategies in competitive on-line prediction, Identification of probabilities, A universal statistical test for random bit generators, Random numbers as probabilities of machine behavior, On relative randomness, Kobayashi compressibility, On empirical meaning of randomness with respect to parametric families of probability distributions, How powerful are integer-valued martingales?, Algorithmically independent sequences, Universal recursively enumerable sets of strings, Randomness on computable probability spaces -- a dynamical point of view, Circuit size relative to pseudorandom oracles, Note on the topological structure of random strings, \(\Sigma^ 0_ n\)-complete properties of programs and Martin-Löf randomness, Program size complexity for possibly infinite computations, Relativized Schnorr tests with universal behavior, Prequential randomness and probability, Process and truth-table characterisations of randomness, Pseudo-randomness and complexity of binary sequences generated by the chaotic system, An empirical study of the complexity and randomness of prediction error sequences, Randomness, independence, and hypotheses, Generalized probabilities taking values in non-Archimedean fields and in topological groups, Computing halting probabilities from other halting probabilities, On a definition of random sequences with respect to conditional probability, Significance testing with no alternative hypothesis: A measure of surprise, Objectively homogeneous reference classes, Optimal asymptotic bounds on the oracle use in computations from Chaitin's Omega, Gales suffice for constructive dimension, Model discrimination using an algorithmic information criterion, Dimension extractors and optimal decompression, From exact sciences to life phenomena: Following Schrödinger and Turing on programs, life and causality, Mathematical metaphysics of randomness, Ergodic theorems for individual random sequences, Non-stochastic infinite and finite sequences, A topological characterization of random sequences, Mass problems associated with effectively closed sets, Constructive equivalence relations on computable probability measures, Computation of recursive functionals using minimal initial segments, Random sequences of binary digits in which missing values can almost certainly be restored, On the relation between descriptional complexity and algorithmic probability, Finite state incompressible infinite sequences, Identifying randomness given by high descriptive complexity, Randomness and reducibility, Higher randomness and forcing with closed sets, Demuth’s Path to Randomness, A Survey of Mučnik and Medvedev Degrees, On Kurtz randomness, The dimensions of individual strings and sequences, Multiple Usage of Random Bits in Finite Automata, The Kolmogorov complexity of random reals, A brief and understandable guide to pseudo-random number generators and specific models for security, Expected utility theory from the frequentist perspective, Randomness, Computation and Mathematics, Mutual dimension and random sequences, On semimeasures predicting Martin-Löf random sequences, Initial segment complexities of randomness notions, The Kolmogorov complexity of infinite words, Pseudorandom sources for BPP, Computability of probability measures and Martin-Löf randomness over metric spaces, Kolmogorov-Loveland stochasticity for finite strings, An approach of randomness of a sample based on its weak ergodic limit, Open problems in universal induction \& intelligence, Competition and the canonical ensemble, Differences of halting probabilities, Weakly complete problems are not rare, Randomness? What randomness?, Optimal redundancy in computations from random oracles, Dimension 1 sequences are close to randoms, Universal probability-free prediction, Randomness and uniform distribution modulo one, On continued fraction randomness and normality, The principles of informational genomics, Schnorr randomness for noncomputable measures, The Kučera-Gács theorem revisited by Levin, Layerwise computability and image randomness, Effective randomness of unions and intersections, Amount of nonconstructivity in deterministic finite automata, Feasible reductions to Kolmogorov-Loveland stochastic sequences, Granularity of wagers in games and the possibility of saving, The sure thing principle, dilations, and objective probabilities, On the hierarchy and extension of monotonically computable real numbers., Revisiting Chaitin's incompleteness theorem, Equidistribution, uniform distribution: a probabilist's perspective, Bi-immunity over different size alphabets, Compressibility, laws of nature, initial conditions and complexity, Things that can be made into themselves, Computational randomness and lowness, Dynamics of a generic Brownian motion: Recursive aspects, A Chaitin \(\Omega\) number based on compressible strings, Randomness deficiencies, Process complexity and effective random tests, Weakly useful sequences, Randomness relative to Cantor expansions, Prediction and dimension, On the non-randomness of maximum Lempel Ziv complexity sequences of finite size, Application of Kolmogorov complexity and universal codes to identity testing and nonparametric testing of serial independence for time series, Equivalences between learning of data and probability distributions, and their applications, Liouville, computable, Borel normal and Martin-Löf random numbers, The random members of a \({\Pi }_{1}^{0}\) class, DEMUTH’S PATH TO RANDOMNESS, Microscopic reversibility and macroscopic irreversibility: from the viewpoint of algorithmic randomness, Algorithmically random series and Brownian motion, Algorithmic tests and randomness with respect to a class of measures, Solution of nonlinear equations with space filling curves, Randomness and initial segment complexity for measures, Randomness: Quantum versus classical, Learning (to disagree?) in large worlds, Resource bounded randomness and computational complexity, Randomness is inherently imprecise, Endliche Automaten und Zufallsfolgen, Testing randomness online, On the complexities of de-Bruijn sequences, Symbolic dynamics of one-dimensional maps: Entropies, finite precision, and noise, Measure and cupping in the Turing degrees, Uniform test of algorithmic randomness over a general space, Randomness for non-computable measures, Applying MDL to learn best model granularity, Lowness properties and randomness, Hintikka and the functions of logic, The descriptive complexity of Brownian motion, On partial randomness, Kolmogorov-Loveland randomness and stochasticity, Experimental investigation of forecasting methods based on data compression algorithms, Recursive computational depth., Modeling parallel transport, Thinking with notations: epistemic actions and epistemic activities in mathematical practice, ASYMPTOTIC BEHAVIOR AND RATIOS OF COMPLEXITY IN CELLULAR AUTOMATA, Resource-bounded martingales and computable Dowd-type generic sets, On the (dis)similarities between stationary imprecise and non-stationary precise uncertainty models in algorithmic randomness, On Martin-Löf (non-)convergence of Solomonoff's universal mixture, Randomness below complete theories of arithmetic, Universality, optimality, and randomness deficiency, Presentations of computably enumerable reals., Integer valued betting strategies and Turing degrees, Randomness on full shift spaces, Feasible analysis, randomness, and base invariance, Schnorr triviality and its equivalent notions, Trivial measures are not so trivial, Cryptography and algorithmic randomness, Denjoy, Demuth and density, A Church-Turing thesis for randomness?, Simple betting and stochasticity, Probabilities over rich languages, testing and randomness, Computational depth and reducibility, Computability of convergence rates in the ergodic theorem for Martin-Löf random points, UNIVERSAL CODING AND PREDICTION ON ERGODIC RANDOM POINTS, Unnamed Item, Non-Algorithmic Theory of Randomness, Sub-computable Bounded Pseudorandomness, A test for randomness based on a complexity measure, Partial Randomness and Dimension of Recursively Enumerable Reals, Unnamed Item, Unnamed Item, Unnamed Item, On a theorem of gács, Defining a randomness notion via another, Weakly useful sequences, Algorithmic complexity of points in dynamical systems, Unnamed Item, Unpredictability and Computational Irreducibility, On weakly correlated random numbers generator, Unnamed Item, An observation on probability versus randomness with applications to complexity classes, Recursive computational depth, Statistical properties of finite sequences with high Kolmogorov complexity, Universality probability of a prefix-free machine, On complexity classes and algorithmically random languages, PROBLEMS WITH COMPLEXITY IN GOLD'S PARADIGM OF INDUCTION Part II: Static Complexity, Algorithmically Random Functions and Effective Capacities, A NOTE ON THE LEARNING-THEORETIC CHARACTERIZATIONS OF RANDOMNESS AND CONVERGENCE, Kolmogorov and mathematical logic, On initial segment complexity and degrees of randomness, HIGHER RANDOMNESS AND GENERICITY, Higher-order dangers and precisely constructed taxa in models of randomness, Not all (possibly) “random” sequences are created equal, COMPLEXITY, INFORMATION, ENERGY, Minimal-program complexity of pseudo-recursive and pseudo-random sequences, Prequential Randomness, Universal Recursively Enumerable Sets of Strings, Algorithmically Independent Sequences, Fractal Intersections and Products via Algorithmic Dimension, Unnamed Item, Secure Random Number Generation in Continuous Variable Systems, Who Asked Us? How the Theory of Computing Answers Questions about Analysis, Algorithmic information theory and its statistical mechanical interpretation, The Kolmogorov-Loveland stochastic sequences are not closed under selecting subsequences, SYSTEM IDENTIFICATION, APPROXIMATION AND COMPLEXITY, Schnorr trivial sets and truth-table reducibility, HIERARCHIES OF GENERALIZED KOLMOGOROV COMPLEXITIES AND NONENUMERABLE UNIVERSAL MEASURES COMPUTABLE IN THE LIMIT, Schnorr Randomness, Trivial Reals, Random reals, the rainbow Ramsey theorem, and arithmetic conservation, On Oscillation-free ε-random Sequences, A Characterization of Constructive Dimension, Fractals Generated by Algorithmically Random Brownian Motion, An Application of Martin-Löf Randomness to Effective Probability Theory, A Divergence Formula for Randomness and Dimension, Schnorr Trivial Reals: A construction, Effective Randomness for Computable Probability Measures, Random Continuous Functions, Selection by Recursively Enumerable Sets, On Martin-Löf Convergence of Solomonoff’s Mixture, RECOGNIZING STRONG RANDOM REALS, Lowness Properties of Reals and Hyper-Immunity, Unnamed Item, Unnamed Item, Unnamed Item, A relation between correctness and randomness in the computation of probabilistic algorithms, A combinatorial characterization of sequential p. martin-löf tests, The importance of Π₁⁰ classes in effective randomness, Randomness and Determination, from Physics and Computing towards Biology, Binary Pseudo-Random Sequences Theory, Lowness for the class of random sets, Unnamed Item, Arithmetical representations of Brownian motion I, GENERICITY AND RANDOMNESS WITH ITTMS, Mass Problems and Randomness, A characterization of constructive dimension, Unnamed Item, RELATIVIZING CHAITIN'S HALTING PROBABILITY, Difference randomness, Quasi-Monte Carlo methods and pseudo-random numbers, Randomness and the Ergodic Decomposition, Amount of Nonconstructivity in Finite Automata, On the robustness of ALMOST-$\mathcal {R}$, Randomness and Effective Dimension of Continued Fractions., Chaitin's halting probability and the compression of strings using oracles, Random Subgroups of Rationals, Kolmogorov-Complexity Based on Infinite Computations, Genericity and measure for exponential time, Unnamed Item, Mass Problems and Measure-Theoretic Regularity, Measure theory aspects of locally countable orderings, Lowness and nullsets, Calibrating Randomness, When van Lambalgen’s Theorem fails, Kolmogorov complexity and symmetric relational structures, Strong noncomputability of random strings, Unnamed Item, Computable Measure Theory and Algorithmic Randomness, Algorithmic Fractal Dimensions in Geometric Measure Theory, Closure of resource-bounded randomness notions under polynomial time permutations