All Articles

Perspectives on the transformation of random sequences

The theory of algorithmic randomness provides a framework for studying the behavior of algorithmically random sequences under effective transformations, i.e. transformations that are Turing computable. In this talk, I will take as a starting point a theorem due to Demuth, which states that if we apply a total computable transformation to a sufficiently random sequence—here taken to be a Martin-Löf random sequence—then as long as the resulting sequence is not computable, one can recover an unbiased random sequence from the transformed sequence. I will then discuss the efficiency of the procedure that recovers unbiased randomness from this transformed sequence. More specifically, I will survey results on (1) the conditions for the existence of a computable bound on the number of input bits needed for this procedure to yield a given number of output bits (based on joint work with Laurent Bienvenu and subsequent work with Rupert Hölzl), and (2) finding the average-case extraction rate of this procedure (based on joint work with Douglas Cenzer).