Random Binary Sequences

From Mathsreach

Jump to: navigation, search

Adam Day’s whole mathematics career has been about two numbers, the 0 and 1 of infinite binary sequences. The new field of algorithmic randomness in which he works defines a sequence as random if it appears so to any algorithm.

The field captures three intuitions about randomness; the first being that random numbers are complex and incompressible. A complexity function assigns a natural number to each finite binary sequence, representing the complexity of the sequence, A sequence is considered random if its complexity is longer than its length. For example, the binary sequence 01001 has length 5, so if its complexity was 4 it would be considered not random. Infinite sequences can also be seen as sets of natural numbers.

The second intuition is that random numbers should pass statistical tests for randomness, and the third is that no betting strategy on any computer should be able to make money betting on a random sequence.

The field draws from measure and computability theory, which abstracts computing to an environment with no restrictions on memory or time, and uses idealized oracle machines to study decision problems.

Algorithmic randomness has applications to random number generators based on quantum mechanics, but like many other areas of pure mathematics it is largely applied to other areas of the discipline such as logic.

Day’s PhD thesis at Victoria University of Wellington, supervised by Rod Downey and Noam Greenberg, developed new results unifying previously separate Russian and European developments in the field. It won him the 2011 Royal Society of NZ Hatherton Award for the best scientific paper by a PhD student at a New Zealand university, and was one of the two 2011 winners of the international Association for Symbolic Logic’s Sacks Prize.

He was also awarded a three-year Miller Research Fellowship at the Berkeley campus of the University of California, which goes to “exceptional young scientists”. “I would never have anticipated being here five years ago,” he said from Berkeley. Originally, he returned from working overseas to study as a secondary mathematics teacher. “I was going to do a year of maths then a year at teachers’ college – I just started doing some maths papers and never stopped.”

He eventually hopes to get a permanent university mathematics job in New Zealand, but is now “trying to learn as much as I can from the experts here on the relationship between set theory and randomness”.

Answering one question just leads onto another, he says. “For example, lots of mathematics theorems have a statement such as ‘For almost all the real numbers some property x is true’. I’ve been looking at to what extent you can capture that notion of ‘almost all’ in algorithmic randomness.”

In particular, Day is interested in ergodic theory, the study of the behaviour of dynamical systems over a long period of time. His current question is “does a random particle always comes back to itself ”?

For Day, mathematics has realms of gold just like those Keats wrote about in his poem on Chapman’s translation of Homer. Like literature, mathematics is done entirely in the mind; it has “amazing sites and beauties – it’s just a privilege to travel round this most coherent body of logical thought, contemplating it and adding your own contribution”.