Abstract:
The word "martingale" has related, but different, meanings in probability theory and theoretical computer science. In computational complexity and algorithmic information theory, a martingale is typically a function d on strings such that E(d(wb) | w) = d(w) for all strings w, where the conditional expectation is computed over all possible values of the next symbol b. In modern probability theory a martingale is typically a sequence ξ₀,ξ₁,ξ₂, ... of random variables such that E(ξ_n+1 | ξ₀,...,ξ_n) = ξ_n for all n.

This paper elucidates the relationship between these notions and proves that the latter notion is too weak for many purposes in computational complexity, because under this definition every computable martingale can be simulated by a polynomial-time computable martingale.

Journal Version:

• Theory of Computing Systems, 39(2):277-296, 2006.
  [PostScript | PDF | DOI link]

• Proceedings of the 29th International Colloquium on Automata, Languages, and Programming (Malaga, Spain, July 8-13, 2002), Lecture Notes in Computer Science 2380, pages 549-560. Springer-Verlag, 2002.
  [Publisher's Page]