My talk focuses on two aspects of my thesis, in the theory of algorithmic randomness.
The first result relates to the finite-state compressibility of infinite sequences. If $s$ is a real number in the unit interval and $q$ is a non-zero rational represented in base-$k$ notation, we show that their product ($q \\bmod 1$) represented in base-$k$, has exactly the same finite-state compressibility as $s$. This result has applications to a classical area in mathematics, the theory of normal numbers. It generalizes and provides a new proof of Wall's classical result that multiplication with a non-zero rational preserves normality of a number. This part of the talk provides a brief overview of the tools used to prove this result, namely, Schur concavity and majorization.
The second part of the talk focuses on a result in the theory of algorithmic randomness. One of the major initial successes in this theory was Martin-L\\ {o}f's use of computability theory to give the formal definition of an individual random sequence. In this theory, we try to prove effective versions of probabilistic laws. We attempt to establish that classical laws which hold with probability 1, indeed hold for every random sequence. This version of a theorem is stronger and has more intuitive content, since it justifies our belief that a random sequence passes most tests of randomness embodied in probablistic laws.
Birkhoff's Ergodic Theorem is a famous probabilistic law that was widely believed to resist effectivization. However, V'yugin proved an effective version of the Ergodic theorem based on Bishop's constructive version of the theorem. V'yugin's theorem has limited applications, however, since he assumes that the random variables are computable, hence continuous. Braverman in a recent work introduced a notion termed `graph computability' to deal with discontinuous functions. In this part of the talk, we extend his theorem to hold for a suitable restriction of graph-computable functions. We also discuss some applications of this theorem to continued fractions.
