Mathematical logic seminar - Nov 23, 2010

Time: 12:00 - 13:20

Room: Wean Hall 7201

Speaker:     Jason Rute    
Department of Mathematical Sciences
Carnegie Mellon University

Title: Randomness and the Convergence of Betting Systems


Suppose someone flips a fair coin infinitely often.  Every time t the coin flips you get the chance to bet x(t) dollars of your choice on the coin landing heads or tails.  If you win, then you gain that much money; if you lose, then you are down that amount.  Such a system is an example of a betting system, or a martingale.  Martingales are extremely powerful tools in probability theory that have been studied extensively.  One of the best known results about them is the Doob Martingale Convergence Theorem, which states that a martingale converges almost surely if it is L^1-bounded.  To say a martingale is L^1-bounded means the expectation of how much the player can lose is bounded---and hence by the fairness of the system, the expectation of how much the player can win is also bounded.

We will give an effective proof of the martingale convergence theorem (for betting systems on fair coin flips), namely if the martingale is "computable", then from it we can obtain a computable description of the null set which it doesn't converge on.  Further, applying this to the field of algorithmic randomness, we will give a characterization of a well-known type of randomness, Martin-Lof randomness.  Namely we will show that the Martin-Lof randoms are exactly those which converge on all computable L^1-bounded martingales.