Randomness through computation

A few months ago, I received a puzzling advertising for this book, Randomness through Computation, and I eventually ordered it, despite getting a rather negative impression from reading the chapter written by Tomasso Toffoli… The book as a whole is definitely perplexing (even when correcting for this initial bias) and I would not recommend it to readers interested in simulation, in computational statistics or even in the philosophy of randomness. My overall feeling is indeed that, while there are genuinely informative and innovative chapters in this book, some chapters read more like newspeak than scientific material (mixing the Second Law of Thermodynamics, Gödel’s incompleteness theorem, quantum physics, and NP completeness within the same sentence) and do not provide a useful entry on the issue of randomness. Hence, the book is not contributing in a significant manner to my understanding of the notion. (This post also appeared on the Statistics Forum.)

“Any attempt to capture the nature of finite randomness is subjective at the end, since it always seems to depend on the observer.” H. Zenil

The structure of the book is uniform in that all chapters involve answers to the questions

  • What drew me to the study of computation and randomness
  • What we have learned
  • What we don’t yet know
  • The most important open problems
  • The prospects for progress

However, the contents and answers are quite variable in length, from three to twenty-five pages, and in depth, from meaningless chatter to mathematical results. Even though this sounds unbelievable, there is no truly probabilistic chapter about randomness (the above chapter by Toffoli making little sense)! One chapter by Andrew Rukhin covers statistical tests of random generators and this is all about statistics… The book does not seem to contain anything else about pseudo- or quasi-random generators either! (Except for a paragraph in Chapter 5.)

In connection with several earlier posts of mine, if not directly with the topic of the book, Gauvrit and Delahaye wrote an interesting chapter on Benford’s law. They prove an approximation/convergence theorem related to the unimodality of the mean integrand and quantify the approximation total variation error in terms of the bound on this integrand. This chapter also contains [what I find] slightly puzzling results of sequences of distributions converging [possibly via a transform] to the Benford’s law when one of their parameters goes to a boundary of their definition space. For instance, a log-normal variate with variance parameter σ² converges to a Benford’s law when σ² goes to zero. Or a uniform (0,k) rv X is such that the decimal part of πX²  converges to a Benford’s law when k goes to infinity. Or an exponential rv X with rate k is such that πX²  again converges to a Benford’s law when k goes to zero. Of course, mathematically, there is nothing unsound with the property that, while X has no limiting distribution, the decimal part  of a transform of X may still have one… Jean-Paul Delahaye (mentioned in Parcours de mathématiciens) also wrote an updated 1990 survey about Martin-Löf’s definition of randomness, a notion I encountered in 1986 in Rouen during my PhD there, when discussing with Jean-Claude Dellacherie about simulations and pseudo-random generators. (I was then evaluating weird James-Stein estimators using my own congruential generator programmed in Pascal on my Apple II. Running for days!) An interesting trivia is that Delahaye starts with a reference to (and a one page extract from) von Mises‘ Kollectiv, a notion much debated in A search for certainty! For Martin-Löf, a real number (understood as a sequence of digits) r is random if and only if

for every enumerable sequence Ai of sets of intervals, such that μ(Ai)< 2-i, r does not belong to every Ai.

The rest of the chapter goes through the arguments about Martin-Löf-Chaitin’s and Church-Turing theses. (The later identifies recursive functions as those computable with a discrete deterministic finite algorithm.) This notion of Martin-Löf’s randomness is discussed in several chapters of the book.

