Title: Computability of martingale convergence
In both probability theory and computability theory, an important theme is “information”, and an important tool for studying information is a “martingale”. Informally, a martingale is a betting strategy. More formally, it is a sequence of random variables $M_n$ such that $E[M_{n+1} \mid M_n] = M_n$. There are many well known convergence results for martingales. In this talk I will discuss two methods for investigating the computability of martingale convergence. First I will give general conditions for when the rate of convergence of a martingale is computable. Second, I will characterize the points for which computable martingales converge. Such questions are interesting because they provide a bridge between the practical applications of probability theory on one hand and its nonconstructive set theoretic foundations on the other. This also ties in closely to the logical topics of algorithmic randomness and constructive/computable mathematics.
The Lovasz local lemma and its application in logic / theoretical computer science
Topic: Nondeterministic finite state complexity