The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy

Hector Zenil, Narsis A. Kiani, Jesper Tegner

Research output: Contribution to journalArticlepeer-review

6 Scopus citations


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.
Original languageEnglish (US)
Pages (from-to)560
Issue number6
StatePublished - Jun 3 2019

Bibliographical note

KAUST Repository Item: Exported on 2020-10-01
Acknowledgements: H.Z. wishes to received funding from the Swedish Research Council (Vetenskapsrådet) grant No. 2015-05299. J.T. received funding from the King Abdullah University of Science and Technology.


Dive into the research topics of 'The Thermodynamics of Network Coding, and an Algorithmic Refinement of the Principle of Maximum Entropy'. Together they form a unique fingerprint.

Cite this