Explore the vast range of titles available.

Information-theoretic-based measures have been useful in quantifying network complexity. Here we briefly survey and contrast (algorithmic) information-theoretic methods which have been used to characterize graphs and networks. We illustrate the strengths and limitations of Shannon’s entropy, lossless compressibility and algorithmic complexity when used to identify aspects and properties of complex networks. We review the fragility of computable measures on the one hand and the invariant properties of algorithmic measures on the other demonstrating how current approaches to algorithmic complexity are misguided and suffer of similar limitations than traditional statistical approaches such as Shannon entropy. Finally, we review some current definitions of algorithmic complexity which are used in analyzing labelled and unlabelled graphs. This analysis opens up several new opportunities to advance beyond traditional measures.

We investigate the properties of a Block Decomposition Method (BDM), which extends the power of a Coding Theorem Method (CTM) that approximates local estimations of algorithmic complexity based on Solomonoff–Levin’s theory of algorithmic probability providing a closer connection to algorithmic complexity than previous attempts based on statistical regularities such as popular lossless compression schemes. The strategy behind BDM is to find small computer programs that produce the components of a larger, decomposed object. The set of short computer programs can then be artfully arranged in sequence so as to produce the original object. We show that the method provides efficient estimations of algorithmic complexity but that it performs like Shannon entropy when it loses accuracy. We estimate errors and study the behaviour of BDM for different boundary conditions, all of which are compared and assessed in detail. The measure may be adapted for use with more multi-dimensional objects than strings, objects such as arrays and tensors. To test the measure we demonstrate the power of CTM on low algorithmic-randomness objects that are assigned maximal entropy (e.g., π ) but whose numerical approximations are closer to the theoretical low algorithmic-randomness expectation. We also test the measure on larger objects including dual, isomorphic and cospectral graphs for which we know that algorithmic randomness is low. We also release implementations of the methods in most major programming languages—Wolfram Language (Mathematica), Matlab, R, Perl, Python, Pascal, C++, and Haskell—and an online algorithmic complexity calculator.

Kolmogorov complexity of a finite binary word reflects both algorithmic structure and the empirical distribution of symbols appearing in the word. Words with symbol frequencies far from one half belong to smaller combinatorial classes and therefore appear less complex under the standard definition. In this paper, an entropy-normalized complexity measure is introduced that divides the Kolmogorov complexity of a word by the empirical entropy of its observed distribution of zeros and ones. This adjustment isolates intrinsic descriptive complexity from the purely combinatorial effect of symbol imbalance. For Martin–Löf random sequences under constructive exchangeable measures, the adjusted complexity grows linearly and converges to one. A pathological construction shows that regularity of the underlying measure is essential. The proposed framework connects Kolmogorov complexity, empirical entropy, and randomness in a natural manner and suggests applications in randomness testing and in the analysis of structured binary data.

We characterize some major algorithmic randomness notions via differentiability of effective functions. (1) As the main result we show that a real number z∈[0,1]z\\in [0,1] is computably random if and only if each nondecreasing computable function [0,1]→R[0,1]\\rightarrow \\mathbb {R} is differentiable at zz. (2) We prove that a real number z∈[0,1]z\\in [0,1] is weakly 2-random if and only if each almost everywhere differentiable computable function [0,1]→R[0,1]\\rightarrow \\mathbb {R} is differentiable at zz. (3) Recasting in classical language results dating from 1975 of the constructivist Demuth, we show that a real zz is Martin-Löf random if and only if every computable function of bounded variation is differentiable at zz, and similarly for absolutely continuous functions. We also use our analytic methods to show that computable randomness of a real is base invariant and to derive other preservation results for randomness notions.

We postulate a principle stating that the initial condition of a physical system is typically algorithmically independent of the dynamical law. We discuss the implications of this principle and argue that they link thermodynamics and causal inference. On the one hand, they entail behavior that is similar to the usual arrow of time. On the other hand, they motivate a statistical asymmetry between cause and effect that has recently been postulated in the field of causal inference, namely, that the probability distribution P cause contains no information about the conditional distribution P effect cause and vice versa, while P effect may contain information about P cause effect .

In this article, we study the extraction rate, or output/input rate, of continuous functionals on the Cantor space 2ω, in particular for algorithmically random functionals. It is shown that random functionals have an average extraction rate over all inputs corresponding to the rate of producing a single bit of output, and that this average rate is attained for any sufficiently random input. We also examine functionals computed by discrete distribution generating trees, where we calculate the expected extraction rate and show that this rate is attained for any sufficiently random input.

The principle of maximum entropy (Maxent) is often used to obtain prior probability distributions as a method to obtain a Gibbs measure under some restriction giving the probability that a system will be in a certain state compared to the rest of the elements in the distribution. Because classical entropy-based Maxent collapses cases confounding all distinct degrees of randomness and pseudo-randomness, here we take into consideration the generative mechanism of the systems considered in the ensemble to separate objects that may comply with the principle under some restriction and whose entropy is maximal but may be generated recursively from those that are actually algorithmically random offering a refinement to classical Maxent. We take advantage of a causal algorithmic calculus to derive a thermodynamic-like result based on how difficult it is to reprogram a computer code. Using the distinction between computable and algorithmic randomness, we quantify the cost in information loss associated with reprogramming. To illustrate this, we apply the algorithmic refinement to Maxent on graphs and introduce a Maximal Algorithmic Randomness Preferential Attachment (MARPA) Algorithm, a generalisation over previous approaches. We discuss practical implications of evaluation of network randomness. Our analysis provides insight in that the reprogrammability asymmetry appears to originate from a non-monotonic relationship to algorithmic probability. Our analysis motivates further analysis of the origin and consequences of the aforementioned asymmetries, reprogrammability, and computation.

Suppose that we have a method which estimates the conditional probabilities of some unknown stochastic source and we use it to guess which of the outcomes will happen. We want to make a correct guess as often as it is possible. What estimators are good for this? In this work, we consider estimators given by a familiar notion of universal coding for stationary ergodic measures, while working in the framework of algorithmic randomness, i.e., we are particularly interested in prediction of Martin-Löf random points. We outline the general theory and exhibit some counterexamples. Completing a result of Ryabko from 2009 we also show that universal probability measure in the sense of universal coding induces a universal predictor in the prequential sense. Surprisingly, this implication holds true provided the universal measure does not ascribe too low conditional probabilities to individual symbols. As an example, we show that the Prediction by Partial Matching (PPM) measure satisfies this requirement with a large reserve.

The emergence of deterministic and irreversible macroscopic behavior from deterministic and reversible microscopic dynamics is understood as a result of the law of large numbers. In this paper, we prove on the basis of the theory of algorithmic randomness that Martin-Löf random initial microstates satisfy an irreversible macroscopic law in the Kac infinite chain model. We find that the time-reversed state of a random state is not random as well as it violates the macroscopic law.

This expository paper advocates an approach to physics in which “typicality” is identified with a suitable form of algorithmic randomness. To this end various theorems from mathematics and physics are reviewed. Their original versions state that some property Φ(x) holds for P-almost all x∈X, where P is a probability measure on some space X. Their more refined (and typically more recent) formulations show that Φ(x) holds for all P-random x∈X. The computational notion of P-randomness used here generalizes the one introduced by Martin-Löf in 1966 in a way now standard in algorithmic randomness. Examples come from probability theory, analysis, dynamical systems/ergodic theory, statistical mechanics, and quantum mechanics (especially hidden variable theories). An underlying philosophical theme, inherited from von Mises and Kolmogorov, is the interplay between probability and randomness, especially: which comes first?