Non-algorithmic theory of randomness

First the crucial but very confidential fact is brought into evidence that, as Kolmogorov himself repeatedly claimed, there exists no abstract theory of probabilities, simply because the factual concept of probability is itself unachieved: it is nowhere specified how to construct the factual probability law to be asserted on a given physical random phenomenon. Then an algorithm of semantic integration is built that permits to identify this factual probability law.

Ability to generate random numbers is an important resource for many applications ranging from scientific research to practical cryptography and quantum technologies. However, a widely accepted definition of random numbers, or randomness, has eluded researchers thus far. Without a definition, it is impossible to complete security proofs or make new industrial standards. Here, we propose an information-theory-based definition of randomness which, unlike state of the art, does ...

The law of large numbers is one of the fundamental properties which algorithmically random infinite sequences ought to satisfy. In this paper, we show that the law of large numbers can be effectivized for an arbitrary Schnorr random infinite sequence, with respect to an arbitrary computable Bernoulli measure. Moreover, we show that an absolute speed limit of convergence exists in this effectivization, and it equals 2 in a certain sense. In the paper, we also provide the corre...

Consider a randomized algorithm that draws samples exactly from a distribution using recursion. Such an algorithm is called a perfect simulation, and here a variety of methods for building this type of algorithm are shown to derive from the same result: the Fundamental Theorem of Perfect Simulation (FTPS). The FTPS gives two necessary and sufficient conditions for the output of a recursive probabilistic algorithm to come exactly from the desired distribution. First, the algor...

We consider the problem of inferring the probability distribution associated with a language, given data consisting of an infinite sequence of elements of the languge. We do this under two assumptions on the algorithms concerned: (i) like a real-life algorothm it has round-off errors, and (ii) it has no round-off errors. Assuming (i) we (a) consider a probability mass function of the elements of the language if the data are drawn independent identically distributed (i.i.d.), ...

One can consider $\mu$-Martin-L\"of randomness for a probability measure $\mu$ on $2^{\omega}$, such as the Bernoulli measure $\mu_p$ given $p \in (0, 1)$. We study Bernoulli randomness of sequences in $n^{\omega}$ with parameters $p_0, p_1, \dotsc, p_{n-1}$, and we introduce a biased version of normality. We prove that every Bernoulli random real is normal in the biased sense, and this has the corollary that the set of biased normal reals has full Bernoulli measure in $n^{\o...

Suppose that $X_1,X_2,\ldots$ are independent identically distributed Bernoulli random variables with mean $p$. A Bernoulli factory for a function $f$ takes as input $X_1,X_2,\ldots$ and outputs a random variable that is Bernoulli with mean $f(p).$ A fast algorithm is a function that only depends on the values of $X_1,\ldots,X_T$, where $T$ is a stopping time with small mean. When $f(p)$ is a real analytic function the problem reduces to being able to draw from linear functio...

We survey the Kolmogorov's approach to the notion of randomness through the Kolmogorov complexity theory. The original motivation of Kolmogorov was to give up a quantitative definition of information. In this theory, an object is randomness in the sense that it has a large information content. Afterwards, we present parts of the work of Martin-Lof, Schnorr, Chaitin and Levin which supply a mathematical notion of randomness throughout diverse theories from the the 60' up to re...

The issue of defining a random sequence of qubits is studied in the framework of Algorithmic Free Probability Theory.Its connection with Quantum Algorithmic Information Theory is shown

This paper is a survey of applications of the theory of algorithmic randomness to ergodic theory. We establish various degrees of constructivity for asymptotic laws of probability theory. In the framework of the Kolmogorov approach to the substantiation of the probability theory and information theory on the base of the theory of algorithms, we formulate probabilistic laws, i.e. statements which hold almost surely, in a pointwise form, i.e., for Martin-Lof random points. It i...