`”Random” is not the opposite of “deterministic”‘ G. Longo et al

Chapter 5 is far from uninteresting, trying to link notions of randomness in physics (classical=ergodicity and quantum=intrinsic), algorithmic (=à la Martin-Löf), computer science (=nondeterminism) and biology (=evolution).  It is very discursive though, with an extensive list of references, and in its learned way manages to remain at such a general level that I emerged none the wiser from reading this chapter. (There is, I think, a typo at the top of page 86:  “clarification of the link ! between this dichotomy between (not intrinsic) randomness and the true (intrinsic) one…”)

“We shall use the notion of algorithmic information to discuss what is a physical law, to determine the limits of the axiomatic method, and to analyze Darwin’s theory of evolution.” G. Chaitin

“Intrinsic randomness has an important prediction: it suggest that the randomness we see should be repeatable.” S. Wolfram

Gregory Chaitin writes an essay as Chapter 6 that I do not find particularly deep (despite the ambitious above program!) and that is not directly related to the topic, once again. (I wonder what Alan Sokal would make of this essay…) Chapters 7 and 8 seem equally unhelpful in defining randomness, even though the reference list in the later is as long as the text itself. I was similarly disappointed in Wolfram’s chapter, given his tendency to monumental volumes! It mostly consisted of one sentence paragraphs with very little content…

“Using the concept of Algorithmic Probability, it may be possible to explain why there is something rather than nothing.” H. Zenil

“That model selection error is a necessary part of statistical estimation is an idea that is relatively new, but our understanding of it has been made quite clear by algorithmic probability.” R. Solomonoff

Part III of the book is about Algorithmic inference and artificial intelligence. I had never encountered the term Algorithmic inference so far, hence I was interested in finding more. Unfortunately, this part is not self-sufficient to provide the “more” and hardly compelling to go looking for “more”! The first chapter by Ray Solomonoff (which also happens to be the last article he wrote) is about algorithmic probability, which is a Turing machine turning an infinite iid Bernoulli input into a binary output with finite or infinite length. After reading the chapter, I remain uncertain about the whole point, even though Salomonoff has a somehow Bayesian section (11.2, page 153) on subjectivity which considers the choice of reference [prior] as a “necessary feature” for implementing Bayesian learning. Salomonoff also mentions Rissanen’s minimum description length priors, whose applicability I always found limited… Marcus Hutter maintains that Kolmogorov’s complexity can quantify Ockham’s razor, which he defends in his complete theory of everything as

“Ockham’s razor could be regarded as correct if among all considered theories, the one selected by Ockham’s razor is the one that most likely leads to correct predictions.”

but he does not provide any illustration. Among his open problems, the need “to convince the (scientific) world that the induction problem is essentially solved”, defining artificial intelligence, “finding a unique “best” universal Turing machine”.

“We have no real proof that randomness even exists in our universe.” E. Allender

Given that this book review is already over the reasonable (at least) in terms of length, I will skip Calude’s “pictures with”, Miller’s survey of Martin-Löf’s randomness, Nies’ mix of travel stories (“I wrote up a 7 page paper in the internet cafés of Panama City”) and formal logic applied to computability, Downey’s sumary of the Downey and Hirschfeldt monograph, with a mention of MCMC algorithms (which only need weak sources of randomness), Ferbus-Zanda and Grigorieff’s dialogue à la Hofstadter (Gödel again and … von Mises as well!), Allender’s further defense of Kolmogorov’s complexity, with an absent “connection to pseudorandomness”, and Li’s alternative defense, in connection with his 2008 book with Vitányi, and Kucera’s and Staiger’s short chapters. Watanabe’s final chapter on the use of randomness in algorithms is much closer to my field of expertise than any of the previous ones, but it seems to stop at the known station that randomness is presumably essential to achieve efficient optimisation algorithms (even though we do not understand why). The book concludes with two long transcripts (100 pages total) of panel discussions at two NKS conferences in 2007 and 2008, about “Is the Universe random?” and “What is computation? (How) does Nature compute? ” that I hope I can cover in another post later. (An important remark at this stage is that NKS stands for New kind of Science, named after Wolfram’s book and sponsoring conferences and summer schools!)

13 Responses to “Randomness through computation”

  1. R. Vazquez Says:

    I think that you find the book not that useful because you look it as statisticians. Whoever that think that statisticians can say something deep about randomness is in a state of sin. Statisticians are users of randomness, the contributors of this book are thinkers of randomness (and most of them pioneers to connecting the topic to other areas, hence why it is related to undecidability and intractability, for example). It is not statistics but computability theory that has captured. I don’t either see the connection to NKS, which you clearly also neglected to read repeating what some deviated reviews (a few only) have said before.

    • It may well be that statisticians cannot say anything deep about randomness, even though they may be the scientists the most versed into randomness for making a living of it… As neglecting to read NKS, I did read through it with a growing feeling of puzzlement and disbelief until I gave up about page 700. I simply do not see how this qualifies as science.

    • Am I missing something or you are confusing this book with Wolfram’s NKS? If it is true that Stephen Wolfram contributes to this book with an essay of about 6 pages, there are like 30 other contributors to the book covering over 440 pages…

      • Greg: If you read the whole collection of replies, you will see that the points about NKS are connected with an earlier question. I am not confusing Randomness through Computation with NKS and I am not criticising the entirety of Randomness through Computation but rather its poor editing.

    • Greg Laf. Says:

      Oops. I’m still confused, I thought you were complaining about the content of the book (and some, if not most, contributors). If it is the editing, could you elaborate a bit? Perhaps you would have liked more homogeneity? I think the contributions are classified by subtopics and so it is more or less clear that they cover different topics, most of them following the questions structure. Thanks.

      • Seems like we are heading towards an infinite regress there! So, as a last and final summary of my motivations for writing the post: As some earlier reviews, it emerged from the feeling of having wasted my time/a perfect Sunday afternoon. The book as a book did not bring me the enlightenment I was seeking (about randomness). It did not help in my understanding of “true randomness”. It did not make a significant contribution to the use of randomness in simulation or in statistics. Some chapters would have withstood the test of academic refereeing, and some, not. In at least this respect, I consider this is poor scientific editing.

    • Greg Laf. Says:

      I’m quite thrilled, if the book didn’t en-light you much it may mean that you are an expert in all the covered domains, specially the connections to computability and recursion theory. I’m impressed about it coming from a statistician. As for the ‘scientific editing’ how can one assume that every paper or essay has to be scientific? Some are scientific papers and some are philosophical essays. It is not the first not the last time this will happen, and that is just fine. For example, have a look at this beautiful book: http://tinyurl.com/caludevolume
      That is why these books are called review volumes. The fact that it is not interesting for you doesn’t mean it is not scientific or that others may not find it interesting. I still find this book one of the best ways to understand the foundations and deep connections of randomness to other areas. There are too many statistical (shallow for a theoretician) books on pseudorandomness to have expected yet another one. Take care.

  2. Greg Lafitte Says:

    I also bought the book. The book is a review volume which means that it is written by several authors with different backgrounds, different views and different motivations around a common topic, as the book description clearly let the reader know. That is something different than a mess. Perhaps you mean that you didn’t find anything useful for you as a researcher on simulation methods, which is a rather specific and narrow topic related to randomness. Randomness, today, is deeply connected and mostly explained by calculability. The definition of a random object or random sequence is accepted to be the algorithmic definition one. Most, if not all, the contributors of the book are the experts in every of the different fields, specially on this connection to recursive theory. Each author shares heir particular story and their points of view of the topic in broader terms, including philosophical connections as the book back cover states and from which I, myself, find the most appealing contribution of the book. I also found the round table transcriptions quite passionate and not negligible the original contributions both to understanding the concept and clarifying the state of the current research that they cover. But maybe you will also diminish Nobel’s laureate Tonny Legget participation in the discussion as you seem to have disqualified everyone else despite their expertise in the field. =)

    • As written at the end of my review, I did not get through either of both round tables. I clearly intend to do so. As for the philosophical connections in the earlier chapters, I find them rather limited…

    • Greg Lafitte Says:

      So xi’an, perhaps you can illustrate us w.r.t. your philosophical thoughts on randomness. I think it is actually the only book with some serious philosophical content on randomness (even if perhaps limited because the area may not be completely mature).

  3. Sounds like this volume’s a mess. It’s not clear to me what your level of familiarity with this topic (algorithmic probability, randomness) is – but If you really want a nice, short, readable introduction to this topic, I recommend you read the chapter titled “Kolmogorov Complexity” in Cover and Thomas’s information theory book.

  4. Shalizi once argued that Wolfram’s NKS is a by product of a Crank and your review sometimes seems to suggest something similar about this book, even though in a allusive way.

    In fact, my impression from your review is that the book oscilates between being a book about the ontology and epistemology of randomness and about technical stuff on randomness (like the Benford Law chapter). However, it seems to fail do neither of them, by flirting with pseudo-scientific arguments on the philosofy side, and being not well connected with what actual practioners of statistics do.

    Is this accurate?

    • Manoel: This is quite accurate. (1) Wolfram’s NKS as a book and as a theory are in my opinion akin to pseudo-science or newscience (as in newspeak!). There is only that much one can derive from watching 2D cellular automatas and the pretention of NKS to turn this into an explanation of the whole universe is stunning by its pretension! (I once wrote a long review for amazon but it did not get published and I did not keep a copy of it.) (2) This book (RtC) has no clear purpose due to the highly uneven level of the contributions. The most scientific ones are often recycling of earlier surveys or works, the less serious ones are collections of vague thoughts that indeed sound pseudo-scientific. As a researcher on simulation methods, I certainly come none the wiser from reading this book. The reason for editing it is not explained in the preface and I wonder if it stemmed from one of those NKS conferences…

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s


Get every new post delivered to your Inbox.

Join 558 other followers