Non-algorithmic theory of randomness

We study the empirical meaning of randomness with respect to a family of probability distributions $P_\theta$, where $\theta$ is a real parameter, using algorithmic randomness theory. In the case when for a computable probability distribution $P_\theta$ an effectively strongly consistent estimate exists, we show that the Levin's a priory semicomputable semimeasure of the set of all $P_\theta$-random sequences is positive if and only if the parameter $\theta$ is a computable r...

Generating random bits from a source of biased coins (the biased is unknown) is a classical question that was originally studied by von Neumann. There are a number of known algorithms that have asymptotically optimal information efficiency, namely, the expected number of generated random bits per input bit is asymptotically close to the entropy of the source. However, only the original von Neumann algorithm has a `streaming property' - it operates on a single input bit at a t...

We show that probabilistic computable functions, i.e., those functions outputting distributions and computed by probabilistic Turing machines, can be characterized by a natural generalization of Church and Kleene's partial recursive functions. The obtained algebra, following Leivant, can be restricted so as to capture the notion of polytime sampleable distributions, a key concept in average-case complexity and cryptography.

In a prequential approach to algorithmic randomness, probabilities for the next outcome can be forecast `on the fly' without the need for fully specifying a probability measure on all possible sequences of outcomes, as is the case in the more standard approach. We take the first steps in allowing for probability intervals instead of precise probabilities in this prequential approach, based on ideas from our earlier imprecise-probabilistic and martingale-theoretic account of a...

This paper, which is dedicated to Alan Turing on the 50th anniversary of his death, gives an overview and discusses the philosophical implications of incompleteness, uncomputability and randomness.

The field of algorithmic randomness studies what it means for infinite binary sequences to be random for some given uncertainty model. Classically, martingale-theoretic notions of such randomness involve precise uncertainty models, and it is only recently that imprecision has been introduced into this context. As a consequence, the investigation into how imprecision alters our view on martingale-theoretic random sequences has only just begun. In this contribution, where we al...

We present an algorithm for effectively generating binary sequences which would be rated by people as highly likely to have been generated by a random process, such as flipping a fair coin.

This paper has several objectives. First, it separates randomness from lawlessness and shows why even genuine randomness does not imply lawlessness. Second, it separates the question -why should I call a phenomenon random? (and answers it in part one) from the patent question -What is a random sequence? -for which the answer lies in Kolmogorov complexity (which is explained in part two). While answering the first question the note argues why there should be four motivating fa...

We shall show in this paper that there are experiments which are Bernoulli trials with success probability p > 0.5, and which have the curious feature that it is possible to correctly predict the outcome with probability > p.

The definition of conditional probability in case of continuous distributions was an important step in the development of mathematical theory of probabilities. How can we define this notion in algorithmic probability theory? In this survey we discuss the developments in this direction trying to explain what are the difficulties and what can be done to avoid them. Almost all the results discussed in this paper have been published (and we provide the references), but we tried t...