Title: Defining Randomness by Martingales

Speaker: Dr. Nan Fang (State Key Laboratory of Computer Science, Institute of Software, Chinese Academy of Sciences)

Time: 15:10-18:00, Dec. 10th

Room:  Classroom 406, Second Teaching Building, PKU（二教406）

Abstract: 

One intuition about randomness is its unpredictability. If one sequence is random, any of its initial fragment should be of no help to predict the following bit. Then if we bet along such a sequence, we should not expect to gain unbounded profit. A betting strategy is usually formulated by a martingale, which records the capital at every stage. We say a sequence is random if no martingale could succeed on it, i.e., the capital along it is unbounded. To make the definition algorithmic, usually we need to restrict the effectiveness of the martingales taking into consideration, while some other restrictions might be imposed as well. With different classes of martingales taking into consideration, the resulting randomness notion might also diverse.

In this talk, I will introduce some background and basics about this aspect of algorithmic randomness, and then show some recent results about restricted martingales, i.e., single-sided martingales and granular martingales. Some related open questions will also be introduced.