PSU Mark
Eberly College of Science Mathematics Department

Meeting Details

For more information about this meeting, contact Jan Reimann, Stephen Simpson.

Title:Computable randomness and martingales a la probability theory
Seminar:Logic Seminar
Speaker:Jason Rute, Carniegie Mellon University
Abstract:
In this talk, I will outline a martingale characterization of computable randomness that goes beyond the usual one. An infinite sequence of coin flips is said to be computably random if one cannot win arbitrarily large amounts of money while betting on the flips with a computable strategy (called a martingale) and a limited starting capital. In this talk I will extend the notion of computable betting strategy to the martingale definition more commonly used in probability theory. In probability theory, a martingale is a pair (M,F), where M={M_n} is sequence of random variables and F={F_n} is a sequence of increasing sigma-algebras (called a filtration), such that E[M_{n+1} | F_n] = M_n for all n. The L^1 bound of a martingale M is the supremum over n of the L^1 norm of M_n. The limit F_infty of a filtration F is the sigma-algebra generated by the union of all F_n. I will show that a point x in a computable Polish space with a computable Borel measure is computably random if an only if for all computable martingales (M,F) such that the L^1 bound is computable and F_infty is computable, the sequence M_n(x) is Cauchy. Not only does this result extend the usual definition, but it covers most (if not all) known gambling characterizations of computable randomness. It also is easily adapted to characterize Schnorr and Martin-Lof randomness This result draws together a number of tools from computable analysis and randomness. I will define what it means for a point to be computably random on a computable Borel measure. I will define what it means for a martingale and a sigma-algebra to be computable. I will also discuss various measure theoretic lemmas that are not only useful in proving this result, but are useful in proving many facts about algorithmic randomness.

Room Reservation Information

Room Number:MB315
Date:11 / 13 / 2012
Time:02:30pm - 03:45pm