A unified approach to the definition of random sequences

From MaRDI portal
Publication:5634706

DOI10.1007/BF01694181zbMath0227.62005OpenAlexW2008797389WikidataQ55924447 ScholiaQ55924447MaRDI QIDQ5634706

Claus Peter Schnorr

Publication date: 1971

Published in: Mathematical Systems Theory (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01694181



Mathematics Subject Classification ID

Statistical aspects of information-theoretic topics (62B10) Sufficient statistics and fields (62B05)


Related Items

A Quest for Algorithmically Random Infinite Structures, II ⋮ Scaled dimension and nonuniform complexity ⋮ On stability of probability laws with respect to small violations of algorithmic randomness ⋮ When does randomness come from randomness? ⋮ Unnamed Item ⋮ On Kurtz randomness ⋮ The dimensions of individual strings and sequences ⋮ Multiple Usage of Random Bits in Finite Automata ⋮ Equivalence of measures of complexity classes ⋮ On fairness and randomness ⋮ Randomness, Computation and Mathematics ⋮ Mutual dimension and random sequences ⋮ Comparing notions of randomness ⋮ Sub-computable Bounded Pseudorandomness ⋮ Probabilistic Algorithmic Randomness ⋮ The smallest probability interval a sequence is random for: a study for six types of randomness ⋮ Low for random reals and positive-measure domination ⋮ Turing incomparability in Scott sets ⋮ On the construction of effectively random sets ⋮ Every 2-random real is Kolmogorov random ⋮ Lower bounds on the redundancy in computations from random oracles via betting strategies with restricted wagers ⋮ Defining a randomness notion via another ⋮ Lines missing every random point1 ⋮ Randomness and the linear degrees of computability ⋮ Automatic Kolmogorov complexity, normality, and finite-state dimension revisited ⋮ An unpredictability approach to finite-state randomness ⋮ Recursive computational depth ⋮ Weakly complete problems are not rare ⋮ Unnamed Item ⋮ Dimension 1 sequences are close to randoms ⋮ On continued fraction randomness and normality ⋮ A divergence formula for randomness and dimension ⋮ Strict process machine complexity ⋮ How to gamble against all odds ⋮ Did Jean Ville Invent Martingales? ⋮ Martingales in the Study of Randomness ⋮ RANDOMNESS NOTIONS AND REVERSE MATHEMATICS ⋮ Effective martingales with restricted wagers ⋮ A LEARNING-THEORETIC CHARACTERISATION OF MARTIN-LÖF RANDOMNESS AND SCHNORR RANDOMNESS ⋮ On the stability property of asymptotic laws of ergodic theory and universal compression schemes ⋮ Complexity of algorithms and computations ⋮ A measure-theoretic proof of Turing incomparability ⋮ Some Questions in Computable Mathematics ⋮ Minimal-program complexity of pseudo-recursive and pseudo-random sequences ⋮ Feasible reductions to Kolmogorov-Loveland stochastic sequences ⋮ Granularity of wagers in games and the possibility of saving ⋮ Algorithmic randomness of continuous functions ⋮ Schnorr trivial reals: a construction ⋮ Random reals à la Chaitin with or without prefix-freeness ⋮ Random sequences with respect to a measure defined by two linear fractional transformations ⋮ SOLVING DIFFERENCE EQUATIONS IN SEQUENCES: UNIVERSALITY AND UNDECIDABILITY ⋮ Cook versus Karp-Levin: Separating completeness notions if NP is not small ⋮ Weak completeness in \(\text{E}\) and \(\text{E}_{2}\) ⋮ Truth-table Schnorr randomness and truth-table reducible randomness ⋮ Almost everywhere high nonuniform complexity ⋮ Randomness, relativization and Turing degrees ⋮ SYSTEM IDENTIFICATION, APPROXIMATION AND COMPLEXITY ⋮ A Characterization of Constructive Dimension ⋮ A Divergence Formula for Randomness and Dimension ⋮ How powerful are integer-valued martingales? ⋮ Effective Randomness for Computable Probability Measures ⋮ ON ANALOGUES OF THE CHURCH–TURING THESIS IN ALGORITHMIC RANDOMNESS ⋮ Lowness Properties of Reals and Hyper-Immunity ⋮ Lowness for integer-valued randomness ⋮ Process and truth-table characterisations of randomness ⋮ Prediction and dimension ⋮ General random sequences and learnable sequences ⋮ DEMUTH’S PATH TO RANDOMNESS ⋮ Randomness, independence, and hypotheses ⋮ Objectively homogeneous reference classes ⋮ A characterization of constructive dimension ⋮ Gales suffice for constructive dimension ⋮ Dimension extractors and optimal decompression ⋮ Monotonous betting strategies in warped casinos ⋮ Randomness and Effective Dimension of Continued Fractions. ⋮ Random Subgroups of Rationals ⋮ Genericity and randomness over feasible probability measures ⋮ Computable randomness and betting for computable probability spaces ⋮ Constructive equivalence relations on computable probability measures ⋮ Martin-Löf random quantum states ⋮ Calibrating Randomness ⋮ A computational definition of financial randomness ⋮ When van Lambalgen’s Theorem fails ⋮ Kolmogorov Complexity in Perspective Part I: Information Theory and Randomness ⋮ Random sequences of binary digits in which missing values can almost certainly be restored ⋮ Kolmogorov-Loveland randomness and stochasticity ⋮ Recursive computational depth. ⋮ Modeling parallel transport ⋮ Thinking with notations: epistemic actions and epistemic activities in mathematical practice ⋮ Unpredictability of complex (pure) strategies ⋮ ASYMPTOTIC BEHAVIOR AND RATIOS OF COMPLEXITY IN CELLULAR AUTOMATA ⋮ Resource-bounded martingales and computable Dowd-type generic sets ⋮ Feasible analysis, randomness, and base invariance ⋮ Cryptography and algorithmic randomness ⋮ Denjoy, Demuth and density ⋮ A stronger Kolmogorov zero-one law for resource-bounded measure ⋮ A Church-Turing thesis for randomness? ⋮ Simple betting and stochasticity



Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:5634706&oldid=30303983"
Powered by MediaWiki